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 ranges math.statistics
   4 project-euler.common sequences sequences.private ;
   5 IN: project-euler.150
   6
   7 ! http://projecteuler.net/index.php?section=problems&id=150
   8
   9 ! DESCRIPTION
  10 ! -----------
  11
  12 ! In a triangular array of positive and negative integers, we wish to find a
  13 ! sub-triangle such that the sum of the numbers it contains is the smallest
  14 ! possible.
  15
  16 ! In the example below, it can be easily verified that the marked triangle
  17 ! satisfies this condition having a sum of -42.
  18
  19 ! We wish to make such a triangular array with one thousand rows, so we
  20 ! generate 500500 pseudo-random numbers sk in the range +/-2^19, using a type of
  21 ! random number generator (known as a Linear Congruential Generator) as
  22 ! follows:
  23
  24 ! ...
  25
  26 ! Find the smallest possible sub-triangle sum.
  27
  28
  29 ! SOLUTION
  30 ! --------
  31
  32 <PRIVATE
  33
  34 ! sequence helper functions
  35
  36 : partial-sums ( seq -- sums )
  37     cum-sum 0 prefix ; inline
  38
  39 : partial-sum-infimum ( seq quot -- seq )
  40     [ 0 0 ] 2dip [ + [ min ] keep ] compose each drop ; inline
  41
  42 : map-infimum ( seq quot -- min )
  43     [ min ] compose 0 swap reduce ; inline
  44
  45 ! triangle generator functions
  46
  47 : next ( t -- new-t s )
  48     615949 * 797807 + 20 2^ rem dup 19 2^ - ; inline
  49
  50 : sums-triangle ( -- seq )
  51     0 1000 [1..b] [ [ next ] replicate partial-sums ] map nip ; inline
  52
  53 :: (euler150) ( m -- n )
  54     sums-triangle :> table
  55     m <iota> [| x |
  56         x 1 + <iota> [| y |
  57             m x - <iota> [| z |
  58                 x z + table nth-unsafe
  59                 [ y z + 1 + swap nth-unsafe ]
  60                 [ y         swap nth-unsafe ] bi -
  61             ] partial-sum-infimum
  62         ] map-infimum
  63     ] map-infimum ; inline
  64
  65 PRIVATE>
  66
  67 : euler150 ( -- answer )
  68     1000 (euler150) ;
  69
  70 ! [ euler150 ] 10 ave-time
  71 ! 30208 ms ave run time - 593.45 SD (10 trials)
  72
  73 SOLUTION: euler150