extra/project-euler/067/067.factor

   1 ! Copyright (c) 2007 Aaron Schaefer.
   2 ! See http://factorcode.org/license.txt for BSD license.
   3 USING: io io.files kernel math.parser namespaces project-euler.common sequences
   4     splitting system vocabs ;
   5 IN: project-euler.067
   6
   7 ! http://projecteuler.net/index.php?section=problems&id=67
   8
   9 ! DESCRIPTION
  10 ! -----------
  11
  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.
  14
  15 !        3
  16 !       7 5
  17 !      2 4 6
  18 !     8 5 9 3
  19
  20 ! That is, 3 + 7 + 4 + 9 = 23.
  21
  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
  24 ! one-hundred rows.
  25
  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)
  30
  31
  32 ! SOLUTION
  33 ! --------
  34
  35 <PRIVATE
  36
  37 : (source-067) ( -- path )
  38     [
  39         "project-euler.067" vocab-root ?resource-path %
  40         os "windows" = [
  41             "\\project-euler\\067\\triangle.txt" %
  42         ] [
  43             "/project-euler/067/triangle.txt" %
  44         ] if
  45     ] "" make ;
  46
  47 : source-067 ( -- triangle )
  48     (source-067) <file-reader> lines [ " " split [ string>number ] map ] map ;
  49
  50 PRIVATE>
  51
  52 : euler067 ( -- answer )
  53     source-067 max-path ;
  54
  55 ! [ euler067 ] 100 ave-time
  56 ! 15 ms run / 0 ms GC ave time - 100 trials
  57
  58 MAIN: euler067