# 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
"""

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)

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
"""

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]

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
"""

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]

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
"""

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]

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


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 int 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 int 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 int 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 int the maximum run_len long product in the vertical direction from grid