[QUIZ] Making Change (#154)

[Sharon Phillips]

make_change 14, [10,7,3]

Why would this fail?

Because my code tried [10, 3] and saw it couldn't make 14
I think my job here is to be the person the rest of you point to and
go 'ha! at least I'm not *that* bad'...

 

[tho_mica_l]

Is it that hard to call sort()?

Not exactly hard. But since the coin sets in the examples were
ordered, I asked myself if this is intended.

Thomas.

 

[Jens Wille]

James Gray [2008-01-26 04:59]:

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.

well, i guess i have to be glad to be unprejudiced in this regard,
since i don't have any formal CS education ;-)

I guess he hadn't run into Ruby yet.

that's so true! ruby's expressiveness is just amazing. with the
added benefit that the most simple way to do something is almost
always the most efficient one (both in terms of coding speed as well
as execution speed) -- at least from a layman's perspective...

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/

 

[Dominik Honnef]

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

=> [5, 3, 3, 3]

Regards,
Pit

I wonder if it would be a big problem, if my script wouldnt handle this case.
It works perfect on the standard cases and (14, [10, 7, 3]) though.

 

[tho_mica_l]

I guess I should have said: is it that hard to call sort { |a,b|

I guess he hadn't run into Ruby yet.

I think reversing an array/list is rather cheap (especially when the
interpreter can use a built-in method coded in C) in comparison to
interpreting a code snippet and performing a comparison for each
element.

 

[Robert Dober]

Stupid me

sort() does not exclude the idiom you have mentioned above.
Funny error of mine.
R.

 

[SpringFlowers AutumnMoon]

make_change 14, [10,7,3]

my original implementation missed this one

Why would this fail?

Because my code tried [10, 3] and saw it couldn't make 14
I think my job here is to be the person the rest of you point to and
go 'ha! at least I'm not *that* bad'...

Are you Pisces, Sharon? Pisces like to make people feel happy.

 

[SpringFlowers AutumnMoon]

Sure.

James Edward Gray II

seeems like in some weird case:

# make_change(297, [100, 99, 1]) should return [99,99,99]
# make_change(397, [100, 99, 1]) should return [100,99,99,99]
# make_change(497, [100, 99, 1]) should return [100,100,99,99,99]

so there is no rule as to whether 100 or 99 should be used in the first
place.

 

[Andrew Timberlake]

-----Original Message-----

From: Pit Capitain [mailto[email protected]]
Sent: 26 January 2008 08:44 AM
To: ruby-talk ML
Subject: Re: [QUIZ] Making Change (#154)

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

=> [5, 3, 3, 3]

Regards,
Pit

Nice Pit
Next time I'll test before opening my mouth.

 

[Denis Hennessy]

Here's another test case:

make_change 1000001, [1000000, 1] # => [1000000, 1] AND complete in a
reasonable time (avoid brute force searches)

/dh

 

[tho_mica_l]

Here's another test case:

Yet another:

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])
=> [5, 7, 89, 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]

 

[Denis Hennessy]

Here's another test case:

Yet another:

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])
=> [5, 7, 89, 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]

It wasn't an explicit requirement, but I think the higher value coins
should appear first in the output list.

 

[tho_mica_l]

It wasn't an explicit requirement, but I think the higher value coins

should appear first in the output list.

I took extra care to sort them this way in order to compensate for my
above demand that the input list should be sorted in descending
order. :-(

 

[Alex Shulgin]

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.

We have even richer set of common coins here in UA: [50, 25, 10, 5, 2,
1] (though 1 and 2 are rarely used, and there is also a coin with the
value of 100, but it's not that common).

BTW, is it reasonable to assume amount <= 100 or do we need to prepare
for this one:

def test_huge
assert_equal([...], make_change(1_000_001)
end

?

 

[JJ]

Yet another:

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])
=> [5, 7, 89, 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]

That one has two answers (at least):

[3, 17, 89, 89, 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]

-JJ

 

[Marcelo]

Here's another test case:

make_change 1000001, [1000000, 1] # => [1000000, 1] AND complete in a
reasonable time (avoid brute force searches)

Didn't you have something like this in mind instead?

assert_equal([1_000_000, 1], make_change(1_000_001, [1_000_000, 2, 1]))

Marcelo

 

[tho_mica_l]

That one has two answers (at least):

You're right. Here is another one:

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 89 89 89 89 89 89 89 89 89 89 89 89 89 89 89 89 89 89 89
89 89 83

Sorry.

 

[Denis Hennessy]

Here's another test case:

make_change 1000001, [1000000, 1] # => [1000000, 1] AND
complete in a
reasonable time (avoid brute force searches)

Didn't you have something like this in mind instead?

assert_equal([1_000_000, 1], make_change(1_000_001, [1_000_000, 2,
1]))

Marcelo

No. I just meant that exhaustive searches should be avoided. Where a
large number of answer permutations are possible, they need to be
pruned early.

/dh

 

[James Gray]

BTW, is it reasonable to assume amount <= 100 or do we need to prepare
for this one:

def test_huge
assert_equal([...], make_change(1_000_001)
end

?

I leave that to your best judgement. We should probably remember that
not all places in the world have a 100 cent dollar though.

James Edward Gray II

 

[Yoan Blanc]

This is what I'm currently working on:

There, mines, using rspec (a first try for the fun).

http://pastie.caboo.se/143937

it's basically a compilation of the examples given today, nothing new.
It took me a while to have the last 2 ones running in a decent time
because I wasn't pruning enough.

$ spec quiz154_spec.rb
..........

Finished in 0.210093 seconds

10 examples, 0 failures

Cheers,

Yoan