Problem #18 is one of the first problems on Project Euler to prominently feature DP (Dynamic Programming) and the first to explicitly be part of a series of similar problems. The problem reads:
Project Euler Problem 18: Maximum path sum I
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 routs, it is possible to solve this problem by trying every route. However, 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! ;o)
This time, the problem explicitly encourages us not to check every route and instead to search for an efficient solution. Luckily, we can find a more efficient solution with the use of DP:
Solution #1: Dynamic Approach
The boring part of this problem is figuring out how to store the triangle. I decided to use a jagged 2D array to store the numbers in each row, and I filled the array by reading from a text file which I labeled “PE18Triangle.txt”. I have worked with programming languages such as TI-nspire Basic which do not support jagged arrays as they interpret 2D arrays as matrices. Unfortunately, my method of storing the triangle probably will not work in those languages. Once we’ve stored the triangle, it’s time for the fun part:
Instead of proceeding from the top of the triangle to the bottom, we instead go from the bottom up, recording the maximum path to the bottom that enters each number in the triangle. This is quite difficult to explain with words, so here is my implementation of this method in Python 2.7:
'''
Author: Walker Kroubalkian
Dynamic Approach to Project Euler Problem #18
'''
import time
f = open("PE18Triangle.txt","r")
if(f.mode == "r"):
contents = f.readlines()
realContents = []
for x in contents:
realContents.append(map(int,x.split()))
else:
raise ValueError("Cannot read from file")
def projectEulerProblemEighteen(triangle):
rows = len(triangle)
currentRow = triangle[rows-1]
c = (rows-2)
while(c>=0):
temp = []
for i in range(c+1):
temp.append(triangle[c][i] + max(currentRow[i],currentRow[i+1]))
currentRow = temp
c-=1
return currentRow[0]
start = time.time()
print projectEulerProblemEighteen(realContents)
print ("--- %s seconds ---" % (time.time()-start))
'''
Prints
1074
--- 5.19752502441e-05 seconds ---
for input of triangle = given triangle
'''
And with that, we’re done. This problem was one of my first experiences with DP, and as a result, it remains one of my favorite computer programming questions to this day.
Thanks for reading! See you tomorrow.
The Inner Machinations of Walker 