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>

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