1 ! Copyright (c) 2008 Eric Mertens.
2 ! See http://factorcode.org/license.txt for BSD license.
3 USING: hints kernel locals math math.order sequences sequences.private project-euler.common ;
6 ! http://projecteuler.net/index.php?section=problems&id=150
11 ! In a triangular array of positive and negative integers, we wish to find a
12 ! sub-triangle such that the sum of the numbers it contains is the smallest
15 ! In the example below, it can be easily verified that the marked triangle
16 ! satisfies this condition having a sum of -42.
18 ! We wish to make such a triangular array with one thousand rows, so we
19 ! generate 500500 pseudo-random numbers sk in the range +/-2^19, using a type of
20 ! random number generator (known as a Linear Congruential Generator) as
25 ! Find the smallest possible sub-triangle sum.
33 ! sequence helper functions
35 : partial-sums ( seq -- sums )
36 0 [ + ] accumulate swap suffix ; inline
38 : (partial-sum-infimum) ( inf sum elt -- inf sum )
39 + [ min ] keep ; inline
41 : partial-sum-infimum ( seq -- seq )
42 0 0 rot [ (partial-sum-infimum) ] each drop ; inline
44 : map-infimum ( seq quot -- min )
45 [ min ] compose 0 swap reduce ; inline
47 ! triangle generator functions
49 : next ( t -- new-t s )
50 615949 * 797807 + 20 2^ rem dup 19 2^ - ; inline
52 : sums-triangle ( -- seq )
53 0 1000 [ 1+ [ next ] replicate partial-sums ] map nip ;
55 :: (euler150) ( m -- n )
56 [let | table [ sums-triangle ] |
60 x z + table nth-unsafe
61 [ y z + 1+ swap nth-unsafe ]
62 [ y swap nth-unsafe ] bi -
63 ] map partial-sum-infimum
68 HINTS: (euler150) fixnum ;
72 : euler150 ( -- answer )
75 ! [ euler150 ] 10 ave-time
76 ! 30208 ms ave run time - 593.45 SD (10 trials)