1 ! Copyright (c) 2008 Eric Mertens.
2 ! See http://factorcode.org/license.txt for BSD license.
3 USING: arrays assocs combinators kernel locals math math.order math.ranges
7 ! http://projecteuler.net/index.php?section=problems&id=76
12 ! How many different ways can one hundred be written as a
13 ! sum of at least two positive integers?
19 ! This solution uses dynamic programming and the following
24 ! ways(n,i) = ways(n-i,i) + ways(n,i-1)
29 [1,b] [ 0 2array 0 ] H{ } map>assoc
30 1 { 0 0 } pick set-at ;
33 [ - dup ] keep min ; inline
35 : ways ( n i table -- )
39 [ [ 1- 2array ] dip at ]
40 [ [ use 2array ] dip at + ]
41 [ [ 2array ] dip set-at ] 3tri
44 :: each-subproblem ( n quot -- )
45 n [1,b] [ dup [1,b] quot with each ] each ; inline
47 : (euler076) ( n -- m )
49 [ [ ways ] curry each-subproblem ]
50 [ [ dup 2array ] dip at 1- ] 2bi ;
54 : euler076 ( -- answer )
57 ! [ euler076 ] 100 ave-time
58 ! 704 ms run time - 100 trials