Project Euler # 67 Maximum path sum II (Bottom up) in Python

Question

This is Project Euler #67: Maximum path sum II:

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 in triangle.txt (right click and 'Save Link/Target As...'), a 15K text file containing a triangle with one-hundred rows.

NOTE: This is a much more difficult version of Problem 18. It is not possible to try every route to solve this problem, as there are 2⁹⁹ altogether! If you could check one trillion (10¹²) routes every second it would take over twenty billion years to check them all. There is an efficient algorithm to solve it. ;o)

I previously posted a solution to problem 18 using a greedy algorithm, here's the optimal solution using bottom up recursion.

from time import time


def get_triangle(triangle_filename):
    """Return a list of lists containing rows of the triangle."""
    triangle = open(triangle_filename).read().split('\n')
    triangle = [[int(number) for number in row.split()] for row in triangle]
    return triangle


def maximize_triangle(triangle, start_index=-1):
    """Return the maximum triangle path sum(bottom up)."""
    if start_index == - len(triangle):
        return triangle[0][0]
    for index in range(len(triangle[start_index]) - 1):
        maximum = max(triangle[start_index][index], triangle[start_index][index + 1])
        triangle[start_index - 1][index] += maximum
    return maximize_triangle(triangle, start_index - 1)


if __name__ == '__main__':
    start_time = time()
    triangle_file = get_triangle('p067_triangle.txt')
    print(f'Maximum Path: {maximize_triangle(triangle_file)}')
    print(f'Time: {time() - start_time} seconds.')

Answer 1

The algorithm is very efficient, your program computes the result in fractions of a second.

Reading the file into a nested list can be simplified to

def get_triangle(triangle_filename):
    """Return a list of lists containing rows of the triangle."""
    triangle = [[int(number) for number in row.split()]
                for row in open(triangle_filename)]
    return triangle

because open() returns a file object that can be iterated over. As an additional advantage, no empty list is appended. Your reading function actually returns

[[59], [73, 41], [52, 40, 9], ... , []]

Here

triangle_file = get_triangle('p067_triangle.txt')

I find the naming confusing: The return value is not a file, and the nested list is called triangle everywhere else. Therefore I would change that here as well:

triangle = get_triangle('p067_triangle.txt')

In the main routine

def maximize_triangle(triangle, start_index=-1):

I would use a nested loop instead of recursion. That makes the start_index parameter with its default value obsolete, and the logic is easier to understand (in my opinion). Instead of start_index and index I would use row and col as variable names. Finally the function does not “maximize a triangle” but computes the “maximal path sum,” so let's name it accordingly:

def maximal_path_sum(triangle):
    """Return the maximum triangle path sum(bottom up)."""
    # Starting with the last row ...
    for row in range(len(triangle) - 1, 0, -1):
        # ... add maximum of adjacent entries to the corresponding entry
        # in the preceding row:
        for col in range(len(triangle[row]) - 1):
            maximum = max(triangle[row][col], triangle[row][col + 1])
            triangle[row - 1][col] += maximum
    return triangle[0][0]

Answer 2

When you open() a resource, such as a file, it is important to close() it. Failure to close the resource can result in other processes not being able to access it until the garbage collector finally determines the resource is not longer in use.

The with statement is useful when opening auto-closable resources, as it will ensure the resource is closed even if execution abruptly exits with an exception.

with open(triangle_filename) as file:
    # ... use file here
# ... file is automatically closed here

---

Your bottom-up solution requires reading in the entire file, so that you can get and start the process with the last row of the triangle. As such, your solution will be \$O(n^2)\$ in memory.

There is a top-down solution, which will allow you to process from the top of the triangle down to the bottom. This means you don't need to read-in and store the entire triangle; you can process it one line at a time. As a result, a solution can be written in \$O(n)\$ memory.

def pe87(filename):

    prev = []

    with open(filename) as file:
        for line in file:
            prev = [0] + prev + [0]
            curr = map(int, line.split())
            prev = [max(a, b) + c for a, b, c in zip(prev[:-1], prev[1:], curr)]

    return max(prev)

I'm maintaining the previous maximum partial sum in prev. For each new row, I'm prepending and appending a 0 value, as a convenience for the next step.

At any given row:

• prev[:-1] is the list of previous maximum partial sums, with a 0 at the start
• prev[1:] is the list of previous maximum partial sums, with a 0 at the end
• curr is the list of values on the current row.
• All 3 list are the same length

If we take those lists, and zip them together, we get a list of tuples. Each tuple contains a previous maximum partial sum from the row above (or zero if this is the first tuple), a different previous maximum partial sum from the row above (or zero if this is the last tuple), and the value from the current row. Adding the current value to the maximum of the two previous maximum partial sums will produce the new maximum partial sum over all paths leading to this cell of the triangle.

The maximum value from the maximum partial sums of the last row is the answer.

No recursion is necessary.