extra/project-euler/067/067.factor

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