Coin Change, Part 1

May 17, 2013

The counting function loops through the coins in xs, and for each coin loops from the value of the coin to n adding the count for the current target less the current coin:

(define (count xs n) (let ((cs (make-vector (+ n 1) 0))) (vector-set! cs 0 1) (do ((xs xs (cdr xs))) ((null? xs) (vector-ref cs n)) (do ((x (car xs) (+ x 1))) ((< n x)) (vector-set! cs x (+ (vector-ref cs x) (vector-ref cs (- x (car xs)))))))))

The enumerating function is the same, except that it keeps list of coins instead of counts:

(define (coins xs n) (let ((cs (make-vector (+ n 1) (list)))) (vector-set! cs 0 (list (list))) (do ((xs xs (cdr xs))) ((null? xs) (vector-ref cs n)) (do ((i (car xs) (+ i 1))) ((< n i)) (vector-set! cs i (append (vector-ref cs i) (map (lambda (zs) (cons (car xs) zs)) (vector-ref cs (- i (car xs))))))))))

The dynamic programming aspect of the solution is obvious, as both functions use the vector cs to keep solutions to sub-problems, finally returning the value in the last element of the vector.

Here are two examples:

> (count '(1 5 10 25) 40) 31 > (coins '(1 5 10 25) 40) ((1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1) (5 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1) (5 5 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1) (5 5 5 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1) (5 5 5 5 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1) (5 5 5 5 5 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1) (5 5 5 5 5 5 1 1 1 1 1 1 1 1 1 1) (5 5 5 5 5 5 5 1 1 1 1 1) (5 5 5 5 5 5 5 5) (10 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1) (10 5 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1) (10 5 5 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1) (10 5 5 5 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1) (10 5 5 5 5 1 1 1 1 1 1 1 1 1 1) (10 5 5 5 5 5 1 1 1 1 1) (10 5 5 5 5 5 5) (10 10 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1) (10 10 5 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1) (10 10 5 5 1 1 1 1 1 1 1 1 1 1) (10 10 5 5 5 1 1 1 1 1) (10 10 5 5 5 5) (10 10 10 1 1 1 1 1 1 1 1 1 1) (10 10 10 5 1 1 1 1 1) (10 10 10 5 5) (10 10 10 10) (25 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1) (25 5 1 1 1 1 1 1 1 1 1 1) (25 5 5 1 1 1 1 1) (25 5 5 5) (25 10 1 1 1 1 1) (25 10 5))

You can run the program at http://programmingpraxis.codepad.org/RekApsRy.

In a future exercise we will see a variant on the coin change problem where the task is to determine the smallest set of coins that sum to a particular target, without first enumerating all the possibilities.

5 Responses to “Coin Change, Part 1”

Programming Praxis – Coin Change, Part 1 | Bonsai Code said
May 17, 2013 at 3:06 PM
[…] today’s Programming Praxis exercise, our goal is to list all of the ways in which a target amount can be […]

Remco Niemeijer said

May 17, 2013 at 3:06 PM

My Haskell solution (see http://bonsaicode.wordpress.com/2013/05/17/programming-praxis-coin-change-part-1/ for a version with comments):

import Data.List

coins :: (Num a, Ord a) => [a] -> a -> [[a]]
coins _  0 = [[]]
coins xs n = [c:r | (c:cs) <- tails xs, c <= n, r <- coins (c:cs) (n-c)]

count :: (Num a, Ord a) => [a] -> a -> Int
count xs = length . coins xs

Alan S. said

May 21, 2013 at 4:23 PM

Here is a Ruby program with both functions

#!/usr/bin/env ruby
# coin-change1.rb
#
# count sets of coins (pennies, nickles, dimes, quarters) that
# add to a specific total
#
# Count the different sets of the polynomial: 
#   total = P + N*5 + D*10 * Q*25
# 
# A "coin set" is a 4-tuple of [P,N,D,Q]
#
 
$coin_values = [ 1, 5, 10, 25 ]
 
# given a total, find the maximum number of coins for each
# denomination
 
def compute_max_coins(total)
  $max_coins = $coin_values.map {|value| Integer(total / value)}
  $max_pennies  = $max_coins[0]
  $max_nickles  = $max_coins[1]
  $max_dimes    = $max_coins[2]
  $max_quarters = $max_coins[3]
end
 
# get all the coin sets for a given total
 
def get_coin_sets(total)
  coin_sets = []
  (0..$max_quarters).each { |q|
    break if total < q*25
    qtotal = total - q*25
    (0..$max_dimes).each { |d|
      break if qtotal < d*10
      dtotal = qtotal - d*10
      (0..$max_nickles).each { |n|
        break if dtotal < n*5
        p = dtotal - n*5
        coin_sets += [[q,d,n,p]]
      }
    }
  }
  coin_sets
end
 
if ARGV.size > 0
  total = ARGV.shift.to_i
else
  total = 40
end
 
compute_max_coins(total)
coin_sets = get_coin_sets(total)
 
puts "For total = #{total}"
puts "There are #{coin_sets.size} sets of coins"
puts ''
set = 1
printf "Set  $.25  $.10  $.05  $.01\n"
coin_sets.each do |q,d,n,p| 
  printf "%3d: %4d  %4d  %4d  %4d\n", set, q, d, n, p
  set += 1
end
 
exit

aks said

May 21, 2013 at 4:24 PM

Here is the output:

$ ./coin-change1.rb 
For total = 40
There are 31 sets of coins
 
Set  $.25  $.10  $.05  $.01
  1:    0     0     0    40
  2:    0     0     1    35
  3:    0     0     2    30
  4:    0     0     3    25
  5:    0     0     4    20
  6:    0     0     5    15
  7:    0     0     6    10
  8:    0     0     7     5
  9:    0     0     8     0
 10:    0     1     0    30
 11:    0     1     1    25
 12:    0     1     2    20
 13:    0     1     3    15
 14:    0     1     4    10
 15:    0     1     5     5
 16:    0     1     6     0
 17:    0     2     0    20
 18:    0     2     1    15
 19:    0     2     2    10
 20:    0     2     3     5
 21:    0     2     4     0
 22:    0     3     0    10
 23:    0     3     1     5
 24:    0     3     2     0
 25:    0     4     0     0
 26:    1     0     0    15
 27:    1     0     1    10
 28:    1     0     2     5
 29:    1     0     3     0
 30:    1     1     0     5
 31:    1     1     1     0

Programming Praxis – Coin Change, Part 1, C# Solutions | Software Salad said
June 10, 2013 at 11:37 PM
[…] This post presents C# solutions to a coin change problem as described in https://programmingpraxis.com/2013/05/17/coin-change-part-1. […]

Programming Praxis