Problem 11 - Largest Product in a Grid

Top down view of Sigiriya Fortress - Lion Rock with surrounding grounds, garden, & nearby lake.
Sigirya, Sri Lanka - May 2nd, 2025

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

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

The product of these numbers is \(26 \times 63 \times 78 \times 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?

https://projecteuler.net/problem=11

Development

We need to loop through the grid of numbers, writing one outer loop for each possible adjecent direction.

The set of possible directions in the grid: \[\{up, down, left, right, diagonal\}\]

can logically be written as the equivalent vector set: \[\{\overrightarrow{vert}, \overrightarrow{horz}, \overrightarrow{diag_1}, \overrightarrow{diag_2}\}\]

Where \(\overrightarrow{diag_1}\) runs direction bottom left to upper right (northeast or southwest): \(\nearrow\)

And \(\overrightarrow{diag_1}\) runs direction upper left to bottom right (southeast or northwest): \(\searrow\)

The set of vectors of 4 adjacent numbers is what we’re searching for.

Thus, each of these vector directions can be re-written as 4 vector subspaces, and we can search through the set of the 4 subspaces.

i.e. \[\{V, H, D_1, D_2\}\]

With \(v_1, v_2, ..., v_k \in V\), \(h_1, h_2, ..., h_k \in H\), etc.

Where each vector can be expressed as a set of 4 numbers (points) on the grid. Each number/point can be expressed in terms of \(i\) & \(j\) (think x & y 2-D space values) i.e.

\[v_k = \{(x_{i_1}, y_{j_1}), (x_{i_2}, y_{j_2}), (x_{i_3}, y_{j_3}), (x_{i_4}, y_{j_4}) \mid 1 \leq k \leq n\}\]

Where \(k\) can be expressed in terms of \(ij\). & bounds can be set to define the subspace, i.e.

\[v_k = v_{ij} = \{(i, j), (i, j+1), (i, j+2), (i, j+3) \mid 1 \leq i \leq 20 - 3 = 17; 1 \leq j \leq 20\}\]

We can extrapolate this logic to fully define \(\{V, H, D_1, D_2\}\). Where:

\[ v_k = v_{ij} = \{(i, j), (i, j+1), (i, j+2), (i, j+3) \mid 1 \leq i \leq 20; 1 \leq j \leq 20 - 3 = 17\} \] \[ h_k = h_{ij} = \{(i, j), (i+1, j), (i+2, j), (i+3, j) \mid 1 \leq i \leq 20 - 3 = 17; 1 \leq j \leq 20\} \] \[ {d_1}_k = {d_1.}_{ij} = \{(i, j), (i+1, j+1), (i+2, j+2), (i+3, j+3) \mid 1 \leq i \leq 17; 1 \leq j \leq 17\} \] \[ {d_2}_k = {d_2}_{ij} = \{(i, j), (i+1, j-1), (i+2, j-2), (i+3, j-3) \mid 0 \leq i \leq 17; 4 \leq j \leq 20\} \]

R

Note, the entire grid rows will be mirrored in terms of \(y\) values, e.g. with original point (x,y) = (1,1) = 01 now being point (x,y) = (1,1) = 08.

Applying the above logic on the grid does not change our outcome because the vector subspaces are equal for the mirrored grid.

Answer 1 - Grid Search

x <- "
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.max.prod <- function(x, n) {
  d <- read.table(text = x)
  d <- lapply(d, as.integer) |> data.frame()
  x <- dim(d)[1]
  y <- dim(d)[2]
  p <- c()
  # vert
  for (i in 1:x) {
    for (j in 1:(y-n+1)) {
      v <- c()
      for (k in 0:(n-1)) {
        v <- c(v, d[i, j+k])
      }
      p <- c(p, list(v))
    }
  }
  # horz
  for (i in 1:(x-n+1)) {
    for (j in 1:y) {
      v <- c()
      for (k in 0:(n-1)) {
        v <- c(v, d[i+k, j])
      }
      p <- c(p, list(v))
    }
  }
  # diag 1 - ne / sw
  for (i in 1:(x-n+1)) {
    for (j in 1:(y-n+1)) {
      v <- c()
      for (k in 0:(n-1)) {
        v <- c(v, d[i+k, j+k])
      }
      p <- c(p, list(v))
    }
  }
  # diag 2 - se / nw
  for (i in 1:(x-n+1)) {
    for (j in n:y) {
      v <- c()
      for (k in 0:(n-1)) {
        v <- c(v, d[i+k, j-k])
      }
      p <- c(p, list(v))
    }
  }
  m <- lapply(p, prod) |> unlist()
  i <- which.max(m)
  return(list(max = m[i], numbers = p[[i]]))
}

tic()
grid.max.prod(x, n = 4)
toc()

$max
[1] 70600674

$numbers
[1] 89 94 97 87

0.079 sec elapsed

Python

We can read the grid into a list of lists that creates an indexable array structure that matches the dataframe structure from R.

Answer 1 - Grid Search

This is insanely fast.

import time
from math import prod

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

def grid_max_prod(x: str, n: int) -> dict:
  d = x.strip().split('\n')
  d = [[int(j) for j in i.split()] for i in d]
  x = len(d[0])
  y = len(d)
  p = []
  # vert
  for i in range(x):
    for j in range(y-n+1):
      v = []
      for k in range(n):
        v.append(d[i][j+k])
      p.append(v)
  # horz
  for i in range(x-n+1):
    for j in range(y):
      v = []
      for k in range(n):
        v.append(d[i+k][j])
      p.append(v)
  # diag 1 - ne / sw
  for i in range(x-n+1):
    for j in range(y-n+1):
      v = []
      for k in range(n):
        v.append(d[i+k][j+k])
      p.append(v)
  # diag 2 - se / nw
  for i in range(x-n+1):
    for j in range(n, y):
      v = []
      for k in range(n):
        v.append(d[i+k][j-k])
      p.append(v)
  m = [prod(i) for i in p]
  i = m.index(max(m))
  return({'max': m[i], 'numbers': p[i]})

t0 = time.perf_counter()
print(grid_max_prod(x, n = 4))
t1 = time.perf_counter()
t = t1 - t0
print(f'{t:.3f} sec elapsed')

{'max': 70600674, 'numbers': [89, 94, 97, 87]}
0.003 sec elapsed