*Source code available on GitHub.*

3 7 4 2 4 6 8 5 9 375 95 64 17 47 82 18 35 87 10 20 04 82 47 65 19 01 23 75 03 34 88 02 77 73 07 63 67 99 65 04 28 06 16 70 92 41 41 26 56 83 40 80 70 33 41 48 72 33 47 32 37 16 94 29 53 71 44 65 25 43 91 52 97 51 14 70 11 33 28 77 73 17 78 39 68 17 57 91 71 52 38 17 14 91 43 58 50 27 29 48 63 66 04 68 89 53 67 30 73 16 69 87 40 31 04 62 98 27 23 09 70 98 73 93 38 53 60 04 23

This is a really wonderful problem, another great example of dynamic programming. Of course, as the problem tells us, it’s perfectly possible to solve this by trying every route possible, but it’s ridiculously inefficient. In fact this problem has complexity , meaning the time taken increases exponentially with how many rows there are in the triangle (as for each extra row, every route splits into two branches).

No, we’re going to have to be clever about this if we want our solution to work for bigger triangles. I encourage you to think about this for a while, because that’s how I came across the way to do it.

What works is if, starting at the top, we assign each number a value which is *the maximum sum down to that number*. To find the maximum sum for a particular number, we just add that number to the greater of the two maximum sums directly above it. When we get to the bottom we take the largest of the maximum sums and we have our answer.

Let’s start by pasting the triangle into `triangle.txt`

and opening it with Python. We’ll make a list called `triangle`

contain as each of its entries a list of the numbers in that row of the triangle.

triangle = [] # Put input triangle into a list of lists with open('input.txt') as input: for line in input: triangle.append(line.strip().split(' '))

Next, we’ll initialise our array `maxSum`

that will hold all the maximum sums we just talked about:

maxsum = [[0 for entry in row] for row in triangle] # Zeroes same size as triangle

Now we want to iterate through the whole triangle, one row at a time, using two nested `for`

loops. When we get to each number, we want to compare the two entries above it in `maxSum`

and add the greater of the two to the number itself, then store that value in the current entry in `maxSum`

. I’m going to use the useful `enumerate(iterable)`

function which on every iteration returns both the index and value of the current position in `iterable`

.

for i, row in enumerate(triangle): for j, entry in enumerate(row): # Compare the two numbers directly above entry and add the largest to the maxsum here if maxsum[i-1][j-1] > maxsum[i-1][j]: maxsum[i][j] = int(entry) + maxsum[i-1][j-1] else: maxsum[i][j] = int(entry) + maxsum[i-1][j]

Of course, if we’re in the first row of the triangle that number won’t *have* any entries above it, so we just set the `maxSum`

there to be the entry itself.

for i, row in enumerate(triangle): for j, entry in enumerate(row): if i == 0: maxsum[i][j] = int(entry) else: # Normally, compare the two numbers directly above entry and add the largest to the maxsum here if maxsum[i-1][j-1] > maxsum[i-1][j]: maxsum[i][j] = int(entry) + maxsum[i-1][j-1] else: maxsum[i][j] = int(entry) + maxsum[i-1][j]

The only thing we haven’t accounted for is numbers at the end of rows. These numbers will only have one entry directly above them, so we have no choice about what we do with the maximum sum there:

for i, row in enumerate(triangle): for j, entry in enumerate(row): if i == 0: maxsum[i][j] = int(entry) elif j == 0: # If at the start of the line, only one option for max sum maxsum[i][j] = int(entry) + maxsum[i-1][j] elif j == len(row) - 1: # If at the end of the line, only one option maxsum[i][j] = int(entry) + maxsum[i-1][j-1] else: # Normally, compare the two numbers directly above entry and add the largest to the maxsum here if maxsum[i-1][j-1] > maxsum[i-1][j]: maxsum[i][j] = int(entry) + maxsum[i-1][j-1] else: maxsum[i][j] = int(entry) + maxsum[i-1][j]

Now once we’ve got to the end we just want to take the maximum value of the last row of `maxSum`

. Put the whole program together and it looks like this:

triangle = [] # Put input triangle into a list of lists with open('input.txt') as input: for line in input: triangle.append(line.strip().split(' ')) maxsum = [[0 for entry in row] for row in triangle] # Zeroes same size as triangle for i, row in enumerate(triangle): for j, entry in enumerate(row): if i == 0: maxsum[i][j] = int(entry) elif j == 0: # If at the start of the line, only one option for max sum maxsum[i][j] = int(entry) + maxsum[i-1][j] elif j == len(row) - 1: # If at the end of the line, only one option maxsum[i][j] = int(entry) + maxsum[i-1][j-1] else: # Normally, compare the two numbers directly above entry and add the largest to the maxsum here if maxsum[i-1][j-1] > maxsum[i-1][j]: maxsum[i][j] = int(entry) + maxsum[i-1][j-1] else: maxsum[i][j] = int(entry) + maxsum[i-1][j] print(max(maxsum[len(triangle)-1]))