6
\$\begingroup\$

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?

Question

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

I want to receive advice on my code.

\$\endgroup\$
  • \$\begingroup\$ 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 \$\endgroup\$ – janos Sep 3 '15 at 15:41
5
\$\begingroup\$

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
\$\endgroup\$
  • 1
    \$\begingroup\$ Welcome to code review! Remember to avoid except: it will swallow any exception \$\endgroup\$ – Caridorc Sep 3 '15 at 13:29
  • 1
    \$\begingroup\$ @Caridorc Changed it to except IndexError:. I was mostly trying to demonstrate a functional solution and was not really paying attention to style. \$\endgroup\$ – Jakube Sep 3 '15 at 13:33
  • \$\begingroup\$ Sadly this does not produce the right answer according to the Project Euler site. \$\endgroup\$ – chicks Nov 10 '15 at 20:22
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ – Jakube Nov 10 '15 at 20:30
6
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ 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? \$\endgroup\$ – Nick May 7 '16 at 7:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.