Making Change (#154)

Ruby
61

On Jan 27, 9:00 am, Paolo B. [email protected] wrote:

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.

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

Slim2:Desktop 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

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

Slim2:Desktop 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

Slim2:Desktop phrogz$ cat paolo.rb
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

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 :frowning:
assert_equal( nil, make_change( 127, (1…10).map{ |n|
2n } ) )
}
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( [i], 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 = i10
m = b/2+1
assert_equal( [m, m], make_change( m2, [b, m, 1]) )
end
}
end
def test_first_and_last
N.times{
for i in 1…10
b = i100
assert_equal( [b, 1], make_change( b+1, (1…b).to_a) )
end
}
end
def test_binary
N.times{
a = (0…7).map{ |n| 2n }.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
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[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
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( 9i, [10,9,1] ) )
assert_equal( [10]+[9]i, make_change( 10+9i, [10,9,1] ) )
end
}
end
end

62

On Jan 27, 6:41 pm, tho_mica_l [email protected] wrote:

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?

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

63

On Jan 27, 2008 6:55 PM, Ilan B. [email protected] wrote:

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 :slight_smile:

Jesus.

64

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.

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.

65

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

66

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.

67

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 Ruby Quiz - Making Change (#154) 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”, :parent, :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

catch(:found) 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

68

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[i]==nil
s=change[i].to_s+" of coins of value "+coins[i].to_s
puts(s)
end
end
end

69

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 :stuck_out_tongue:

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

70

my solution(s).

g phil

71

jonty wrote:

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

72

Thanks Yoan - back to the drawing board!

73

On Jan 27, 3:45 pm, jonty [email protected] wrote:

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

74

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

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

I’m too lazy to run it… how does it fare for

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

?

Paolo

75

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.

76

On Jan 27, 9:47 pm, “Eric I.” [email protected] wrote:

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

77

On 1/27/08, hadley wickham [email protected] wrote:

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:

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

Rick DeNatale

My blog on Ruby
http://talklikeaduck.denhaven2.com/

78

On Jan 27, 10:55 pm, Paolo B. [email protected] wrote:

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

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

I’m too lazy to run it… how does it fare for

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

?

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

Paolo

79

below is my recursive solution
(also here: Parked at Loopia)
optimized for faster existence checking;
don’t expect too much, though,
I still can’t manage
make_change(p10-1, (1…20).map{|n|pn})
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 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.
=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-ncoin
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-ncoin
# 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| 3n } ) )
assert_equal( nil, make_change( 7, (1…10).map{ |n| 5n } ) )
assert_equal( nil, make_change( 7, (1…10).map{ |n| [3n,
5n] }.flatten ) )
end

def test_no_solution_hard

trlog
[2,3,5,7,11].each{|pn|
assert_equal( nil, make_change( pn4-1, (1…10).map{ |n|
pnn } ) )
}
# 1023 instead of 383 is too slow :frowning:
assert_equal( nil, make_change( 383, (1…10).map{ |n|
2n } ) )
# to disable even/odd optimization
assert_equal( nil, make_change( 36-1, (1…10).map{ |n|
3n } ) )
assert_equal( nil, make_change( 55-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( [i], 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 = i10
m = b/2+1
assert_equal( [m, m], make_change( m2, [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([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

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[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

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( 9i, [10,9,1] ) )
assert_equal( [10]+[9]i, make_change( 10+9i,
[10,9,1] ) )
end
end
end

80

On Jan 25, 2008, at 9:50 AM, Ruby Q. wrote:

This week’s Ruby Q. is to complete a change making function…

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

#!/usr/bin/env ruby -wKU

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

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

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

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

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

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

 return if cur_totals.empty?

 prev_totals = cur_totals

end
end

if FILE == $PROGRAM_NAME
amount, *coins = ARGV.map { |n| Integer(n) }
abort “Usage: #{$PROGRAM_NAME} AMOUNT [COIN[ COIN]…]” unless
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
at what the fastest strategies have been.

James Edward G. II