From: Yoan Blanc <greut.lists@...>
Date: 2008-01-28T01:49:23+09:00
Subject: [SOLUTION][QUIZ] Making Change (#154)

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