This problem is the same as Project Euler Problem 18, but is done on a much, much larger triangle. Problem 18 can be done with a depth-first backtrack approach, but I showed that a much easier solution solves it. I use that same approach here.
Problem: 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.
2 4 6
8 5 9 3
That is, $3+7+4+9=23$. Find the maximum total from top to bottom of the triangle contained in this triangle (text file)
Solution: Keep It Simple Stupid
The sums traveling from top to bottom will be the same as the sums traveling from bottom to top. Start at the second to bottom row, and for each number $N$ in that row, do the following: Take the maximum of the numbers directly down and left or down and right from $N$, and add that to $N$. Now do the same for the third-to-last row, then fourth-to-last, and so on. We’re modifying the triangle as we go to produce maximum partial sums from the bottom, and the last stage will be to replace to top number in the triangle, which will then be the maximum sum. So easy.
#!/usr/bin/env python import time # read file rows =  FILE = open("triangle.txt", "r") for blob in FILE: rows.append([int(i) for i in blob.split(" ")]) start = time.time() for i,j in [(i,j) for i in range(len(rows)-2,-1,-1) for j in range(i+1)]: rows[i][j] += max([rows[i+1][j],rows[i+1][j+1]]) elapsed = time.time() - start print "%s found in %s seconds" % (rows,elapsed)
When executed, we find:
7273 found in 0.0093560218811 seconds