Largest Product in a Grid

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?

The solution to this problem involves computation of a large number of multiplicative products. This problem would be more suitable to be solved algorithmically using a computer program than manually. For each element in the 20×20 grid, you compute the product of the next three neighbors in the horizontal (right), vertical (down), diagonal (right & down), and also diagonal (left & down) direction, and then keep track of the maximum product.

The main steps involved in solving this problem algorithmically are as follows:

1. Parse the grid: We begin by converting the text representation of the numbers in the grid into an appropriate data structure for further computations. A two-dimensional array (a list of lists in Python, an ArrayList of ArrayLists in Java, etc.) is a suitable choice.

2. Compute the maximum product: We can then iterate through this array, for each element, computing the product of the current element and its three neighbors to the right, three neighbors down, three neighbors diagonally down-right, and, if appropriate, three neighbors diagonally down-left. Each product is conditional on having three neighbors in the respective direction as the boundary elements will not have neighbors in all directions.

3. Update the maximum product: After computing the products, we compare the current maximum product with the newly computed product, and if the newly computed product is larger, we update the maximum product.

4. Continue computing: We repeat this process for every element in the two-dimensional array.

5. Return the result: After all products are computed and all comparisons made, the computed maximum product is the solution of the problem.

Given the size of the grid, there will be significant amount of computations, making it impractical for a purely manual approach.

Here’s a pseudo-code that gives an idea of how you can approach this problem:
“`python
max_product = 0
for i in range(20):
for j in range(20):
if j < 17: # calculate products to the right product = grid[i][j] * grid[i][j + 1] * grid[i][j + 2] * grid[i][j + 3] max_product = max(max_product, product) if i < 17: # calculate products down product = grid[i][j] * grid[i + 1][j] * grid[i + 2][j] * grid[i + 3][j] max_product = max(max_product, product) if i < 17 and j < 17: # calculate products on the diagonals product = grid[i][j] * grid[i + 1][j + 1] * grid[i + 2][j + 2] * grid[i + 3][j + 3] max_product = max(max_product, product) if i < 17 and j > 2: # calculate products on the other diagonals
product = grid[i][j] * grid[i + 1][j – 1] * grid[i + 2][j – 2] * grid[i + 3][j – 3]
max_product = max(max_product, product)
return max_product
“`

More Answers: