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 math.order sequences sequences.private
   4 locals hints ;
   5 IN: project-euler.150
   6
   7 <PRIVATE
   8
   9 ! sequence helper functions
  10
  11 : partial-sums ( seq -- sums )
  12     0 [ + ] accumulate swap suffix ; inline
  13
  14 : (partial-sum-infimum) ( inf sum elt -- inf sum )
  15     + [ min ] keep ; inline
  16
  17 : partial-sum-infimum ( seq -- seq )
  18     0 0 rot [ (partial-sum-infimum) ] each drop ; inline
  19
  20 : map-infimum ( seq quot -- min )
  21     [ min ] compose 0 swap reduce ; inline
  22
  23
  24 ! triangle generator functions
  25
  26 : next ( t -- new-t s )
  27     615949 * 797807 + 20 2^ rem dup 19 2^ - ; inline
  28
  29 : sums-triangle ( -- seq )
  30     0 1000 [ 1+ [ next ] replicate partial-sums ] map nip ;
  31
  32 PRIVATE>
  33
  34 :: (euler150) ( m -- n )
  35     [let | table [ sums-triangle ] |
  36         m [| x |
  37             x 1+ [| y |
  38                 m x - [| z |
  39                     x z + table nth-unsafe
  40                     [ y z + 1+ swap nth-unsafe ]
  41                     [ y        swap nth-unsafe ] bi -
  42                 ] map partial-sum-infimum
  43             ] map-infimum
  44         ] map-infimum
  45     ] ;
  46
  47 HINTS: (euler150) fixnum ;
  48
  49 : euler150 ( -- n )
  50     1000 (euler150) ;