Project Euler Solution 18: Maximum path sum I

In today's installment of the Project Euler series we have Problem 18: Maximum path sum I which is quite an interesting one. We need to find the best weighted path through a triangle.

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

Note: As there are only 16,384 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)

Some of the problems with Project Euler are quite easy to solve. Maybe that is because I already had the neccessary insights already. Some others were quite challenging at the time. This one is one of my favorites because I initially didn't get the idea. But somehow I picked it up from somebody else and really understood why it works. That's why writing this article was especially rewarding.

Before we can do any fancy computation, we need to parse the data. For this I just represent it as a list of list of integers.

data = """
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
"""


def parse_triangle() -> list[list[int]]:
    return [[int(word) for word in line.split()] for line in data.strip().split("\n")]

Let's start with the obvious solution, namely trying all possible ways from the top to the bottom. The problems says that we start at the top, so our program will do so too. We use a recursive function traverse which will start at the top and then just take both ways. With the triangle shaped like in the code, we can either go down (row_i + 1) or down-right (row_i + 1 and col_i + 1). We let it recursively take both paths from each junction and then afterwards takes the maximum path sum from both paths. This way it will be able to reconstruct the maximum to the very top.

def traverse(triangle: list[list[int]], row_i: int, col_i: int) -> int:
    this = triangle[row_i][col_i]
    if row_i == len(triangle) - 1:
        return this
    else:
        return this + max(
            traverse(triangle, row_i + 1, col_i),
            traverse(triangle, row_i + 1, col_i + 1),
        )


def solution_brute_force() -> int:
    triangle = parse_triangle()
    return traverse(triangle, 0, 0)

And fair enough, this gets the solution 1,074 in 5.627 ms. This satisfies the “one minute rule” by far, so we're done here. Well, for this simple triangle we're done. But the problem statement already said that we can do better. So let's try this.

What what are we really doing here? We have a binary tree with shared children, like this:

But with the call stack we don't take these shared children into account. Instead we are building up a regular binary tree:

When the recursion reaches the end, it starts to propagate the numbers up. We take the maximum from both children and then pass up that maximum to the parent. Eventually the 23 emerges at the top.

Given that we have the shared children, you can see how we are doing more work that we would have to. The node 4 with children 5 and 9 is replicated twice, and we do work redundantly there. In both cases it will have a maximum path sum of 13.

We can see that the number of red arrows scales as $2^n$ with $n$ layers in the tree/triangle. This means that we will have a real bad performance with each additional layer.

The key insight here is that we do the computation bottom-up, even though our recursive function starts at the top.

But it doesn't have to be this way. Let us go back to the shared children. When we work upwards from the last layer to the one above, we can apply the same logic as before. We just don't have to redundantly compute more things. The number of computations on layer $n$ is just $2n - 2$ because the middle ones have to propagate to two parents and the outer ones to one parent.

Doing all the computations to the top is then only $\sum_{i = n}^1 (2n - 2)$ elements, which is $O(n^2)$ and therefore much easier than $O(2^n)$ as we had before.

The Python code to implement this is also rather short. We just traverse the rows and add the maximum from both children to the parent.

def solution_bottom_up() -> int:
    triangle = parse_triangle()
    for row_i in reversed(range(len(triangle) - 1)):
        row = triangle[row_i]
        for col_i in range(len(row)):
            row[col_i] += max(
                triangle[row_i + 1][col_i], triangle[row_i + 1][col_i + 1]
            )
    return triangle[0][0]

This way we can get the solution in just 44 µs. And it will also work with the bigger problem.