Project Euler problem 11

Source code available on GitHub.

This next problem reminds us very much of problem 8:

  In the \(20 \times 20\) grid below, four numbers along a diagonal line have been marked in red.

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

  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 \times 20\) grid?

Well, this is the same problem as problem 8 but instead of just a long number we’re actually dealing with a grid now, so we’re going to have to change our data construct to reflect that.

We copy and paste the grid into a text file and open it with Python as before, but instead of putting it all into a string, we want a list where each entry is itself a list of numbers in that line. First we want to have each entry be a different line:

with open('input.txt') as f:
    grid = [line.replace('\n','') for line in f]

If you iterate through a text file in Python it automatically returns it one line at a time, which is why we can just say for line in f. Doing line.replace('\n','') instead of just line gets rid of the new line characters that end up in the string.

Now for each entry in grid we want to split it up into a list of all the numbers – splitting the string every time there’s a space character. This is very simple with the split() function:

with open('input.txt') as f:
    grid = [line.replace('\n','').split(' ') for line in f]

Our last problem is that each entry in each line of grid is a short string, not a number – that is, each entry looks something like '54' or '63' rather than 54 or 63. So, for each entry in each the line we want to convert the entry to an integer using int():

with open('input.txt') as f:
    grid = [[int(i) for i in line.replace('\n','').split(' ')] for line in f]

Done! Now we’re told that the grid is 20 by 20, but just in case we want to use a different grid later on we’ll work out the width and height with:

width = len(grid[0])
height = len(grid)

Remember that grid is the list of lines, and grid[i] is the list of numbers on the ith line.

Okay, so we’re told to find the maximum product of four adjacent numbers (let’s do adjacents = 4 for generality) in any direction, which gives us four possible directions to check: up and down, left and right, diagonally top-left to bottom-right and diagonally top-right to bottom-left.

Let’s check all groups of vertically adjacent digits first – that is, the direction ‘up and down’. Try to visualise this, for each row in the grid we’ll take the first number in the row and the three numbers directly below it, then repeat for the next number along in the row, and so on. Then we just drop down a row and start again. In the end we have 20-3 = 17 rows to do this to (since we’re always taking 3 numbers below the current row).

Using the numbers 20 and 4 as in the question, an implementation of this is as below:

maxProduct = 0

# Vertical adjacents
for i in range(17):
    for j in range(20):
        product = prod([grid[i+k][j] for k in range(4)])
        if product > maxProduct:
            maxProduct = product

It always helps to imagine you’re Python and follow along the first loop or two to understand what’s going on. We’re still using our prod() function that we’ve defined previously to take the product of all entries in a list.

Now getting rid of 20 and 4 and replacing them with width, height and adjacents, that code becomes:

width = len(grid[0])
height = len(grid)

maxProduct = 0
adjacents = 4

# Vertical adjacents
for i in range(height - adjacents + 1):
    for j in range(width):
        product = prod([grid[i+k][j] for k in range(adjacents)])
        if product > maxProduct:
            maxProduct = product

Now that we’ve done it for vertically adjacent numbers, we can pretty much use the exact same structure with only small alterations for our other three directions. For horizontally adjacent numbers, the code becomes this:

# Horizontal adjacents
for i in range(height):
    for j in range(width - adjacents + 1):
        product = prod([grid[i][j+k] for k in range(adjacents)])
        if product > maxProduct:
            maxProduct = product

And it’s not hard to carry on this pattern to diagonally adjacent numbers:

# Diagonal tl-br adjacents
for i in range(height - adjacents + 1):
    for j in range(width - adjacents + 1):
        product = prod([grid[i+k][j+k] for k in range(adjacents)])
        if product > maxProduct:
            maxProduct = product

# Diagonal tr-bl adjacents
for i in range(adjacents - 1,height):
    for j in range(width - adjacents + 1):
        product = prod([grid[i-k][j+k] for k in range(adjacents)])
        if product > maxProduct:
            maxProduct = product

All the while, I was visualising the grid quite a lot while coding this, so visualisation definitely helps in understanding what’s going on here.

Finally, once we’ve checked all four directions (and therefore all possible groups of 4 adjacent numbers) our variable maxProduct must contain the largest product of any of them. So, we just print it off!

That makes our full program look like this:

def prod(iterable):
    product = 1
    for i in iterable:
        product *= i
    return product

with open('input.txt') as f:
    grid = [[int(i) for i in line.replace('\n','').split(' ')] for line in f]

width = len(grid[0])
height = len(grid)

maxProduct = 0
adjacents = 4

# Vertical adjacents
for i in range(height - adjacents + 1):
    for j in range(width):
        product = prod([grid[i+k][j] for k in range(adjacents)])
        if product > maxProduct:
            maxProduct = product

# Horizontal adjacents
for i in range(height):
    for j in range(width - adjacents + 1):
        product = prod([grid[i][j+k] for k in range(adjacents)])
        if product > maxProduct:
            maxProduct = product

# Diagonal tl-br adjacents
for i in range(height - adjacents + 1):
    for j in range(width - adjacents + 1):
        product = prod([grid[i+k][j+k] for k in range(adjacents)])
        if product > maxProduct:
            maxProduct = product

# Diagonal tr-bl adjacents
for i in range(adjacents - 1,height):
    for j in range(width - adjacents + 1):
        product = prod([grid[i-k][j+k] for k in range(adjacents)])
        if product > maxProduct:
            maxProduct = product

print(maxProduct)

 

 

Leave a Reply

Your email address will not be published. Required fields are marked *