Project Euler problem #67

067_maximum_path_sum_ii.py

#!/usr/bin/env python3
"""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, a 15K text file
containing a triangle with one-hundred rows.

https://projecteuler.net/project/triangle.txt
"""

import urllib.request

TRIANGLE_URL = 'https://projecteuler.net/project/triangle.txt'

# Read the triangle
with urllib.request.urlopen(TRIANGLE_URL) as triangle_txt:
    # (This did fit on one line, but it was kind of hard to read)
    triangle = [
        [int(num) for num in row.split()]
        for row in triangle_txt
    ]

# Collapse the triangle from the top down.  In each iteration, the bigger
# number in each pair of adjacent numbers gets added to the number below.
while len(triangle) > 1:
    # Handle edge cells
    triangle[1][0] += triangle[0][0]
    triangle[1][-1] += triangle[0][-1]

    # Go through all the non-edge cells in the second row, adding the bigger
    # upstairs neighbour to each
    for n in range(1, len(triangle[1]) - 1):
        triangle[1][n] += max(
            triangle[0][n - 1],
            triangle[0][n]
        )

    # Chop off the top row
    del triangle[0]

# We're left with the max total for each end point; we want the MAX max total
print(max(triangle[0]))