public
Created

find the smallest number of coins (pennies, nickles, dimes, quarters) that add to a specific total

  • Download Gist
coin-change2.rb output
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36
$ ./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
gistfile1.rb
Ruby
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80
#!/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

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.