1 ! Copyright (c) 2007 Samuel Tardieu, Aaron Schaefer.
2 ! See http://factorcode.org/license.txt for BSD license.
3 USING: io io.files kernel math.parser namespaces project-euler.018
4 project-euler.common sequences splitting system vocabs ;
7 ! http://projecteuler.net/index.php?section=problems&id=67
12 ! By starting at the top of the triangle below and moving to adjacent numbers
13 ! on the row below, the maximum total from top to bottom is 23.
20 ! That is, 3 + 7 + 4 + 9 = 23.
22 ! Find the maximum total from top to bottom in triangle.txt (right click and
23 ! 'Save Link/Target As...'), a 15K text file containing a triangle with
26 ! NOTE: This is a much more difficult version of Problem 18. It is not possible
27 ! to try every route to solve this problem, as there are 2^99 altogether! If you
28 ! could check one trillion (10^12) routes every second it would take over twenty
29 ! billion years to check them all. There is an efficient algorithm to solve it. ;o)
35 ! Propagate from bottom to top the longest cumulative path as is done in
41 "resource:extra/project-euler/067/triangle.txt" ?resource-path
42 <file-reader> lines [ " " split [ string>number ] map ] map ;
46 : euler067 ( -- answer )
47 pyramid propagate-all first first ;
49 ! [ euler067 ] 100 ave-time
50 ! 18 ms run / 0 ms GC time
58 : (source-067a) ( -- path )
60 "project-euler.067" vocab-root ?resource-path %
62 "\\project-euler\\067\\triangle.txt" %
64 "/project-euler/067/triangle.txt" %
68 : source-067a ( -- triangle )
69 (source-067a) <file-reader> lines [ " " split [ string>number ] map ] map ;
73 : euler067a ( -- answer )
74 source-067a max-path ;
76 ! [ euler067a ] 100 ave-time
77 ! 15 ms run / 0 ms GC ave time - 100 trials
79 ! source-067a [ max-path ] curry 100 ave-time
80 ! 3 ms run / 0 ms GC ave time - 100 trials