In the 20×20 grid below, four numbers along a diagonal line have been marked in red.

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×20 grid?

https://projecteuler.net/problem=11

That grid is way too much to type by hand. It’s necessary to ingest it using file I/O. I saved the grid as `grid.txt`

. Ingesting the data and writing it to a 2D array is just a few lines:

grid = [] with open('grid.txt') as f: for line in f: row = [int(cell) for cell in line.split()] grid.append(row)

`grid[row][col]`

accesses the cell in the specified row and column. Now, we iterate through the grid, row by row, column by column. At each cell, there are a bunch of products to check. Since the iteration is being done from left to right, top to down, it is unnecessary to calculate products in the north or west directions. The same idea applies to the northwest and northeast diagonals. Just by knowing the direction of iteration helps us deduce that the east, south, southwest, and southeast directions only need to be checked.

### East

Checking the eastern product is pretty easy since all entries remain in a row. For a cell at row `r`

and column `c`

, its easterly neighbors are `grid[r][c+1]`

, `grid[r][c+2]`

, and `grid[r][c+3]`

.

### South

Checking the southern product is also easy since all entries remain in a column. For a cell at row `r`

and column `c`

, its southerly neighbors are `grid[r+1][c]`

, `grid[r+2][c]`

, and `grid[r+3][c]`

.

### Southeast

The diagonals change both row and column. In this direction, both row and column are increasing. For a cell at row `r`

and column `c`

, its southeasterly neighbors are `grid[r+1][c+1]`

, `grid[r+2][c+2]`

, and `grid[r+3][c+3]`

.

### Southwest

In this direction, the rows are increasing but the columns are decreasing. Thus, a cell’s southwesterly neighbors are `grid[r+1][c-1]`

, `grid[r+2][c-2]`

, and `grid[r+3][c-3]`

.

### Where There Be Dragons

We need to add logic for when a cell is near the edge of the grid. Attempting to access a nonexistent cell beyond the edge incurs an `IndexError`

. One way I thought of is expecting the exception. We could `try`

the function that collects a cell’s neighbors and suppress `IndexError`

s when they arise. However, this isn’t good design. Exception handling is costly. Another way is to add logic that checks if there is enough room in the direction to explore.

Making sure there are enough cells in the easterly direction is easy. Just make sure that the easternmost cell to be checked’s column number doesn’t exceed the number of columns available in the grid.

if c + 3 < len(grid[0]): # Safe to check the eastern product

This idea extends to the other directions.

if r + 3 < len(grid): # Safe to check the southern product if r + 3 < len(grid) and c + 3 < len(grid[0]): # Safe to check the southeastern product if r + 3 < len(grid) and c - 3 >= 0: # Safe to check the southwestern product

The solution is now within grasp. A preliminary maximum product is stored. For each cell in the grid, its eastern, southern, southeastern, and southwestern products are calculated (if possible). These products are compared to the temporary maximum product. If there is a new maximum, assign the new maximum to the temporary maximum. Thus, when the search finishes, the temporary maximum will indeed be the maximum product of four adjacent numbers.

maximum_product = 0 for r in range(len(grid)): for c in range(len(grid[0])): # Check eastern product if c + 3 < len(grid[0]): product = grid[r][c] * grid[r][c+1] * grid[r][c+2] * grid[r][c+3] if product > maximum_product: maximum_product = product # Check southern product if r + 3 < len(grid): product = grid[r][c] * grid[r+1][c] * grid[r+2][c] * grid[r+3][c] if product > maximum_product: maximum_product = product # Check southeastern product if r + 3 < len(grid) and c + 3 < len(grid[0]): product = grid[r][c] * grid[r+1][c+1] * grid[r+2][c+2] * grid[r+3][c+3] if product > maximum_product: maximum_product = product # Check southwestern product if r + 3 < len(grid) and c - 3 >= 0: product = grid[r][c] * grid[r+1][c-1] * grid[r+2][c-2] * grid[r+3][c-3] if product > maximum_product: maximum_product = product print(maximum_product)

Siccing the algorithm on the grid gives the result 70600674. You can find the solution code on my Github.