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.
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
- 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
- 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
- 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
- grid (