[QUIZ] Making Change (#154)

[Ruby Quiz]

The three rules of Ruby Quiz:

1. Please do not post any solutions or spoiler discussion for this quiz until
48 hours have passed from the time on this message.

2. Support Ruby Quiz by submitting ideas as often as you can:

http://www.rubyquiz.com/

3. Enjoy!

Suggestion: A [QUIZ] in the subject of emails about the problem helps everyone
on Ruby Talk follow the discussion. Please reply to the original quiz message,
if you can.

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

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.

One interesting subproblem of these simulations is that of making change. For
example, if we need to give 39 cents change in the United States (where there
are 25, 10, 5, and 1 cent pieces), we can give:
=> [25, 10, 1, 1, 1, 1]

What if the coins were 10, 7, and 1 cent pieces though and we wanted to make 14
cents change? We would probably want to do:

make_change(14, [10, 7, 1])

=> [7, 7]

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.

 

[Warren Brown]

James,

What if the coins were 10, 7, and 1 cent pieces though
and we wanted to make 14 cents change? We would
probably want to do:
=20
>> make_change(14, [10, 7, 1])
=3D> [7, 7]
...
Your function should always return the optimal change
with optimal being the least amount of coins involved.

Do you have a preference for breaking ties? For example, which
would you prefer for make_change(21, [10, 7, 1]): [7, 7, 7] or [10, 10,
1]?

Warren Brown

 

[James Gray]

James,

What if the coins were 10, 7, and 1 cent pieces though
and we wanted to make 14 cents change? We would
probably want to do:

>> make_change(14, [10, 7, 1])
=> [7, 7]
...
Your function should always return the optimal change
with optimal being the least amount of coins involved.

Do you have a preference for breaking ties? For example, which
would you prefer for make_change(21, [10, 7, 1]): [7, 7, 7] or [10,
10,
1]?

No preference. Either is a valid answer.

James Edward Gray II

 

[Joshua Ballanco]

with optimal being the least amount of coins involved.

Do you have a preference for breaking ties? For example, which
would you prefer for make_change(21, [10, 7, 1]): [7, 7, 7] or [10,
10,
1]?

No preference. Either is a valid answer.

James Edward Gray II

I don't know...I hate pennies. IMHO, any answer that minimizes the
number of pennies should win out.

 

[tho_mica_l]

Are the coin values always given in descending order?

regards,
thomas.

 

[James Gray]

Are the coin values always given in descending order?

Is it that hard to call sort()?

I don't mind if you want to assume they are.

James Edward Gray II

 

[Dominik Honnef]

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?

 

[Jesús Gabriel y Galán]

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? I assume it is, and
it this case everybody could send a couple...

Jesus.

 

[James Gray]

Is it ok to share test cases before the spoiler?

Sure.

James Edward Gray II

 

[Jesús Gabriel y Galán]

Sure.

This is what I'm currently working on:

require 'test/unit'

class TestMakeChange < Test::Unit::TestCase
def test_zero
assert_equal([], make_change(0))
end

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

def test_two_middles
assert_equal([7, 7], make_change(14, [10, 7, 1]))
end
end

For now:

3 tests, 3 assertions, 3 failures, 0 errors

:-(

It's not really surprising, since I still have an empty method

Jesus.

 

[Robert Dober]

Is it that hard to call sort()?

funny mistake of yours James
Robert

 

[James Gray]

funny mistake of yours James

I guess I should have said: is it that hard to call sort { |a,b| b
<=> a }?

James Edward Gray II

 

[Sharon Phillips]

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

This means I have to consider the case where it is not possible to
construct the amount from the given coins, eg. $7.99

Nice to have one I could do in the ten minutes after breakfast while
the kids get dressed

Cheers,
Dave

 

[Denis Hennessy]

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

# result may not be achievable using just lowest value coin

make_change(11,[10,9,2]) #=> [9,2]

/dh

 

[Jens Wille]

James Gray [2008-01-25 23:57]:

I guess I should have said: is it that hard to call sort { |a,b|
b <=> a }?

am i missing something? what's wrong with sort.reverse? apart from
the fact that it's a whole lot faster ;-)

i know, this is not all too serious, but just for the fun of it...
here are the timings for M = 10, 100, 1_000, 10_000:

user system total real
block 3.940000 0.410000 4.350000 ( 4.349146)
by 2.580000 0.290000 2.870000 ( 3.033811)
reverse 0.260000 0.020000 0.280000 ( 0.287276)

block 8.540000 0.870000 9.410000 ( 9.406218)
by 2.740000 0.210000 2.950000 ( 2.953615)
reverse 0.180000 0.000000 0.180000 ( 0.179436)

block 13.810000 1.340000 15.150000 ( 15.176457)
by 2.880000 0.220000 3.100000 ( 3.099212)
reverse 0.220000 0.010000 0.230000 ( 0.234392)

block 17.820000 2.230000 20.050000 ( 20.255648)
by 3.380000 0.280000 3.660000 ( 3.656010)
reverse 0.300000 0.010000 0.310000 ( 0.305090)

----[ sort_bench.rb ]----
require 'benchmark'

M = ARGV.first.to_i
N = 1_000_000 / M
A = (0..M).sort_by { rand }

Benchmark.bm(7) { |x|
x.report('block') { N.times { A.sort { |a, b| b <=> a } } }
x.report('by') { N.times { A.sort_by { |a| a * -1 } } }
x.report('reverse') { N.times { A.sort.reverse } }
}
-------------------------

cheers
jens

--
Jens Wille, Dipl.-Bibl. (FH)
prometheus - Das verteilte digitale Bildarchiv für Forschung & Lehre
Kunsthistorisches Institut der Universität zu Köln
Albertus-Magnus-Platz, D-50923 Köln
Tel.: +49 (0)221 470-6668, E-Mail: (e-mail address removed)
http://www.prometheus-bildarchiv.de/

 

[Sharon Phillips]

Are there any advanced combinations of change/array of coins which
make_change 14, [10,7,3]

my original implementation missed this one

 

[Andrew Timberlake]

Same here in South Africa. We're phasing out 1c & 2c coins so change of
R7.99 would usually be R8.00 (ie. The store rounds to the benefit of the
consumer)
This could be applied to a case like make_change(14, [10,5,3]) where the
answer is [10,5] as the answer should leave the change giver the least out
of pocket?

Andrew Timberlake
(e-mail address removed)
082 415 8283
skype: andrewtimberlake

"I have never let my schooling interfere with my education."
--Mark Twain


-----Original Message-----
From: Sharon Phillips [mailto[email protected]]
Sent: 26 January 2008 01:09 AM
To: ruby-talk ML
Subject: Re: [QUIZ] Making Change (#154)

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

This means I have to consider the case where it is not possible to
construct the amount from the given coins, eg. $7.99

Nice to have one I could do in the ten minutes after breakfast while
the kids get dressed

Cheers,
Dave




!DSPAM:3,479a6d34191821551420065!

 

[Andrew Timberlake]

Why would this fail? The answer would be [7,7]
make_change 14, [10, 5, 3] would fail though (see my previous post on a
possible addendum to the quiz to handle cases like this though - instead of
failing)

Andrew Timberlake
(e-mail address removed)
082 415 8283
skype: andrewtimberlake

"I have never let my schooling interfere with my education."
--Mark Twain


-----Original Message-----
From: Sharon Phillips [mailto[email protected]]
Sent: 26 January 2008 05:09 AM
To: ruby-talk ML
Subject: Re: [QUIZ] Making Change (#154)

make_change 14, [10,7,3]

my original implementation missed this one


!DSPAM:3,479aa59d18003599465482!

 

[James Gray]

James Gray [2008-01-25 23:57]:

I guess I should have said: is it that hard to call sort { |a,b|
b <=> a }?

am i missing something? what's wrong with sort.reverse? apart from
the fact that it's a whole lot faster ;-)

Because my first computer science teacher drilled into my head that
you sort it correctly in the first place, instead of using two
operations to get what you wanted. I guess he hadn't run into Ruby
yet.

James Edward Gray II

 

[Pit Capitain]

make_change 14, [10, 5, 3] would fail though (...)

=> [5, 3, 3, 3]

Regards,
Pit