Project Euler Problem 11: Largest Product In A Grid

The source code for this problem can be found here.

Problem Statement

In the \(20 \times 20\) grid below, four numbers along a diagonal line have been marked in red.

\[\begin{split}08,02,22,97,38,15,00,40,00,75,04,05,07,78,52,12,50,77,91,08 \\ 49,49,99,40,17,81,18,57,60,87,17,40,98,43,69,48,04,56,62,00 \\ 81,49,31,73,55,79,14,29,93,71,40,67,53,88,30,03,49,13,36,65 \\ 52,70,95,23,04,60,11,42,69,24,68,56,01,32,56,71,37,02,36,91 \\ 22,31,16,71,51,67,63,89,41,92,36,54,22,40,40,28,66,33,13,80 \\ 24,47,32,60,99,03,45,02,44,75,33,53,78,36,84,20,35,17,12,50 \\ 32,98,81,28,64,23,67,10,\color{red}{26},38,40,67,59,54,70,66,18,38,64,70 \\ 67,26,20,68,02,62,12,20,95,\color{red}{63},94,39,63,08,40,91,66,49,94,21 \\ 24,55,58,05,66,73,99,26,97,17,\color{red}{78},78,96,83,14,88,34,89,63,72 \\ 21,36,23,09,75,00,76,44,20,45,35,\color{red}{14},00,61,33,97,34,31,33,95 \\ 78,17,53,28,22,75,31,67,15,94,03,80,04,62,16,14,09,53,56,92 \\ 16,39,05,42,96,35,31,47,55,58,88,24,00,17,54,24,36,29,85,57 \\ 86,56,00,48,35,71,89,07,05,44,44,37,44,60,21,58,51,54,17,58 \\ 19,80,81,68,05,94,47,69,28,73,92,13,86,52,17,77,04,89,55,40 \\ 04,52,08,83,97,35,99,16,07,97,57,32,16,26,26,79,33,27,98,66 \\ 88,36,68,87,57,62,20,72,03,46,33,67,46,55,12,32,63,93,53,69 \\ 04,42,16,73,38,25,39,11,24,94,72,18,08,46,29,32,40,62,76,36 \\ 20,69,36,41,72,30,23,88,34,62,99,69,82,67,59,85,74,04,36,16 \\ 20,73,35,29,78,31,90,01,74,31,49,71,48,86,81,16,23,57,05,54 \\ 01,70,54,71,83,51,54,69,16,92,33,48,61,43,52,01,89,19,67,48\end{split}\]

The product of these numbers is \(\color{red}{26} \times \color{red}{63} \times \color{red}{78} \times \color{red}{14} = 1788696\).

What is the greatest product of four adjacent numbers in the same direction (up, down, left, right, or diagonally) in the \(20 \times 20\) grid?

Solution Discussion

Multiplication is associative, which means ‘up’ and ‘down’ are equivalent as are ‘left’ and ‘right’. This means we can simply consider the vertical and horizontal cases to cover all four directions. Similarly, this logic reduces the number of diagonal directions; ‘lower left to upper right’ is equivalent to ‘upper right to lower left’, and ‘upper left to lower right’ is equivalent to ‘lower right to upper left’.

So, simply search (exhaustively) for the greatest product in each of these four cases and then find the maximum of those four scores.

Solution Implementation

from functools import reduce
from operator import mul
from typing import List


def horizontal(grid: List[List[int]], run_len: int) -> int:
    """ Find the maximal `run_len` long product in the horizontal direction

    :param grid: the two-dimensional integer grid
    :param run_len: the product run-length
    :return: the maximum `run_len` long product in the horizontal direction from `grid`
    """

    answer = 0
    n, m = len(grid), len(grid[0])
    for i in range(n):
        for j in range(m - run_len + 1):
            subset = grid[i][j:j+run_len]
            product = reduce(mul, subset, 1)
            answer = max(answer, product)
    return answer


def vertical(grid: List[List[int]], run_len: int) -> int:
    """ Find the maximal `run_len` long product in the vertical direction

    :param grid: the two-dimensional integer grid
    :param run_len: the product run-length
    :return: the maximum `run_len` long product in the vertical direction from `grid`
    """

    answer = 0
    n, m = len(grid), len(grid[0])
    for i in range(n - run_len + 1):
        for j in range(m):
            product = 1
            for k in range(run_len):
                product *= grid[i+k][j]
            answer = max(answer, product)
    return answer


def diagonal_natural(grid: List[List[int]], run_len: int) -> int:
    """ Find the maximal `run_len` long product in the 'natural' diagonal direction

    The 'natural' diagonal is defined as top-left to bottom-right when viewed in the C-array style convention.

    :param grid: the two-dimensional integer grid
    :param run_len: the product run-length
    :return: the maximum `run_len` long product in the natural diagonal direction from `grid`
    """

    answer = 0
    n, m = len(grid), len(grid[0])
    for i in range(n - run_len+1):
        for j in range(m - run_len+1):
            product = 1
            for k in range(run_len):
                product *= grid[i+k][j+k]
            answer = max(answer, product)
    return answer


def diagonal_reverse(grid: List[List[int]], run_len: int) -> int:
    """ Find the maximal `run_len` long product in the 'reverse' diagonal direction

    The 'reverse' diagonal is defined as bottom-left to top-right when viewed in the C-array style convention.

    :param grid: the two-dimensional integer grid
    :param run_len: the product run-length
    :return: the maximum `run_len` long product in the reverse diagonal direction from `grid`
    """

    answer = 0
    n, m = len(grid), len(grid[0])
    for i in range(run_len - 1, n):
        for j in range(m - run_len+1):
            product = 1
            for k in range(run_len):
                product *= grid[i-k][j+k]
            answer = max(answer, product)
    return answer


def solve():
    """ Compute the answer to Project Euler's problem #11 """

    # Build two-dimensional array of integers
    grid = """
        08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08
        49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00
        81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65
        52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91
        22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80
        24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50
        32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70
        67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21
        24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72
        21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95
        78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92
        16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57
        86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58
        19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40
        04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66
        88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69
        04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36
        20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16
        20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54
        01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48
    """
    grid = [row.strip() for row in grid.split("\n")]
    grid = [[int(cell) for cell in row.split(" ")] for row in grid if row != ""]

    # Search for maximal run_len long products in each direction
    run_len = 4
    answers = [horizontal(grid, run_len), vertical(grid, run_len),
               diagonal_natural(grid, run_len), diagonal_reverse(grid, run_len)]

    # Identify the maximum of those partial answers
    answer = max(answers)
    return answer


expected_answer = 70600674
solutions.problem11.diagonal_natural(grid, run_len)

Find the maximal run_len long product in the ‘natural’ diagonal direction

The ‘natural’ diagonal is defined as top-left to bottom-right when viewed in the C-array style convention.

Parameters:
  • grid (List[List[int]]) – the two-dimensional integer grid
  • run_len (int) – the product run-length
Return type:

int

Returns:

the maximum run_len long product in the natural diagonal direction from grid

solutions.problem11.diagonal_reverse(grid, run_len)

Find the maximal run_len long product in the ‘reverse’ diagonal direction

The ‘reverse’ diagonal is defined as bottom-left to top-right when viewed in the C-array style convention.

Parameters:
  • grid (List[List[int]]) – the two-dimensional integer grid
  • run_len (int) – the product run-length
Return type:

int

Returns:

the maximum run_len long product in the reverse diagonal direction from grid

solutions.problem11.horizontal(grid, run_len)

Find the maximal run_len long product in the horizontal direction

Parameters:
  • grid (List[List[int]]) – the two-dimensional integer grid
  • run_len (int) – the product run-length
Return type:

int

Returns:

the maximum run_len long product in the horizontal direction from grid

solutions.problem11.solve()

Compute the answer to Project Euler’s problem #11

solutions.problem11.vertical(grid, run_len)

Find the maximal run_len long product in the vertical direction

Parameters:
  • grid (List[List[int]]) – the two-dimensional integer grid
  • run_len (int) – the product run-length
Return type:

int

Returns:

the maximum run_len long product in the vertical direction from grid