9
\$\begingroup\$

Project Euler problem 11 says:

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

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 102638 40 67 59 54 70 66 18 38 64 70
67 26 20 68 02 62 12 20 956394 39 63 08 40 91 66 49 94 21
24 55 58 05 66 73 99 26 97 177878 96 83 14 88 34 89 63 72
21 36 23 09 75 00 76 44 20 45 351400 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

The product of these numbers is 26 × 63 × 78 × 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?

So, I coded this:

grid=[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]

largest=[0,0,0,0]

#horizontal and verticle

for h in xrange(0,20):
    for hsub in xrange(0,17):
        if grid[h*10+hsub]*grid[h*10+hsub+1]*grid[h*10+hsub+2]*grid[h*10+hsub+3] > largest[0]:
            largest[0] = grid[h*10+hsub]*grid[h*10+hsub+1]*grid[h*10+hsub+2]*grid[h*10+hsub+3]


        if grid[(hsub*20)+h]* grid[((hsub+1)*20)+h]* grid[((hsub+2)*20)+h]* grid[((hsub+3)*20)+h] > largest[1]:
            largest[1] = grid[(hsub*20)+h]* grid[((hsub+1)*20)+h]* grid[((hsub+2)*20)+h]* grid[((hsub+3)*20)+h]

#diagonal right and left

for r in xrange(0,17):
    for rsub in xrange (0,17):
        if grid[(rsub*20)+r]* grid[((rsub+1)*20)+1+r]* grid[((rsub+2)*20)+2+r]* grid[((rsub+3)*20)+3+r] > largest[2]:
            largest[2] = grid[(rsub*20)+r]* grid[((rsub+1)*20)+1+r]* grid[((rsub+2)*20)+2+r]* grid[((rsub+3)*20)+3+r] 

        if grid[(rsub*20)+3+r]* grid[((rsub+1)*20)+2+r]* grid[((rsub+2)*20)+1+r]* grid[((rsub+3)*20)+r] > largest[3]:
            largest[3] =  grid[(rsub*20)+3+r]* grid[((rsub+1)*20)+2+r]* grid[((rsub+2)*20)+1+r]* grid[((rsub+3)*20)+r]

print max(largest)

Even though I got the answer right, I am quite unsatisfied with my current code. I feel as though it's very very messy. I have always thought that in order to become a good programmer, one has to code in a neat and elegant manner.

I am a complete beginner. What should I do differently?

\$\endgroup\$

2 Answers 2

Reset to default
13
\$\begingroup\$

Your code would be much simpler if you'd use a list of lists for the matrix:

grid = [
  [...],
  [...],
  ...
]

each row is a list itself, so to get the element at (x, y) we can now say grid[y][x]. This is massively more readable than your previous grid[y*20+x].

Your code now looks like:

#horizontal and vertical
for h in xrange(0,20):
    for hsub in xrange(0,17):
        if grid[h][hsub]*grid[h][hsub+1]*grid[h][hsub+2]*grid[h][hsub+3] > largest[0]:
            largest[0] = grid[h][hsub]*grid[h][hsub+1]*grid[h][hsub+2]*grid[h][hsub+3]
        if grid[hsub][h]* grid[hsub+1][h]* grid[hsub+2][h]* grid[hsub+3][h] > largest[1]:
            largest[1] = grid[hsub][h]* grid[hsub+1][h]* grid[hsub+2][h]* grid[hsub+3][h]

#diagonal right and left
for r in xrange(0,17):
    for rsub in xrange (0,17):
        if grid[rsub][r]* grid[rsub+1][1+r]* grid[rsub+2][2+r]* grid[rsub+3][3+r] > largest[2]:
            largest[2] = grid[rsub][r]* grid[rsub+1][1+r]* grid[rsub+2][2+r]* grid[rsub+3][3+r] 
        if grid[rsub][3+r]* grid[rsub+1][2+r]* grid[rsub+2][1+r]* grid[rsub+3][r] > largest[3]:
            largest[3] =  grid[rsub][3+r]* grid[rsub+1][2+r]* grid[rsub+2][1+r]* grid[rsub+3][r]

At this step I also removed uneccessary empty lines from your code.

We see that each expression for summing adjacent cells in a certain direction is repeated two times. We can avoid this by using a variable each time:

#horizontal and vertical
for h in xrange(0,20):
    for hsub in xrange(0,17):
        horizontal = grid[h][hsub] * grid[h][hsub+1] * grid[h][hsub+2] * grid[h][hsub+3]
        vertical   = grid[hsub][h] * grid[hsub+1][h] * grid[hsub+2][h] * grid[hsub+3][h]
        if horizontal > largest[0]:
            largest[0] = horizontal
        if vertical > largest[1]:
            largest[1] = vertical

#diagonal right and left
for r in xrange(0,17):
    for rsub in xrange (0,17):
        right_diagonal = grid[rsub][0+r] * grid[rsub+1][1+r] * grid[rsub+2][2+r] * grid[rsub+3][3+r]
        left_diagonal  = grid[rsub][3+r] * grid[rsub+1][2+r] * grid[rsub+2][1+r] * grid[rsub+3][r]
        if right_diagonal > largest[2]:
            largest[2] = right_diagonal
        if left_diagonal > largest[3]:
            largest[3] = left_diagonal

This format makes it much easier to spot errors – just as I'm writing this, I see that we forgot a +1 in the left diagonal (corrected in the previous code as well).

All of these products look similar: We have some starting point and a direction. We then take three steps in that direction, and multiply all numbers. We could abstract this:

def product_in_direction(grid, start, direction, steps):
    x0, y0 = start
    dx, dy = direction
    product = 1
    for n in range(steps):
        product *= grid[y0 + n*dy][x0 + n*dx]
    return product

Now the rest of the code simplifies to:

#horizontal and vertical
for h in xrange(0,20):
    for hsub in xrange(0,17):
        horizontal = product_in_direction(grid, (hsub, h), (1, 0), 4)
        vertical   = product_in_direction(grid, (h, hsub), (0, 1), 4)
        if horizontal > largest[0]:
            largest[0] = horizontal
        if vertical > largest[1]:
            largest[1] = vertical

#diagonal right and left
for r in xrange(0,17):
    for rsub in xrange (0,17):
        right_diagonal = product_in_direction(grid, (rsub, r  ), (1,  1), 4)
        left_diagonal  = product_in_direction(grid, (rsub, r+3), (1, -1), 4)
        if right_diagonal > largest[2]:
            largest[2] = right_diagonal
        if left_diagonal > largest[3]:
            largest[3] = left_diagonal

As a next step, we will remove the unnecesary largest array: Why do we need to remember four different values when we only want the largest?

largest = 0

#horizontal and vertical
for h in xrange(0,20):
    for hsub in xrange(0,17):
        largest = max(
            product_in_direction(grid, (hsub, h), (1, 0), 4), # horizontal
            product_in_direction(grid, (h, hsub), (0, 1), 4), # vertical
            largest,
        )

#diagonal right and left
for r in xrange(0,17):
    for rsub in xrange (0,17):
        largest = max(
            product_in_direction(grid, (rsub, r  ), (1,  1), 4), # right diagonal
            product_in_direction(grid, (rsub, r+3), (1, -1), 4), # left diagonal
            largest,
         )

It is annoying that we iterate over two different ranges. If we update our product_in_direction function to employ a range check, then we can avoid the need for that:

def product_in_direction(grid, start, direction, steps):
    x0, y0 = start
    dx, dy = direction

    if  not(0 <= y0                  < len(grid) and
            0 <= y0 + (steps - 1)*dy < len(grid) and
            0 <= x0                  < len(grid[y0]) and
            0 <= x0 + (steps - 1)*dx < len(grid[y0])):
        return 0

    product = 1
    for n in range(steps):
        product *= grid[y0 + n*dy][x0 + n*dx]
    return product

Now we just iterate over all indices:

#horizontal and vertical
for y in range(len(grid)):
    for x in range(len(grid[y])):
        largest = max(
            product_in_direction(grid, (x, y),   (1,  0), 4), # horizontal
            product_in_direction(grid, (x, y),   (0,  1), 4), # vertical
            product_in_direction(grid, (x, y  ), (1,  1), 4), # right diagonal
            product_in_direction(grid, (x, y+3), (1, -1), 4), # left diagonal
            largest,
        )

Note how the variable names x and y more clearly express what they actually mean than h or rsub.

To sum up what I did:

  1. picked appropriate data structures
  2. factored out common code, using functions if appropriate
  3. abstract details like bounds checking away
\$\endgroup\$
3
  • \$\begingroup\$ I was about to write all that, but I thought it would be easier to wait for you, then upvote yours instead.... \$\endgroup\$
    – rolfl
    Commented Dec 19, 2013 at 20:13
  • 1
    \$\begingroup\$ Nice answer. Have you thought about using numpy? It could offer some more efficient constructs/abstractions. \$\endgroup\$
    – Nobody moving away from SE
    Commented Dec 22, 2013 at 9:39
  • \$\begingroup\$ @Nobody good point: using numpy would hide most of the loops. OTOH I think that using explicit loops is easier to understand and to explain: OP seems fairly new to Python, so maybe it wouldn't be wise to introduce a library that changes how the language behaves. \$\endgroup\$
    – amon
    Commented Dec 22, 2013 at 22:49
5
\$\begingroup\$
  • xrange(0, N) to xrange(N)
  • name your loop variables something meaningful, like row and col
  • create some variables for the indices you need, e.g. one_cell_up = grid[h*whatever]
  • do you need a list of largest numbers, or just one largest number?
  • what is 17 and what is 20? If you created GRID_SIZE = 20 it'd be more obvious
  • Might a list (rows) of lists (cols) be a more intuitive data structure?
  • Better comments would help people understand your code, which is important. It'd take me 15, 20, who knows how many minutes to walk through this algorithm (which I'm not going to do) or 30 seconds to read some comments.
  • anytime you repeat the same big chunk of code, grid[h*10...hsub+3], just store it in a variable
  • you might check out the step argument to xrange, so you can get steps of 10 instead of h * 10 everywhere
  • check out pep8
\$\endgroup\$

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