Project Euler 18: Maximum sum from top to bottom of triangular array
Project Euler 18 Problem Description
Project Euler 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 5
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
… {data continues} …
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)
Analysis
To solve this problem and problem 67, which is much larger, start the search from the bottom to the top, adding the maximums along the way. This will “bubble” the maximum total to the top of the pyramid.
Let’s follow this technique, step-by-step, with the 4 row triangle example above to show how this works.
A step-by-step look at this algorithm
3
7 5
2 4 6
8 5 9 3
Starting at the bottom,
We look at 8 and 5, pick the maximum, 8 in this case, and replace the 2 in the previous row with their sum 10.
We look next at 5 and 9, pick the maximum, 9, and replace the 4 in the previous row with their sum 13.
We look lastly at 9 and 3, pick the maximum, 9, and replace the 6 in the previous row with their sum 15.
Now our array looks like:
3
7 5
10 13 15
Let’s do it again. Take the larger of 10 and 13 and add it to 7 making 20.
Take the larger of 13 and 15 and add it to 5 making 20.
Now our array looks like:
3
20 20
At last we take the larger of 20 and 20 (yes, I know they’re the same) and add it to 3 making 23.
And our array looks like:
23
The maximum total path in the triangle.
HackerRank doesn’t add more to the challenge other than running 10 trials. The data for this problem is kept in the second Trinket tab named pe18.txt, next to the main.py tab.
Project Euler 18 Solution
Runs < 0.001 seconds in Python 2.7.
Use this link to get the Project Euler 18 Solution Python 2.7 source.
Afterthoughts
- The first line of the program reads the data file, pe18.txt, into a two dimensional array named
table. - See also, :
Project Euler 18
As I understood the formulation of the question, I started coding with starting with the row at index 1 to n -1, adding the maximum of the numbers at the level below at the same index or index + 1 of the current level and then add up a[0][0]. But turns out my answer is wrong.
Posted by Adi | January 18, 2015, 5:44 PMWhy I keep findind 1064, I did it manually too
Posted by Murilo Camargos | January 27, 2013, 9:21 AMHi Murilo, the path is RRLLRLLRRRRRLR. R is down to the right and L is down to the left. Hope this helps you find your problem.
Posted by Mike | January 29, 2013, 4:00 PMwas stuck at this problem. your solution is genius! thanks so much!
Posted by Raj | July 9, 2011, 8:54 AMThanks! Always glad to help.
Posted by Mike | July 12, 2011, 6:48 PMI feel so dumb! Your solution is not only elegant and smart, but the code is compact and to the point. I envy you! Your explanation is the best I found in the web, I really learned a lot!
Posted by Ariel Meilij | January 26, 2011, 8:08 PMThanks Ariel! I’m really glad it helped you.
Posted by Mike | January 27, 2011, 3:33 PMGreat explanation, but shouldn’t the 2nd row of your test triangle be 7 4 instead of 7 5 to coincide with problem 18’s example. Not a big deal at all, just saying..
Posted by Anonymous | January 17, 2011, 9:10 PMThanks Anon, I guess they changed the problem description since 2007. I went to archive.org just to make sure and it used to be (7,5).
http://web.archive.org/web/20071127122922/http://projecteuler.net/index.php?section=problems&id=18
I guess I’ll leave it as it was back in 2007, but I appreciate your keen attention to details!
Posted by Mike | January 17, 2011, 11:48 PMNice Solution, It helped me a lot 😛
Posted by S2xC | July 11, 2010, 11:50 PMNice Solution!
Posted by Amir | June 19, 2010, 8:57 AMDidn’t understand until I saw your explanation.
Thanks.
Posted by tom | September 7, 2009, 11:27 PMThanks for the acknowledgement. I’m glad it helped you.
Posted by Mike | September 8, 2009, 12:03 AMThis is by far the best explanation I have seen. Thank you!
Posted by Marshall | August 18, 2009, 10:51 AMThanks Marshall. I’m sorry I missed your kind words until now.
Posted by Mike | September 8, 2009, 12:04 AM