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.

About these ads

Pages: 1 2

5 Responses to “Coin Change, Part 1”

  1. […] today’s Programming Praxis exercise, our goal is to list all of the ways in which a target amount can be […]

  2. 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
    
  3. Alan S. said

    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
    
  4. aks said

    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
    
  5. […] This post presents C# solutions to a coin change problem as described in http://programmingpraxis.com/2013/05/17/coin-change-part-1. […]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 632 other followers

%d bloggers like this: