Count the coins
From Rosetta Code
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.
[edit] Ada
with Ada.Text_IO;Output:
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;
242 13398445413854501
[edit] AutoHotkey
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)
[edit] AWK
Iterative implementation, derived from Run BASIC:
#!/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;
}
Run time:
time ./change-itr.awk 242 real 0m0.065s user 0m0.063s sys 0m0.002s
Recursive implementation (derived from Scheme example):
#!/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]
}
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.
[edit] BBC BASIC
Non-recursive solution:
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)
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
[edit] C
Using some crude 128-bit integer type.
#include <stdio.h>output (only the first two lines are required by task):
#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) {{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;
}
242
13398445413854501
1333983445341383545001
133339833445334138335450001
4563
10056050940818192726001
99341140660285639188927260001
992198221207406412424859964272600001
[edit] Common Lisp
(defun count-change (amount coins)
(let ((cache (make-array (list (1+ amount) (length coins))
:initial-element nil)))
(macrolet ((h () `(aref cache n l)))
(labels
((recur (n coins &optional (l (1- (length coins))))
(cond ((< l 0) 0)
((< n 0) 0)
((= n 0) 1)
(t (if (h) (h) ; cached
(setf (h) ; or not
(+ (recur (- n (car coins)) coins l)
(recur n (cdr coins) (1- l)))))))))
;; enable next line if recursions too deep
;(loop for i from 0 below amount do (recur i coins))
(recur amount coins)))))
; (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)
[edit] D
[edit] Minimal version
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[amount];
}
void main() {
writeln(changes( 1_00, [25, 10, 5, 1]));
writeln(changes(1000_00, [100, 50, 25, 10, 5, 1]));
}
Output:
242 13398445413854501
[edit] Faster version
import std.stdio, std.bigint;
BigInt countChanges(in int amount, in int[] coins)/*pure nothrow*/ {
immutable size_t n = coins.length;
int cycle;
foreach (const c; coins)
if (c <= amount && c >= cycle)
cycle = c + 1;
cycle *= n;
auto table = new BigInt[cycle];
table[0 .. n] = BigInt(1);
int pos = n;
foreach (s; 1 .. amount + 1) {
foreach (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 (coins; [usCoins, euCoins]) {
writeln(countChanges( 1_00, coins[2 .. $]));
writeln(countChanges( 1000_00, coins));
writeln(countChanges( 10000_00, coins));
writeln(countChanges(100000_00, coins), "\n");
}
}
- Output:
242 13398445413854501 1333983445341383545001 133339833445334138335450001 4562 10056050940818192726001 99341140660285639188927260001 992198221207406412424859964272600001
[edit] 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.
import std.stdio, std.bigint, std.algorithm, std.conv;
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 {
this.hi += y.hi;
if (this.lo >= ~y.lo)
this.hi++;
this.lo += y.lo;
}
const string toString() const {
return text((BigInt(this.hi) << 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]).ptr;
auto q = (new Ucent*[n]).ptr; // iterates it.
//auto buf = new Ucent[sum(coins)];
auto buf = new Ucent[reduce!q{ a + b }(0, coins)]; // not nothrow
p[0] = buf.ptr;
foreach (i; 0 .. n) {
if (i)
p[i] = coins[i - 1] + p[i - 1];
*p[i] = Ucent.one;
q[i] = p[i];
}
Ucent prev;
foreach (j; 1 .. amount + 1)
foreach (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 (coins; [usCoins, euCoins]) {
writeln(countChanges( 1_00, coins[2 .. $]));
writeln(countChanges( 1000_00, coins));
writeln(countChanges( 10000_00, coins));
writeln(countChanges(100000_00, coins), "\n");
}
}
[edit] 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).
- 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
[edit] 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 ;
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.
[edit] 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 .
[edit] Go
A translation of the Lisp code referenced by the task description:
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)
}
Output:
amount, ways to make change: 100 242
Alternative algorithm, practical for the optional task.
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]
}
Output:
amount, ways to make change: 100000 13398445413854501
[edit] Groovy
Intuitive Recursive Solution:
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)
}
}
Fast Iterative Solution:
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]
}
Test:
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")
Output:
Base: iterative answer: 242 elapsed: 5ms recursive answer: 242 elapsed: 220ms Extra Credit: iterative answer: 13398445413854501 elapsed: 1077ms
[edit] Haskell
Naive implementation:
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])
Much faster, probably harder to read, is to update results from bottom up:
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)
[edit] Icon and Unicon
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
This is a naive implementation and very slow.
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
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
[edit] 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).
merge=: ({:"1 (+/@:({."1),{:@{:)/. ])@;
count=: {.@] <@,. {:@] - [ * [ i.@>:@<.@%~ {:@]
init=: (1 ,. ,.)^:(0=#@$)
nsplits=: 0 { [: +/ [: (merge@:(count"1) init)/ }.@/:~@~.@,
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:
100 nsplits 1 5 10 25
242
And, on a 64 bit machine with sufficient memory:
100000 nsplits 1 5 10 25 50 100
13398445413854501
[edit] Java
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");
}
}
}
Output:
242 13398445413854501 1333983445341383545001 133339833445334138335450001 4562 10056050940818192726001 99341140660285639188927260001 992198221207406412424859964272600001
[edit] JavaScript
[edit] Iterative
Efficient iterative algorithm (cleverly calculates number of combinations without permuting them)
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];
}
- Output:
JavaScript hit's integer limit for optional task
countcoins(100, [1,5,10,25]);
242
[edit] Recursive
Inefficient recursive algorithm (naively calculates number of combinations by actually permuting them)
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;
}
- Output:
Too slow for optional task
countcoins(100, [1,5,10,25]);
242
[edit] Mathematica
CountCoins[amount_, coinlist_] := ( ways = ConstantArray[1, amount];
Do[For[j = coin, j <= amount, j++,
If[ j - coin == 0,
ways[[j]] ++,
ways[[j]] += ways[[j - coin]]
]]
, {coin, coinlist}];
ways[[amount]])
Example usage:
CountCoins[100, {25, 10, 5}]
-> 242
CountCoins[100000, {100, 50, 25, 10, 5}]
-> 13398445413854501
[edit] 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).
[edit] OCaml
Translation of the D minimal version:
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]);
;;
Output:
$ ocaml coins.ml 242 13398445413854501
[edit] PARI/GP
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)
Output:
%1 = 242 %2 = 13398445413854501
[edit] Perl 6
[edit] Recursive (cached)
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(-*)); # 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];
- Output:
242 13398445413854501
[edit] Iterative
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];
[edit] 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 ) )
Test:
(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) )
Output:
242 13398445413854501 1333983445341383545001 133339833445334138335450001 4562 10056050940818192726001 99341140660285639188927260001 992198221207406412424859964272600001
[edit] Python
[edit] Simple version
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])
Output:
242 13398445413854501
[edit] Fast version
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()
Output:
242 13398445413854501 1333983445341383545001 133339833445334138335450001 4562 10056050940818192726001 99341140660285639188927260001 992198221207406412424859964272600001
[edit] Racket
This is the basic recursive way:
#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
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
(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 |#
[edit] REXX
The recursive calls to the subroutine have been unrolled somewhat,
this reduces the number of recursive calls substantially.
/*REXX program makes change from some amount with various specie (coins)*/
parse arg n $
if n='' then n=100 /*Not specified? Use $1 default.*/
if $='' then $=1 5 10 25 /*Use penny/nickle/dime/quarter ?*/
coins=words($) /*count number of coins specified*/
do j=1 for coins /*create a fast way of accessing.*/
$.j=word($,j) /*define a stemmed array element.*/
end /*j*/
say 'with an amount of ' n", there're " kaChing(n,coins),
' ways to make change with: ' $
exit /*stick a fork in it, we're done.*/
/*──────────────────────────────────kaChing subroutine──────────────────*/
kaChing: procedure expose $.; parse arg a,k
if a==0 then f=1 /*unroll some special cases. */
else if k==0 | k==1 then f=0 /*unroll some more special cases.*/
else f=kaChing(a,k-1) /*recurse the amount*/
if a==$.k then return f+1 /*handle another special case. */
if a<$.k | k==0 then return f /*if amount is <coin, return F. */
return f+kaChing(a-$.k,k) /*keep recursing the diminished $*/
output when using the default input
with an amount of 100, there're 242 ways to make change with: 1 5 10 25
[edit] Ruby
The algorithm also appears here
Recursive, with caching
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])
outputs
242 13398445413854501
Iterative
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])
outputs
242 13398445413854501
[edit] Run BASIC
for penny = 0 to 100Output:
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"
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
[edit] 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))
Output:
res0: Int = 6
[edit] Scheme
A simple recursive implementation:
(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)
Output:
242
[edit] 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;
Output:
242 13398445413854501 1333983445341383545001 10056050940818192726001 99341140660285639188927260001
[edit] 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}]
Output:
242 13398445413854501 4563 10056050940818192726001
Categories:
- Programming Tasks
- Solutions by Programming Task
- Ada
- AutoHotkey
- AWK
- BBC BASIC
- C
- Common Lisp
- D
- Erlang
- Factor
- Forth
- Go
- Groovy
- Haskell
- Icon
- Unicon
- Needs a better algorithm. examples needing attention
- Examples needing attention
- Icon Programming Library
- J
- Java
- JavaScript
- Mathematica
- Mercury
- OCaml
- PARI/GP
- Perl 6
- PicoLisp
- Python
- Racket
- REXX
- Ruby
- Run BASIC
- Scala
- Scheme
- Seed7
- Tcl
