Count the coins

Count the coins
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 2³²).

Algorithm: See here.

C

Using some crude 128-bit integer type. <lang c>#include <stdio.h>

1. include <stdlib.h>
2. include <string.h>
3. 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) {

1. define BITS (sizeof(ull) * CHAR_BIT/2)
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

Translation of: Go

<lang d>import std.stdio, std.bigint;

auto changes(int amount, int[] coins) {

   auto ways = new BigInt[amount + 1];
   ways[0] = BigInt(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

Translation of: C

<lang d>import std.stdio, std.bigint;

BigInt countChanges(in int amount, in int[] coins) {

   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;
   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) {
               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 Cents struct is a poor's man unit of measure, as often done in F#. The output is the same as the first D version.

Translation of: C

<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];

   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; // 0
   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(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.

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

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

Translation of: D

<lang 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");
       }
   }

}</lang> Output:

242
13398445413854501
1333983445341383545001
133339833445334138335450001

4562
10056050940818192726001
99341140660285639188927260001
992198221207406412424859964272600001

PicoLisp

Translation of: C

<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

Translation of: C

<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

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|
     table[i][j] = (i-coins[j] < 0 ? 0 : table[i-coins[j]][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

Translation of: Ruby

<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}]

1. 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