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 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 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 of the triangle below:
  22
  23 !                                 75
  24 !                               95  64
  25 !                             17  47  82
  26 !                           18  35  87  10
  27 !                         20  04  82  47  65
  28 !                       19  01  23  75  03  34
  29 !                     88  02  77  73  07  63  67
  30 !                   99  65  04  28  06  16  70  92
  31 !                 41  41  26  56  83  40  80  70  33
  32 !               41  48  72  33  47  32  37  16  94  29
  33 !             53  71  44  65  25  43  91  52  97  51  14
  34 !           70  11  33  28  77  73  17  78  39  68  17  57
  35 !         91  71  52  38  17  14  91  43  58  50  27  29  48
  36 !       63  66  04  68  89  53  67  30  73  16  69  87  40  31
  37 !     04  62  98  27  23  09  70  98  73  93  38  53  60  04  23
  38
  39 ! NOTE: As there are only 16384 routes, it is possible to solve this problem by
  40 ! trying every route. However, Problem 67, is the same challenge with a
  41 ! triangle containing one-hundred rows; it cannot be solved by brute force, and
  42 ! requires a clever method! ;o)
  43
  44
  45 ! SOLUTION
  46 ! --------
  47
  48 ! Propagate from bottom to top the longest cumulative path. This is very
  49 ! efficient and will be reused in problem 67.
  50
  51 <PRIVATE
  52
  53 : source-018 ( -- triangle )
  54     {                              75
  55                                  95  64
  56                                17  47  82
  57                              18  35  87  10
  58                            20  04  82  47  65
  59                          19  01  23  75  03  34
  60                        88  02  77  73  07  63  67
  61                      99  65  04  28  06  16  70  92
  62                    41  41  26  56  83  40  80  70  33
  63                  41  48  72  33  47  32  37  16  94  29
  64                53  71  44  65  25  43  91  52  97  51  14
  65              70  11  33  28  77  73  17  78  39  68  17  57
  66            91  71  52  38  17  14  91  43  58  50  27  29  48
  67          63  66  04  68  89  53  67  30  73  16  69  87  40  31
  68        04  62  98  27  23  09  70  98  73  93  38  53  60  04  23
  69      } 15 [ 1+ cut swap ] map nip ;
  70
  71 PRIVATE>
  72
  73 : euler018 ( -- answer )
  74     source-018 propagate-all first first ;
  75
  76 ! [ euler018 ] 100 ave-time
  77 ! 0 ms ave run time - 0.29 SD (100 trials)
  78
  79
  80 ! ALTERNATE SOLUTIONS
  81 ! -------------------
  82
  83 : euler018a ( -- answer )
  84     source-018 max-path ;
  85
  86 ! [ euler018a ] 100 ave-time
  87 ! 0 ms ave run time - 0.39 SD (100 trials)
  88
  89 MAIN: euler018a