1 ! Copyright (c) 2012 Anonymous
2 ! See https://factorcode.org/license.txt for BSD license.
3 USING: arrays math ranges sequences sets sorting ;
4 IN: rosetta-code.count-the-coins
6 ! https://rosettacode.org/wiki/Count_the_coins
8 ! There are four types of common coins in US currency: quarters
9 ! (25 cents), dimes (10), nickels (5) and pennies (1). There are 6
10 ! ways to make change for 15 cents:
12 ! A dime and a nickel;
13 ! A dime and 5 pennies;
15 ! 2 nickels and 5 pennies;
16 ! A nickel and 10 pennies;
19 ! How many ways are there to make change for a dollar using
20 ! these common coins? (1 dollar = 100 cents).
24 ! Less common are dollar coins (100 cents); very rare are half
25 ! dollars (50 cents). With the addition of these two coins, how
26 ! many ways are there to make change for $1000? (note: the answer
27 ! is larger than 232).
31 :: (make-change) ( cents coins -- ways )
32 cents 1 + 0 <array> :> ways
35 coin cents [a..b] [| j |
36 j coin - ways nth j ways [ + ] change-nth
42 ! How many ways can we make the given amount of cents
43 ! with the given set of coins?
44 : make-change ( cents coins -- ways )
45 members inv-sort (make-change) ;