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 IndexErrors 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.