Making Change (#154)

bbazzarrakk · January 26, 2008, 8:00am

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.

bbazzarrakk · January 26, 2008, 11:00am

James G. [2008-01-26 04:59]:

On Jan 25, 2008, at 5:44 PM, Jens W. wrote:

James G. [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

bbazzarrakk · January 26, 2008, 7:47am

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’…

bbazzarrakk · January 26, 2008, 11:55am

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

bbazzarrakk · January 26, 2008, 12:59pm

Stupid me

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

–
http://ruby-smalltalk.blogspot.com/

Whereof one cannot speak, thereof one must be silent.
Ludwig Wittgenstein

bbazzarrakk · January 26, 2008, 11:43am

On [Sat, 26.01.2008 15:43], Pit C. wrote:

2008/1/26, Andrew T. [email protected]:

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.

bbazzarrakk · January 26, 2008, 2:29pm

James G. wrote:

Is it ok to share test cases before the spoiler?

Sure.

James Edward G. 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.

bbazzarrakk · January 26, 2008, 2:45pm

Regards,
Pit

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

bbazzarrakk · January 26, 2008, 4:11pm

Here’s another test case:

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

/dh

bbazzarrakk · January 26, 2008, 2:24pm

Sharon P. wrote:

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.

bbazzarrakk · January 26, 2008, 4:20pm

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]

bbazzarrakk · January 26, 2008, 4:44pm

On 26 Jan 2008, at 15:20, tho_mica_l wrote:

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.

bbazzarrakk · January 26, 2008, 8:40pm

On Jan 25, 5:50 pm, Ruby Q. [email protected] wrote:

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

?

bbazzarrakk · January 26, 2008, 5:05pm

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.

bbazzarrakk · January 26, 2008, 8:45pm

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

bbazzarrakk · January 26, 2008, 9:34pm

On Jan 26, 2008 9:10 AM, Denis H. [email protected] wrote:

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

bbazzarrakk · January 26, 2008, 10:00pm

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.

bbazzarrakk · January 27, 2008, 12:46am

On Jan 26, 2008, at 1:40 PM, Alex S. wrote:

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 G. II

bbazzarrakk · January 26, 2008, 10:29pm

On 26 Jan 2008, at 20:33, Marcelo wrote:

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

bbazzarrakk · January 27, 2008, 2:04am

Jesús Gabriel y Galán wrote:

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