#!/usr/bin/pythondatain = [l.strip().split(" ") for l in open("triangle.txt").read().split("\n") \ if len(l) != 0]#dynamic programming! No idea why it's called that...#m is lines of lists of [value, running-total, direction-total-from]#/me longs for enumsVALUE = 0RUNNING_TOTAL = 1PREVIOUS = 2LEFT = 0RIGHT = 1m = [[[int(d), 0, None] for d in l] for l in datain]for l in range(1, len(m)): line_above = m[l-1] line = m[l] #For each item on the line, identify the item above that is bigger #First item (nothing above-left) line[0][RUNNING_TOTAL] = line_above[0][RUNNING_TOTAL] + line[0][VALUE] line[0][PREVIOUS] = line_above[0] for n in range(1, len(line)-2): #Do it for others in the line if line_above[n-1][RUNNING_TOTAL] > line_above[n][RUNNING_TOTAL]: #Sum from above-left line[n][RUNNING_TOTAL] = line_above[n-1][RUNNING_TOTAL] + line[n][VALUE] line[n][PREVIOUS] = line_above[n-1] else: #Sum from above-right line[n][RUNNING_TOTAL] = line_above[n][RUNNING_TOTAL] + line[n][VALUE] line[n][PREVIOUS] = line_above[n] #Last item (nothing above-right) n = len(line)-1 line[n][RUNNING_TOTAL] = line_above[len(line_above)-1][RUNNING_TOTAL] + line[n][VALUE] line[n][PREVIOUS] = line_above[len(line_above)-1]#Now find the route (backwards)#Find the endbest = Nonebest_total = 0for n in m[len(m)-1]: if n[RUNNING_TOTAL] > best_total: best = nprint "Total: %d" % n[RUNNING_TOTAL]winners = [n]while n[PREVIOUS] != None: n = n[PREVIOUS] winners.insert(0, n)print [n[VALUE] for n in winners]