Problem 18

Comments

I tried just picking the route that lead to the largest of the two numbers below each number option, but that wasn’t right. I figured I should test the easy solution before diving into the tough stuff. Now the trick will be to do this strategically…

I am struggling to try to figure out exactly how to cut the workload down on this problem. There are 2^(number of rows - 1) different ways to get from the top to the bottom. There must be a way to cut the triangle up and evaluate it piece wise. In doing so, I would then like to be able to rule out sections of the triangle at once, thus reducing the number of necessary calculations.

After considering Pascal’s Triangle for a very long time, I decided to just start writing out the given triangle and adding the sums row by row as I went. That’s when I realized that I should replace the value at each point in the triangle with the given value at that point plus the larger of the two points above it. This makes sense to me because if you are going to arrive at any point, then you would want to do so through the greatest value available, thus allowing you to ignore the lesser values completely.

Resources

I’m spending some time looking at Pascal’s Triangle on wikipedia. One important thing that they’ve said here is that the number of different paths to get from the upper vertex to any given point, is the number assigned to that point in Pascal’s Triangle.

Results

It took a few rounds of tweeking, but in the end it was good! Hard work pays off!

Code

from time import time
start_time= time()
print """Process started
----------"""

#form empty triangle:

r = []
for q in range(15):
	r[q:] = [0]


#the triangle as given:

r[0] = [75]
r[1] = [95, 64]
r[2] = [17, 47, 82]
r[3] = [18, 35, 87, 10]
r[4] = [20, 4, 82, 47, 65]
r[5] = [19, 1, 23, 75, 3, 34]
r[6] = [88, 2, 77, 73, 7, 63, 67]
r[7] = [99, 65, 4, 28, 6, 16, 70, 92]
r[8] = [41, 41, 26, 56, 83, 40, 80, 70, 33]
r[9] = [41, 48, 72, 33, 47, 32, 37, 16, 94, 29]
r[10] = [53, 71, 44, 65, 25, 43, 91, 52, 97, 51, 14]
r[11] = [70, 11, 33, 28, 77, 73, 17, 78, 39, 68, 17, 57]
r[12] = [91, 71, 52, 38, 17, 14, 91, 43, 58, 50, 27, 29, 48]
r[13] = [63, 66, 4, 68, 89, 53, 67, 30, 73, 16, 69, 87, 40, 31]
r[14] = [4, 62, 98, 27, 23, 9, 70, 98, 73, 93, 38, 53, 60, 4, 23]


#define functions:

def value(n, m):
	return r[n][m]

def maxi(n, m):
	if n==0:
		return r[n][m]
	elif m==0:
		return r[n-1][m]
	elif m==n:
		return r[n-1][m-1]
	else:
		return max(value(n-1, m-1), value(n-1, m))


#summing the element plus the greater of the two above it:

for s in range(1, 15):
	for t in range(s+1):
		r[s][t] = value(s, t) + maxi(s, t)
	print r[s]
		

#big pay off:

print max(r[14]), 'Tah Dah!'
		

end_time= time()
elapse_time= end_time - start_time
print '----------'
print elapse_time, 'seconds have passed'