extra/project-euler/067/067.factor

   1 ! Copyright (c) 2007 Samuel Tardieu, Aaron Schaefer.
   2 ! See http://factorcode.org/license.txt for BSD license.
   3 USING: io.files math.parser namespaces project-euler.common sequences splitting ;
   4 IN: project-euler.067
   5
   6 ! http://projecteuler.net/index.php?section=problems&id=67
   7
   8 ! DESCRIPTION
   9 ! -----------
  10
  11 ! By starting at the top of the triangle below and moving to adjacent numbers
  12 ! on the row below, the maximum total from top to bottom is 23.
  13
  14 !        3
  15 !       7 5
  16 !      2 4 6
  17 !     8 5 9 3
  18
  19 ! That is, 3 + 7 + 4 + 9 = 23.
  20
  21 ! Find the maximum total from top to bottom in triangle.txt (right click and
  22 ! 'Save Link/Target As...'), a 15K text file containing a triangle with
  23 ! one-hundred rows.
  24
  25 ! NOTE: This is a much more difficult version of Problem 18. It is not possible
  26 ! to try every route to solve this problem, as there are 2^99 altogether! If you
  27 ! could check one trillion (10^12) routes every second it would take over twenty
  28 ! billion years to check them all. There is an efficient algorithm to solve it. ;o)
  29
  30
  31 ! SOLUTION
  32 ! --------
  33
  34 ! Propagate from bottom to top the longest cumulative path as is done in
  35 ! problem 18.
  36
  37 <PRIVATE
  38
  39 : source-067 ( -- seq )
  40     "extra/project-euler/067/triangle.txt" resource-path
  41     file-lines [ " " split [ string>number ] map ] map ;
  42
  43 PRIVATE>
  44
  45 : euler067 ( -- answer )
  46     source-067 propagate-all first first ;
  47
  48 ! [ euler067 ] 100 ave-time
  49 ! 18 ms run / 0 ms GC time
  50
  51
  52 ! ALTERNATE SOLUTIONS
  53 ! -------------------
  54
  55 : euler067a ( -- answer )
  56     source-067 max-path ;
  57
  58 ! [ euler067a ] 100 ave-time
  59 ! 14 ms run / 0 ms GC ave time - 100 trials
  60
  61 ! source-067 [ max-path ] curry 100 ave-time
  62 ! 3 ms run / 0 ms GC ave time - 100 trials
  63
  64 MAIN: euler067a