Created
February 18, 2012 03:27
-
-
Save SavinaRoja/1857198 to your computer and use it in GitHub Desktop.
A solution to Project Euler #18.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#Problem 18 from Project Euler | |
#Solution by Paul Barton | |
# | |
#The problem presents us with a triangle, which I represent as a list of lists | |
#in the code the below. Though this problem *may* be brute forced, I would like | |
#to do this problem elegantly the first time through, as it is merely a scaled | |
#down version of one which is not brute-forceable later on (#67). | |
#Thus we need a method that scales well. | |
# | |
#I observe that the algorithm has only limited need for memory. Each point has | |
#multiple routes to get to it, but only the one of highest value matters. I | |
#still need to test this on #67 to prove that it scales well (or not...), here | |
#is the basic concept. | |
# | |
# 75 -- -- | |
# 95 64 --> 170 139 --> --- --- | |
#17 47 82 17 47 82 187 217/186 221 | |
# | |
#On the third step we hav a choice, there were multiple routes to this middle | |
#node, but the future choice space is the same, so why even think about the one | |
#that has a lesser value. I use only the highest valued history for the | |
#degenerate states in the future calculations. Thus the next step would be: | |
# | |
# 187 217 221 --- --- --- | |
#18 35 87 10 --> 205 222/252 304/308 231 | |
# | |
#And so it goes... I think that perhaps this problem could be done in reverse. | |
#I will have to look into it. Intuitively, it might be even faster. | |
import time | |
TRIA = [[75],[95, 64], [17, 47, 82], [18, 35, 87, 10], [20, 4, 82, 47, 65], | |
[19, 1, 23, 75, 3, 34], [88, 2, 77, 73, 7, 63, 67], [99, 65, 4, 28, | |
6, 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, 4, 68, 89, 53, 67, 30, 73, | |
16, 69, 87, 40, 31], [4, 62, 98, 27, 23, 9, 70, 98, 73, 93, 38, 53, | |
60, 4, 23]] | |
t = time.time() | |
def compute_layer(top, bottom): | |
'''I will do some stuff that might seem ugly, but it should be a little | |
faster and still comprehensible.''' | |
ind = 0 | |
pairs = [] | |
while ind < len(bottom): | |
f = top[ind - 1] | |
try: | |
s = top[ind] | |
except IndexError: | |
s = 0 | |
pairs.append((f + bottom[ind], s + bottom[ind])) | |
ind += 1 | |
layer = [] | |
for each in pairs: | |
layer.append(max(each)) | |
return layer | |
last = [] | |
m = 0 | |
while m < len(TRIA) - 1: | |
if not last: | |
last = compute_layer(TRIA[m], TRIA[m + 1]) | |
else: | |
last = compute_layer(last, TRIA[m + 1]) | |
m += 1 | |
print(max(last)) | |
print(time.time() - t) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment