Velocity Reviews > Ruby > [QUIZ] Making Change (#154)

# [QUIZ] Making Change (#154)

Robert Dober
Guest
Posts: n/a

 01-25-2008
On Jan 25, 2008 9:20 PM, James Gray <(E-Mail Removed)> wrote:
> On Jan 25, 2008, at 1:49 PM, tho_mica_l wrote:
>
> > Are the coin values always given in descending order?

>
> Is it that hard to call sort()?

funny mistake of yours James
Robert

James Gray
Guest
Posts: n/a

 01-25-2008
On Jan 25, 2008, at 4:30 PM, Robert Dober wrote:

> On Jan 25, 2008 9:20 PM, James Gray <(E-Mail Removed)> wrote:
>> On Jan 25, 2008, at 1:49 PM, tho_mica_l wrote:
>>
>>> Are the coin values always given in descending order?

>>
>> Is it that hard to call sort()?

> 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
Guest
Posts: n/a

 01-25-2008
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
Guest
Posts: n/a

 01-25-2008
On 25 Jan 2008, at 20:53, Dominik Honnef wrote:
> 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
Guest
Posts: n/a

 01-25-2008
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.40621
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.25564
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: http://www.velocityreviews.com/forums/(E-Mail Removed)
http://www.prometheus-bildarchiv.de/

Sharon Phillips
Guest
Posts: n/a

 01-26-2008
>>> Are there any advanced combinations of change/array of coins which
>>> are likely to fail
>>> on some implementations?

make_change 14, [10,7,3]

my original implementation missed this one

Andrew Timberlake
Guest
Posts: n/a

 01-26-2008
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 Removed)
082 415 8283
skype: andrewtimberlake

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

-----Original Message-----
From: Sharon Phillips [mailto(E-Mail Removed)]
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
Guest
Posts: n/a

 01-26-2008
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 Removed)
082 415 8283
skype: andrewtimberlake

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

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

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

make_change 14, [10,7,3]

my original implementation missed this one

!DSPAM:3,479aa59d18003599465482!

James Gray
Guest
Posts: n/a

 01-26-2008
On Jan 25, 2008, at 5:44 PM, Jens Wille wrote:

> 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
Guest
Posts: n/a

 01-26-2008
2008/1/26, Andrew Timberlake <(E-Mail Removed)>:
> make_change 14, [10, 5, 3] would fail though (...)

=> [5, 3, 3, 3]

Regards,
Pit