Project Euler problem 18

Source code available on GitHub.

  By starting at the top of the triangle below and moving to adjacent numbers on the row below, the maximum total from top to bottom is 23.

3
7 4
2 4 6
8 5 9 3

  That is, \(3 + 7 + 4 + 9 = 23\).  Find the maximum total from top to bottom of the triangle below:

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

  \footnotesize \textbf{NOTE:} As there are only 16384 routes, it is possible to solve this problem by trying every route. However, Problem 67, is the same challenge with a triangle containing one-hundred rows; it cannot be solved by brute force, and requires a clever method! ;o)

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 O(2^n), 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]))

 

Leave a Reply

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