Source code available on GitHub.
This next problem reminds us very much of problem 8:
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
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 i
th 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 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)