extra/project-euler/150/150.factor

   1 ! Copyright (c) 2008 Eric Mertens
   2 ! See http://factorcode.org/license.txt for BSD license.
   3 USING: kernel math sequences locals ;
   4 IN: project-euler.150
   5
   6 <PRIVATE
   7
   8 ! sequence helper functions
   9
  10 : partial-sums ( seq -- seq )
  11     0 [ + ] accumulate swap suffix ; inline
  12
  13 : generate ( n quot -- seq )
  14     [ drop ] swap compose map ; inline
  15
  16 : map-infimum ( seq quot -- min )
  17     [ min ] compose 0 swap reduce ; inline
  18
  19
  20 ! triangle generator functions
  21
  22 : next ( t -- new-t s )
  23     615949 * 797807 + 1 20 shift mod dup 1 19 shift - ; inline
  24
  25 : sums-triangle ( -- seq )
  26     0 1000 [ 1+ [ next ] generate partial-sums ] map nip ;
  27
  28 PRIVATE>
  29
  30 :: (euler150) ( m -- n )
  31     [let | table [ sums-triangle ] |
  32         m [| x |
  33             x 1+ [| y |
  34                 m x - [| z |
  35                     x z + table nth
  36                     [ y z + 1+ swap nth ]
  37                     [ y        swap nth ] bi -
  38                 ] map partial-sums infimum
  39             ] map-infimum
  40         ] map-infimum
  41     ] ;
  42
  43 : euler150 ( -- n )
  44     1000 (euler150) ;