Count the coins: Difference between revisions
m (→{{header|REXX}}: added whitespace to the output (SAY). -- ~~~~) |
m (→{{header|REXX}}: removed a blank line, added verbage to the '''output''' section. -- ~~~~) |
||
Line 1,117: | Line 1,117: | ||
say 'with an amount of ' n", there're " kaChing(n,coins), |
say 'with an amount of ' n", there're " kaChing(n,coins), |
||
' ways to make change with: ' $ |
' ways to make change with: ' $ |
||
exit /*stick a fork in it, we're done.*/ |
exit /*stick a fork in it, we're done.*/ |
||
/*──────────────────────────────────kaChing subroutine──────────────────*/ |
/*──────────────────────────────────kaChing subroutine──────────────────*/ |
||
Line 1,128: | Line 1,127: | ||
if a<$.k | k==0 then return f /*if amount is <coin, return F. */ |
if a<$.k | k==0 then return f /*if amount is <coin, return F. */ |
||
return f+kaChing(a-$.k,k) /*keep recursing the diminished $*/</lang> |
return f+kaChing(a-$.k,k) /*keep recursing the diminished $*/</lang> |
||
'''output''' |
'''output''' when using the default input |
||
<pre style="overflow:scroll"> |
<pre style="overflow:scroll"> |
||
with an amount of 100, there're 242 ways to make change with: 1 5 10 25 |
with an amount of 100, there're 242 ways to make change with: 1 5 10 25 |
Revision as of 22:07, 24 August 2012
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.
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
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
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 <string.h>
- include <limits.h>
/* Simple recursion method. Using uint64 would have
been enough for task, if supremely slow */
int count(int sum, int *coins) { return (!*coins || sum < 0) ? 0 : !sum ? 1 : count(sum - *coins, coins) + count(sum, coins + 1); }
/* ad hoc 128-bit integer (faster than GMP) */ typedef unsigned long long ull; typedef struct xint { ull v, c; } xint; typedef struct node { xint x; struct node *next; } node;
xint one = { 1, 0 };
xint countx(register int sum, int *coins) { /* lumping all declarations here to avoid gcc -pedantic C89 mode warnings */ unsigned int n;
/* q[i] points to a cyclic buffer of length coins[i] */ node *buf, **q; xint prev, cur; register int i, j, carry = 0;
/* alloc and init buffers */ for (n = j = 0; coins[n]; j += coins[n++]); q = malloc(sizeof(node*) * n);
q[0] = buf = calloc(j, sizeof(node)); for (n = 0; coins[n]; n++) { if (n) q[n] = q[n - 1] + coins[n - 1];
for (j = 1; j < coins[n]; j++) q[n][j - 1].next = q[n] + j;
q[n][coins[n] - 1].next = q[n]; q[n]->x = one; }
/* critical loops. for whatever reason, "while (sum--)" is a lot slower */ for (j = 0; j < sum; j++) { for (i = 0; i < n; i++) { /* each int128 buffer is linked via pointers. It avoids a separate look up on array bounds, while ->next is in cache anyway; arrays are bigger, but we had to allocate more than one page regardless */ q[i] = q[i]->next; cur = q[i]->x;
if (i) { /* 128-bit integer addition */ /* don't add high bits until we've seen a carry */ if (carry) cur.c += prev.c; if (cur.v >= ~prev.v) carry = ++cur.c; cur.v += prev.v; } prev = q[i]->x = cur; } }
free(buf), free(q); return prev; }
void print (xint v) {
- define BITS (sizeof(ull) * CHAR_BIT/2)
- define BASE (1ULL << BITS)
int i, k = 63; char buf[64] = {0}; ull n[3]; n[0] = v.c, n[1] = v.v >> BITS, n[2] = v.v & (BASE - 1);
while (n[0] || n[1] || n[2]) for (i = 0; i < 3; n[i++] /= 10) if (i < 2) n[i + 1] += BASE * (n[i] % 10); else buf[--k] = '0' + n[2] % 10;
puts(buf + k); }
int main() { int us_coins[] = { 100, 50, 25, 10, 5, 1, 0 }; int eu_coins[] = { 200, 100, 50, 20, 10, 5, 2, 1, 0 };
printf("%d\n", count(100, us_coins + 2));
print(countx( 1000 * 100, us_coins)); print(countx( 10000 * 100, us_coins)); print(countx(100000 * 100, us_coins));
putchar('\n');
print(countx( 1 * 100, eu_coins)); print(countx( 1000 * 100, eu_coins)); print(countx( 10000 * 100, eu_coins)); print(countx(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>
Common Lisp
<lang 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)</lang>
D
Minimal 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[amount];
}
void main() {
writeln(changes( 1_00, [25, 10, 5, 1])); writeln(changes(1000_00, [100, 50, 25, 10, 5, 1]));
}</lang> Output:
242 13398445413854501
Faster version
<lang d>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 int 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"); }
}</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;
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"); }
}</lang>
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
J
In this draft intermediate results are a two column array. The first column is tallies and the second column is unallocated value.
<lang j>merge=: ({:"1 (+/@:({."1),{:@{:)/. ])@; count=: {.@] <@,. {:@] - [ * [ i.@>:@<.@%~ {:@] init=: (1 ,. ,.)^:(0=#@$) nsplits=: [: +/@:({."1) [: (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
Mathematica
<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
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>
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 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(-*)); # 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
REXX
The recursive (calls) to the subroutine have been unrolled somewhat,
this reduces the number of recursive calls substantially.
<lang rexx>/*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 $*/</lang> output when using the default input
with an amount of 100, there're 242 ways to make change with: 1 5 10 25
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
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
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
- 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
- Mathematica
- Mercury
- OCaml
- PARI/GP
- Perl 6
- PicoLisp
- Python
- REXX
- Ruby
- Run BASIC
- Scheme
- Seed7
- Tcl