Instantly share code, notes, and snippets.

# aks/coin-change2.rb output Created May 21, 2013

What would you like to do?
find the smallest number of coins (pennies, nickles, dimes, quarters) that add to a specific total
 \$ ./coin-change2.rb For total = 40 There are 31 sets of coins Set \$.25 \$.10 \$.05 \$.01 Coins 1: 1 1 1 0 3 2: 1 0 3 0 4 3: 0 4 0 0 4 4: 0 3 2 0 5 5: 0 2 4 0 6 6: 1 1 0 5 7 7: 0 1 6 0 7 8: 1 0 2 5 8 9: 0 0 8 0 8 10: 0 3 1 5 9 11: 0 2 3 5 10 12: 0 1 5 5 11 13: 0 0 7 5 12 14: 1 0 1 10 12 15: 0 3 0 10 13 16: 0 2 2 10 14 17: 0 1 4 10 15 18: 0 0 6 10 16 19: 1 0 0 15 16 20: 0 2 1 15 18 21: 0 1 3 15 19 22: 0 0 5 15 20 23: 0 2 0 20 22 24: 0 1 2 20 23 25: 0 0 4 20 24 26: 0 1 1 25 27 27: 0 0 3 25 28 28: 0 1 0 30 31 29: 0 0 2 30 32 30: 0 0 1 35 36 31: 0 0 0 40 40 The smallest coin set has 3 coins: 1, 1, 1, 0
 #!/usr/bin/env ruby # coin-change2.rb # # find the smallest number of coins (pennies, nickles, dimes, quarters) that # add to a specific total # # Find the numbers that fulfill 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 class Array def sum self.reduce(:+) end end def compare(a,b) a == b ? 0 : a < b ? -1 : 1 end if ARGV.size > 0 total = ARGV.shift.to_i else total = 40 end compute_max_coins(total) coin_sets = get_coin_sets(total) shortest_coin_set = coin_sets.sort!{|a,b| compare(a.sum, b.sum)}.first puts "For total = #{total}" puts "There are #{coin_sets.size} sets of coins" set = 1 printf "Set \$.25 \$.10 \$.05 \$.01 Coins\n" coin_sets.each do |q,d,n,p| printf "%3d: %4d %4d %4d %4d %5d\n", set, q, d, n, p, [q,d,n,p].sum set += 1 end printf "The smallest coin set has %d coins: %s\n", shortest_coin_set.sum, shortest_coin_set.join(", ") exit