! Copyright (c) 2008 Eric Mertens.
! See http://factorcode.org/license.txt for BSD license.
-USING: hints kernel locals math math.order sequences sequences.private project-euler.common ;
+USING: kernel math math.order ranges math.statistics
+project-euler.common sequences sequences.private ;
IN: project-euler.150
! http://projecteuler.net/index.php?section=problems&id=150
! sequence helper functions
: partial-sums ( seq -- sums )
- 0 [ + ] accumulate swap suffix ; inline
+ cum-sum 0 prefix ; inline
-: (partial-sum-infimum) ( inf sum elt -- inf sum )
- + [ min ] keep ; inline
-
-: partial-sum-infimum ( seq -- seq )
- 0 0 rot [ (partial-sum-infimum) ] each drop ; inline
+: partial-sum-infimum ( seq quot -- seq )
+ [ 0 0 ] 2dip [ + [ min ] keep ] compose each drop ; inline
: map-infimum ( seq quot -- min )
[ min ] compose 0 swap reduce ; inline
615949 * 797807 + 20 2^ rem dup 19 2^ - ; inline
: sums-triangle ( -- seq )
- 0 1000 [ 1+ [ next ] replicate partial-sums ] map nip ;
+ 0 1000 [1..b] [ [ next ] replicate partial-sums ] map nip ; inline
:: (euler150) ( m -- n )
- [let | table [ sums-triangle ] |
- m [| x |
- x 1+ [| y |
- m x - [| z |
- x z + table nth-unsafe
- [ y z + 1+ swap nth-unsafe ]
- [ y swap nth-unsafe ] bi -
- ] map partial-sum-infimum
- ] map-infimum
+ sums-triangle :> table
+ m <iota> [| x |
+ x 1 + <iota> [| y |
+ m x - <iota> [| z |
+ x z + table nth-unsafe
+ [ y z + 1 + swap nth-unsafe ]
+ [ y swap nth-unsafe ] bi -
+ ] partial-sum-infimum
] map-infimum
- ] ;
-
-HINTS: (euler150) fixnum ;
+ ] map-infimum ; inline
PRIVATE>