Skip to content

Embed URL

HTTPS clone URL

Subversion checkout URL

You can clone with
or
.
Download ZIP
coin-change -- count sets of coins (pennies, nickles, dimes, quarters) that add to a specific total
$ ./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
#!/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
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.