In my attempt to learn (Iron)Python out in the open, here’s my solution for Project Euler Problem 18.
As always, any feedback is welcome.
# Euler 18
# http://projecteuler.net/index.php?section=problems&id=18
# 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, 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)
import time
start = time.time()
triangle = [
[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, 9, 70, 98, 73, 93, 38, 53, 60, 04, 23]]
# Loop through each row of the triangle starting at the base.
for a in range(len(triangle) - 1, -1, -1):
for b in range(0, a):
# Get the maximum value for adjacent cells in current row.
# Update the cell which would be one step prior in the path
# with the new total. For example, compare the first two
# elements in row 15. Add the max of 04 and 62 to the first
# position of row 14.This provides the max total from row 14
# to 15 starting at the first position. Continue to work up
# the triangle until the maximum total emerges at the
# triangle's apex.
triangle [a-1][b] += max(triangle [a][b], triangle [a][b+1])
print triangle [0][0]
print "Elapsed Time:", (time.time() - start) * 1000, "millisecs"
a=raw_input('Press return to continue')
Sick! Just acquired a brand-new Pearl and I can now read your weblog on my phone’s browser, it didn’t get the job done on my old one.
I went over this site and I think you have a lot of good info , saved to my bookmarks (:.
I however have belief that this election was entirely rigged and The states does not have any method to verify it.
You have great info on this site… I think it’s super informative! Thank you!
is there anyone hiring bloggers out there?
I appreciate all the work you’ve put into your site! I’m going to Tweet this out to my followers… Definitely worth sharing!
One thing I’d really like to say is the fact that car insurance cancelling is a feared experience and if you’re doing the suitable things being a driver you simply won’t get one. A number of people do obtain notice that they have been officially dumped by the insurance company they have to fight to get additional insurance after having a cancellation. Affordable auto insurance rates are usually hard to get after a cancellation. Having the main reasons pertaining to auto insurance cancellations can help motorists prevent getting rid of in one of the most vital privileges out there. Thanks for the thoughts shared through your blog.
Took me time to read all the comments, but I genuinely enjoyed the post. It proved to become Incredibly helpful to me and I am certain to all the commenters here It is always nice when you can not only be informed, but also entertained I’m certain you had fun writing this post.
L’a Appetito Pizza & Deli
2542 Northbrooke Plaza Drive, Naples, FL 34119
(239) 592-7008 ?