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 twodimensional integer grid
:param run_len: the product runlength
: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 twodimensional integer grid
:param run_len: the product runlength
: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 topleft to bottomright when viewed in the Carray style convention.
:param grid: the twodimensional integer grid
:param run_len: the product runlength
: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 bottomleft to topright when viewed in the Carray style convention.
:param grid: the twodimensional integer grid
:param run_len: the product runlength
: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[ik][j+k]
answer = max(answer, product)
return answer
def solve():
""" Compute the answer to Project Euler's problem #11 """
# Build twodimensional 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 topleft to bottomright when viewed in the Carray style convention.
Parameters:  grid (
List
[List
[int
]]) – the twodimensional integer grid  run_len (
int
) – the product runlength
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 bottomleft to topright when viewed in the Carray style convention.
Parameters:  grid (
List
[List
[int
]]) – the twodimensional integer grid  run_len (
int
) – the product runlength
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 twodimensional integer grid  run_len (
int
) – the product runlength
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 twodimensional integer grid  run_len (
int
) – the product runlength
Return type: int
Returns: the maximum run_len long product in the vertical direction from grid
 grid (