extra/rosetta-code/count-the-coins/count-the-coins.factor

   1 ! Copyright (c) 2012 Anonymous
   2 ! See http://factorcode.org/license.txt for BSD license.
   3 USING: arrays locals math math.ranges sequences sets sorting ;
   4 IN: rosetta-code.count-the-coins
   5
   6 ! http://rosettacode.org/wiki/Count_the_coins
   7
   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:
  11
  12 ! A dime and a nickel;
  13 ! A dime and 5 pennies;
  14 ! 3 nickels;
  15 ! 2 nickels and 5 pennies;
  16 ! A nickel and 10 pennies;
  17 ! 15 pennies.
  18
  19 ! How many ways are there to make change for a dollar using
  20 ! these common coins? (1 dollar = 100 cents).
  21
  22 ! Optional:
  23
  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).
  28
  29 <PRIVATE
  30
  31 :: (make-change) ( cents coins -- ways )
  32     cents 1 + 0 <array> :> ways
  33     1 ways set-first
  34     coins [| coin |
  35         coin cents [a..b] [| j |
  36             j coin - ways nth j ways [ + ] change-nth
  37         ] each
  38     ] each ways last ;
  39
  40 PRIVATE>
  41
  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-with (make-change) ;