Created

Embed URL

HTTPS clone URL

SSH clone URL

You can clone with HTTPS or SSH.

Download Gist

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

View 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
View 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 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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Something went wrong with that request. Please try again.