Count the coins

From Rosetta Code
Revision as of 13:05, 31 October 2011 by 79.30.42.33 (talk) (Tweaked C code)
Count the coins is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

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>

  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 c, v; } xint; xint one = { 0, 1 };

xint countx(int sum, int *coins) { 

   int s, i, n, cycle = 0;
   xint *cache, *p, *end, *q, out;

   for (n = 0; coins[n]; n++)
       if (coins[n] <= sum && coins[n] >= cycle)
           cycle = coins[n] + 1;

   cycle *= n;
   p = cache = calloc(cycle, sizeof(xint));
   end = cache + cycle;

   for (i = 0; i < n; i++, *p++ = one);

   for (s = 1, i = 0; s <= sum; p++) {
       if (!i && p >= end)
           p = cache;

       if (coins[i] <= s) {
           q = p - coins[i] * n;
           *p = (q >= cache) ? *q : q[cycle];
       }

       if (i++) {  /* 128 bit addition */
           p->c += p[-1].c;
           if (p->v >= ~(p[-1].v))
               p->c++;
           p->v += p[-1].v;
       }
       if (i == n)
           i = 0, s++;
   }

   out = p[-1];
   free(cache);

   return out;

}

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] = {v.c, v.v >> BITS, 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

Translation of: C

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

struct Cents { 

   int c;
   alias c this;

}

BigInt changeCount(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 {
       immutable int n = coins.length;
       auto t = new BigInt[n * (amount + 1)];
       t[0 .. n] = BigInt(1);

       size_t pos = n;
       foreach (s; 1 .. amount.c + 1) {
           if (coins[0] <= s)
               t[pos] = t[pos - (n * coins[0])];
           pos++;
           foreach (i; 1 .. n) {
               if (coins[i] <= s)
                   t[pos] = t[pos - (n * coins[i])];
               t[pos] += t[pos - 1];
               pos++;
           }
       }

       return t[pos - 1];
   }

void main() { 

   immutable usCoins = [100, 50, 25, 10, 5, 1];
   writeln(changeCount(Cents(    1_00), usCoins[2 .. $]));
   writeln(changeCount(Cents( 1000_00), usCoins));
   writeln(changeCount(Cents(10000_00), usCoins));

   immutable euCoins = [200, 100, 50, 20, 10, 5, 2, 1];
   writeln(changeCount(Cents( 1000_00), euCoins));
   writeln(changeCount(Cents(10000_00), euCoins));

}</lang> Output: 

242
13398445413854501
1333983445341383545001
10056050940818192726001
99341140660285639188927260001

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>

Thus:

<lang j> 100 nsplits 1 5 10 25 242</lang>


Python

Translation of: D

<lang python>try: 

   import psyco
   psyco.full()

except ImportError: 

   pass

def make_change(amount_cents, coins): 

   n = len(coins)
   t = [0] * (n * (amount_cents + 1))
   for i in xrange(n):
       t[i] = 1

   pos = n
   for s in xrange(1, amount_cents + 1):
       if coins[0] <= s:
           t[pos] = t[pos - (n * coins[0])]
       pos += 1
       for i in xrange(1, n):
           if coins[i] <= s:
               t[pos] = t[pos - (n * coins[i])]
           t[pos] += t[pos - 1]
           pos += 1

   return t[pos - 1]

print make_change( 100, [1,5,10,25]) print make_change( 100000, [1,5,10,25,50,100])

  1. extra

print make_change(1000000, [1,5,10,25,50,100]) print make_change( 100000, [1,2,5,10,20,50,100,200]) print make_change(1000000, [1,2,5,10,20,50,100,200])</lang> Output: 

242
13398445413854501
1333983445341383545001
10056050940818192726001
99341140660285639188927260001

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

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
Retrieved from "https://rosettacode.org/wiki/Count_the_coins?oldid=203833"