Count the coins
![Task](http://static.miraheze.org/rosettacodewiki/thumb/b/ba/Rcode-button-task-crushed.png/64px-Rcode-button-task-crushed.png)
You are encouraged to solve this task according to the task description, using any language you may know.
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).
Algorithm: See here.
360 Assembly
<lang 360asm>* count the coins 04/09/2015 COINS CSECT
USING COINS,R12 LR R12,R15 L R8,AMOUNT npenny=amount L R4,AMOUNT SRDA R4,32 D R4,=F'5' LR R9,R5 nnickle=amount/5 L R4,AMOUNT SRDA R4,32 D R4,=F'10' LR R10,R5 ndime=amount/10 L R4,AMOUNT SRDA R4,32 D R4,=F'25' LR R11,R5 nquarter=amount/25 SR R1,R1 count=0 SR R4,R4 p=0
LOOPP CR R4,R8 do p=0 to npenny
BH ELOOPP SR R5,R5 n=0
LOOPN CR R5,R9 do n=0 to nnickle
BH ELOOPN SR R6,R6
LOOPD CR R6,R10 do d=0 to ndime
BH ELOOPD SR R7,R7 q=0
LOOPQ CR R7,R11 do q=0 to nquarter
BH ELOOPQ LR R3,R5 n MH R3,=H'5' LR R2,R4 p AR R2,R3 LR R3,R6 d MH R3,=H'10' AR R2,R3 LR R3,R7 q MH R3,=H'25' AR R2,R3 s=p+n*5+d*10+q*25 C R2,=F'100' if s=100 BNE NOTOK LA R1,1(R1) count=count+1
NOTOK LA R7,1(R7) q=q+1
B LOOPQ
ELOOPQ LA R6,1(R6) d=d+1
B LOOPD
ELOOPD LA R5,1(R5) n=n+1
B LOOPN
ELOOPN LA R4,1(R4) p=p+1
B LOOPP
ELOOPP XDECO R1,PG+0 edit count
XPRNT PG,12 print count XR R15,R15 BR R14
AMOUNT DC F'100' start value in cents PG DS CL12
YREGS END COINS</lang>
- Output:
242
Ada
<lang Ada>with Ada.Text_IO;
procedure Count_The_Coins is
type Counter_Type is range 0 .. 2**63-1; -- works with gnat type Coin_List is array(Positive range <>) of Positive;
function Count(Goal: Natural; Coins: Coin_List) return Counter_Type is Cnt: array(0 .. Goal) of Counter_Type := (0 => 1, others => 0); -- 0 => we already know one way to choose (no) coins that sum up to zero -- 1 .. Goal => we do not (yet) other ways to choose coins begin for C in Coins'Range loop for Amount in 1 .. Cnt'Last loop if Coins(C) <= Amount then Cnt(Amount) := Cnt(Amount) + Cnt(Amount-Coins(C)); -- Amount-Coins(C) plus Coins(C) sums up to Amount; end if; end loop; end loop; return Cnt(Goal); end Count;
procedure Print(C: Counter_Type) is begin Ada.Text_IO.Put_Line(Counter_Type'Image(C)); end Print;
begin
Print(Count( 1_00, (25, 10, 5, 1))); Print(Count(1000_00, (100, 50, 25, 10, 5, 1)));
end Count_The_Coins;</lang>
Output:
242 13398445413854501
ALGOL 68
This corresponds to a "naive" Haskell version; to do the larger problem will require a better approach.
<lang Algol68>
Rosetta Code "Count the coins" This is a direct translation of a Haskell version, using an array rather than a list. LWB, UPB, and array slicing makes the mapping very simple: LWB > UPB <=> [] LWB = UPB <=> [x] a[LWB a] <=> head xs a[LWB a + 1:] <=> tail xs
BEGIN
PROC ways to make change = ([] INT denoms, INT amount) INT : BEGIN IF amount = 0 THEN 1 ELIF LWB denoms > UPB denoms THEN 0 ELIF LWB denoms = UPB denoms THEN (amount MOD denoms[LWB denoms] = 0 | 1 | 0) ELSE INT sum := 0; FOR i FROM 0 BY denoms[LWB denoms] TO amount DO sum +:= ways to make change(denoms[LWB denoms + 1:], amount - i) OD; sum FI END; [] INT denoms = (25, 10, 5, 1); print((ways to make change(denoms, 100), newline))
END </lang>
Output:
+242
AutoHotkey
<lang AHK>countChange(amount){ return cc(amount, 4) }
cc(amount, kindsOfCoins){ if ( amount == 0 ) return 1 if ( amount < 0 ) || ( kindsOfCoins == 0 ) return 0 return cc(amount, kindsOfCoins-1) + cc(amount - firstDenomination(kindsOfCoins), kindsOfCoins) }
firstDenomination(kindsOfCoins){ return [1, 5, 10, 25][kindsOfCoins] } MsgBox % countChange(100)</lang>
AWK
Iterative implementation, derived from Run BASIC:
<lang awk>#!/usr/bin/awk -f
BEGIN {
print cc(100) exit
}
function cc(amount, coins, numPennies, numNickles, numQuarters, p, n, d, q, s, count) {
numPennies = amount numNickles = int(amount / 5) numDimes = int(amount / 10) numQuarters = int(amount / 25) count = 0 for (p = 0; p <= numPennies; p++) { for (n = 0; n <= numNickles; n++) { for (d = 0; d <= numDimes; d++) { for (q = 0; q <= numQuarters; q++) { s = p + n * 5 + d * 10 + q * 25; if (s == 100) count++; } } } } return count;
} </lang>
Run time:
time ./change-itr.awk 242 real 0m0.065s user 0m0.063s sys 0m0.002s
Recursive implementation (derived from Scheme example):
<lang awk>#!/usr/bin/awk -f
BEGIN {
COINSEP = ", " coins = 1 COINSEP 5 COINSEP 10 COINSEP 25 print cc(100, coins) exit
}
function cc(amt, coins) {
if (length(coins) == 0) return 0 if (amt < 0) return 0 if (amt == 0) return 1 return cc(amt, tail(coins)) + cc(amt - head(coins), coins)
}
function tail(coins, koins, s, c) {
split(coins, koins, COINSEP) s = "" for (c = 2; c <= length(koins); c++) s = s (s == "" ? "" : COINSEP) koins[c] return s;
}
function head(coins, koins) {
split(coins, koins, COINSEP) return koins[1]
} </lang>
Run time:
time ./change-rec.awk 242 real 0m0.081s user 0m0.079s sys 0m0.002s
While the recursive version is slower for small amounts, about 2 bucks it gets faster than the iterative version, at least until is segfaults from exhausting the stack.
BBC BASIC
Non-recursive solution: <lang bbcbasic> DIM uscoins%(3)
uscoins%() = 1, 5, 10, 25 PRINT FNchange(100, uscoins%()) " ways of making $1" PRINT FNchange(1000, uscoins%()) " ways of making $10" DIM ukcoins%(7) ukcoins%() = 1, 2, 5, 10, 20, 50, 100, 200 PRINT FNchange(100, ukcoins%()) " ways of making £1" PRINT FNchange(1000, ukcoins%()) " ways of making £10" END DEF FNchange(sum%, coins%()) LOCAL C%, D%, I%, N%, P%, Q%, S%, table() C% = 0 N% = DIM(coins%(),1) + 1 FOR I% = 0 TO N% - 1 D% = coins%(I%) IF D% <= sum% IF D% >= C% C% = D% + 1 NEXT C% *= N% DIM table(C%-1) FOR I% = 0 TO N%-1 : table(I%) = 1 : NEXT P% = N% FOR S% = 1 TO sum% FOR I% = 0 TO N% - 1 IF I% = 0 IF P% >= C% P% = 0 IF coins%(I%) <= S% THEN Q% = P% - coins%(I%) * N% IF Q% >= 0 table(P%) = table(Q%) ELSE table(P%) = table(Q% + C%) ENDIF IF I% table(P%) += table(P% - 1) P% += 1 NEXT NEXT = table(P%-1)
</lang> Output (BBC BASIC does not have large enough integers for the optional task):
242 ways of making $1 142511 ways of making $10 4563 ways of making £1 321335886 ways of making £10
C
Using some crude 128-bit integer type. <lang c>#include <stdio.h>
- include <stdlib.h>
- include <stdint.h>
// ad hoc 128 bit integer type; faster than using GMP because of low // overhead typedef struct { uint64_t x[2]; } i128;
// display in decimal void show(i128 v) { uint32_t x[4] = {v.x[0], v.x[0] >> 32, v.x[1], v.x[1] >> 32}; int i, j = 0, len = 4; char buf[100]; do { uint64_t c = 0; for (i = len; i--; ) { c = (c << 32) + x[i]; x[i] = c / 10, c %= 10; }
buf[j++] = c + '0'; for (len = 4; !x[len - 1]; len--); } while (len);
while (j--) putchar(buf[j]); putchar('\n'); }
i128 count(int sum, int *coins) { int n, i, k; for (n = 0; coins[n]; n++);
i128 **v = malloc(sizeof(int*) * n); int *idx = malloc(sizeof(int) * n);
for (i = 0; i < n; i++) { idx[i] = coins[i]; // each v[i] is a cyclic buffer v[i] = calloc(sizeof(i128), coins[i]); }
v[0][coins[0] - 1] = (i128) Template:1, 0;
for (k = 0; k <= sum; k++) { for (i = 0; i < n; i++) if (!idx[i]--) idx[i] = coins[i] - 1;
i128 c = v[0][ idx[0] ];
for (i = 1; i < n; i++) { i128 *p = v[i] + idx[i];
// 128 bit addition p->x[0] += c.x[0]; p->x[1] += c.x[1]; if (p->x[0] < c.x[0]) // carry p->x[1] ++; c = *p; } }
i128 r = v[n - 1][idx[n-1]];
for (i = 0; i < n; i++) free(v[i]); free(v); free(idx);
return r; }
// simple recursive method; slow int count2(int sum, int *coins) { if (!*coins || sum < 0) return 0; if (!sum) return 1; return count2(sum - *coins, coins) + count2(sum, coins + 1); }
int main(void) { int us_coins[] = { 100, 50, 25, 10, 5, 1, 0 }; int eu_coins[] = { 200, 100, 50, 20, 10, 5, 2, 1, 0 };
show(count( 100, us_coins + 2)); show(count( 1000, us_coins));
show(count( 1000 * 100, us_coins)); show(count( 10000 * 100, us_coins)); show(count(100000 * 100, us_coins));
putchar('\n');
show(count( 1 * 100, eu_coins)); show(count( 1000 * 100, eu_coins)); show(count( 10000 * 100, eu_coins)); show(count(100000 * 100, eu_coins));
return 0; }</lang>output (only the first two lines are required by task):<lang>242 13398445413854501 1333983445341383545001 133339833445334138335450001
4563 10056050940818192726001 99341140660285639188927260001 992198221207406412424859964272600001</lang>
C#
<lang csharp>
// Adapted from http://www.geeksforgeeks.org/dynamic-programming-set-7-coin-change/ class Program { static long Count(int[] C, int m, int n) { var table = new long[n + 1]; table[0] = 1; for (int i = 0; i < m; i++) for (int j = C[i]; j <= n; j++) table[j] += table[j - C[i]]; return table[n]; } static void Main(string[] args) { var C = new int[] { 1, 5, 10, 25 }; int m = C.Length; int n = 100; Console.WriteLine(Count(C, m, n)); //242 Console.ReadLine(); } }
</lang>
Clojure
<lang lisp>(def denomination-kind [1 5 10 25])
(defn- cc [amount denominations]
(cond (= amount 0) 1 (or (< amount 0) (empty? denominations)) 0 :else (+ (cc amount (rest denominations)) (cc (- amount (first denominations)) denominations))))
(defn count-change
"Calculates the number of times you can give change with the given denominations." [amount denominations] (cc amount denominations))
(count-change 15 denomination-kind) ; = 6 </lang>
Coco
<lang coco>changes = (amount, coins) ->
ways = [1].concat [0] * amount for coin of coins for j from coin to amount ways[j] += ways[j - coin] ways[amount]
console.log changes 100, [1 5 10 25]</lang>
Common Lisp
Recursive Version With Cache
<lang lisp>(defun count-change (amount coins
&optional (length (1- (length coins))) (cache (make-array (list (1+ amount) (length coins)) :initial-element nil))) (cond ((< length 0) 0) ((< amount 0) 0) ((= amount 0) 1) (t (or (aref cache amount length) (setf (aref cache amount length) (+ (count-change (- amount (first coins)) coins length cache) (count-change amount (rest coins) (1- length) cache)))))))
- (compile 'count-change) ; for CLISP
(print (count-change 100 '(25 10 5 1))) ; = 242 (print (count-change 100000 '(100 50 25 10 5 1))) ; = 13398445413854501 (terpri)</lang>
Iterative Version
<lang lisp>(defun count-change (amount coins &aux (ways (make-array (1+ amount) :initial-element 0)))
(setf (aref ways 0) 1) (loop for coin in coins do (loop for j from coin upto amount do (incf (aref ways j) (aref ways (- j coin))))) (aref ways amount))</lang>
D
Basic Version
<lang d>import std.stdio, std.bigint;
auto changes(int amount, int[] coins) {
auto ways = new BigInt[amount + 1]; ways[0] = 1; foreach (coin; coins) foreach (j; coin .. amount + 1) ways[j] += ways[j - coin]; return ways[$ - 1];
}
void main() {
changes( 1_00, [25, 10, 5, 1]).writeln; changes(1000_00, [100, 50, 25, 10, 5, 1]).writeln;
}</lang>
- Output:
242 13398445413854501
Safe Ulong Version
This version is very similar to the precedent, but it uses a faster ulong type, and performs a checked sum to detect overflows at run-time. <lang d>import std.stdio, core.checkedint;
auto changes(int amount, int[] coins, ref bool overflow) {
auto ways = new ulong[amount + 1]; ways[0] = 1; foreach (coin; coins) foreach (j; coin .. amount + 1) ways[j] = ways[j].addu(ways[j - coin], overflow); return ways[amount];
}
void main() {
bool overflow = false; changes( 1_00, [25, 10, 5, 1], overflow).writeln; if (overflow) "Overflow".puts; overflow = false; changes( 1000_00, [100, 50, 25, 10, 5, 1], overflow).writeln; if (overflow) "Overflow".puts;
}</lang> The output is the same.
Faster Version
<lang d>import std.stdio, std.bigint;
BigInt countChanges(in int amount, in int[] coins) pure /*nothrow*/ {
immutable n = coins.length; int cycle; foreach (immutable c; coins) if (c <= amount && c >= cycle) cycle = c + 1; cycle *= n; auto table = new BigInt[cycle]; table[0 .. n] = 1.BigInt;
int pos = n; foreach (immutable s; 1 .. amount + 1) { foreach (immutable i; 0 .. n) { if (i == 0 && pos >= cycle) pos = 0; if (coins[i] <= s) { immutable int q = pos - (coins[i] * n); table[pos] = (q >= 0) ? table[q] : table[q + cycle]; } if (i) table[pos] += table[pos - 1]; pos++; } }
return table[pos - 1];
}
void main() {
immutable usCoins = [100, 50, 25, 10, 5, 1]; immutable euCoins = [200, 100, 50, 20, 10, 5, 2, 1];
foreach (immutable coins; [usCoins, euCoins]) { countChanges( 1_00, coins[2 .. $]).writeln; countChanges( 1000_00, coins).writeln; countChanges( 10000_00, coins).writeln; countChanges(100000_00, coins).writeln; writeln; }
}</lang>
- Output:
242 13398445413854501 1333983445341383545001 133339833445334138335450001 4562 10056050940818192726001 99341140660285639188927260001 992198221207406412424859964272600001
128-bit Version
A much faster version that mixes high-level and low-level style programming. This version uses basic 128-bit unsigned integers, like the C version. The output is the same as the second D version.
<lang d>import std.stdio, std.bigint, std.algorithm, std.conv, std.functional;
struct Ucent { /// Simplified 128-bit integer (like ucent).
ulong hi, lo; static immutable one = Ucent(0, 1);
void opOpAssign(string op="+")(in ref Ucent y) pure nothrow @nogc @safe { this.hi += y.hi; if (this.lo >= ~y.lo) this.hi++; this.lo += y.lo; }
string toString() const /*pure nothrow @safe*/ { return text((this.hi.BigInt << 64) + this.lo); }
}
Ucent countChanges(in int amount, in int[] coins) pure nothrow {
immutable n = coins.length;
// Points to a cyclic buffer of length coins[i] auto p = new Ucent*[n]; auto q = new Ucent*[n]; // iterates it. auto buf = new Ucent[coins.sum];
p[0] = buf.ptr; foreach (immutable i; 0 .. n) { if (i) p[i] = coins[i - 1] + p[i - 1]; *p[i] = Ucent.one; q[i] = p[i]; }
Ucent prev; foreach (immutable j; 1 .. amount + 1) foreach (immutable i; 0 .. n) { q[i]--; if (q[i] < p[i]) q[i] = p[i] + coins[i] - 1; if (i) *q[i] += prev; prev = *q[i]; }
return prev;
}
void main() {
immutable usCoins = [100, 50, 25, 10, 5, 1]; immutable euCoins = [200, 100, 50, 20, 10, 5, 2, 1];
foreach (immutable coins; [usCoins, euCoins]) { countChanges( 1_00, coins[2 .. $]).writeln; countChanges( 1000_00, coins).writeln; countChanges( 10000_00, coins).writeln; countChanges(100000_00, coins).writeln; writeln; }
}</lang>
Printing Version
This version prints all the solutions (so it can be used on the smaller input): <lang d>import std.stdio, std.conv, std.string, std.algorithm, std.range;
void printChange(in uint tot, in uint[] coins) in {
assert(coins.isSorted);
} body {
auto freqs = new uint[coins.length];
void inner(in uint curTot, in size_t start) { if (curTot == tot) return writefln("%-(%s %)", zip(coins, freqs) .filter!(cf => cf[1] != 0) .map!(cf => format("%u:%u", cf[])));
foreach (immutable i; start .. coins.length) { immutable ci = coins[i]; for (auto v = (freqs[i] + 1) * ci; v <= tot; v += ci) if (curTot + v <= tot) { freqs[i] += v / ci; inner(curTot + v, i + 1); freqs[i] -= v / ci; } } }
inner(0, 0);
}
void main() {
printChange(1_00, [1, 5, 10, 25]);
}</lang>
- Output:
1:5 5:1 10:4 25:2 1:5 5:1 10:9 1:5 5:2 10:1 25:3 1:5 5:2 10:6 25:1 1:5 5:3 10:3 25:2 1:5 5:3 10:8 1:5 5:4 10:5 25:1 1:5 5:4 25:3 1:5 5:5 10:2 25:2 1:5 5:5 10:7 1:5 5:6 10:4 25:1 1:5 5:7 10:1 25:2 ... 5:11 10:2 25:1 5:12 10:4 5:13 10:1 25:1 5:14 10:3 5:15 25:1 5:16 10:2 5:18 10:1 5:20 10:5 25:2 10:10 25:4
EchoLisp
Recursive solution using memoization, adapted from CommonLisp and Racket. <lang scheme> (lib 'compile) ;; for (compile) (lib 'bigint) ;; integer results > 32 bits (lib 'hash) ;; hash table
- h-table
(define Hcoins (make-hash))
- the function to memoize
(define (sumways cents coins) (+ (ways cents (cdr coins)) (ways (- cents (car coins)) coins)))
- accelerator
- ways (cents, coins) = ways ((cents - cents % 5) , coins)
(define (ways cents coins)
(cond ((null? coins) 0) ((negative? cents) 0) ((zero? cents) 1) ((eq? coins c-1) 1) ;; if coins = (1) --> 1 (else (hash-ref! Hcoins (list (- cents (modulo cents 5)) coins) sumways))))
(compile 'ways) ;; speed-up things </lang>
- Output:
<lang scheme> (define change '(25 10 5 1)) (define c-1 (list-tail change -1)) ;; pointer to (1) (ways 100 change)
→ 242
(define change '(100 50 25 10 5 1)) (define c-1 (list-tail change -1)) (for ((i (in-range 0 200001 20000)))
(writeln i (time (ways i change)) (hash-count Hcoins)))
- iterate cents = 20000, 40000, ..
- cents ((time (msec) number-of-ways) number-of-entries-in-h-table
20000 (350 4371565890901) 9398 40000 (245 138204514221801) 18798 60000 (230 1045248220992701) 28198 80000 (255 4395748062203601) 37598 100000 (234 13398445413854501) 46998 120000 (230 33312577651945401) 56398 140000 (292 71959878152476301) 65798 160000 (736 140236576291447201) 75198 180000 (237 252625397444858101) 84598 200000 (240 427707562988709001) 93998
- One can see that the time is linear, and the h-table size reasonably small
change
→ (100 50 25 10 5 1)
(ways 100000 change)
→ 13398445413854501
</lang>
Elixir
Recursive Dynamic Programming solution in Elixir <lang Elixir>defmodule Coins do
def find(coins,lim) do vals = Enum.into(0..lim,Map.new,&{&1,0}) |> Dict.put(0,1) count(coins,lim,vals) |> Dict.values |> Enum.max |> IO.inspect end defp count([],_,vals), do: vals defp count([coin|coins],lim,vals) do count(coins,lim,ways(coin,coin,lim,vals)) end defp ways(num,_coin,lim,vals) when num > lim, do: vals defp ways(num, coin,lim,vals) do ways(num+1,coin,lim,ad(coin,num,vals)) end defp ad(a,b,c), do: Dict.put(c,b,c[b]+c[b-a])
end
Coins.find([1,5,10,25],100) Coins.find([1,5,10,25,50,100],100_000)</lang>
- Output:
242 13398445413854501
Erlang
<lang erlang> -module(coins). -compile(export_all).
count(Amount, Coins) ->
{N,_C} = count(Amount, Coins, dict:new()), N.
count(0,_,Cache) ->
{1,Cache};
count(N,_,Cache) when N < 0 ->
{0,Cache};
count(_N,[],Cache) ->
{0,Cache};
count(N,[C|Cs]=Coins,Cache) ->
case dict:is_key({N,length(Coins)},Cache) of true -> {dict:fetch({N,length(Coins)},Cache), Cache}; false -> {N1,C1} = count(N-C,Coins,Cache), {N2,C2} = count(N,Cs,C1), {N1+N2,dict:store({N,length(Coins)},N1+N2,C2)} end.
print(Amount, Coins) ->
io:format("~b ways to make change for ~b cents with ~p coins~n",[count(Amount,Coins),Amount,Coins]).
test() ->
A1 = 100, C1 = [25,10,5,1], print(A1,C1), A2 = 100000, C2 = [100, 50, 25, 10, 5, 1], print(A2,C2).
</lang>
- Output:
42> coins:test(). 242 ways to make change for 100 cents with [25,10,5,1] coins 13398445413854501 ways to make change for 100000 cents with [100,50,25,10,5,1] coins ok
Factor
<lang factor>USING: combinators kernel locals math math.ranges sequences sets sorting ; IN: rosetta.coins
<PRIVATE ! recursive-count uses memoization and local variables. ! coins must be a sequence. MEMO:: recursive-count ( cents coins -- ways )
coins length :> types { ! End condition: 1 way to make 0 cents. { [ cents zero? ] [ 1 ] } ! End condition: 0 ways to make money without any coins. { [ types zero? ] [ 0 ] } ! Optimization: At most 1 way to use 1 type of coin. { [ types 1 number= ] [ cents coins first mod zero? [ 1 ] [ 0 ] if ] } ! Find all ways to use the first type of coin. [ ! f = first type, r = other types of coins. coins unclip-slice :> f :> r ! Loop for 0, f, 2*f, 3*f, ..., cents. 0 cents f <range> [ ! Recursively count how many ways to make remaining cents ! with other types of coins. cents swap - r recursive-count ] [ + ] map-reduce ! Sum the counts. ] } cond ;
PRIVATE>
! How many ways can we make the given amount of cents ! with the given set of coins?
- make-change ( cents coins -- ways )
members [ ] inv-sort-with ! Sort coins in descending order. recursive-count ;</lang>
From the listener:
USE: rosetta.coins ( scratchpad ) 100 { 25 10 5 1 } make-change . 242 ( scratchpad ) 100000 { 100 50 25 10 5 1 } make-change . 13398445413854501
This algorithm is slow. A test machine needed 1 minute to run 100000 { 100 50 25 10 5 1 } make-change . and get 13398445413854501. The same machine needed less than 1 second to run the Common Lisp (SBCL), Ruby (MRI) or Tcl (tclsh) programs and get the same answer.
Forth
<lang forth>\ counting change (SICP section 1.2.2)
- table create does> swap cells + @ ;
table coin-value 0 , 1 , 5 , 10 , 25 , 50 ,
- count-change ( total coin -- n )
over 0= if 2drop 1 else over 0< over 0= or if 2drop 0 else 2dup coin-value - over recurse >r 1- recurse r> + then then ;
100 5 count-change .</lang>
Go
A translation of the Lisp code referenced by the task description: <lang go>package main
import "fmt"
func main() {
amount := 100 fmt.Println("amount, ways to make change:", amount, countChange(amount))
}
func countChange(amount int) int64 {
return cc(amount, 4)
}
func cc(amount, kindsOfCoins int) int64 {
switch { case amount == 0: return 1 case amount < 0 || kindsOfCoins == 0: return 0 } return cc(amount, kindsOfCoins-1) + cc(amount - firstDenomination(kindsOfCoins), kindsOfCoins)
}
func firstDenomination(kindsOfCoins int) int {
switch kindsOfCoins { case 1: return 1 case 2: return 5 case 3: return 10 case 4: return 25 } panic(kindsOfCoins)
}</lang> Output:
amount, ways to make change: 100 242
Alternative algorithm, practical for the optional task. <lang go>package main
import "fmt"
func main() {
amount := 1000 * 100 fmt.Println("amount, ways to make change:", amount, countChange(amount))
}
func countChange(amount int) int64 {
ways := make([]int64, amount+1) ways[0] = 1 for _, coin := range []int{100, 50, 25, 10, 5, 1} { for j := coin; j <= amount; j++ { ways[j] += ways[j-coin] } } return ways[amount]
}</lang> Output:
amount, ways to make change: 100000 13398445413854501
Groovy
Intuitive Recursive Solution: <lang groovy>def ccR ccR = { BigInteger tot, List<BigInteger> coins ->
BigInteger n = coins.size() switch ([tot:tot, coins:coins]) { case { it.tot == 0 } : return 1g case { it.tot < 0 || coins == [] } : return 0g default: return ccR(tot, coins[1..<n]) + ccR(tot - coins[0], coins) }
}</lang>
Fast Iterative Solution: <lang groovy>def ccI = { BigInteger tot, List<BigInteger> coins ->
List<BigInteger> ways = [0g] * (tot+1) ways[0] = 1g coins.each { BigInteger coin -> (coin..tot).each { j -> ways[j] += ways[j-coin] } } ways[tot]
}</lang>
Test: <lang groovy>println '\nBase:' [iterative: ccI, recursive: ccR].each { label, cc ->
print "${label} " def start = System.currentTimeMillis() def ways = cc(100g, [25g, 10g, 5g, 1g]) def elapsed = System.currentTimeMillis() - start println ("answer: ${ways} elapsed: ${elapsed}ms")
}
print '\nExtra Credit:\niterative ' def start = System.currentTimeMillis() def ways = ccI(1000g * 100, [100g, 50g, 25g, 10g, 5g, 1g]) def elapsed = System.currentTimeMillis() - start println ("answer: ${ways} elapsed: ${elapsed}ms")</lang>
Output:
Base: iterative answer: 242 elapsed: 5ms recursive answer: 242 elapsed: 220ms Extra Credit: iterative answer: 13398445413854501 elapsed: 1077ms
Haskell
Naive implementation: <lang haskell>count 0 _ = 1 count _ [] = 0 count x (c:coins) = sum [ count (x - (n * c)) coins | n <- [0..(quot x c)] ]
main = print (count 100 [1, 5, 10, 25])</lang>
Much faster, probably harder to read, is to update results from bottom up: <lang haskell>count = foldr addCoin (1:repeat 0) where addCoin c oldlist = newlist where newlist = (take c oldlist) ++ zipWith (+) newlist (drop c oldlist)
main = do print (count [25,10,5,1] !! 100) print (count [100,50,25,10,5,1] !! 100000)</lang>
Icon and Unicon
<lang Icon>procedure main()
US_coins := [1, 5, 10, 25] US_allcoins := [1,5,10,25,50,100] EU_coins := [1, 2, 5, 10, 20, 50, 100, 200] CDN_coins := [1,5,10,25,100,200] CDN_allcoins := [1,5,10,25,50,100,200]
every trans := ![ [15,US_coins], [100,US_coins], [1000*100,US_allcoins] ] do printf("There are %i ways to count change for %i using %s coins.\n",CountCoins!trans,trans[1],ShowList(trans[2]))
end
procedure ShowList(L) # helper list to string every (s := "[ ") ||:= !L || " " return s || "]" end</lang>
This is a naive implementation and very slow.
<lang Icon>procedure CountCoins(amt,coins) # very slow, recurse by coin value local count static S
if type(coins) == "list" then {
S := sort(set(coins)) if *S < 1 then runerr(205,coins) return CountCoins(amt) }
else {
/coins := 1 if value := S[coins] then { every (count := 0) +:= CountCoins(amt - (0 to amt by value), coins + 1) return count } else return (amt ~= 0) | 1 }
end</lang>
printf.icn provides formatting
Output:
There are 6 ways to count change for 15 using [ 1 5 10 25 ] coins. There are 242 ways to count change for 100 using [ 1 5 10 25 ] coins. ^c
Another one: <lang Icon>
- coin.icn
- usage: coin value
procedure count(coinlist, value) if value = 0 then return 1 if value < 0 then return 0 if (*coinlist <= 0) & (value >= 1) then return 0 return count(coinlist[1:*coinlist], value) + count(coinlist, value - coinlist[*coinlist]) end
procedure main(params)
money := params[1]
coins := [1,5,10,25]
writes("Value of ", money, " can be changed by using a set of ") every writes(coins[1 to *coins], " ") write(" coins in ", count(coins, money), " different ways.") end </lang> Output:
Value of 15 can be changed by using a set of 1 5 10 25 coins in 6 different ways. Value of 100 can be changed by using a set of 1 5 10 25 coins in 242 different ways.
J
In this draft intermediate results are a two column array. The first column is tallies -- the number of ways we have for reaching the total represented in the second column, which is unallocated value (which we will assume are pennies). We will have one row for each different in-range value which can be represented using only nickles (0, 5, 10, ... 95, 100).
<lang j>merge=: ({:"1 (+/@:({."1),{:@{:)/. ])@; count=: {.@] <@,. {:@] - [ * [ i.@>:@<.@%~ {:@] init=: (1 ,. ,.)^:(0=#@$) nsplits=: 0 { [: +/ [: (merge@:(count"1) init)/ }.@/:~@~.@,</lang>
This implementation special cases the handling of pennies and assumes that the lowest coin value in the argument is 1. If I needed additional performance, I would next special case the handling of nickles/penny combinations...
Thus:
<lang j> 100 nsplits 1 5 10 25 242</lang>
And, on a 64 bit machine with sufficient memory:
<lang j> 100000 nsplits 1 5 10 25 50 100 13398445413854501</lang>
Java
<lang java5>import java.util.Arrays; import java.math.BigInteger;
class CountTheCoins {
private static BigInteger countChanges(int amount, int[] coins){ final int n = coins.length; int cycle = 0; for (int c : coins) if (c <= amount && c >= cycle) cycle = c + 1; cycle *= n; BigInteger[] table = new BigInteger[cycle]; Arrays.fill(table, 0, n, BigInteger.ONE); Arrays.fill(table, n, cycle, BigInteger.ZERO);
int pos = n; for (int s = 1; s <= amount; s++) { for (int i = 0; i < n; i++) { if (i == 0 && pos >= cycle) pos = 0; if (coins[i] <= s) { final int q = pos - (coins[i] * n); table[pos] = (q >= 0) ? table[q] : table[q + cycle]; } if (i != 0) table[pos] = table[pos].add(table[pos - 1]); pos++; } }
return table[pos - 1]; }
public static void main(String[] args) { final int[][] coinsUsEu = {{100, 50, 25, 10, 5, 1}, {200, 100, 50, 20, 10, 5, 2, 1}};
for (int[] coins : coinsUsEu) { System.out.println(countChanges( 100, Arrays.copyOfRange(coins, 2, coins.length))); System.out.println(countChanges( 100000, coins)); System.out.println(countChanges( 1000000, coins)); System.out.println(countChanges(10000000, coins) + "\n"); } }
}</lang> Output:
242 13398445413854501 1333983445341383545001 133339833445334138335450001 4562 10056050940818192726001 99341140660285639188927260001 992198221207406412424859964272600001
JavaScript
Iterative
Efficient iterative algorithm (cleverly calculates number of combinations without permuting them)
<lang Javascript> function countcoins(t, o) { 'use strict'; var targetsLength = t + 1; var operandsLength = o.length; t = [1];
for (var a = 0; a < operandsLength; a ++) { for (var b = 1; b < targetsLength; b ++) {
// initialise undefined target t[b] = t[b] ? t[b] : 0;
// accumulate target + operand ways t[b] += (b < o[a]) ? 0 : t[b - o[a]]; } }
return t[targetsLength - 1]; } </lang>
- Output:
JavaScript hits integer limit for optional task
<lang JavaScript> countcoins(100, [1,5,10,25]); 242 </lang>
Recursive
Inefficient recursive algorithm (naively calculates number of combinations by actually permuting them)
<lang Javascript> function countcoins(t, o) { 'use strict'; var operandsLength = o.length; var solutions = 0;
function permutate(a, x) {
// base case if (a === t) { solutions ++; }
// recursive case else if (a < t) { for (var i = 0; i < operandsLength; i ++) { if (i >= x) { permutate(o[i] + a, i); } } } }
permutate(0, 0); return solutions; } </lang>
- Output:
Too slow for optional task
<lang JavaScript> countcoins(100, [1,5,10,25]); 242 </lang>
Iterative again
<lang javascript>var amount=100, coin=[1,5,10,25] var t=[1]; for (t[amount]=0, a=1; a<amount; a++) t[a]=0 // initialise t[0..amount]=[1,0,...,0] for (var i=0, e=coin.length; i<e; i++) for (var ci=coin[i], a=ci; a<=amount; a++) t[a] += t[a-ci] document.write( t[amount] )</lang>
- Output:
242
jq
Currently jq uses IEEE 754 64-bit numbers. Large integers are approximated by floats, and therefore the answer that the following program provides for the optional task is only correct for the first 15 digits. <lang jq># How many ways are there to make "target" cents, given a list of coin
- denominations as input.
- The strategy is to record at total[n] the number of ways to make n cents.
def countcoins(target):
. as $coin | reduce range(0; length) as $a ( [1]; # there is 1 way to make 0 cents reduce range(1; target + 1) as $b (.; # total[] if $b < $coin[$a] then . else .[$b - $coin[$a]] as $count | if $count == 0 then . else .[$b] += $count end end ) ) | .[target] ;</lang>
Example:
[1,5,10,25] | countcoins(100)
- Output:
242
Lasso
Inspired by the javascript iterative example for the same task <lang Lasso>define cointcoins( target::integer, operands::array ) => {
local( targetlength = #target + 1, operandlength = #operands -> size, output = staticarray_join(#targetlength,0), outerloopcount )
#output -> get(1) = 1
loop(#operandlength) => { #outerloopcount = loop_count loop(#targetlength) => {
if(loop_count >= #operands -> get(#outerloopcount) and loop_count - #operands -> get(#outerloopcount) > 0) => { #output -> get(loop_count) += #output -> get(loop_count - #operands -> get(#outerloopcount)) } } }
return #output -> get(#targetlength) }
cointcoins(100, array(1,5,10,25,))
'
'
cointcoins(100000, array(1, 5, 10, 25, 50, 100))</lang>
Output:
242 13398445413854501
Lua
Lua uses one-based indexes but table keys can be any value so you can define an element 0 just as easily as you can define an element "foo"... <lang Lua>function zeros (length)
local t = {} for i = 1, length do table.insert(t, 0) end return t
end
function countSums (amount, values)
local t = zeros(amount) t[0] = 1 for k, val in pairs(values) do for i = val, amount do t[i] = t[i] + t[i - val] end end return t[amount]
end
print(countSums(100, {1, 5, 10, 25})) print(countSums(100000, {1, 5, 10, 25, 50, 100}))</lang>
Mathematica / Wolfram Language
<lang Mathematica>CountCoins[amount_, coinlist_] := ( ways = ConstantArray[1, amount]; Do[For[j = coin, j <= amount, j++,
If[ j - coin == 0, waysj ++, waysj += waysj - coin
]] , {coin, coinlist}]; waysamount)</lang> Example usage:
CountCoins[100, {25, 10, 5}] -> 242 CountCoins[100000, {100, 50, 25, 10, 5}] -> 13398445413854501
MATLAB / Octave
<lang Matlab> %% Count_The_Coins clear;close all;clc; tic
for i = 1:2 % 1st loop is main challenge 2nd loop is optional challenge
if (i == 1) amount = 100; % Matlab indexes from 1 not 0, so we need to add 1 to our target value amount = amount + 1; coins = [1 5 10 25]; % Value of coins we can use else amount = 100*1000; % Matlab indexes from 1 not 0, so we need to add 1 to our target value amount = amount + 1; coins = [1 5 10 25 50 100]; % Value of coins we can use end % End if ways = zeros(1,amount); % Preallocating for speed ways(1) = 1; % First solution is 1 % Solves from smallest sub problem to largest (bottom up approach of dynamic programming). for j = 1:length(coins) for K = coins(j)+1:amount ways(K) = ways(K) + ways(K-coins(j)); end % End for end % End for if (i == 1) fprintf(‘Main Challenge: %d \n', ways(amount)); else fprintf(‘Bonus Challenge: %d \n', ways(amount)); end % End if
end % End for toc </lang> Example Output:
Main Challenge: 242 Bonus Challenge: 13398445413854501
Mercury
<lang Mercury>:- module coins.
- - interface.
- - import_module int, io.
- - type coin ---> quarter; dime; nickel; penny.
- - type purse ---> purse(int, int, int, int).
- - pred sum_to(int::in, purse::out) is nondet.
- - pred main(io::di, io::uo) is det.
- - implementation.
- - import_module solutions, list, string.
- - func value(coin) = int.
value(quarter) = 25. value(dime) = 10. value(nickel) = 5. value(penny) = 1.
- - pred supply(coin::in, int::in, int::out) is multi.
supply(C, Target, N) :- upto(Target div value(C), N).
- - pred upto(int::in, int::out) is multi.
upto(N, R) :- ( nondet_int_in_range(0, N, R0) -> R = R0 ; R = 0 ).
sum_to(To, Purse) :- Purse = purse(Q, D, N, P), sum(Purse) = To, supply(quarter, To, Q), supply(dime, To, D), supply(nickel, To, N), supply(penny, To, P).
- - func sum(purse) = int.
sum(purse(Q, D, N, P)) = value(quarter) * Q + value(dime) * D + value(nickel) * N + value(penny) * P.
main(!IO) :- solutions(sum_to(100), L), show(L, !IO), io.format("There are %d ways to make change for a dollar.\n",
[i(length(L))], !IO).
- - pred show(list(purse)::in, io::di, io::uo) is det.
show([], !IO). show([P|T], !IO) :- io.write(P, !IO), io.nl(!IO), show(T, !IO).</lang>
Nim
<lang nim>proc changes(amount, coins): int =
var ways = @[1] ways.setLen(amount+1) for coin in coins: for j in coin..amount: ways[j] += ways[j-coin] ways[amount]
echo changes(100, [1, 5, 10, 25]) echo changes(100000, [1, 5, 10, 25, 50, 100])</lang> Output:
242 13398445413854501
OCaml
Translation of the D minimal version:
<lang ocaml>let changes amount coins =
let ways = Array.make (amount + 1) 0L in ways.(0) <- 1L; List.iter (fun coin -> for j = coin to amount do ways.(j) <- Int64.add ways.(j) ways.(j - coin) done ) coins; ways.(amount)
let () =
Printf.printf "%Ld\n" (changes 1_00 [25; 10; 5; 1]); Printf.printf "%Ld\n" (changes 1000_00 [100; 50; 25; 10; 5; 1]);
- </lang>
Output:
$ ocaml coins.ml 242 13398445413854501
PARI/GP
<lang parigp>coins(v)=prod(i=1,#v,1/(1-'x^v[i])); ways(v,n)=polcoeff(coins(v)+O('x^(n+1)),n); ways([1,5,10,25],100) ways([1,5,10,25,50,100],100000)</lang> Output:
%1 = 242 %2 = 13398445413854501
Perl
<lang perl>use 5.01; use Memoize;
sub cc {
my $amount = shift; return 0 if !@_ || $amount < 0; return 1 if $amount == 0; my $first = shift; cc( $amount, @_ ) + cc( $amount - $first, $first, @_ );
} memoize 'cc';
- Make recursive algorithm run faster by sorting coins descending by value:
sub cc_optimized {
my $amount = shift; cc( $amount, sort { $b <=> $a } @_ );
}
say 'Ways to change $ 1 with common coins: ',
cc_optimized( 100, 1, 5, 10, 25 );
say 'Ways to change $ 1000 with addition of less common coins: ',
cc_optimized( 1000 * 100, 1, 5, 10, 25, 50, 100 );
</lang>
- Output:
Ways to change $ 1 with common coins: 242 Ways to change $ 1000 with addition of less common coins: 13398445413854501
Perl 6
Recursive (cached)
<lang perl6>sub ways-to-make-change($amount, @coins) {
my @cache = $[1 xx @coins]; multi ways($n where $n >= 0, @now [$coin,*@later]) { @cache[$n][+@later] //= ways($n - $coin, @now) + ways($n, @later); } multi ways($,@) { 0 } ways($amount, @coins.sort(-*).list); # sort descending
}
say ways-to-make-change 1_00, [1,5,10,25]; say ways-to-make-change 1000_00, [1,5,10,25,50,100];</lang>
- Output:
242 13398445413854501
Iterative
<lang perl6>sub ways-to-make-change-slowly(\n, @coins) {
my @table = [1 xx @coins], [0 xx @coins] xx n; for 1..n X ^@coins -> (\i, \j) { my \c = @coins[j]; @table[i][j] = [+] @table[i - c][j ] // 0, @table[i ][j - 1] // 0; } @table[*-1][*-1];
}
say ways-to-make-change-slowly 1_00, [1,5,10,25]; say ways-to-make-change-slowly 1000_00, [1,5,10,25,50,100];</lang>
PicoLisp
<lang PicoLisp>(de coins (Sum Coins)
(let (Buf (mapcar '((N) (cons 1 (need (dec N) 0))) Coins) Prev) (do Sum (zero Prev) (for L Buf (inc (rot L) Prev) (setq Prev (car L)) ) ) Prev ) )</lang>
Test: <lang PicoLisp>(for Coins '((100 50 25 10 5 1) (200 100 50 20 10 5 2 1))
(println (coins 100 (cddr Coins))) (println (coins (* 1000 100) Coins)) (println (coins (* 10000 100) Coins)) (println (coins (* 100000 100) Coins)) (prinl) )</lang>
Output:
242 13398445413854501 1333983445341383545001 133339833445334138335450001 4562 10056050940818192726001 99341140660285639188927260001 992198221207406412424859964272600001
Python
Simple version
<lang python>def changes(amount, coins):
ways = [0] * (amount + 1) ways[0] = 1 for coin in coins: for j in xrange(coin, amount + 1): ways[j] += ways[j - coin] return ways[amount]
print changes(100, [1, 5, 10, 25]) print changes(100000, [1, 5, 10, 25, 50, 100])</lang> Output:
242 13398445413854501
Fast version
<lang python>try:
import psyco psyco.full()
except ImportError:
pass
def count_changes(amount_cents, coins):
n = len(coins) # max([]) instead of max() for Psyco cycle = max([c+1 for c in coins if c <= amount_cents]) * n table = [0] * cycle for i in xrange(n): table[i] = 1
pos = n for s in xrange(1, amount_cents + 1): for i in xrange(n): if i == 0 and pos >= cycle: pos = 0 if coins[i] <= s: q = pos - coins[i] * n table[pos]= table[q] if (q >= 0) else table[q + cycle] if i: table[pos] += table[pos - 1] pos += 1 return table[pos - 1]
def main():
us_coins = [100, 50, 25, 10, 5, 1] eu_coins = [200, 100, 50, 20, 10, 5, 2, 1]
for coins in (us_coins, eu_coins): print count_changes( 100, coins[2:]) print count_changes( 100000, coins) print count_changes( 1000000, coins) print count_changes(10000000, coins), "\n"
main()</lang> Output:
242 13398445413854501 1333983445341383545001 133339833445334138335450001 4562 10056050940818192726001 99341140660285639188927260001 992198221207406412424859964272600001
Racket
This is the basic recursive way: <lang Racket>#lang racket (define (ways-to-make-change cents coins)
(cond ((null? coins) 0) ((negative? cents) 0) ((zero? cents) 1) (else (+ (ways-to-make-change cents (cdr coins)) (ways-to-make-change (- cents (car coins)) coins)))))
(ways-to-make-change 100 '(25 10 5 1)) ; -> 242 </lang> This works for the small numbers, but the optional task is just too slow with this solution, so with little change to the code we can use memoization: <lang Racket>#lang racket
(define memos (make-hash)) (define (ways-to-make-change cents coins)
(cond [(or (empty? coins) (negative? cents)) 0] [(zero? cents) 1] [else (define (answerer-for-new-arguments) (+ (ways-to-make-change cents (rest coins)) (ways-to-make-change (- cents (first coins)) coins))) (hash-ref! memos (cons cents coins) answerer-for-new-arguments)]))
(time (ways-to-make-change 100 '(25 10 5 1))) (time (ways-to-make-change 100000 '(100 50 25 10 5 1))) (time (ways-to-make-change 1000000 '(200 100 50 20 10 5 2 1)))
- | Times in milliseconds, and results:
cpu time: 1 real time: 1 gc time: 0 242
cpu time: 524 real time: 553 gc time: 163 13398445413854501
cpu time: 20223 real time: 20673 gc time: 10233 99341140660285639188927260001 |#</lang>
REXX
recursive
The recursive calls to the subroutine have been unrolled somewhat, this reduces the number of recursive calls substantially.
These REXX versions also support fractional cents (as in a ½-cent and ¼-cent coins). Any fractional coin can be
specified as a decimal fraction (.5, .25, ···).
Support was included to allow specification of half-cent and quarter-cent coins as 1/2 and 1/4.
The amount can be specified in cents (as a number), or in dollars (as for instance, $1000). <lang rexx>/*REXX program counts the number of ways to make change with coins from an given amount.*/ numeric digits 20 /*be able to handle large amounts of $.*/ parse arg N $ /*obtain optional arguments from the CL*/ if N= | N="," then N=100 /*Not specified? Then Use $1 (≡100¢).*/ if $= | $="," then $=1 5 10 25 /*Use penny/nickel/dime/quarter default*/ if left(N,1)=='$' then N=100*substr(N,2) /*the amount was specified in dollars.*/ coins=words($) /*the number of coins specified. */ NN=N; do j=1 for coins /*create a fast way of accessing specie*/
_=word($,j) /*define an array element for the coin.*/ if _=='1/2' then _=.5 /*an alternate spelling of a half-cent.*/ if _=='1/4' then _=.25 /* " " " " " quarter-¢.*/ $.j=_ /*assign the value to a particular coin*/ end /*j*/
_=n//100; cnt=' cents' /* [↓] is the amount in whole dollars?*/ if _=0 then do; NN='$' || (NN%100); cnt=; end /*show the amount in dollars, not cents*/ say 'with an amount of ' commas(NN)cnt", there are " commas( MKchg(N, coins) ) say 'ways to make change with coins of the following denominations: ' $ exit /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ commas: procedure; parse arg _; n=_'.9'; #=123456789; b=verify(n,#,"M")
e=verify(n,#'0',,verify(n,#"0.",'M'))-4 do j=e to b by -3; _=insert(',',_,j); end /*j*/; return _
/*──────────────────────────────────────────────────────────────────────────────────────*/ MKchg: procedure expose $.; parse arg a,k /*this function is invoked recursively.*/
if a==0 then return 1 /*unroll for a special case of zero. */ if k==1 then return 1 /* " " " " " " unity. */ if k==2 then f=1 /*handle this special case of two. */ else f=MKchg(a, k-1) /*count, and then recurse the amount. */ if a==$.k then return f+1 /*handle this special case of A=a coin.*/ if a <$.k then return f /* " " " " " A<a coin.*/ return f+MKchg(a-$.k,k) /*use diminished amount ($) for change.*/</lang>
output when using the default input:
with an amount of $1, there are 242 ways to make change with coins of the following denominations: 1 5 10 25
output when using the following input: $1 1/4 1/2 1 2 3 5 10 20 25 50 100
with an amount of $1, there are 29,034,171 ways to make change with coins of the following denominations: 1/4 1/2 1 2 3 5 10 20 25 50 100
with memoization
This REXX version is more than a couple of orders of magnitude faster than the 1st version when using larger amounts. <lang rexx>/*REXX program counts the number of ways to make change with coins from an given amount.*/ numeric digits 20 /*be able to handle large amounts of $.*/ parse arg N $ /*obtain optional arguments from the CL*/ if N= | N="," then N=100 /*Not specified? Then Use $1 (≡100¢).*/ if $= | $="," then $=1 5 10 25 /*Use penny/nickel/dime/quarter default*/ if left(N,1)=='$' then N=100*substr(N,2) /*the amount was specified in dollars.*/ coins=words($) /*the number of coins specified. */ !.=.; NN=N; do j=1 for coins /*create a fast way of accessing specie*/
_=word($,j); ?=_ ' coin' /*define an array element for the coin.*/ if _=='1/2' then _=.5 /*an alternate spelling of a half-cent.*/ if _=='1/4' then _=.25 /* " " " " " quarter-¢.*/ $.j=_ /*assign the value to a particular coin*/ end /*j*/
_=n//100; cnt=' cents' /* [↓] is the amount in whole dollars?*/ if _=0 then do; NN='$' || (NN%100); cnt=; end /*show the amount in dollars, not cents*/ say 'with an amount of ' commas(NN)cnt", there are " commas( MKchg(N, coins) ) say 'ways to make change with coins of the following denominations: ' $ exit /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ commas: procedure; parse arg _; n=_'.9'; #=123456789; b=verify(n,#,"M")
e=verify(n,#'0',,verify(n,#"0.",'M'))-4 do j=e to b by -3; _=insert(',',_,j); end /*j*/; return _
/*──────────────────────────────────────────────────────────────────────────────────────*/ MKchg: procedure expose $. !.; parse arg a,k /*function is recursive. */
if !.a.k\==. then return !.a.k /*found this A & K before? */ if a==0 then return 1 /*unroll for a special case*/ if k==1 then return 1 /* " " " " " */ if k==2 then f=1 /*handle this special case.*/ else f=MKchg(a, k-1) /*count, recurse the amount*/ if a==$.k then do; !.a.k=f+1; return !.a.k; end /*handle this special case.*/ if a <$.k then do; !.a.k=f ; return f ; end /* " " " " */ !.a.k=f + MKchg(a-$.k, k); return !.a.k /*compute, define, return. */</lang>
output when using the following input for the optional test case: $1000 1 5 10 25 50 100
with an amount of $1,000, there are 13,398,445,413,854,501 ways to make change with coins of the following denominations: 1 5 10 25 50 100
with error checking
This REXX version is identical to the previous REXX version, but has error checking for the amount and the coins specified. <lang rexx>/*REXX program counts the number of ways to make change with coins from an given amount.*/ numeric digits 20 /*be able to handle large amounts of $.*/ parse arg N $ /*obtain optional arguments from the CL*/ if N= | N="," then N=100 /*Not specified? Then Use $1 (≡100¢).*/ if $= | $="," then $=1 5 10 25 /*Use penny/nickel/dime/quarter default*/ X=N /*save original for possible error msgs*/ if left(N,1)=='$' then do /*the amount has a leading dollar sign.*/
_=substr(N,2) /*the amount was specified in dollars.*/ if \isNum(_) then call ser "amount isn't numeric: " N N=100*_ /*change amount (in $) ───► cents (¢).*/ end
max$=10**digits() /*the maximum amount this pgm can have.*/ if \isNum(N) then call ser X " amount isn't numeric." if N=0 then call ser X " amount can't be zero." if N<0 then call ser X " amount can't be negative." if N>max$ then call ser X " amount can't be greater than " max$'.' coins=words($); !.=.; NN=N; p=0 /*#coins specified; coins; amount; prev*/ @.=0 /*verify a coin was only specified once*/
do j=1 for coins /*create a fast way of accessing specie*/ _=word($,j); ?=_ ' coin' /*define an array element for the coin.*/ if _=='1/2' then _=.5 /*an alternate spelling of a half-cent.*/ if _=='1/4' then _=.25 /* " " " " " quarter-¢.*/ if \isNum(_) then call ser ? "coin value isn't numeric." if _<0 then call ser ? "coin value can't be negative." if _<=0 then call ser ? "coin value can't be zero." if @._ then call ser ? "coin was already specified."
if _
N then call ser ? "coin must be less or equal to amount:" X
@._=1; p=_ /*signify coin was specified; set prev.*/
$.j=_ /*assign the value to a particular coin*/
end /*j*/
_=n//100; cnt=' cents' /* [↓] is the amount in whole dollars?*/
if _=0 then do; NN='$' || (NN%100); cnt=; end /*show the amount in dollars, not cents*/
say 'with an amount of ' commas(NN)cnt", there are " commas( MKchg(N, coins) )
say 'ways to make change with coins of the following denominations: ' $
exit /*stick a fork in it, we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
isNum: return datatype(arg(1), 'N') /*return 1 if arg is numeric, 0 if not.*/
ser: say; say '***error***'; say; say arg(1); say; exit 13 /*error msg.*/
/*──────────────────────────────────────────────────────────────────────────────────────*/
commas: procedure; parse arg _; n=_'.9'; #=123456789; b=verify(n,#,"M")
e=verify(n,#'0',,verify(n,#"0.",'M'))-4
do j=e to b by -3; _=insert(',',_,j); end /*j*/; return _
/*──────────────────────────────────────────────────────────────────────────────────────*/
MKchg: procedure expose $. !.; parse arg a,k /*function is recursive. */
if !.a.k\==. then return !.a.k /*found this A & K before? */
if a==0 then return 1 /*unroll for a special case*/
if k==1 then return 1 /* " " " " " */
if k==2 then f=1 /*handle this special case.*/
else f=MKchg(a, k-1) /*count, recurse the amount*/
if a==$.k then do; !.a.k=f+1; return !.a.k; end /*handle this special case.*/
if a <$.k then do; !.a.k=f ; return f ; end /* " " " " */
!.a.k=f + MKchg(a-$.k, k); return !.a.k /*compute, define, return. */</lang>
output is the same as the previous REXX versions.
Ruby
The algorithm also appears here
Recursive, with caching
<lang ruby>def make_change(amount, coins)
@cache = Array.new(amount+1){|i| Array.new(coins.size, i.zero? ? 1 : nil)} @coins = coins do_count(amount, @coins.length - 1)
end
def do_count(n, m)
if n < 0 || m < 0 0 elsif @cache[n][m] @cache[n][m] else @cache[n][m] = do_count(n-@coins[m], m) + do_count(n, m-1) end
end
p make_change( 1_00, [1,5,10,25]) p make_change(1000_00, [1,5,10,25,50,100])</lang>
outputs
242 13398445413854501
Iterative
<lang ruby>def make_change2(amount, coins)
n, m = amount, coins.size table = Array.new(n+1){|i| Array.new(m, i.zero? ? 1 : nil)} for i in 1..n for j in 0...m table[i][j] = (i<coins[j] ? 0 : table[i-coins[j]][j]) + (j<1 ? 0 : table[i][j-1]) end end table[-1][-1]
end
p make_change2( 1_00, [1,5,10,25]) p make_change2(1000_00, [1,5,10,25,50,100])</lang> outputs
242 13398445413854501
Run BASIC
<lang runbasic>for penny = 0 to 100
for nickel = 0 to 20 for dime = 0 to 10 for quarter = 0 to 4 if penny + nickel * 5 + dime * 10 + quarter * 25 = 100 then print penny;" pennies ";nickel;" nickels "; dime;" dimes ";quarter;" quarters" count = count + 1 end if next quarter next dime next nickel
next penny print count;" ways to make a buck"</lang>Output:
0 pennies 0 nickels 0 dimes 4 quarters 0 pennies 0 nickels 5 dimes 2 quarters 0 pennies 0 nickels 10 dimes 0 quarters 0 pennies 1 nickels 2 dimes 3 quarters ...... 65 pennies 5 nickels 1 dimes 0 quarters 65 pennies 7 nickels 0 dimes 0 quarters 70 pennies 0 nickels 3 dimes 0 quarters 70 pennies 1 nickels 0 dimes 1 quarters ..... 242 ways to make a buck
Scala
<lang scala>def countChange(amount: Int, coins:List[Int]) = { val ways = Array.fill(amount + 1)(0) ways(0) = 1 coins.foreach (coin => for (j<-coin to amount) ways(j) = ways(j) + ways(j - coin) ) ways(amount)
}
countChange (15, List(1, 5, 10, 25)) </lang> Output:
res0: Int = 6
Recursive implementation: <lang scala>def count(target: Int, coins: List[Int]): Int = {
if (target == 0) 1 else if (coins.isEmpty || target < 0) 0 else count(target, coins.tail) + count(target - coins.head, coins)
}
count(100, List(25, 10, 5, 1))
</lang>
Scheme
A simple recursive implementation: <lang scheme>(define ways-to-make-change
(lambda (x coins) (cond [(null? coins) 0] [(< x 0) 0] [(zero? x) 1] [else (+ (ways-to-make-change x (cdr coins)) (ways-to-make-change (- x (car coins)) coins))])))
(ways-to-make-change 100)</lang> Output:
242
Seed7
<lang seed7>$ include "seed7_05.s7i";
include "bigint.s7i";
const func bigInteger: changeCount (in integer: amountCents, in array integer: coins) is func
result var bigInteger: waysToChange is 0_; local var array bigInteger: t is 0 times 0_; var integer: pos is 0; var integer: s is 0; var integer: i is 0; begin t := length(coins) times 1_ & (length(coins) * amountCents) times 0_; pos := length(coins) + 1; for s range 1 to amountCents do if coins[1] <= s then t[pos] := t[pos - (length(coins) * coins[1])]; end if; incr(pos); for i range 2 to length(coins) do if coins[i] <= s then t[pos] := t[pos - (length(coins) * coins[i])]; end if; t[pos] +:= t[pos - 1]; incr(pos); end for; end for; waysToChange := t[pos - 1]; end func;
const proc: main is func
local const array integer: usCoins is [] (1, 5, 10, 25, 50, 100); const array integer: euCoins is [] (1, 2, 5, 10, 20, 50, 100, 200); begin writeln(changeCount( 100, usCoins[.. 4])); writeln(changeCount( 100000, usCoins)); writeln(changeCount(1000000, usCoins)); writeln(changeCount( 100000, euCoins)); writeln(changeCount(1000000, euCoins)); end func;</lang>
Output:
242 13398445413854501 1333983445341383545001 10056050940818192726001 99341140660285639188927260001
Sidef
<lang ruby>func cc(_) { 0 } func cc({ .is_neg }, *_) { 0 } func cc({ .is_zero }, *_) { 1 }
func cc(amount, first, *rest) is cached {
cc(amount, rest...) + cc(amount - first, first, rest...);
}
func cc_optimized(amount, *rest) {
cc(amount, rest.sort_by{|v| -v }...);
}
var x = cc_optimized(100, 1, 5, 10, 25); say "Ways to change $1 with common coins: #{x}";
var y = cc_optimized(1000 * 100, 1, 5, 10, 25, 50, 100); say "Ways to change $1000 with addition of less common coins: #{y}";</lang>
- Output:
Ways to change $1 with common coins: 242 Ways to change $1000 with addition of less common coins: 13398445413854501
Tcl
<lang tcl>package require Tcl 8.5
proc makeChange {amount coins} {
set table [lrepeat [expr {$amount+1}] [lrepeat [llength $coins] {}]] lset table 0 [lrepeat [llength $coins] 1] for {set i 1} {$i <= $amount} {incr i} {
for {set j 0} {$j < [llength $coins]} {incr j} { set k [expr {$i - [lindex $coins $j]}] lset table $i $j [expr { ($k < 0 ? 0 : [lindex $table $k $j]) + ($j < 1 ? 0 : [lindex $table $i [expr {$j-1}]]) }] }
} return [lindex $table end end]
}
puts [makeChange 100 {1 5 10 25}] puts [makeChange 100000 {1 5 10 25 50 100}]
- Making change with the EU coin set:
puts [makeChange 100 {1 2 5 10 20 50 100 200}] puts [makeChange 100000 {1 2 5 10 20 50 100 200}]</lang> Output:
242 13398445413854501 4563 10056050940818192726001
uBasic/4tH
<lang>c = 0 for p = 0 to 100
for n = 0 to 20 for d = 0 to 10 for q = 0 to 4 if p + n * 5 + d * 10 + q * 25 = 100 then print p;" pennies ";n;" nickels "; d;" dimes ";q;" quarters" c = c + 1 endif next q next d next n
next p print c;" ways to make a buck"</lang>
- Output:
0 pennies 0 nickels 0 dimes 4 quarters 0 pennies 0 nickels 5 dimes 2 quarters 0 pennies 0 nickels 10 dimes 0 quarters ... 90 pennies 2 nickels 0 dimes 0 quarters 95 pennies 1 nickels 0 dimes 0 quarters 100 pennies 0 nickels 0 dimes 0 quarters 242 ways to make a buck 0 OK, 0:312
UNIX Shell
<lang bash>function count_change {
local -i amount=$1 coin j local ways=(1) shift for coin; do for (( j=coin; j <= amount; j++ )); do let ways[j]=${ways[j]:-0}+${ways[j-coin]:-0} done done echo "${ways[amount]}"
} count_change 100 25 10 5 1 count_change 100000 100 50 25 10 5 1</lang>
<lang bash>function count_change {
typeset -i amount=$1 coin j typeset ways set -A ways 1 shift for coin; do for (( j=coin; j <= amount; j++ )); do let ways[j]=${ways[j]:-0}+${ways[j-coin]:-0} done done echo "${ways[amount]}"
} count_change 100 25 10 5 1 count_change 100000 100 50 25 10 5 1</lang>
<lang bash>function count_change {
typeset -i amount=$1 coin j typeset ways set -A ways 1 shift for coin; do let j=coin while (( j <= amount )); do let ways[j]=${ways[j]:-0}+${ways[j-coin]:-0} let j+=1 done done echo "${ways[amount]}"
} count_change 100 25 10 5 1
- (optional task exceeds a subscript limit in ksh88)</lang>
And just for fun, here's one that works even with the original V7 shell:
<lang bash>if [ $# -lt 2 ]; then
set ${1-100} 25 10 5 1
fi amount=$1 shift ways_0=1 for coin in "$@"; do
j=$coin while [ $j -le $amount ]; do d=`expr $j - $coin` eval "ways_$j=\`expr \${ways_$j-0} + \${ways_$d-0}\`" j=`expr $j + 1` done
done eval "echo \$ways_$amount"</lang>
- Output:
242 13398445413854501
VBScript
<lang vb> Function count(coins,m,n) ReDim table(n+1) table(0) = 1 i = 0 Do While i < m j = coins(i) Do While j <= n table(j) = table(j) + table(j - coins(i)) j = j + 1 Loop i = i + 1 Loop count = table(n) End Function
'testing arr = Array(1,5,10,25) m = UBound(arr) + 1 n = 100 WScript.StdOut.WriteLine count(arr,m,n) </lang>
- Output:
242
zkl
<lang zkl>fcn ways_to_make_change(x, coins=T(25,10,5,1)){
if(not coins) return(0); if(x<0) return(0); if(x==0) return(1); ways_to_make_change(x, coins[1,*]) + ways_to_make_change(x - coins[0], coins)
} ways_to_make_change(100).println();</lang>
- Output:
242
Blows the stack on the optional part, so try this:
<lang zkl>fcn make_change2(amount, coins){
n, m := amount, coins.len(); table := (0).pump(n+1,List, (0).pump(m,List().write,1).copy); foreach i,j in ([1..n],[0..m-1]){ table[i][j] = (if(i<coins[j]) 0 else table[i-coins[j]][j]) + (if(j<1) 0 else table[i][j-1]) } table[-1][-1]
}
println(make_change2( 100, T(1,5,10,25))); make_change2(0d1000_00, T(1,5,10,25,50,100)) : "%,d".fmt(_).println();</lang>
- Output:
242 13,398,445,413,854,501
- Programming Tasks
- Solutions by Programming Task
- 360 Assembly
- Ada
- ALGOL 68
- AutoHotkey
- AWK
- BBC BASIC
- C
- C sharp
- Clojure
- Coco
- Common Lisp
- D
- EchoLisp
- Elixir
- Erlang
- Factor
- Forth
- Go
- Groovy
- Haskell
- Icon
- Unicon
- Icon examples needing attention
- Examples needing attention
- Icon Programming Library
- J
- Java
- JavaScript
- Jq
- Lasso
- Lua
- Mathematica
- Wolfram Language
- MATLAB
- Octave
- Mercury
- Nim
- OCaml
- PARI/GP
- Perl
- Perl 6
- PicoLisp
- Python
- Racket
- REXX
- Ruby
- Run BASIC
- Scala
- Scheme
- Seed7
- Sidef
- Tcl
- UBasic/4tH
- UNIX Shell
- VBScript
- Zkl