Count the coins

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? (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.

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>

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.

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

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