# Project Euler 11: Largest product in a grid

Problem 11

Largest product in a grid

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

import numpy as np
initial_max = 0
candidate_max1 = 1
candidate_max2 = 1
candidate_max3 = 1
S = {}
S[1] = "08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08"
S[2] = "49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00"
S[3] = "81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65"
S[4] = "52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91"
S[5] = "22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80"
S[6] = "24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50"
S[7] = "32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70"
S[8] = "67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21"
S[9] = "24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72"
S[10] = "21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95"
S[11] = "78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92"
S[12] = "16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57"
S[13] = "86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58"
S[14] = "19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40"
S[15] = "04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66"
S[16] = "88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69"
S[17] = "04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36"
S[18] = "20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16"
S[19] = "20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54"
S[20] = "01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48"

# for making an input matrix
raw_matrix = np.zeros(shape=(20,20))
for i in range(20):
for j in range(20):
S_list = S[i+1].split(" ")
raw_matrix[i][j] = int(S_list[j])
print raw_matrix[13,5]

for i in range(20):
for j in range(20):
candidate_max1 = raw_matrix[i][j]
candidate_max2 = raw_matrix[i][j]
candidate_max3 = raw_matrix[i][j]
candidate_max4 = raw_matrix[i][j]
try:
for cnt in range(1,4):
candidate_max1 = candidate_max1 * raw_matrix[i][j+cnt] # for horizon
candidate_max2 = candidate_max2 * raw_matrix[i+cnt][j] #for vertical
candidate_max3 = candidate_max3 * raw_matrix[i+cnt][j+cnt] #for diagonal
candidate_max4 = candidate_max4 * raw_matrix[i-cnt][j+cnt] #for reverse diagonal
if initial_max < max(candidate_max1,candidate_max2,candidate_max3,candidate_max4):
initial_max = max(candidate_max1,candidate_max2,candidate_max3,candidate_max4)
except:
continue
print initial_max


• Welcome to Code Review! Please replace that image at the top with simple text. On the front page your post shows up as "Python2.7 Question link: projecteuler.net/problem=..." instead of a nice description. That's not very attractive for reviewers. You'll get more out of Code Review by writing good descriptions as the first paragraph of your post Sep 3, 2015 at 15:41

# Your approach misses a few products

For instance, replace the last row of your matrix with 99 99 99 99 .... Clearly the maximal product should be 99*99*99*99 = 96059601, but your approach doesn't find this solution.

You can only find this solution, when i = 19. But than you receive an IndexError, because your simultaneously calculate the product of matrix[19,0] - matrix[22,0].

One way of handling this would be to compute each direction separately, each one with each own direction.

But of course you could put it back into a loop. For instance like this:

for i in range(20):
for j in range(20):

for direction in ((0,1), (1,0), (1,1), (-1,-1)):
try:
product = 1
for l in range(4):
product *= raw_matrix[i + direction[0]*l][j + direction[1]*l]
if product > initial_max:
initial_max = product
except IndexError:
pass

print initial_max


# No need for numpy-arrays

I would get rid of numpy-arrays. Not really necessary, since you never use any matrix/vector operations. A standard 2D-list should be quite enough. The parsing of the matrix can also a bit simplified using List Comprehensions.

raw_matrix = '''\
08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08
...
01 70 54 71 99 99 99 99 16 92 33 48 61 43 52 01 89 19 67 48'''

matrix = [map(int, line.split()) for line in raw_matrix.split('\n')]


Notice. I import the matrix as a multi-line string. Then I extract each line by splitting at new-lines. Then each line gets split by spaces and mapped to ints.

# Variable naming

Well, kinda obvious. What does S stand for, why call the matrix raw_matrix. raw_matrix would be good name instead of S, because the matrix is still in raw form (string). And call the parsed matrix simply matrix.

Others renaming I would prefer: i -> row, j -> column, initial_product -> max_product.

So all in all, here a improved version of your code:

raw_matrix = '''\
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 99 99 99 99 16 92 33 48 61 43 52 01 89 19 67 48'''

matrix = [map(int, line.split()) for line in raw_matrix.split('\n')]

max_product = 0

for row in range(20):
for column in range(20):
for direction in ((0,1), (1,0), (1,1), (-1,-1)):
try:
product = 1
for l in range(4):
product *= matrix[row + direction[0]*l][column + direction[1]*l]
if product > max_product:
max_product = product
except IndexError:
pass

print max_product

• Welcome to code review! Remember to avoid except: it will swallow any exception Sep 3, 2015 at 13:29
• @Caridorc Changed it to except IndexError:. I was mostly trying to demonstrate a functional solution and was not really paying attention to style. Sep 3, 2015 at 13:33
• Sadly this does not produce the right answer according to the Project Euler site. Nov 10, 2015 at 20:22
• @chicks The matrix I used is not exactly the same matrix as in Project Euler. I modified the last row a little bit. Basically I wanted to show off a test case, that the OP's code was unable to find. Nov 10, 2015 at 20:30

We take take advantage of these features of numpy to reduce the code quite a bit:

1. array reshaping
2. array row, column and diagonal slices
3. np.prod to compute the product of all elements in an array
4. flipping the array to get anti-diagonals

# Reshaping

Reshaping allows you to (for instance) reorganize a 1-dimensional array into a 2-dimenstional array. Just the dimension metadata is changed so the operation is very efficient:

a = np.array([1,2,3,4,5,6]).reshape(3,2)
print a

[[1 2]
[3 4]
[5 6]]


# Slicing

Here are example of how to take row, column and diagonal slices of arrays:

import numpy as np

a = np.array( [[11,12,13,14,15,16],
[21,22,23,24,25,26],
[31,32,33,34,35,36],
[41,42,43,44,45,46]
] )

print "row",     a[1][3:5]         # horizontal slice, row 1, columns 3..5
print "column:", a[:,4]            # column 4
print "diag:",   np.diagonal(a, 2) # 2nd diagonal


Note that row and column indices start from 0. In the case of diagonals, 0 is the main diagonal, with positive diagonals to the right and negative diagonals to the left of the main.

# Products

And here is how to use np.prod:

a = np.array([5,6,7,8])
print np.prod(a)             # prints 1680


# Anti-diagonals

We can get anti-diagonals by first flipping the matrix along one of its dimensions:

a = np.array([1,2,3,4,5,6,7,8]).reshape(2,4)
b = a[::-1,]
print b


b has the same shape as a and the diagonals of b are the anti-diagonals of a.

# Solution

Putting it all together:

def euler11():
data = """
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
"""
a = np.array([ int(x) for x in data.split() ]).reshape(20,20)
# print a
b = a[::-1,]

maxprod = 0
for i in xrange(20):
for j in xrange(20):
r = np.prod( a[i][j:j+4] )
c = np.prod( a[:,j][i:i+4] )
k = min(i,j)
d1 = np.prod( np.diagonal(a, j-i)[ k:k+4 ] )
d2 = np.prod( np.diagonal(b, j-i)[ k:k+4 ] )
maxprod = max([maxprod,r,c,d1,d2])
print maxprod


Note here is i,j represents the upper left corner of either the row, column or diagonal we are taking the product of. That's why both range from 0 to 16 We just run both i and j from 0 through 19. We examine a few extra products (some with less than 4 terms), but since we are looking for the maximum it doesn't matter.

• This solution using numpy is really clear and clever. Can you recommend any book on learning numpy? or any doc that you consider useful for a better understanding on numpy?
– Nick
May 7, 2016 at 7:59