extra/project-euler/018/018.factor

   1 ! Copyright (c) 2007 Samuel Tardieu, Aaron Schaefer.
   2 ! See http://factorcode.org/license.txt for BSD license.
   3 USING: kernel math math.ranges project-euler.common sequences ;
   4 IN: project-euler.018
   5
   6 ! http://projecteuler.net/index.php?section=problems&id=18
   7
   8 ! DESCRIPTION
   9 ! -----------
  10
  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
  13 ! 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 of the triangle
  23 ! below:
  24
  25 !                                 75
  26 !                               95  64
  27 !                             17  47  82
  28 !                           18  35  87  10
  29 !                         20  04  82  47  65
  30 !                       19  01  23  75  03  34
  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
  40
  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
  45 ! clever method! ;o)
  46
  47
  48 ! SOLUTION
  49 ! --------
  50
  51 ! Propagate from bottom to top the longest cumulative path. This
  52 ! is very efficient and will be reused in problem 67.
  53
  54 <PRIVATE
  55
  56 : source-018 ( -- triangle )
  57     {
  58                                    75
  59                                  95  64
  60                                17  47  82
  61                              18  35  87  10
  62                            20  04  82  47  65
  63                          19  01  23  75  03  34
  64                        88  02  77  73  07  63  67
  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 ;
  74
  75 PRIVATE>
  76
  77 : euler018 ( -- answer )
  78     source-018 propagate-all first first ;
  79
  80 ! [ euler018 ] 100 ave-time
  81 ! 0 ms ave run time - 0.29 SD (100 trials)
  82
  83
  84 ! ALTERNATE SOLUTIONS
  85 ! -------------------
  86
  87 : euler018a ( -- answer )
  88     source-018 max-path ;
  89
  90 ! [ euler018a ] 100 ave-time
  91 ! 0 ms ave run time - 0.39 SD (100 trials)
  92
  93 SOLUTION: euler018a