Maximum path sum I
2014-09-13
Problem 018: Maximum path sum I
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 3That 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
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 |