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.

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 of the triangle below.

75
95 64
17 47 82
18 35 87 10
20 04 82 47 65
19 01 23 75 03 34
88 02 77 73 07 63 67
99 65 04 28 06 16 70 92
41 41 26 56 83 40 80 70 33
41 48 72 33 47 32 37 16 94 29
53 71 44 65 25 43 91 52 97 51 14
70 11 33 28 77 73 17 78 39 68 17 57
91 71 52 38 17 14 91 43 58 50 27 29 48
63 66 04 68 89 53 67 30 73 16 69 87 40 31
04 62 98 27 23 09 70 98 73 93 38 53 60 04 23

NOTE: As there are only 16384 routes, it is possible to solve this problem by trying every route. However, Project Euler Problem 67 is the same challenge, with a triangle containing one-hundred rows; it cannot be solved by brute force and requires a clever method.

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.

Python Solution

I stored the triangle in the file “problem-18-data”.

#!/usr/bin/env python
 
import time
 
# define a recursive function to create partial sums by row
def recSumAtRow(rowData, rowNum):
    # iterate over the given row
    for i in range(len(rowData[rowNum])):
        # add the largest of the values below-left or below-right
        rowData[rowNum][i] += max([rowData[rowNum+1][i],rowData[rowNum+1][i+1]])
    # base case
    if len(rowData[rowNum])==1: return rowData[rowNum][0]
    # recursive case
    else: return recSumAtRow(rowData, rowNum-1)
 
# read in the data
rows = []
with open('problem-18-data') as f:
    for line in f:
        rows.append([int(i) for i in line.rstrip('\n').split(" ")])
 
 
start = time.time()
result = recSumAtRow(rows, len(rows)-2) # start at second to last row
elapsed = time.time() - start
 
 
print "%s found in %s seconds" % (result ,elapsed)

When executed, we find:

1074 found in 6.79492950439e-05 seconds

2 Trackbacks

  1. [...] 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 [...]

  2. [...] of the stuff I can find on the web (and there’s a LOT more googling that happened beyond that) is some variation [...]