Count the coins: Difference between revisions
(→{{header|C}}: speed) |
(Updated second D version, as the C code changes again) |
||
Line 264: | Line 264: | ||
assert(c > 0); |
assert(c > 0); |
||
} body { |
} body { |
||
static int findCycle(in Cents amount, in int[] coins) |
|||
pure nothrow { |
|||
⚫ | |||
⚫ | |||
⚫ | |||
lcycle = c + 1; |
|||
return lcycle * coins.length; |
|||
⚫ | |||
⚫ | |||
immutable int n = coins.length; |
immutable int n = coins.length; |
||
⚫ | |||
⚫ | |||
int tot; |
|||
Ucent* start = p; // const pointer |
|||
⚫ | |||
const Ucent* end = start + cycle; |
|||
⚫ | |||
// points to a cyclic buffer of length coins[i] |
|||
p[0 .. n] = Ucent.one; |
|||
p |
auto p = (new Ucent*[n]).ptr; |
||
auto q = (new Ucent*[n]).ptr; // iterates it. |
|||
⚫ | |||
{ |
|||
for (int i, s=1; s <= amount; p++) { |
|||
uint i; |
|||
for (p[i = 0] = buf.ptr; i < n; i++) { |
|||
if (i) |
|||
p[i] = coins[i - 1] + p[i - 1]; |
|||
*(q[i] = p[i]) = Ucent.one; |
|||
*p = (q >= start) ? *q : q[cycle]; |
|||
} |
} |
||
⚫ | |||
Ucent prev; |
|||
foreach (j; 1 .. amount + 1) { |
|||
i++ |
for (int i = 0; i < n; prev = *q[i++]) { |
||
if (i |
if (--q[i] < p[i]) |
||
i = |
q[i] = p[i] + coins[i] - 1; |
||
if (i) |
|||
⚫ | |||
} |
} |
||
} |
} |
||
return |
return prev; |
||
} |
} |
||
Revision as of 13:23, 1 November 2011
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.
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 c, v; } xint; xint one = { 0, 1 };
xint countx(unsigned int sum, int *coins) { /* p[i] points to a cyclic buffer of length coins[i]; q[i] iterates it */ xint *buf, **p, **q, prev; unsigned int n, i, len;
for (n = len = 0; coins[n]; len += coins[n++]);
p = malloc(sizeof(xint*) * n); q = malloc(sizeof(xint*) * n); buf = calloc(sizeof(xint), len);
for (p[i = 0] = buf; i < n; i++) { if (i) p[i] = coins[i - 1] + p[i - 1]; *(q[i] = p[i]) = one; }
/* for whatever reason, "while (sum--)" is a lot slower... */ for (len = 1; len <= sum; len++) { for (i = 0; i < n; prev = *q[i++]) { if (--q[i] < p[i]) q[i] = p[i] + coins[i] - 1;
if (i) { /* 128-bit integer addition */ q[i]->c += prev.c; if (q[i]->v >= ~prev.v) q[i]->c++; q[i]->v += prev.v; } } }
free(buf), free(p), 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
Basic version
The Cents struct is a poor's man unit of measure, as often done in F#. <lang d>import std.stdio, std.bigint;
struct Cents {
int c; alias c this;
}
BigInt countChanges(in Cents amount, in int[] coins)/*pure nothrow*/ in {
assert(amount > 0); assert(coins.length > 0); foreach (c; coins) assert(c > 0);
} out(result) {
assert(cast()result > 0); // de-const, bug workaround
} body {
static int findCycle(in Cents amount, in int[] coins) pure nothrow { int lcycle; foreach (const int c; coins) if (c <= amount && c >= lcycle) lcycle = c + 1; return lcycle * coins.length; } immutable int cycle = findCycle(amount, coins); immutable size_t n = coins.length;
auto table = new BigInt[cycle]; table[0 .. n] = BigInt(1);
int pos = n; int i; for (int s = 1; s <= amount; ) { 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]; i++; if (i == n) { i = 0; s++; }
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(Cents( 1_00), coins[2 .. $])); writeln(countChanges(Cents( 1000_00), coins)); writeln(countChanges(Cents( 10000_00), coins)); writeln(countChanges(Cents(100000_00), coins), "\n"); }
}</lang> Output:
242 13398445413854501 1333983445341383545001 133339833445334138335450001 4562 10056050940818192726001 99341140660285639188927260001 992198221207406412424859964272600001
Alternative 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 first D version.
<lang d>import std.stdio, std.bigint;
immutable struct Cents {
int c; alias c this;
}
struct Ucent { /// Simplified 128-bit integer (like ucent).
ulong hi, lo; static immutable one = Ucent(0, 1);
void opOpAssign(string op="+")(const ref Ucent y) pure nothrow { this.hi += y.hi; if (this.lo >= ~y.lo) this.hi++; this.lo += y.lo; }
const string toString() { return toDecimalString((BigInt(this.hi) << 64) + this.lo); }
}
Ucent countChanges(in Cents amount, in int[] coins) pure nothrow in {
assert(amount > 0); assert(coins.length > 0); foreach (c; coins) assert(c > 0);
} body {
immutable int n = coins.length; //immutable int tot = reduce!q{ a + b }(coins); int tot; foreach (c; coins) tot += c;
// 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[tot];
{ uint i; for (p[i = 0] = buf.ptr; i < n; i++) { if (i) p[i] = coins[i - 1] + p[i - 1]; *(q[i] = p[i]) = Ucent.one; } }
Ucent prev; foreach (j; 1 .. amount + 1) { for (int i = 0; i < n; prev = *q[i++]) { if (--q[i] < p[i]) q[i] = p[i] + coins[i] - 1; if (i) *q[i] += prev; } }
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(Cents( 1_00), coins[2 .. $])); writeln(countChanges(Cents( 1000_00), coins)); writeln(countChanges(Cents( 10000_00), coins)); writeln(countChanges(Cents(100000_00), coins), "\n"); }
}</lang>
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.
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
This solution is too slow for the optional task (obviously counting up to about 1.3*10^16 will not finish any time soon), plus the number of different coins is coded into the for loops.
<lang java>class CountTheCoins {
public static void main(String[] args) { System.out.println("combinations to form $1 " + coins()); } private static int coins() { int count = 0; int amount = 100; for (int i0 = 0; i0 <= amount; i0 += 1) { for (int i1 = i0; i1 <= amount; i1 += 5) { for (int i2 = i1; i2 <= amount; i2 += 10) { if ((amount - i2) % 25 == 0) { count++; } } } } return count; }
}</lang>
Python
<lang python>try:
import psyco psyco.full()
except ImportError:
pass
def count_changes(amount_cents, coins):
n = len(coins) 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 i = 0 s = 1 while s <= amount_cents: 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] i += 1 if i == n: i = 0; s += 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
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
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