#!/usr/bin/python
#
# Project Euler Problem 18
# 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 5
#  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.
# 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^(99) altogether!
# If you could check one trillion (10^(12)) routes every second it would take
# over twenty billion years to check them all. There is an efficient algorithm
# to solve it. ;o)

triangle_file = open('Problem067-triangle.txt')
triangle = triangle_file.read().strip().split('\n')
triangle_file.close()

for i, line in enumerate(triangle):
        row = []
        for n in line.split():
            row.append(int(n))
        triangle[i] = row

for i in range(100):
    for j in range(i+1):
        if i != 0:
            if j == 0:
                triangle[i][j] += triangle[i-1][j]
            elif j == i:
                triangle[i][j] += triangle[i-1][j-1]
            else:
                triangle[i][j] += max(triangle[i-1][j-1], triangle[i-1][j])

print max(triangle[99])