Making Change (#154)

Ruby
41

On Jan 26, 6:45 pm, James G. [email protected] wrote:

I leave that to your best judgement. We should probably remember that
not all places in the world have a 100 cent dollar though.

James Edward G. II

my best ‘judgement’ so far can be formalized in the following code:

require ‘test/unit’
class TestMakeChange < Test::Unit::TestCase

def test_no_solution
    assert_equal( nil, make_change( -1 ) )
    assert_equal( nil, make_change( 1, [] ) )
    assert_equal( nil, make_change( 1.5, [2, 1] ) )
    assert_equal( nil, make_change( 1, [2] ) )
    assert_equal( nil, make_change( 7, [5, 3] ) )
    # 1023 instead of 127 is too slow :(
    assert_equal( nil, make_change( 127, (1..10).map{ |n|

2**n } ) )
end

def test_no_change
    assert_equal( [], make_change(0) )
end

def test_one_coin
    a = [*(1..100)]
    for i in a
        assert_equal( [i], make_change(i, a) )
    end
end

def test_ones
    a = [*(1..100)]
    for i in a
        assert_equal( [1]*i, make_change( i, [1]+a[i..-1] ) )
    end
end

def test_two_middles
    for i in 1..100
        b = i*10
        m = b/2+1
        assert_equal( [m, m], make_change( m*2, [b, m, 1]) )
    end
end

def test_first_and_last
    for i in 1..10
        b = i*100
        assert_equal( [b, 1], make_change( b+1, (1..b).to_a) )
    end
end

def test_binary
    a = (0..7).map{ |n| 2**n }.reverse!
    for i in 0..255
        bits = a.inject([i]){ |r,x| r[0]<x ? r :
                                   [r[0]-x, *(r[1..-1]<<x)]
                              }[1..-1]
        assert_equal( bits, make_change( i, a ) )
    end
end

def test_primes
    a = [3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53,

59, 61, 67, 71, 73, 79, 83, 89, 97]
a.reverse!
for i in 1…a.size
v = a[0,i].inject(){|r,n|r+n}
r = make_change( v, a )
assert( r.size <= i )
end
for i in 1…a.size/2
assert_equal( 2, make_change( a[i]+a[-i], a ).size )
end
# by tho_mica_l
assert_equal( [97]*46 + [89, 7, 5], make_change( 4563, a ) )
end

def test_misc
    assert_equal( [25, 10, 1, 1, 1, 1], make_change( 39 ) )
    assert_equal( [9, 2], make_change( 11, [10, 9, 2] ) )
    assert_equal( [5, 2, 2, 2], make_change( 11, [10, 5, 2] ) )
    assert_equal( [8]*3, make_change( 24, [10, 8, 5, 1] ) )
    assert_equal( [9]*3, make_change( 27, [10, 9, 5, 1] ) )
    #
    for i in 1..8
        assert_equal( [9]*i, make_change( 9*i, [10,9,1] ) )
        assert_equal( [10]+[9]*i, make_change( 10+9*i,

[10,9,1] ) )
end
end
end

BRs
Sergey

42

On Jan 26, 4:10 pm, Denis H. [email protected] wrote:

Here’s another test case:

make_change 1000001, [1000000, 1] # => [1000000, 1]
AND complete in a reasonable time (avoid brute force searches)

It should be obvious, but I’ll point it out anyway: since make_change
is the knapsack problem (which is NP-complete), it is impossible to
have the solution always be optimal without implementing a brute force
search. You can prune it somehow, but there will always be a worst
case where you have to search more or less the whole search space.

That said, would you say 5 minutes (3 seconds for 10001, 30 seconds
for 100001, 300 for 1000001) is a reasonable time?

Paolo

43

On Jan 25, 4:24 pm, James G. [email protected] wrote:

Are there any advanced combinations of change/array of coins which
are likely to fail
on some implementations?

Is it ok to share test cases before the spoiler?

Sure.

James Edward G. II

I found this combination problematic:
make_change(1023, (1…10).map{|n| 2**n}) # must be nil

44

What dh probably meant is that it’s quite obvious that there is no
better solution for 1000001 with the “coins” [1000000, 1] than
[1000000, 1]. The program shouldn’t need to add 1000001-times 1 to
find this out.

45

On Jan 27, 2:04 pm, tho_mica_l [email protected] wrote:

What dh probably meant is that it’s quite obvious that there is no
better solution for 1000001 with the “coins” [1000000, 1] than
[1000000, 1]. The program shouldn’t need to add 1000001-times 1 to
find this out.

Right, but what I’ve said is that, for all correct solutions, there
will be a case where it will do seemingly stupid trials first. I’ll
work on a “fast” solution. and see if it outperforms the “slow”
solution in more general cases too.

Paolo

46

vsv wrote:

end

    assert_equal( nil, make_change( 127, (1..10).map{ |n|

2**n } ) )

I managed to get a solution (which is nil) even for this:

make_change( 2100-1, (1…100).map{ |n| 2n } )

in a reasonable time.

– Yoan

47

Here’s my solution, attached and pastied here:
http://pastie.caboo.se/pastes/144060

Its recursive, can solve the simplest problems, but soon gets
overwhelmed by
cases like Yoan’s Swiss money test. I killed it after 12 hours.
Solutions are
stored as hashes of coin-value => count (if you want it in the array
form its
easy to convert - see line 59). Its also accepts a score function, and
so can
do things like:

jesse@ricercar $ ./make_change.rb 21 1 7 10 least
0 of 1-coins
3 of 7-coins
0 of 10-coins
3 total
jesse@ricercar $ ./make_change.rb 21 1 7 10 variety
4 of 1-coins
1 of 7-coins
1 of 10-coins
6 total
jesse@ricercar $ ./make_change.rb 21 1 7 10 most
21 of 1-coins
0 of 7-coins
0 of 10-coins
21 total

I played around with a few optimizations, like storing the coins array
once
and passing indices instead of duplicating it on line 18, but they
hardly
made a difference.

-Jesse

48

Here is my second attempt:

def make_change(a, list = [25, 10, 5, 1])

to pass testcases :stuck_out_tongue:

return nil if a < 0
return nil if a != a.floor

parents = Array.new(a + 1)
parents[0] = 0
worklist = [0]
while parents[a].nil? && !worklist.empty? do
base = worklist.shift
list.each do |coin|
tot = base + coin
if tot <= a && parents[tot].nil?
parents[tot] = base
worklist << tot
end
end
end

return nil if parents[a].nil?
result = []
while a > 0 do
parent = parents[a]
result << a - parent
a = parent
end
result.sort!.reverse!
end

parents[a] is nil if the solution for amount “a” has not been found
yet, and a-c if the solution is the same as the solution for amount “a-
c” plus a coin of value “c”. The solution is reconstructed in the
second while loop.

My first solution used an 1.upto(a) loop to compute the optimal
solution for make_change(1), then for make_change(2), etc. This was a
classic dynamic programming style where lower-cost solutions replace
older ones as they are found. In this solution, instead of computing
subproblem solutions in order of amount, I compute solutions in order
of cost: first all solutions of cost 1, then all solutions of cost 2,
etc., until the solution is found for the requested amount (see the
parents[a].nil? test). It is interesting that in this way we don’t
even need to store the solutions’ costs.

The worst case is when there’s no solution and it has cost O(a |
list|). I didn’t make any attempt at optimizing it.

The performance is good; vsv’s testcases run in 10 seconds (compared
to 30 for my 1.upto(a) solution).

I tried running a similar program in GNU Smalltalk and the results
were disappointing for Ruby 1.8: GNU Smalltalk was about 10 times
faster for this solution, and 18 times faster for the slower
solution. The ratio goes down from 18 to 10 probably because variable-
size collection in Smalltalk require an OrderedCollection, which is
written in 100% Smalltalk (unlike Ruby’s Arrays and Smalltalk’s fixed-
size Arrays). I’d be very interested if people ran it under Ruby 1.9
or Rubinius and gave times for it.

Paolo

49

This is my solution. Handles the basic cases very well, but gets
overwhelmed by complicated ones.
http://pastie.caboo.se/private/mk82p5c00tqwhqmzigqbxw

50

Here’s my submission to the making change quiz. As Paolo mentioned,
this is the Knapsack problem which means that finding the absolute
optimal answer can be extremely expensive. One way of thinking of the
problem is as an N-dimensional search problem, where N is the number
of coins available. The key is to limit the variance in each dimension
to restrict the search space.

We start with a list of coins: [C0, C1, … Cn) and must end up with a
count for each coin such that

V = X0C0 + X1C1 + … + XnCn

The counts all have to be positive and V has to match the target value
supplied by the user. It’s possible that there’s no set of counts that
will produce a correct answer. The ‘best’ answer is the one that
contains the least number of coins.

My approach is to take each coin in turn and vary it between a lower
bound and an upper bound. For each count, I try to match the value
with the remaining coins. In order to minimise the search space as
much as possible, I compute the bounds as follows:

For the lower bound, first I compute the least common multiple of the
coin and the higher value coins (taking the largest one that won’t put
be over the value), and then use the highest multiple of that which is
less than the value.

For example, if the problem is make_change(75, [30, 5, 1]) and I’m
varying ‘5’, then the lcm of 5 and [30] is 30 and the lower bound is 60.

Then I compute the same thing for the lower value coins except that I
combine all of them (giving me the smallest number whereby changing
lower value coins can no longer improve the solution). The best of
these two bounds is used as the lower bound.

The upper bound is the highest count of the coin which is still below
the target value.

In each iteration, I recursively call make_change with the remaining
value and coins.

Here’s a couple of runs with logging to show the effect. Notice that
in both cases, it doesn’t waste time trying permutations of ‘2’ and
‘1’ that could not produce a better result.

$ ruby -v make_change.rb 1000001 1000000 2 1
ruby 1.8.6 (2007-09-23 patchlevel 110) [powerpc-darwin9.0.0]
make_change 1000001, [1000000, 2, 1]
make_change 1, [2, 1]
make_change 1, [1]
make_change 1, [1000000, 1]
make_change 1, [1]
[1000000, 1]

$ ruby -v make_change.rb 1000001 1000000 999999 2
ruby 1.8.6 (2007-09-23 patchlevel 110) [powerpc-darwin9.0.0]
make_change 1000001, [1000000, 999999, 2]
make_change 1000001, [999999, 2]
make_change 1000001, [2]
make_change 2, [2]
make_change 1, [999999]
make_change 1, [999999, 2]
make_change 1, [2]
make_change 1, [999999]
make_change 1000001, [1000000, 2]
make_change 1, [2]
make_change 1, [1000000]
make_change 2, [1000000, 2]
make_change 2, [2]
make_change 1, [1000000, 999999]
make_change 1, [999999]
make_change 1, [1000000]
[999999, 2]

/dh

make_change.rb:
#!/usr/bin/env ruby

def greatest_common_divisor(a, b)
return a if b == 0
greatest_common_divisor(b, a % b)
end

def least_common_multiple(a, b)
return 0 if a == 0 or b == 0
(a * b) / greatest_common_divisor(a, b)
end

def make_change(value, coins=[])
return [] if value == 0
return nil if coins.empty?

puts “make_change #{value}, #{coins.inspect}” if $VERBOSE

best = nil
coins.each_with_index do |c, i|
lcm = coins[0,i].inject(0) { |memo, val| lcm =
least_common_multiple(c, val); lcm > memo && lcm <= value ? lcm : memo}
start = lcm == 0 ? 0 : (value - (value % lcm)) / c
lcm = coins[i+1,coins.size].inject© { |memo, val|
least_common_multiple(memo, val)}
if lcm != 0
try = (value - (value % lcm)) / c
start = try if try > start && try <= value
end
max = value / c
others = coins.reject {|v| v == c}
start = max if others.empty?
start.upto(max) do |n|
remaining = value - n * c
change = make_change(remaining, others)
next if change == nil
try = [c] * n + change
best = try if best.nil? or try.size < best.size
end
end
best.sort!.reverse! if best
best
end

if $0 == FILE
if ARGV.size == 0
puts “Usage: #{File.basename($PROGRAM_NAME)}
…”
exit
end
value = ARGV.shift.to_i
coins = ARGV.collect {|c| c.to_i}
coins.sort!.reverse!

change = make_change value, coins
if change
puts change.inspect
else
puts “It’s not possible to make #{value} with coins of value
#{coins.inspect}”
end
end

51

This week’s Ruby Q. is to complete a change making function with
this skeleton:

    def make_change(amount, coins = [25, 10, 5, 1])

    end

Your function should always return the optimal change with optimal
being the least amount of coins involved. You can assume you have an
infinite number of coins to work with.

I have two solutions. One is short and sweet, but since it doesn’t use
memoization at all, it is only suitable for small problems. I include
it here because I like how succinct it is.

def make_change_aux(amount, coins)
return [[]] if amount == 0
return [] if coins.empty? or amount < 0
return make_change_aux(amount - coins[0], coins).collect {
|n| n << coins[0]
} + make_change_aux(amount, coins[1 … -1])
end

def make_change(amount, coins = [25, 10, 5, 1])
return make_change_aux(amount, coins).sort {
|a, b| a.size <=> b.size
}.first
end

My second solution uses a M*N in time and space algorithm by building
a table with M rows (one for each amount) and N columns (one for each
coin value). It fills in the table top-to-bottom, keeping the value in
a cell equal to the fewest number of coins so far needed to make that
amount M using only coins[0…N]. The optimal solution is in table[-1]
[-1] if it exists.

def make_change(amount, coins = [25, 10, 5, 1])
return [] if amount <= 0
return nil if coins == nil

coins = [nil] + coins # Use 1-based indexing
table = [[0] * coins.size]
amount.times { table << Array.new(coins.size) }

for i in 1 ... table.size do
  for j in 1 ... table[i].size do
    coin = coins[j]
    poss = [table[i][j - 1]]
    if i >= coin && table[i - coin][j] then
      poss << table[i - coin][j] + 1
    end
    table[i][j] = poss.compact.sort.first
  end
end

# Walk the solution from the last index to the first
return nil unless table[-1][-1]

soln = []
i = table.size - 1
j = table[i].size - 1

while i > 0 && j > 0 do
  if table[i][j - 1] == table[i][j] then
    j -= 1
  else
    soln << coins[j]
    i -= coins[j]
  end
end

return soln

end

This was reasonably fast on most inputs; the pathological inputs with
thousands of coins and an amount in the thousands slows it down quite
a bit though.

-JJ

52

Hi,

Here is my solution. It’s ruby19 only.

The test cases posted in the quiz thread should be solved in no time
(<
1sec). The only case I have found yet that takes some time to solve
is
something like:

make_change(998, [3, 6, 9, 12])
# => nil

We sort the coins in descending order and use this knowledge to cut
of
certain searches.

Regards,
Thomas.

#!/usr/bin/env ruby19

Author:: Thomas Link (micathom AT gmail com)

Created:: 2008-01-25.

def make_change(amount, coins = [25, 10, 5, 1])
# I use the ruby19 syntax here in order to make sure this code
isn’t
# run with ruby18 (because of the return statements).
changer = ->(amount, coins, max_size) do
return [] if amount == 0
return nil if coins.empty? or
max_size <= 0 or
(amount.odd? and coins.all? {|c| c.even?})
set = nil
max_size1 = max_size - 1
coins.each_with_index do |coin, i|
n_coins = amount / coin
# The coin value is getting too small
break if n_coins > max_size
if amount >= coin
if amount % coin == 0
# Since coins are sorted in descending order,
# this is the optimal solution.
set = [coin] * n_coins
break
else
other = changer.call(amount - coin,
coins[i, coins.size],
max_size1)
if other
set = other.unshift(coin)
max_size = set.size - 1
max_size1 = max_size - 1
end
end
end
end
return set
end

coins  = coins.sort_by {|a| -a}
# We don't care about micro-pennies.
amount = amount.to_i
changer.call(amount, coins, amount / coins.last)

end

if FILE == $0
args = ARGV.map {|e| e.to_i}
coins = make_change(args.shift, (args.empty? ? [25, 10, 5, 1] :
args).sort_by {|a| -a})
if coins
puts “#{coins.inject(0) {|a, c| a += c}}/#{coins.size}:
#{coins.join(’ ')}”
else
puts “Please go away.”
end
end

53

Here’s my very simple recursive solution. It has a cache though, so
it’s O(coins.size * amount) like the standard knapsack algorithm.

def make_change(amount, coins = [25, 10, 5, 1])
r = Hash.new{|h,k|
h[k] = k<0 ? [1/0.0,[]] : coins.map{|c| l=h[k-c]; [l[0]+1,l[1]+[c]]
}.min
}.merge(0=>[0,[]])[amount]
r[1] if r[0].to_f.finite?
end

54

There is my solution which I’m proud of :wink:

Parked at Loopia (solution)
Parked at Loopia (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 :wink:

…

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

55

On Jan 25, 8:50 am, Ruby Q. [email protected] wrote:

This week’s Ruby Q. is to complete a change making function with this
skeleton:

    def make_change(amount, coins = [25, 10, 5, 1])

    end

Here’s my solution. Unlike greedy or giving algorithms that round one
way or the other if the exact change cannot be made, mine explicitly
returns nil.

I added an optional argument to choose how to break ties. I figure
this is legal, since it duck types with the method ‘signature’ above.

If multiple solutions exist that have the same number of coins,

the winning answer is determined by the value of ‘avoid_pennies’:

If true, whichever answer gives the biggest of the small change is

used.

If false, whichever answer gives the biggest of the large change

is used.
def make_change( amount, coins=[25,10,5,1], avoid_pennies=true,
recursing=false )

Don’t sort in place, in case the user wants to preserve the coin

array
coins = coins.sort_by{ |coin| -coin }
owed = amount
change = []
coins.each{ |coin|
while owed >= coin
owed -= coin
change << coin
end
}
change = nil unless owed == 0

if recursing
change
else
answers = [ change ]
while coins.shift
answers << make_change( amount, coins, avoid_pennies, true )
end
answers.compact.sort_by{ |answer|
[
answer.length,
-answer.send( avoid_pennies ? :last : :first )
]
}.first
end
end

56

I tried running a similar program in GNU Smalltalk and the results
were disappointing for Ruby 1.8

You aren’t trying to make us convert?

57

My 2 cents …

-Doug Seifert

58

def make_change(amount, coins = [25,10,5,1])
coins.sort.reverse.map{|coin| f = amount/coin; amount %= coin;
Array.new(f){coin} }.flatten
end

ilan

59

On Jan 25, 2008 5:09 PM, Sharon P. [email protected] wrote:

For anyone interested, here are the Australian coin values:
[200, 100, 50, 20, 10, 5] # $2 and $1 are coins. We also have no 1c
or 2c

And in New Zealand we’ve got rid of the 5c coin too. Just another
example of NZ being ahead of Australia :wink:

Hadley

60

solution: Parked at Loopia

specs: Parked at Loopia

Nothing particularly CS-y about my solution. I just started with how I
know to make change from my days in retail and added complexity as more
examples came in. Of note, is the fact I wrapped it in a class. That
was done to make heckling and flogging the code easier.

–R