1 ! Copyright (c) 2007 Samuel Tardieu, Aaron Schaefer.
2 ! See http://factorcode.org/license.txt for BSD license.
3 USING: kernel math ranges project-euler.common sequences ;
6 ! http://projecteuler.net/index.php?section=problems&id=18
11 ! By starting at the top of the triangle below and moving to
12 ! adjacent numbers on the row below, the maximum total from top
20 ! That is, 3 + 7 + 4 + 9 = 23.
22 ! Find the maximum total from top to bottom of the triangle
31 ! 88 02 77 73 07 63 67
32 ! 99 65 04 28 06 16 70 92
33 ! 41 41 26 56 83 40 80 70 33
34 ! 41 48 72 33 47 32 37 16 94 29
35 ! 53 71 44 65 25 43 91 52 97 51 14
36 ! 70 11 33 28 77 73 17 78 39 68 17 57
37 ! 91 71 52 38 17 14 91 43 58 50 27 29 48
38 ! 63 66 04 68 89 53 67 30 73 16 69 87 40 31
39 ! 04 62 98 27 23 09 70 98 73 93 38 53 60 04 23
41 ! NOTE: As there are only 16384 routes, it is possible to solve
42 ! this problem by trying every route. However, Problem 67, is
43 ! the same challenge with a triangle containing one-hundred
44 ! rows; it cannot be solved by brute force, and requires a
51 ! Propagate from bottom to top the longest cumulative path. This
52 ! is very efficient and will be reused in problem 67.
56 : source-018 ( -- triangle )
65 99 65 04 28 06 16 70 92
66 41 41 26 56 83 40 80 70 33
67 41 48 72 33 47 32 37 16 94 29
68 53 71 44 65 25 43 91 52 97 51 14
69 70 11 33 28 77 73 17 78 39 68 17 57
70 91 71 52 38 17 14 91 43 58 50 27 29 48
71 63 66 04 68 89 53 67 30 73 16 69 87 40 31
72 04 62 98 27 23 09 70 98 73 93 38 53 60 04 23
73 } 15 [1..b] [ cut swap ] map nip ;
77 : euler018 ( -- answer )
78 source-018 propagate-all first first ;
80 ! [ euler018 ] 100 ave-time
81 ! 0 ms ave run time - 0.29 SD (100 trials)
87 : euler018a ( -- answer )
90 ! [ euler018a ] 100 ave-time
91 ! 0 ms ave run time - 0.39 SD (100 trials)