[SOLUTION][QUIZ] Making Change (#154)
- From: Yoan Blanc <greut.lists@xxxxxxxxxxx>
- Date: Sun, 27 Jan 2008 11:49:23 -0500
There is my solution which I'm proud of ;-)
http://pastie.caboo.se/144083 (solution)
http://pastie.caboo.se/144089 (rspec)
def make_change(amount, coins=[25, 10, 5, 1])
# Does the change, recursively with a kind of
# alpha-beta pruning (whitout the beta)
# Best default value for alpha is +Infinity as
# alpha represents the size of the actual found
# solution, it can only decrease with the time.
def make_change_r(amount, coins, alpha)
# the coin with its solution
# that has to be the shortest one
best_coin = nil
solution = []
# The good coin exists (win!)
if coins.include? amount
best_coin = amount
# Only one coin stand (avoids a lot of recursion)
elsif coins.length == 1
coin = coins[0]
unless coin > amount or amount % coin != 0
# Do not construct a solution if this one
# is bigger than the allowed one (alpha).
size = amount/coin - 1
if size <= alpha
best_coin = coin
solution = [best_coin] * size
end
end
# No solution can be found (odd coins and even amount)
elsif amount % 2 === 1 and \
coins.select{|coin| coin % 2 != 0}.length === 0
# pass
# Alpha(-beta) pruning:
# Do not look to this subtree because another
# shorter solution has been found already.
elsif alpha > 1 and
coins.select{|c| c >= amount/alpha}.each do |coin|
# only give a subset of the coins, the bigger ones
# have been tested already.
found = make_change_r( \
amount-coin, \
coins.select {|c| c <= coin and c <= amount-coin}, \
alpha-1)
# Check if the solution (if there is any) is good enough
if not found.nil? and \
(solution.length === 0 or solution.length >
found.length)
best_coin = coin
solution = found
alpha = solution.length
end
end
end
return best_coin.nil? \
? best_coin \
: [best_coin] + solution
end
# Any money or coins to give back?
if not amount.nil? and amount > 0 and not coins.nil?
# make sure the coins are ready to be used
coins.sort!
coins.uniq!
coins.reverse!
infinity = 1.0/0
return make_change_r(amount, coins, infinity)
else
return []
end
end
And the RSpec I used to test it:
describe "make_change" do
it "should work with US money" do
make_change(39).should == [25, 10, 1, 1, 1, 1]
end
it "should work with alien money" do
make_change(14, [10, 7, 1]).should == [7, 7]
end
it "should work with non solvable solution" do
make_change(0.5).should == nil
end
it "should now when not to give money back" do
make_change(0).should == []
end
it "should agree with dh and Marcelo" do
make_change(1000001, [1000000, 1]).should == [1000000, 1]
make_change(10000001, [10000000, 1]).should == [10000000, 1]
make_change(100000001, [100000000, 1]).should == [100000000, 1]
make_change(1000001, [1000000, 2, 1]).should == [1000000, 1]
end
it "should not be naive (by James)" do
make_change(24, [10, 8, 2]).should == [8, 8, 8]
make_change(11, [10, 9, 2]).should == [9, 2]
end
it "should have a good pruning" do
make_change(19, [5, 2, 1]).should == [5, 5, 5, 2, 2]
make_change(39, [5, 2, 1]).should == [5, 5, 5, 5, 5, 5, 5, 2, 2]
end
it "should work with Swiss paper money" do
money = [1000,500,200,100,50,20,10,5,2,1]
make_change(1789, money).should == [1000,500,200,50,20,10,5,2,2]
end
it "should be nice to tho_mica_l" do
money = [97, 89, 83, 79, 73, 71, 67, 61, 59, 53, 47, 43, 41, 37,
31, 29, 23, 19, 17, 13, 11, 7, 5, 3]
make_change(101, money).should == [89, 7, 5]
make_change(4563, money).should == [97, 97, 97, 97, 97, 97, 97,
97, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97,
97, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97,
97, 97, 97, 89, 7, 5]
end
it "should fail with a combination trick (vsv)" do
make_change(2**10-1, (1..10).map{|n| 2**n}).should == nil
make_change(2**100-1, (1..100).map{|n| 2**n}).should == nil
end
end
with good performances ;-)
..........
Finished in 0.095362 seconds
10 examples, 0 failures
It's basically a min-max algorithm (min only) with alpha-beta pruning
(alpha only). An example with (24, [10, 8, 2])
24, [10, 8, 2], alpha=Infinity
24: tested coin 10 -> 14, [10, 8, 2], Infinity
14: tested coin 10 -> 4, [2], Infinity
4: one coin stands -> return [2, 2]
14: tested coin 8 -> 6, [2], alpha=2 (previous solution (at this
level) is [10, 2, 2] -> length - 1)
6: one coin stands and we need 3 coins which is bigger than
alpha, fail! -> return nil
24: tested coin 8 -> 16, [8, 2], alpha=3 (previous solution is [10,
10, 2, 2])
16: tested coin 8 -> 8, [8, 2], alpha=2
8: amount is a known coin, win! -> return [8]
16: tested coin 2 -> 14, [2], alpha=2
14: one coin stands and we need 7 coins which is bigger than
alpha, fail! -> return nil
24: tested coin 2 -> 22, [2], alpha=2 (previous solution is [8,8,8])
22: one coin stands but we need 11 coins which is far bigger than
alpha, fail! -> return nil
I had a lot of fun with this one coz it was my first play with rspec and
ruby -r profile to spot the weak parts.
Cheers,
-- Yoan
.
- References:
- [QUIZ] Making Change (#154)
- From: Ruby Quiz
- [QUIZ] Making Change (#154)
- Prev by Date: Re: Making Change (#154)
- Next by Date: Re: Making Change (#154)
- Previous by thread: Re: Making Change (#154)
- Next by thread: Re: Making Change (#154)
- Index(es):
Relevant Pages
|
