Count the coins
There are four types of common coins in US currency: quarters (25 cents), dimes (10), nickels (5) and pennies (1). There are 6 ways to make change for 15 cents:
- A dime and a nickel;
- A dime and 5 pennies;
- 3 nickels;
- 2 nickels and 5 pennies;
- A nickel and 10 pennies;
- 15 pennies.
How many ways are there to make change for a dollar using these common coins? (1 dollar = 100 cents).
Optional:
Less common are dollar coins (100 cents); very rare are half dollars (50 cents). With the addition of these two coins, how many ways are there to make change for $1000? (note: the answer is larger than 232).
Algorithm: See here.
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 (I'm aware of GMP, but this is faster) */ typedef struct xint { unsigned long long c, v; } xint; xint one = { 0, 1 }, zero = { 0, 0 };
xint countx(int sum, int *coins) { int s, i, n; xint *cache, *p, out;
- define xadd_to(a, b)\
if (1) { if ((a).v >= ~((b).v)) (a).c++; (a).v += (b).v; }
for (n = 0; coins[n]; n++); p = cache = malloc(sizeof(xint) * n * (1 + sum));
for (i = 0; i < n; i++, *p++ = one); for (s = 1; s <= sum; s++) { for (i = 0; i < n; i++, p++) { if (s < 0) *p = zero; else { *p = (coins[i] <= s) ? p[-n * coins[i]] : zero; if (i) { xadd_to(*p, p[-1]); } } } } out = p[-1]; free(cache);
return out; }
int main() { /* a non-lazy person could have done long decimal output here */
- define print(a)\
if (a.c) printf("%.10g\n", a.v + a.c * (ULLONG_MAX + 1.));\ else printf("%llu\n", a.v)
int us_coins[] = { 100, 50, 25, 10, 5, 1, 0 }; int eu_coins[] = { 200, 100, 50, 20, 10, 5, 2, 1, 0 }; xint ret;
printf("%d\n", count(100, us_coins + 2));
ret = countx(1000 * 100, us_coins); print(ret);
/* these will overflow int64 and force float point display */ ret = countx(10000 * 100, us_coins); print(ret);
ret = countx(1000 * 100, eu_coins); print(ret); ret = countx(10000 * 100, eu_coins); print(ret);
return 0; }</lang>output (only first two lines are asked for by task)<lang>242 13398445413854501 1.333983445e+21 1.005605094e+22 8.033207543e+24</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
<lang d>import std.stdio, std.bigint;
struct Cents { int x; }
BigInt makeChange(in Cents amount, in int[] coins) /*pure nothrow*/
in {
assert(amount.x > 0);
assert(coins.length > 0);
foreach (c; coins) assert(c > 0);
}
out(result) {
assert(cast()result > 0); // de-const, bug workaround
}
body {
const int n = amount.x;
const int m = coins.length - 1;
auto table = new BigInt[][](n + 1, m + 1);
table[0][] = BigInt(1);
foreach (i; 1 .. n + 1)
foreach (j; 0 .. m + 1) {
const int ic = i - coins[j];
table[i][j] = (ic < 0 ? BigInt(0) : table[ic][j]) +
(j-1 < 0 ? BigInt(0) : table[i][j-1]);
}
return table[n][m]; }
void main() {
writeln(makeChange(Cents( 1_00), [1,5,10,25])); writeln(makeChange(Cents( 1000_00), [1,5,10,25,50,100])); // extra writeln(makeChange(Cents(10000_00), [1,5,10,25,50,100]));
}</lang> Output:
242 13398445413854501 1333983445341383545001
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.
Python
<lang python>try:
import psyco psyco.full()
except ImportError:
pass
def make_change(amount_cents, coins):
n = amount_cents m = len(coins) - 1 table = [[0] * (m + 1) for _ in xrange(n + 1)] table[0] = [1] * (m + 1)
for i in xrange(1, n + 1):
for j in xrange(m + 1):
ic = i - coins[j]
table[i][j] = (0 if ic < 0 else table[ic][j]) + \
(0 if j-1 < 0 else table[i][j-1])
return table[n][m]
print make_change( 100, [1,5,10,25]) print make_change( 100000, [1,5,10,25,50,100]) print make_change(1000000, [1,5,10,25,50,100]) # extra</lang> Output:
242 13398445413854501 1333983445341383545001
With Psyco it runs as fast as natively compiled languages.
Ruby
The algorithm also appears here
Recursive, with caching
<lang ruby>def make_change(amt, coins)
@cache = {}
@coins = coins
do_count(amt, @coins.length - 1)
end
def do_count(n, m)
if @cache.has_key?([n,m]) @cachen,m elsif n == 0 1 elsif n < 0 || m < 0 0 else @cachen,m = do_count(n, m-1) + do_count(n-@coins[m], m) end
end
p make_change(1_00, [1,5,10,25]) begin
p make_change(1000_00, [1,5,10,25,50,100])
rescue Exception => e
puts e.message
end</lang>
outputs
242 stack level too deep
Iterative
<lang ruby>def make_change2(amt, coins)
n = amt m = coins.length - 1
table = Array.new(n+1) {|i| Array.new(m+1)}
table[0] = Array.new(m+1, 1)
1.upto(n) do |i|
0.upto(m) do |j|
_i = i - coins[j]
table[i][j] = (_i < 0 ? 0 : table[_i][j]) +
(j-1 < 0 ? 0 : table[i][j-1])
end
end
table[n][m]
end
p make_change2(100, [1,5,10,25]) p make_change2(1000_00, [1,5,10,25,50,100])</lang> outputs
242 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