[QUIZ] Making Change (#154)

[Paolo Bonzini]

You aren't trying to make us convert?

No, but I admit I had more interest in GNU Smalltalk's performance
than Ruby's. Still I'm myself interested in Ruby 1.9 and Rubinius
performance.

Paolo

 

[Jesús Gabriel y Galán]

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.

This is my solution. It explores a tree where each candidate solution
will generate two others: one using the coin with the maximum possible
value, and another one where the maximum one is not used. When it
finds a solution It prunes candidates that would generate worse
solutions.

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?
queue.each {|x| print x}
puts

current = queue.pop

# 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


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.

Regards,

Jesus.

 

[tho_mica_l]

Here is my solution. It's ruby19 only.

In order to make it pass all of phrogz test cases, this line has to be
inserted right after the def make_change() line:

return nil if coins.empty? or !amount.is_a?(Integer)

regards,
Thomas.

 

[Carl Porth]

Here's my memoized functional solution:

def make_change(amount, coins = [25, 10, 5, 1])
coins.sort! { |a, b| b <=> a }

# memoize solutions
optimal_change = Hash.new do |hash, key|
hash[key] = if key < coins.min
[]
elsif coins.include?(key)
[key]
else
coins.
# prune unhelpful coins
reject { |coin| coin > key }.

# prune coins that are factors of larger coins
inject([]) {|mem, var| mem.any? {|c| c%var == 0} ? mem : mem+
[var]}.

# recurse
map { |coin| [coin] + hash[key - coin] }.

# prune unhelpful solutions
reject { |change| change.sum != key }.

# pick the smallest, empty if none
min { |a, b| a.size <=> b.size } || []
end
end

optimal_change[amount]
end

 

[Eric I.]

My solution is somewhat similar to Paolo's in that it too does a
breadth-first search. It prunes and minimizes the tree a little more
aggressively than Paolo's does. However it's more memory intensive
since it creates a Node instance for every node in the tree, and I
keep a hash to note when a total has already been reached. Paolo
makes use of a very compact fixed-size array Integers that can both
track the tree *and* be used to note when a total has already been
reached. Very nice!

Eric

----

Are you interested in on-site Ruby training that uses well-designed,
real-world, hands-on exercises? http://LearnRuby.com

====

# A solution to RubyQuiz #154.

# Given an amount and a set of coins, the make_change method finds the
# shortest combination of coins that equals the amount, if it's
# possible.

# See http://www.rubyquiz.com/quiz154.html for details.

# The latest version of this solution can also be found at
# http://learnruby.com/examples/ruby-quiz-154.shtml .

# Basically it does a breadth-first search by using a search tree,
# where the depth of a node in the tree equates to how many coins are
# used. The search tree is pruned by not building off of nodes with a
# total that exceeds the desired total or nodes that come to a total
# that has already been found by a previous node. Further, the search
# tree is minimized by avoiding coin combinations that could be
# permutations of others. This is achieved by only adding coins that
# appear at the same position or later from the coinage as we descend
# the tree. For example, if the coinage is [25, 10, 5, 1], then
# descending the tree, all 25 coins will appear before all 10 coins,
# and so forth.

# Note: the coinage does not have to be in any particular order (e.g.,
# sorted), but the list of coins returned will have the coins in the
# same order as in the given coinage.


Node = Struct.new("Node", arent, :coin, :total, :starting_coin)

def make_change(amount, coinage = [25, 10, 5, 1])
root = Node.new(nil, nil, 0, 0) # root of tree with no coins
found_totals = { 0 => root } # track totals found to prune
search
queue = [root] # leaves to process breadth-first

# process items from queue in a tree breadth-first order until
# nothing left to process or right total is found
catchfound) do
until queue.empty?
node = queue.shift
node.starting_coin.upto(coinage.size - 1) do |index|
coin = coinage[index]
new_total = node.total + coin
next if new_total > amount || found_totals[new_total] # prune
new_node =
Node.new(node, coin, new_total, index)
found_totals[new_total] = new_node
throw :found if new_total == amount
queue << new_node
end
end
end

return nil if found_totals[amount].nil? # no solution found

# walk up tree and build array of coins used
result = []
cursor = found_totals[amount]
until cursor.coin.nil?
result << cursor.coin
cursor = cursor.parent
end
result.reverse! # reverse so coins in same order as coinage
provided
end

 

[jonty]

Hi, my solution is a lot simpler than most posted so far

As the aim is to find only the optimum solution all I do is
working with the largest coin first find out the maximum number of those
we can use
and then the next largest and so on which self-evidently is the optimal
solution.

Here's the code:

def make_change(amount, coins=[25,10,5,1])
#initialise
amt_orig=amount
change=[]
indx=0

#this works it out!
while amount>0
divarray=amount.divmod(coins[indx])
change.push(divarray[0])
amount=divarray[1]
indx+=1
end

#display result
s=amt_orig.to_s+ " requires: "
puts(s)
for i in 0..3
unless change==nil
s=change.to_s+" of coins of value "+coins.to_s
puts(s)
end
end
end

 

[Eric I.]

I made a slight modification to Paolo's solution, so it avoids
searching coin combinations that are permutations of others (i.e.,
[25, 1] and [1, 25]). It does this by only allowing the system to add
coins at or beyond the last coin used in the combination being built.
So, if the coins are [25, 10, 5, 1], and we're building from 25, 10,
10, 5 then the next coin be only a 5 or a 1. It seems to speed
Paolo's solution by about 30% on my system.

Eric

----

Are you interested in on-site Ruby training that's been highly
reviewed by former students? http://LearnRuby.com

====

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, 0]]
while parents[a].nil? && !worklist.empty? do
base, starting_index = worklist.shift
starting_index.upto(list.size - 1) do |index|
coin = list[index]
tot = base + coin
if tot <= a && parents[tot].nil?
parents[tot] = base
worklist << [tot, index]
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

 

[Yoan Blanc]

Hi, my solution is a lot simpler than most posted so far

As the aim is to find only the optimum solution all I do is
working with the largest coin first find out the maximum number of
those we can use
and then the next largest and so on which self-evidently is the
optimal solution.
make_change(24, [10,8,2])

24 requires:
2 of coins of value 10
0 of coins of value 8
2 of coins of value 2

where the (self-evidently) optimal solution is:

24 requires:
0 of coins of value 10
3 of coins of value 8
0 of coins of value 2

Cheers,

-- Yoan

 

[Eric I.]

Hi, my solution is a lot simpler than most posted so far

As the aim is to find only the optimum solution all I do is
working with the largest coin first find out the maximum number of those
we can use
and then the next largest and so on which self-evidently is the optimal
solution.

If you're trying to make 14 from the coins [10, 7, 2], a test case
previously posted, then the optimal solution would be [7, 7], but
yours would produce [10, 2, 2]. And your program throws an exception
when you try to make 21 from those same coins, even though there is a
valid solution of [7, 7, 7].

The other submitters didn't make their solutions complex for some love
of complexity....

Eric

 

[jonty]

Thanks Yoan - back to the drawing board!

Hi, my solution is a lot simpler than most posted so far

As the aim is to find only the optimum solution all I do is
working with the largest coin first find out the maximum number of
those we can use
and then the next largest and so on which self-evidently is the
optimal solution.
make_change(24, [10,8,2])

24 requires:
2 of coins of value 10
0 of coins of value 8
2 of coins of value 2

where the (self-evidently) optimal solution is:

24 requires:
0 of coins of value 10
3 of coins of value 8
0 of coins of value 2

Cheers,

-- Yoan

 

[Paolo Bonzini]

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

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

I'm too lazy to run it... how does it fare for

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

?

Paolo

 

[Martin Lüdtke]

def make_change(amount, coins = [25, 10, 5, 1])
change = { 0 => [] }
until change.has_key?(amount)
new_change = {}
change.each do |amt, chg|
coins.each { |c| new_change[amt + c] = [c] + chg unless
amt + c > amount or change.has_key?(amt + c) }
end
return nil if new_change.empty?
change.merge!(new_change)
end
change[amount].sort.reverse
end

-------------------

We begin with the simplest known solution (0 => []). Now for each
known solution and for each coin we get new solutions by just adding
the coin. This is repeated until we get a solution for the given
amount. If we don't find any new solutions (new_change.empty?) there
isn't any, so we return just nil.

 

[Paolo Bonzini]

I made a slight modification to Paolo's solution, so it avoids
searching coin combinations that are permutations of others (i.e.,
[25, 1] and [1, 25]). It does this by only allowing the system to add
coins at or beyond the last coin used in the combination being built.
So, if the coins are [25, 10, 5, 1], and we're building from 25, 10,
10, 5 then the next coin be only a 5 or a 1. It seems to speed
Paolo's solution by about 30% on my system.

Cool, thanks!

(By the way, the other solution was 6 times slower than breadth-first,
not 3. The difference arose because I ran one with battery power and
the other with wall power).

Paolo

 

[Rick DeNatale]

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

Man, if I only had a nickel for every time a Kiwi tried to stir up a
Pommie, or vice-versa <G>

 

[Paolo Bonzini]

I'm too lazy to run it... how does it fare for

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

?

Badly (30 seconds for s/100/7/g, of course I didn't try with
100...).

Paolo

 

[vsv]

below is my recursive solution
(also here: http://pastie.caboo.se/144281)
optimized for faster existence checking;
don't expect too much, though,
I still can't manage
make_change(p**10-1, (1..20).map{|n|p**n})
for any prime p (and who can?)

I've made small updates in my tests,
you can easily find test suite code
after __END__ line below;

thanks to all for interesting discussions;
Ruby fun is above rubies!

BRs
Sergey

unit test log:
--------------
[vsv@gx Q154]$ ruby -v
ruby 1.8.6 (2007-03-13 patchlevel 0) [i686-linux]

[vsv@gx Q154]$ ruby ./Q154_vsv.rb
Loaded suite ./Q154_vsv
Started

test_binary.
test_first_and_last.
test_misc.
test_no_change.
test_no_solution.
test_no_solution_hard.
test_one_coin.
test_ones.
test_primes.
test_two_middles.
Finished in 0.905768 seconds.

10 tests, 651 assertions, 0 failures, 0 errors
[vsv@gx Q154]$
--------------

Solution code
--------------
[vsv@gx Q154]$ cat ./Q154_vsv
#!/bin/env ruby
# A solution to RubyQuiz #154
=begin
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.
=end

class Changer
attr_reader :coins
def initialize _coins=[25, 10, 5, 1]
@coins = _coins.sort.reverse!
@minsz = nil
@aa = nil
end
#
def change amount
return [] if amount.zero?
acns = coins.reject{ |c| c>amount || c<1}
return nil if acns.empty?
# try faster method to check existence
return nil unless rec_has?( amount, acns.dup )
@minsz = amount/acns.last+1
rec_chg( amount, acns, [] )
end
#
private
#
def rec_chg amt, cns, res
# assert( amt > 0 )
# assert( not cns.empty? )
# assert( cns.any?{ |c| c<=amt } )
# @minsz - min change size
nres = nil
cns.each do |coin|
q = amt/coin
if (amt%coin).zero?
# [c]*q is the best change for amt
if @minsz > res.size+q
# save better solution
nres = res+[coin]*q
@minsz = nres.size
end
break
end
# at least q+1 more coins needed for change
# can we find better solution?
break if @minsz <= res.size+q+1
# prepare coins for recursive step
ncns = cns.slice(cns.index(coin)+1, cns.size)
next if ncns.empty?
# try add as much big coins as possible
q.downto(1) do |n|
amtc = amt-n*coin
xcnt = ncns.reject{ |c| c>amtc }
next if xcnt.empty?
nres = rec_chg( amtc, xcnt, res+[coin]*n ) || nres
end
end
nres
end
# stripped version of rec_chg
def rec_has? amt, cns
while coin = cns.shift
return true if (amt%coin).zero?
break if cns.empty?
(amt/coin).downto(1) do |n|
amtc = amt-n*coin
# prepare coins for recursive step
xcns = cns.reject{ |c| c>amtc }
next if xcns.empty?
return true if rec_has?( amtc, xcns )
end
end
nil
end
end

# Quiz function
USA_COINS = [25, 10, 5, 1]
def make_change( amount, coins = USA_COINS )
Changer.new(coins).change(amount)
end

if __FILE__ == $0
unless ARGV.empty?
# amount [coin..]
def show_change( *args )
amount = args.shift
coins = args.empty? ? USA_COINS : args
p [:AMOUNT, amount, :COINS, coins]
r = make_change( amount, coins )
p [:RES, r]
end
show_change( *ARGV.map{|arg|arg.to_i} )
else
eval DATA.read, nil, $0, 4+__LINE__
end
end
__END__
require 'test/unit'
class TestMakeChange < Test::Unit::TestCase
def trlog
s=caller(1).first
puts
print s[(s.index(':in ')+5)..-2]
STDOUT.flush
end

def test_no_solution
trlog
assert_equal( nil, make_change( -1 ) )
assert_equal( nil, make_change( 1, [] ) )
assert_equal( nil, make_change( 1, [0] ) )
assert_equal( nil, make_change( 1, [-1] ) )
## not specified
#assert_equal( nil, make_change( 1.5, [2, 1] ) )
assert_equal( nil, make_change( 1, [2] ) )
assert_equal( nil, make_change( 7, [5, 3] ) )
#
assert_equal( nil, make_change( 5, (1..10).map{ |n| 3**n } ) )
assert_equal( nil, make_change( 7, (1..10).map{ |n| 5**n } ) )
assert_equal( nil, make_change( 7, (1..10).map{ |n| [3**n,
5**n] }.flatten ) )
end

def test_no_solution_hard
trlog
[2,3,5,7,11].each{|pn|
assert_equal( nil, make_change( pn**4-1, (1..10).map{ |n|
pn**n } ) )
}
# 1023 instead of 383 is too slow
assert_equal( nil, make_change( 383, (1..10).map{ |n|
2**n } ) )
# to disable even/odd optimization
assert_equal( nil, make_change( 3**6-1, (1..10).map{ |n|
3**n } ) )
assert_equal( nil, make_change( 5**5-1, (1..10).map{ |n|
5**n } ) )
end

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

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

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

def test_two_middles
trlog
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
trlog
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
trlog
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
trlog
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
trlog
assert_equal( [1, 1], make_change( 2 ) )
assert_equal( [5, 1], make_change( 6 ) )
assert_equal( [10, 1], make_change( 11 ) )
assert_equal( [25, 1], make_change( 26 ) )
assert_equal( [25, 5, 1], make_change( 31 ) )
assert_equal( [25, 10, 1, 1, 1, 1], make_change( 39 ) )
assert_equal( [25, 10, 5, 1, 1, 1, 1], make_change( 44 ) )
assert_equal( [25, 10, 10], make_change( 45 ) )
assert_equal( [25, 10, 10, 1, 1, 1, 1], make_change( 49 ) )
#
assert_equal( [9, 2], make_change( 11, [10, 9, 2] ) )
assert_equal( [9, 9, 3], make_change( 21, [9, 3] ) )
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
--------------

 

[tho_mica_l]

I still can't manage

make_change(p**10-1, (1..20).map{|n|p**n})
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

 

[James Gray]

This week's Ruby Quiz is to complete a change making function=85

Here's my own solution to this week's quiz:

#!/usr/bin/env ruby -wKU

def make_change(amount, coins =3D [25, 10, 5, 1])
return [ ] if amount.zero?

coins =3D coins.sort_by { |coin| -coin }

prev_totals =3D {0 =3D> [ ]}
loop do
cur_totals =3D { }

prev_totals.each do |prev_total, prev_coins|
coins.each do |coin|
cur_total, cur_coins =3D prev_total + coin, prev_coins + [coin]

return cur_coins.sort_by { |coin| -coin } if cur_total =3D=3D =20=

amount
cur_totals[cur_total] ||=3D cur_coins if cur_total < =
amount
end
end

return if cur_totals.empty?

prev_totals =3D cur_totals
end
end

if __FILE__ =3D=3D $PROGRAM_NAME
amount, *coins =3D ARGV.map { |n| Integer(n) }
abort "Usage: #{$PROGRAM_NAME} AMOUNT [COIN[ COIN]...]" unless =20
amount

p coins.empty? ? make_change(amount) : make_change(amount, coins)
end

__END__

Has anyone done time comparisons of the submissions? I'm just curious =20=

at what the fastest strategies have been.

James Edward Gray II

 

[paddor]

[Note: parts of this message were removed to make it a legal post.]

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

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?

 

[tho_mica_l]

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