# Project Euler problem 18

Source code available on GitHub. ```3
7 4
2 4 6
8 5 9 3``` ```75
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]))```