Source:
def solve_triangle(x):
    # we start from bottom triangle
    for i in xrange(len(x) - 2, -1, -1):        
        for j in xrange(i + 1):
            #  A
            # B C -> if B > C add B else add C to A, then go up the tree
            x[i][j] += x[i + 1][j] if x[i + 1][j] > x[i + 1][j + 1] else x[i + 1][j + 1]
    return x[0][0]
Sample Usage:
# Sample Input
#        3
#      1  6
#    4   4  2
#  3   2  8   5

print solve_triangle([[3], [1, 6], [4, 4, 2], [3, 2, 8, 5]])
# output is sum of (3 + 6 + 4 + 8)
# 21

# Here is a 100 row input:
# print solve_triangle(map(lambda n: map(lambda i: int(i), n.strip().split(' ')), urllib2.urlopen('http://www.yodlecareers.com/puzzles/triangle.txt').read().split('\n')))

Finds the highest total adjacent numbers from top to bottom of triangle of numbers.

Pythoneer 6 years ago