Velocity Reviews - Computer Hardware Reviews

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

Reply
Thread Tools

[QUIZ] Making Change (#154)

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

>> make_change(39)

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

 
Reply With Quote
 
 
 
 
Warren Brown
Guest
Posts: n/a
 
      01-25-2008
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


 
Reply With Quote
 
 
 
 
James Gray
Guest
Posts: n/a
 
      01-25-2008
On Jan 25, 2008, at 10:55 AM, Warren Brown wrote:

> 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

 
Reply With Quote
 
Joshua Ballanco
Guest
Posts: n/a
 
      01-25-2008
James Gray wrote:
> On Jan 25, 2008, at 10:55 AM, Warren Brown wrote:
>
>>> 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.
--
Posted via http://www.ruby-forum.com/.

 
Reply With Quote
 
tho_mica_l
Guest
Posts: n/a
 
      01-25-2008
Are the coin values always given in descending order?

regards,
thomas.
 
Reply With Quote
 
James Gray
Guest
Posts: n/a
 
      01-25-2008
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()?

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

James Edward Gray II

 
Reply With Quote
 
Dominik Honnef
Guest
Posts: n/a
 
      01-25-2008
On [Sat, 26.01.2008 00:50], Ruby Quiz wrote:
> 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?
--
Dominik Honnef


 
Reply With Quote
 
Jesús Gabriel y Galán
Guest
Posts: n/a
 
      01-25-2008
On Jan 25, 2008 9:53 PM, Dominik Honnef <(E-Mail Removed)> wrote:
> On [Sat, 26.01.2008 00:50], Ruby Quiz wrote:
> > 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?


Is it ok to share test cases before the spoiler? I assume it is, and
it this case everybody could send a couple...

Jesus.

 
Reply With Quote
 
James Gray
Guest
Posts: n/a
 
      01-25-2008
On Jan 25, 2008, at 3:09 PM, Jes=FAs Gabriel y Gal=E1n wrote:

> On Jan 25, 2008 9:53 PM, Dominik Honnef <(E-Mail Removed)> wrote:
>> On [Sat, 26.01.2008 00:50], Ruby Quiz wrote:
>>> In "Practical Ruby Projects," the author includes a couple of =20
>>> chapters involving
>>> coin simulations. These simulators are used to explore the =20
>>> possibilities of
>>> replacing a certain coin or adding a new coin.

>>
>> Are there any advanced combinations of change/array of coins which =20=


>> are likely to fail
>> on some implementations?

>
> Is it ok to share test cases before the spoiler?


Sure.

James Edward Gray II


 
Reply With Quote
 
Jesús Gabriel y Galán
Guest
Posts: n/a
 
      01-25-2008
On Jan 25, 2008 10:24 PM, James Gray <(E-Mail Removed)> wrote:
> On Jan 25, 2008, at 3:09 PM, Jes=FAs Gabriel y Gal=E1n wrote:
> > Is it ok to share test cases before the spoiler?

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

 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Making a small change to a large XML document Dan Stromberg Python 3 09-25-2007 06:59 AM
A Paradise DNS address change? What change? There was no change. Tony Neville NZ Computing 7 09-22-2006 01:02 PM
Re: A fresh new approach to making making online Fakename Computer Information 0 11-18-2005 02:10 AM
Making new Flavors : Making a custom transferhandler for and drop applications ebby83@gmail.com Java 5 01-12-2005 11:10 AM
Data Structure and making the size change dsa89 C++ 3 11-08-2004 06:34 AM



Advertisments