Maximum path sum I


Fork me on GitHub
2014-09-13

Problem 018: Maximum path sum I

Description:

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:

...

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)


Solution:
  >53* 00p00g1-20p010p>10g3*:20g1+g"0"-55+*\1+20g1+g"0"-+10g20g1+p10g1+:10p20g-1-#v_20g:1-20p010p#v_v
75                    ^                                                           <               < v
95 64                 v                                                                             <
17 47 82                                                                 > $v
18 35 87 10           >00g2-:10p20p>10g20g1+g10g20g2+g:10g1+20g2+g -:0`>#^_->+10g20g1+p10g:1-10p#v_20g:1-:20p10p#v_01g.@
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
Start
??
Pause
Reset
Output:
Stack:   (0)

Explanation:

Step 1: Convert the numbers so that 1 field = 1 number

Step 2: Set every field to value + max(value-left, value-right)

Step 3: The solution is the value of the top-most field


Interpreter steps: 15 048
Execution time (BefunExec): 16ms (0.94 MHz)
Program size: 120 x 16
Solution: 1074
Solved at: 2014-09-13



made with vanilla PHP and MySQL, no frameworks, no bootstrap, no unnecessary* javascript