[QUIZ] Making Change (#154)

[vsv]

On [Sat, 26.01.2008 00:50], Ruby Quiz wrote:
In "Practical Ruby Projects," the author includes a couple of
chapters involving
coin simulations. These simulators are used to explore the
possibilities of
replacing a certain coin or adding a new coin.
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 Gray II

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

 

[vsv]

BTW, is it reasonable to assume amount <= 100 or do we need to prepare
for this one:

def test_huge
assert_equal([...], make_change(1_000_001)
end

?

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 Gray 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( , 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(){ |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+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

 

[Paolo Bonzini]

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

 

[Yoan Blanc]

BTW, is it reasonable to assume amount <= 100 or do we need to prepare
for this one:

def test_huge
assert_equal([...], make_change(1_000_001)
end

?

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 Gray 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 } ) )

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

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

in a reasonable time.

-- Yoan

 

[tho_mica_l]

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.

 

[Paolo Bonzini]

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

 

[Paolo Bonzini]

Here is my second attempt:

def make_change(a, list = [25, 10, 5, 1])
# to pass testcases
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

 

[Dominik Honnef]

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

 

[Denis Hennessy]

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(c) { |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)} <value> <coin>
<coin>..."
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

 

[JJ]

This week's Ruby Quiz 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.size do
coin = coins[j]
poss = [table[j - 1]]
if i >= coin && table[i - coin][j] then
poss << table[i - coin][j] + 1
end
table[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.size - 1

while i > 0 && j > 0 do
if table[j - 1] == table[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

 

[Yoan Blanc]

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

 

[tho_mica_l]

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

 

[tho_mica_l]

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?

 

[Sander Land]

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

 

[Phrogz]

This week's Ruby Quiz 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

 

[Ilan Berci]

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

 

[hadley wickham]

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

Hadley

 

[Phrogz]

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.

Slim2esktop phrogz$ ruby -v
ruby 1.8.6 (2007-09-24 patchlevel 111) [i686-darwin9.1.0]

Slim2esktop phrogz$ time ruby paolo.rb
Loaded suite paolo
Started
.........
Finished in 24.261524 seconds.

9 tests, 25240 assertions, 0 failures, 0 errors

real 0m24.290s
user 0m24.253s
sys 0m0.026s



Slim2esktop phrogz$ ruby190 -v
ruby 1.9.0 (2007-12-25 revision 14709) [i686-darwin9.1.0]

Slim2esktop phrogz$ time ruby190 paolo.rb
Loaded suite paolo
Started
.........
Finished in 10.284006 seconds.

9 tests, 25240 assertions, 0 failures, 0 errors

real 0m10.338s
user 0m10.301s
sys 0m0.036s



Slim2esktop phrogz$ cat paolo.rb
def make_change(a, list = [25, 10, 5, 1])
# to pass testcases
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

require 'test/unit'
N = 40
class TestMakeChange < Test::Unit::TestCase
def test_no_solution
N.times{
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
N.times{
assert_equal( [], make_change(0) )
}
end
def test_one_coin
N.times{
a = [*(1..100)]
for i in a
assert_equal( , make_change(i, a) )
end
}
end
def test_ones
N.times{
a = [*(1..100)]
for i in a
assert_equal( [1]*i, make_change( i, [1]+a[i..-1] ) )
end
}
end
def test_two_middles
N.times{
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
N.times{
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
N.times{
a = (0..7).map{ |n| 2**n }.reverse!
for i in 0..255
bits = a.inject(){ |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
N.times{
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+a[-i], a ).size )
end
# by tho_mica_l
assert_equal( [97]*46 + [89, 7, 5], make_change( 4563, a ) )
}
end
def test_misc
N.times{
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

 

[Randall Potter]

solution: http://pastie.caboo.se/144096

specs: http://pastie.caboo.se/144098

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

 

[Jesús Gabriel y Galán]

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

Your solution gives:

[10,1,1,1,1] for make_change(14, [10,7,1]), instead of [7,7]

But it's cool

Jesus.