Making Change (#154)

[bbazzarrakk]

2008/1/27, Paolo B. [email protected]:

worklist = [0]

parents[a] is nil if the solution for amount “a” has not been found
etc., until the solution is found for the requested amount (see the
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

these are the results of vsv’s tests and your script with ruby 1.8.6 and
ruby 1.9.

paddor@pantoo ~ $ ruby --version
ruby 1.8.6 (2007-12-03 patchlevel 113) [x86_64-linux]
paddor@pantoo ~ $ ruby19 --version
ruby 1.9.0 (2008-01-28 revision 15294) [x86_64-linux]
paddor@pantoo ~ $ ruby -rbonzini vsv.rb
Loaded suite vsv
Started
…
Finished in 0.87486 seconds.

9 tests, 631 assertions, 0 failures, 0 errors
paddor@pantoo ~ $ ruby19 -rbonzini vsv.rb
Loaded suite vsv
Started
…
Finished in 0.245152151 seconds.

9 tests, 631 assertions, 0 failures, 0 errors

can i see the sources of your gnu smalltalk solution?

[bbazzarrakk]

I still can’t manage
make_change(p10-1, (1…20).map{|n|pn})
for any prime p (and who can?)

Actually, if I’m not totally mistaken, handling primes is a
generalization of the even/odd optimization. The enclosed code
(ruby19)
includes such checks. Unfortunately, this optimization takes some
time
and makes the code about 2-3 times slower than my first submission (I
assume the optimization could be further optimized :-).

Regards,
Thomas.

require ‘mathn’

def make_change(amount, coins = [25, 10, 5, 1])
return nil if coins.empty? or !amount.kind_of?(Integer)
# Collect the coins’ prime factors.
factors = Hash.new {|h, c| h[c] = Hash[c.prime_division]}

changer = ->(amount, coins, max_size) do
    return [] if amount == 0
    return nil if coins.empty? or max_size <= 0
    cf = Hash.new(0)
    coins.each {|c| c != 0 && factors[c].each {|f, n| cf[f] += 1}}
    # If all coins have a common prime factor but this prime is

no
# factor of amount, then we cannot build a sum equal the
amount
# with these coins.
return nil if cf.any? {|f, n| n == coins.size && amount % f !=
0}
set = nil
coins = coins.dup
until coins.empty?
coin = coins.shift
next if amount < coin
n_coins = amount.div(coin)
break if n_coins > max_size
n_coins.downto(1) do |j|
other = changer.call(amount - coin * j, coins,
max_size - j)
if other
set = ([coin] * j) + other
max_size = set.size - 1
end
end
end
return set
end

coins = coins.sort_by {|a| -a}
coins.reject! {|c| c == 0 || c > amount}
changer.call(amount, coins, amount)

end

[bbazzarrakk]

On Jan 28, 2008, at 10:24 AM, tho_mica_l wrote:

Here is an possible overview that includes only basic tests most
people agreed on:

Thanks!

James Edward G. II

[bbazzarrakk]

Has anyone done time comparisons of the submissions? I’m just curious
at what the fastest strategies have been.

Well, this is somewhat subjective.

Here is an possible overview that includes only basic tests most
people
agreed on:

  user     system      total        real

solution_eric.rb 0.380000 0.000000 0.380000 ( 0.380000)
solution_gray.rb 3.295000 0.000000 3.295000 ( 3.304000)
solution_ludtke.rb 1.552000 0.000000 1.552000 ( 1.553000)
solution_paolo.rb 0.942000 0.190000 1.132000 ( 1.171000)
solution_paolo_eric.rb 0.751000 0.190000 0.941000 ( 0.972000)
solution_porth.rb 0.661000 0.000000 0.661000 ( 0.661000)
solution_tml1.rb 0.050000 0.000000 0.050000 ( 0.050000)
solution_tml2.rb 0.200000 0.000000 0.200000 ( 0.200000)
solution_yoan.rb 0.241000 0.000000 0.241000 ( 0.281000)

I excluded solutions returning unexpected results, caused errors
(with
ruby19) and solutions that took considerably longer than this
selection
to solve the cases listed below.

As always with such listings, another composition of the tests would
result in a totally different table. From other test runs that also
included more exotic tests I’d say that Paolo’s solution performs
much
better than it would look on the basis of this table. It is also one
of
the solutions that deal well with all sorts of crazy input.

Here are the tests I used (I used “print ‘x’” to identify solutions
returning unexpected results, which explains the parentheses and the
!=…). The files are saved in solution_NAME.rb:

Benchmark.bm do |x|
Dir[‘solution_*.rb’].each do |f|
load f
x.report(f) do
20.times do
(make_change(14, [10,7,3]) || []).sort != [7, 7]
(make_change(14, [10, 7, 1]) || []).sort != [7, 7]
(make_change(10, [10, 7, 1]) || []).sort != [10]
(make_change(7, [10, 7, 1]) || []).sort != [7]
(make_change(0)) != []
(make_change(14, [10, 5, 3]) || []).sort != [3, 3, 3,
5]
(make_change(11, [10,9,2]) || []).sort != [2, 9]
(make_change(297, [100, 99, 1]) || []).sort !=
[99,99,99]
(make_change(397, [100, 99, 1]) || []).sort !=
[99,99,99, 100]
(make_change(497, [100, 99, 1]) || []).sort !=
[99,99,99, 100,100]
(make_change(1000001, [1000000, 1]) || []).sort != [1,
1000000]
(make_change(39, [25, 10, 5, 1]) || []).sort.reverse !
= [25, 10, 1, 1, 1, 1]
(make_change(14, [10, 7, 1]) || []).sort.reverse !=
[7, 7]
(make_change(0, [25, 10, 5, 1])) != []
(make_change(1000001, [1000000, 1]) ||
[]).sort.reverse != [1000000, 1]

            (make_change(1000001, [1000000, 2, 1]) ||

[]).sort.reverse != [1000000, 1]
(make_change(24, [10, 8, 2])) != [8, 8, 8]

            (make_change(11, [10, 9, 2]) || []).sort.reverse !=

[9, 2]
(make_change(19, [5, 2, 1]) || []).sort.reverse != [5,
5, 5, 2, 2]
(make_change(39, [5, 2, 1]) || []).sort.reverse != [5,
5, 5, 5, 5, 5, 5, 2, 2]
money = [1000,500,200,100,50,20,10,5,2,1]
(make_change(1789, money) || []).sort.reverse !=
[1000,500,200,50,20,10,5,2,2]
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) || []).sort.reverse != [89,
7, 5]
# print ‘x’ if (make_change(4563, money) ||
[]).sort.reverse != [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
end
end
end

[bbazzarrakk]

Here is an possible overview that includes only basic tests most
people agreed on:

I excluded vsv’s solution because it caused an error. I now realized
that this was because me loading mathn.

solution_vsv.rb 0.180000 0.000000 0.180000 ( 0.180000)

regards,
Thomas.

[bbazzarrakk]

Thanks +1 !

Carl

[bbazzarrakk]

On Jan 28, 11:21 am, tho_mica_l [email protected] wrote:

solution_porth.rb 0.661000 0.000000 0.661000 ( 0.661000)
solution_tml1.rb 0.050000 0.000000 0.050000 ( 0.050000)
solution_tml2.rb 0.200000 0.000000 0.200000 ( 0.200000)
solution_yoan.rb 0.241000 0.000000 0.241000 ( 0.281000)

Those times are awfully small, and I wonder if they’re masking some
useful differences and magnifying some less meaningful differences.

For example, I have a test that I’ve been using, which combines
Phrogz’s, vsv’s, and some of my own. When running with Ruby 1.8.6, I
get:

Paolo: 27.919662 s
Eric: 25.756986 s
tho_mica_l_1: 20.899582 s (note: modified for Ruby 1.8.6)
Paolo (w/ Eric mod): 19.207968 s

And that gives a different sense than tho_mica_l’s solution being 19
times faster than Paolo’s.

So I suspect depending on whether you’re using 1.8.6 vs. 1.9, and
whether or not you use test cases that require larger search spaces,
you’re likely to get different results.

Eric

P.S. To convert the tho_mica_l_1 solution for Ruby 1.8.6, I had to add
the odd? and even? methods to Integer and convert ‘changer’ into a
method.

[bbazzarrakk]

On 1/25/08, 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])

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.

Here’s my somewhat simplisitc solution. I just work upwards through
progressively larger sets of coins until I find one that works. I
think the only interesting part is that you can select what to do when
there is no exact match.
-Adam

#select what to do when can’t make exact change
STRATEGY=[:RoundDown,:RoundUp,:Refuse][1]

class Array
def sum
inject(0){|s,v|s+v}
end
end

def minimum_change coins,strategy
case STRATEGY
when :RoundDown
0
when :RoundUp
coins[0]
when :Refuse
nil
end
end

#make amount of change with the fewest possible coins

iterate through progressively larger sets of coins

until you find a set that adds up to amount,

def make_change(amount, coins = [25, 10, 5, 1])
change = Array.new(amount+1)
coins=coins.sort
#handle cases where change is less than smallest coin
return [minimum_change(coins,STRATEGY)] if amount < coins[0]
#initial sets are one coin
sets = coins.map{|c|[c]}
loop do
sets.each{|set|
return set.reverse if set.sum==amount
# record the first set to match each sum (incase we can’t make
exact change)
change[set.sum]||=set
}
#generate more sets by adding 1 of each coin to existing sets
#only keep unique sums smaller than target amount.
sets = sets.inject([]){|result,set|
newsets=coins.map{|c|(set+[c]).sort}.find_all{|s|s.sum<=amount }
result+newsets
}.uniq
#if we can’t make exact change, reduce amount until we can
if sets.empty?
amount -=1 until change[amount]
#use STRATEGY to round up or down
minchange=minimum_change(coins,STRATEGY)
return (change[amount].reverse<<minchange)-[0] if minchange
return minchange
end
end
end

[bbazzarrakk]

Those times are awfully small

I also ran it with more iterations but the ranking remains about the
same.

For example, I have a test that I’ve been using, which combines
Phrogz’s, vsv’s, and some of my own.

I also have an extended set of test cases that builds on whatever was
posted to the list. For this comparison I only selected test cases
for
which a sufficient number of solutions returned results in finite
time
(I’m doing this on a 4-yrs old notebook, so time is limited :-).

And that gives a different sense

This is also about what I get when I run phrogz’s test cases. But
these
test cases don’t seem representative somehow. phrogz’s cases are
rather
suited to test the program’s correctness not so much to measure its
general performance I’d say. (BTW I would never claim that my
solution
is in general 19 times faster than anyone of other solution in all
possible situations. I know my code well enough to know how to make
it
run in circles for quite some time.)

In a “natural” setting, I think something like this

default_change = [25, 10, 5, 1]
30.times do |a|
    make_change(a ** 2, default_change)
end

is more likely to be a problem the program has to solve. So, my
reasoning is that a good solution should solve these standard cases
fast
and should not go wild on “strange” input, which my first solution
does
with certain input. (But most other solutions do too.)

I also think all solutions in this listing perform pretty well on
these
general cases. This would become obvious if one included a brute
solution that always does a full search.

I think Paolo’s solution is cool because it’s really compact, because
it
avoids recursion and because it doesn’t need to include optimizations
for special cases. My solution on the other hand needs special case
handling in order to avoid deep recursion, which ruby19 doesn’t like
too
much as it seems. But then, with “normal” input the number of
recursions
should be limited since coin values are usually selected in a way to
make it easy for people to give change. This probably is the reason
for
why there aren’t any 17cent coins around – which would be fun
though.
So maybe a depth-first search is the more appropriate approach for
this
problem after all. Or maybe not?

Anyway, I said this listing is rather subjective, didn’t I.

Regards,
Thomas.

[bbazzarrakk]

should be limited since coin values are usually selected in a way to
make it easy for people to give change.

Of course. If every coin is a multiple of the immediately smaller
coin, the greedy algorithm is ok. It happens to be with the euro
coins and Swiss franc coins (both have 200-100-50-20-10-5 cent coins,
and euro has additionally 2-1 cent coins), so there is probably a less
stringent sufficient condition.

why there aren’t any 17cent coins around – which would be fun though.

There was a puzzle on DDJ asking for the optimal set of coins (i.e.
the one giving the smallest number of coins on average). I don’t have
it at hand but the results were weird, I recall.

[bbazzarrakk]

On Jan 28, 2008, at 3:14 PM, Paolo B. wrote:

why there aren’t any 17cent coins around – which would be fun
though.

There was a puzzle on DDJ asking for the optimal set of coins (i.e.
the one giving the smallest number of coins on average). I don’t have
it at hand but the results were weird, I recall.

The book this quiz is based on explores that topic. It recommended we
adopt an 18 cent coin, among other variations.

James Edward G. II

[bbazzarrakk]

On Jan 27, 2008 7:21 PM, Jesús Gabriel y Galán [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

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 am having problems with the 100001, [100000, 1] situation when I
think I shouldn’t so there might be a bug in there. Didn’t have time
to check it yet. I’ll try to find the problem if I have time.

I’ve had 5 minutes and I solved this issue. I wanted shift/push
but I was using pop/push so was trying the combinations
of lower coins before the big ones, leading to more tests
than necessary. Now this case finds a solution with the 100000
coin and quickly prunes the rest. Still having problems with the
2**n stuff but I’m pretty sure I won’t have time to look at it
anymore…

Anyway, fun quiz as usual, thanks for this.

Jesus.

class Solution
attr_reader :remaining_amount, :coins, :usable_coins

def initialize(amount, usable_coins, coins=[])
@remaining_amount = amount
@usable_coins = usable_coins.sort.reverse.select {|x| x <= amount}
@coins = coins
end

def explode
# check if this is an invalid branch or already a solution
return [] if @usable_coins.empty?
return [] if @usable_coins.last > @remaining_amount
return [] if @remaining_amount == 0
# generate two possible scenarios: use a coin of the highest value
and generate a Solution with less remaining amount
# but the same set of usable_coins or remove the highest value and
generate a Solution with the same remaining amount
# but less usable_coins
first = Solution.new(@remaining_amount - @usable_coins.first,
@usable_coins, (@coins.dup) << @usable_coins.first)
second = Solution.new(@remaining_amount, @usable_coins[1…-1],
@coins)
[first, second]
end

def is_solution?
@remaining_amount == 0
end

def number_of_coins
@coins.length
end

def to_s
“[#{@coins.inspect}, #{@remaining_amount},
#{@usable_coins.inspect}]”
end
end

def make_change(amount, coins = [25, 10, 5, 1])
queue = []
solution_so_far = nil
length_so_far = nil
queue << Solution.new(amount, coins)
until queue.empty?
current = queue.shift
# prune branches that would result in a worse solution
next if solution_so_far && current.number_of_coins >= length_so_far
if current.is_solution?
solution_so_far = current
length_so_far = current.number_of_coins
else
queue.push(*current.explode)
end
end
return [] if solution_so_far.nil?
solution_so_far.coins
end

[bbazzarrakk]

It happens to be with the euro
coins and Swiss franc coins (both have 200-100-50-20-10-5 cent coins,
and euro has additionally 2-1 cent coins), so there is probably a less
stringent sufficient condition.

#1
My code does backtracking if it runs into a dead end. I’m not sure if
this qualifies as greedy – but you’re the wizard and I may be wrong.
The problem with primes input (see vsv’s test cases) is that in this
case, it does an exhaustive search then and recurse more often than
those 8000 times or so that are good for ruby.

#2
So I made some real-world-like tests based on Euro Money * 100. The
solutions had to give change for a random amount N times.

C Porth’s solution turned out to be lightning fast on these standard
cases. tml3 is tml2 with the the safety bolts removed. Since Euro
coins
include 1cent coins there always is a good solution and backtracking
can
be minimized. Behold!

N=1000
user system total real
dominik 13.679000 0.000000 13.679000 ( 13.980000)
eric 205.015000 0.951000 205.966000 (210.522000)
paolo 191.516000 3.074000 194.590000 (198.816000)
paolo_eric 158.618000 3.275000 161.893000 (165.488000)
porth 0.811000 0.000000 0.811000 ( 0.811000)
tml1 0.951000 0.000000 0.951000 ( 0.971000)
tml2 5.258000 0.000000 5.258000 ( 5.388000)
tml3 0.651000 0.000000 0.651000 ( 0.651000)
vsv 4.907000 0.000000 4.907000 ( 5.008000)
yoan 10.114000 0.000000 10.114000 ( 10.345000)

So Eric was probably right. There were some space issues involved.

Here is the code for doing the benchmark (in case you’d like to do
this
yourself at home and maybe create your own coin sets):

#!/usr/bin/env ruby

require 'benchmark'

solutions = [
    'tml1', 'tml2', 'tml3',
    'porth',
    'vsv',
    'yoan',
    'paolo', 'paolo_eric',
    'eric',
    'dominik',
]

# N = 100
# X = 3000

N = 1000
X = 30000

# N = 10000
# X = 100000

# In Euro Cents.
COINS = [50000, 10000, 5000, 2000, 1000, 500, 200, 100, 50, 20,

10, 5, 2, 1]

puts "Building cache"
cache = {}
load 'solution_tml3.rb'
X.times do |a|
    if a % 1000 == 0
        STDOUT.print '.'
        STDOUT.flush
    end
    cache[a] = make_change(a, COINS)
end
puts

Benchmark.bm(12) do |x|
    solutions.each do |f|
        load "solution_#{f}.rb"
        x.report(f) do
            N.times do |i|
                money  = rand(X)
                change = make_change(money, COINS)
                if cache[money] != change
                    STDOUT.puts "CONFLICT #{money}:

#{change.inspect} <=> #{cache[money].inspect}"
STDOUT.flush
end
end
end
end
end

BTW, I’m sure Grandma’ would love 18 cent coins.

Regards,
Thomas.

[bbazzarrakk]

Hi, I’m Atsuhiro.
this is the first time I contribute to Ruby-forum.

I find one solution for Ruby-Quiz154.

the following is my solution
(To tell the truth, I have only one-month programming experience and
Ruby is the first programming language I choose.So, I’ll glad if you
point out some problem in my solution.)

class Making_change
$change = []
def make_change(amount,coins=[25,10,5,1])
@coing = coins
if amount < 0
print “amount should be a positive integer \n”
exit
end

coins.each do |i|
if amount >= i
$change << i
amount = amount-i
redo
elsif amount == 0
return $change
else next
end
end
end
end

a = Making_change.new
p a.make_change(52) # => [25,25,1,1]
p a.make_change(-30) # => amount should be a positive integer

[bbazzarrakk]

On Jan 29, 2008, at 4:33 PM, Atsuhiro T. wrote:

Hi, I’m Atsuhiro.
this is the first time I contribute to Ruby-forum.

I find one solution for Ruby-Quiz154.

Welcome!

the following is my solution
(To tell the truth, I have only one-month programming experience and
Ruby is the first programming language I choose.So, I’ll glad if you
point out some problem in my solution.)

Wow. I promise I wasn’t solving problems this hard when I was so
new. Great work!

Youe code does have a small problem with variable scoping. To see it,
change the last few lines to:

a = Making_change.new
p a.make_change(52)
p a.make_change(52)

and run it.

We all run into this when we are new and quickly learn that global
variables are almost never what we want. In this case, your global
$change variable is the problem.

I’ll stop talking there and see if that’s a big enough hint to help
you fix it. If not, just let us know and I’ll give more hints.

Again, I’m impressed!

James Edward G. II

[bbazzarrakk]

Wow. I promise I wasn’t solving problems this hard when I was so
new. Great work!

Hi, I’m really glad to get such a message from you,the author of
Ruby-Quiz!!Thank you so much!

a = Making_change.new
p a.make_change(52)
p a.make_change(52)

I tried this code and found my problem, I also find out why I shouldn’t
use global $change variable.Thank for your advice.I’ll try not to make
this kind of mistakes again.

I’ll try the next Ruby-Quiz, though many of quizes are really difficult
for me^^

AtsuhiroTeshima

[bbazzarrakk]

On Jan 29, 2008 11:33 PM, Atsuhiro T. [email protected]
wrote:

Hi, I’m Atsuhiro.
this is the first time I contribute to Ruby-forum.

Hi, welcome to the Ruby community…

the following is my solution
(To tell the truth, I have only one-month programming experience and
Ruby is the first programming language I choose.So, I’ll glad if you
point out some problem in my solution.)

The first problem is that your solution returns
[10,1,1,1,1] for make_change(14, [10,7,1])
when the correct answer would be [7,7].

Next, some comments on the code

class Making_change
$change = []

you don’t need a global variable here.
If you wanted to store the latest change
given by an instance of this class (but for the
problem at hand you don’t even need that), you could
use a instance variable of the class:

@change

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

here you are storing the coins in an instance variable,
but it’s not needed since every invocation of the make_change
method carries the coins array, so it’s not some state you
would need to store anyway, so I’d just remove this altogether.
As you should remove the $change also, change should be
a local variable to this method so:

change = []

  elsif amount == 0
     return $change
  else next
  end

end
end
end

To avoid iterating so much, check at Ilan B. solution.
For each coin value, making a division you would know
how many of this coins can fit, something like (not tested):

num = amount / coin
num.times {change << coin}
amount %= coin

a = Making_change.new
p a.make_change(52) # => [25,25,1,1]
p a.make_change(-30) # => amount should be a positive integer

Anyway, this algorithm has the problem of the two middles:

p a.make_change(14, [10,7,1]) # => [10,1,1,1,1], should be [7,7]

Hope this helps,

Jesus.

[bbazzarrakk]

i found a solution that can process inputs like “make_change
1_000_000_000_000 4 3 7 6 85 98 54 22 3423 34 509 435 243 345” in <
0.2 sec. (in super no-optimization / ultra-verbose mode)

• no recursion & stack
• possibility to add coins after the processing don’t affect the
  previous memoizing array at all
• it is simple do it manual (pencil / notebook), cause all to do is to
  take note of some x/y integer part and rest

i haven’t seen all solutions posted, so i don’t know if this algorithm
is just been presented, if no, then i’ll post in next minutes

(sorry for my bad english)

[bbazzarrakk]

On Jan 25, 5:50 pm, 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

Hi,

I’ve had some connectivity issues, so here is my a bit too late
solution to this:

#!/usr/bin/env ruby

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

p amount

p coins

best_change = Array.new(amount + 1)
0.upto(amount) do |n|
best_change[n] = coins.map do |c|
n - c < 0
? []
: (best_change[n - c].empty? && n != c
? []
: [c] + best_change[n - c])
end.delete_if{ |a| a.empty? }
.sort{ |a, b| a.size <=> b.size }[0] || []
end

p best_change

best_change[amount]
end

if FILE == $0

require ‘test/unit’

class TestMakeChange < Test::Unit::TestCase
def setup
@_1071_coins = [10, 7, 1]
@ua_coins = [50, 25, 10, 5, 2, 1]
@au_coins = [200, 100, 50, 20, 10, 5]
end

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

def test_change_equal_to_one_coin
  assert_equal([10], make_change(10, @_1071_coins))
  assert_equal([7], make_change(7, @_1071_coins))
end

def test_two_middles
  assert_equal([7, 7], make_change(14, @_1071_coins))
end

def test_us
  assert_equal([25, 10, 1, 1, 1, 1], make_change(39))
  assert_equal([25, 25, 25, 25], make_change(100))
  assert_equal([25, 25, 25, 10, 10, 1, 1, 1, 1], make_change(99))
end

def test_ua
  assert_equal([2, 2], make_change(4, @ua_coins))
  assert_equal([25, 10, 2], make_change(37, @ua_coins))
  assert_equal([50, 25, 10, 10, 2, 2], make_change(99, @ua_coins))
end

def test_24_1082
  assert_equal([8, 8, 8], make_change(24, [10,8,2]))
end

def test_au
  assert_equal([], make_change(1, @au_coins))
  assert_equal([20, 10, 5], make_change(35, @au_coins))
end

def test_15_1053
  assert_equal([5, 3, 3, 3], make_change(14, [10, 5, 3]))
end

def test_x97
  assert_equal([99, 99, 99], make_change(297, [100, 99, 1]))
  assert_equal([100, 99, 99, 99], make_change(397, [100, 99, 1]))
  assert_equal([100, 100, 99, 99, 99], make_change(497, [100, 99,

1]))
end

def test_4563
  assert_equal([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],
               make_change(4563, [97, 89, 83, 79, 73, 71, 67, 61,
                                  59, 53, 47, 43, 41, 37, 31, 29,
                                  23, 19, 17, 13, 11, 7, 5, 3]))
end

def test_huge

assert_equal([], make_change(1_000_001))

end

end

end

Yep, I know it’s ugly, but I hadn’t much time to eliminate that
`best_change[0]’ corner case…

Great Quiz anyway!

[bbazzarrakk]

On Jan 30, 2008, at 4:38 AM, Atsuhiro T. wrote:

I’ll try the next Ruby-Quiz, though many of quizes are really
difficult
for me^^

Some are for me too.

James Edward G. II