Project Euler # 67 Maximum path sum II (Bottom up) in Python 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 299 altogether! If you could check one trillion (1012) 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.')
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]