#!/usr/bin/env setl
--
-- Count the coins in SETL
--
-- From
-- http://rosettacode.org/wiki/Count_the_coins
-- """
-- There are four types of common coins in US currency:
-- quarters (25 cents), dimes (10), nickels (5) and pennies (1).
-- There are 6 ways to make change for 15 cents:
--
-- A dime and a nickel;
-- A dime and 5 pennies;
-- 3 nickels;
-- 2 nickels and 5 pennies;
-- A nickel and 10 pennies;
-- 15 pennies.
--
-- How many ways are there to make change for a dollar using these common coins?
-- (1 dollar = 100 cents).
--
-- Optional:
--
-- Less common are dollar coins (100 cents); very rare are half dollars (50 cents).
-- With the addition of these two coins, how many ways are there to make change for $1000?
-- (note: the answer is larger than 232).
-- """
--
-- This SETL program was created by Hakan Kjellerstrand (hakank@bonetmail.com)
-- Also see my SETL page: http://www.hakank.org/setl/
--
print("m:", 100, "using:", [25,10,5,1]);
t1 := time();
print(changes(100,[25,10,5,1]));
t2 := time();
print("It took", t2-t1, "ms");
for p in [[100,50,25,10,5,1], [200, 100,50,25,10,5,1]] loop
for m in [100, 10000, 100000, 1000000] loop
print("m:", m, "using ", p);
t2 := time();
print(changes(m,[100,50,25,10,5,1]));
t3 := time();
print("It took", t3-t2, "ms");
end loop;
end loop;
proc changes(amount, coins);
ways := [0 : i in [1..amount]];
ways(1) := 1;
for coin in coins loop
for j in [coin..amount] loop
ways(j+1) +:= ways(1+j-coin);
end loop;
end loop;
--print(ways);
return ways(amount+1);
end proc;