On to problem eleven.

*Question: What is the greatest product of four adjacent numbers in any direction (up, down, left, right, or diagonally) in the 20×20 grid?*

Ah, this question was actually pretty difficult. It took me a while to figure out a way to be able to find vertically and diagonally adjacent numbers in the grid, and my eventual solution was to use a list of lists. Essentially, each row in the grid is represented as a list of numbers, and 20 of these lists are put into another list in the order of the grid. After this was done, the rest entailed manipulating individual elements in the lists.

It might be clearer to see the code, so here it is:

nums = [
[ 8, 2, 22, 97, 38, 15, 0, 40, 0, 75, 4, 5, 7, 78, 52, 12, 50, 77, 91, 8],
[49, 49, 99, 40, 17, 81, 18, 57, 60, 87, 17, 40, 98, 43, 69, 48, 4, 56, 62, 0],
[81, 49, 31, 73, 55, 79, 14, 29, 93, 71, 40, 67, 53, 88, 30, 3, 49, 13, 36, 65],
[52, 70, 95, 23, 4, 60, 11, 42, 69, 24, 68, 56, 1, 32, 56, 71, 37, 2, 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, 3, 45, 2, 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, 2, 62, 12, 20, 95, 63, 94, 39, 63, 8, 40, 91, 66, 49, 94, 21],
[24, 55, 58, 5, 66, 73, 99, 26, 97, 17, 78, 78, 96, 83, 14, 88, 34, 89, 63, 72],
[21, 36, 23, 9, 75, 0, 76, 44, 20, 45, 35, 14, 0, 61, 33, 97, 34, 31, 33, 95],
[78, 17, 53, 28, 22, 75, 31, 67, 15, 94, 3, 80, 4, 62, 16, 14, 9, 53, 56, 92],
[16, 39, 5, 42, 96, 35, 31, 47, 55, 58, 88, 24, 0, 17, 54, 24, 36, 29, 85, 57],
[86, 56, 0, 48, 35, 71, 89, 7, 5, 44, 44, 37, 44, 60, 21, 58, 51, 54, 17, 58],
[19, 80, 81, 68, 5, 94, 47, 69, 28, 73, 92, 13, 86, 52, 17, 77, 4, 89, 55, 40],
[ 4, 52, 8, 83, 97, 35, 99, 16, 7, 97, 57, 32, 16, 26, 26, 79, 33, 27, 98, 66],
[88, 36, 68, 87, 57, 62, 20, 72, 3, 46, 33, 67, 46, 55, 12, 32, 63, 93, 53, 69],
[ 4, 42, 16, 73, 38, 25, 39, 11, 24, 94, 72, 18, 8, 46, 29, 32, 40, 62, 76, 36],
[20, 69, 36, 41, 72, 30, 23, 88, 34, 62, 99, 69, 82, 67, 59, 85, 74, 4, 36, 16],
[20, 73, 35, 29, 78, 31, 90, 1, 74, 31, 49, 71, 48, 86, 81, 16, 23, 57, 5, 54],
[ 1, 70, 54, 71, 83, 51, 54, 69, 16, 92, 33, 48, 61, 43, 52, 1, 89, 19, 67, 48]]
result = 0
factors = []
# finds highest in rows
for row in nums:
for i in range(0, 17):
product = row[i]*row[i+1]*row[i+2]*row[i+3]
if product > result:
result = product
factors = [row[i],row[i+1],row[i+2],row[i+3]]
i += 1
# finds highest in columns
for i in range(0, 17):
for j in range(0, 20):
product = nums[i][j]*nums[i+1][j]*nums[i+2][j]*nums[i+3][j]
if product > result:
result = product
factors = [nums[i][j],nums[i+1][j],nums[i+2][j],nums[i+3][j]]
# finds diagonal to the right
for i in range(0, 17):
for j in range(0, 17):
product = nums[i][j]*nums[i+1][j+1]*nums[i+2][j+2]*nums[i+3][j+3]
if product > result:
result = product
factors = [nums[i][j],nums[i+1][j+1],nums[i+2][j+2],nums[i+3][j+3]]
# finds diagonal to the left
for i in range(16, -1, -1):
for j in range(19, 2, -1):
product = nums[i][j]*nums[i+1][j-1]*nums[i+2][j-2]*nums[i+3][j-3]
if product > result:
result = product
factors = [nums[i][j],nums[i+1][j-1],nums[i+2][j-2],nums[i+3][j-3]]
print(result, factors)

The *factors* list is not necessary to solve the problem, but I prefer to keep it in there if only to see what exactly the computer is calculating. This code has four parts, which check the products of the adjacent horizontal, vertical, left-diagonal, and right-diagonal digits respectively.

# finds highest in rows
for row in nums:
for i in range(0, 17):
product = row[i]*row[i+1]*row[i+2]*row[i+3]
if product > result:
result = product
factors = [row[i],row[i+1],row[i+2],row[i+3]]
i += 1

Let’s look at line 26’s block first. The for loop finds each row in the grid, and puts it (as a list) into the variable *row*. For each row, *i* is the variable used to retrieve the *i*th element in the row (list). Since we’re looking for groups of four digits, the last four digits we need to test in each row are in positions 16, 17, 18, and 19 (remember, list positions start at 0). So *i* only has to go up to 16, since we find next three elements after *i* to multiply them. Every time four digits are multiplied, we check it against the previous largest product, and if it’s larger, the variable is overwritten with the that number. The four digits that are factors of the product are also stored.

# finds highest in columns
for i in range(0, 17):
for j in range(0, 20):
product = nums[i][j]*nums[i+1][j]*nums[i+2][j]*nums[i+3][j]
if product > result:
result = product
factors = [nums[i][j],nums[i+1][j],nums[i+2][j],nums[i+3][j]]

Next we tested vertically adjacent digits. In this case, *i* is the variable used to retrieve the *i*th element from *nums*, or in other words it retrieves the *i*th row in the grid. *j* is the variable used to find the *j*th element of that row. From a similar logic as before, the last group of rows we need to test are rows 16, 17, 18, and 19. Therefore, *i* only needs to go up to 16. However, *j* needs to go up to 19 because we need to go all the way to the end of each row and multiply the vertical column of digits below it. Four vertical digits are found by retrieving four adjacent rows (numbered *i* to *i*+3), then finding the same (*j*th) element of each. These four digits are then multiplied, and tested against *product*.

# finds diagonal to the right
for i in range(0, 17):
for j in range(0, 17):
product = nums[i][j]*nums[i+1][j+1]*nums[i+2][j+2]*nums[i+3][j+3]
if product > result:
result = product
factors = [nums[i][j],nums[i+1][j+1],nums[i+2][j+2],nums[i+3][j+3]]

Diagonal to the right means that starting from any digit and going down diagonally, the last digit in that diagonal will be to the right of the initial digit. Again, *i* is used to find the *i*th row, and *j* is the *j*th element in that row. The ranges for *i* and *j* will become more obvious after explaining how the diagonal is found. So the first digit we find is in the *i*th row, at position *j*. The second digit is a row below that, at the *i*+1th row, and one position to the right, at *j*+1. This is repeated until the *i*+3rd row, where we will have a four digits that are diagonal to each other. Since the last digit is 3 down and 3 to the right of the initial digit, *i* (the row) and *j* (the element position) only have to go up to 16. Each product is checked against *product*.

# finds diagonal to the left
for i in range(16, -1, -1):
for j in range(19, 2, -1):
product = nums[i][j]*nums[i+1][j-1]*nums[i+2][j-2]*nums[i+3][j-3]
if product > result:
result = product
factors = [nums[i][j],nums[i+1][j-1],nums[i+2][j-2],nums[i+3][j-3]]

Finding the diagonal to the left is a bit strange. We start from the 4th row from the bottom (*nums*[16]), and work our way up to the top row (*nums*[0]). Therefore, *i*, or the *i*th row, starts at 16 and goes to 0. Following a similar logic as before, since the final digit in the left-diagonal is 3 down and 3 to the left from the initial digit, *j*, or the *j*th element must start from 19 (the end of the row), up to 3 (4 from the left of the row). We test the left-diagonals starting from the right, and moving to the left, or incrementing *j* by -1. Each product is checked against *product*.

So after we test the horizontal, vertical, and diagonal products, we will have exhausted all possibilities and the variable *product* will be storing the largest product it found, and so we print.

*Answer: 70600674 [89, 94, 97, 87]*

Tags: prime, sum