1 ! Copyright (c) 2008 Eric Mertens.
2 ! See https://factorcode.org/license.txt for BSD license.
3 USING: kernel math math.order ranges math.statistics
4 project-euler.common sequences sequences.private ;
7 ! https://projecteuler.net/problem=150
12 ! In a triangular array of positive and negative integers, we
13 ! wish to find a sub-triangle such that the sum of the numbers
14 ! it contains is the smallest possible.
16 ! In the example below, it can be easily verified that the
17 ! marked triangle satisfies this condition having a sum of -42.
19 ! We wish to make such a triangular array with one thousand
20 ! rows, so we generate 500500 pseudo-random numbers sk in the
21 ! range +/-2^19, using a type of random number generator (known
22 ! as a Linear Congruential Generator) as follows:
26 ! Find the smallest possible sub-triangle sum.
34 ! sequence helper functions
36 : partial-sums ( seq -- sums )
37 cum-sum 0 prefix ; inline
39 : partial-sum-infimum ( seq quot -- seq )
40 [ 0 0 ] 2dip [ + [ min ] keep ] compose each drop ; inline
42 : map-infimum ( seq quot -- min )
43 [ min ] compose 0 swap reduce ; inline
45 ! triangle generator functions
47 : next ( t -- new-t s )
48 615949 * 797807 + 20 2^ rem dup 19 2^ - ; inline
50 : sums-triangle ( -- seq )
51 0 1000 [1..b] [ [ next ] replicate partial-sums ] map nip ; inline
53 :: (euler150) ( m -- n )
54 sums-triangle :> table
58 x z + table nth-unsafe
59 [ y z + 1 + swap nth-unsafe ]
60 [ y swap nth-unsafe ] bi -
63 ] map-infimum ; inline
67 : euler150 ( -- answer )
70 ! [ euler150 ] 10 ave-time
71 ! 30208 ms ave run time - 593.45 SD (10 trials)