[QUIZ] Making Change (#154)

Discussion in 'Ruby' started by Ruby Quiz, Jan 25, 2008.

  1. Ruby Quiz

    Ruby Quiz Guest

    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.
     
    Ruby Quiz, Jan 25, 2008
    #1
    1. Advertising

  2. Ruby Quiz

    Warren Brown Guest

    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
     
    Warren Brown, Jan 25, 2008
    #2
    1. Advertising

  3. Ruby Quiz

    James Gray Guest

    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
     
    James Gray, Jan 25, 2008
    #3
  4. Re: Making Change (#154)

    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/.
     
    Joshua Ballanco, Jan 25, 2008
    #4
  5. Ruby Quiz

    tho_mica_l Guest

    Re: Making Change (#154)

    Are the coin values always given in descending order?

    regards,
    thomas.
     
    tho_mica_l, Jan 25, 2008
    #5
  6. Ruby Quiz

    James Gray Guest

    Re: Making Change (#154)

    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
     
    James Gray, Jan 25, 2008
    #6
  7. 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
     
    Dominik Honnef, Jan 25, 2008
    #7
  8. On Jan 25, 2008 9:53 PM, Dominik Honnef <> 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.
     
    Jesús Gabriel y Galán, Jan 25, 2008
    #8
  9. Ruby Quiz

    James Gray Guest

    On Jan 25, 2008, at 3:09 PM, Jes=FAs Gabriel y Gal=E1n wrote:

    > On Jan 25, 2008 9:53 PM, Dominik Honnef <> 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
     
    James Gray, Jan 25, 2008
    #9
  10. On Jan 25, 2008 10:24 PM, James Gray <> 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.
     
    Jesús Gabriel y Galán, Jan 25, 2008
    #10
  11. Ruby Quiz

    Robert Dober Guest

    Re: Making Change (#154)

    On Jan 25, 2008 9:20 PM, James Gray <> 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
     
    Robert Dober, Jan 25, 2008
    #11
  12. Ruby Quiz

    James Gray Guest

    Re: Making Change (#154)

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

    > On Jan 25, 2008 9:20 PM, James Gray <> 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
     
    James Gray, Jan 25, 2008
    #12
  13. 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
     
    Sharon Phillips, Jan 25, 2008
    #13
  14. 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
     
    Denis Hennessy, Jan 25, 2008
    #14
  15. Ruby Quiz

    Jens Wille Guest

    Re: Making Change (#154)

    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:
    http://www.prometheus-bildarchiv.de/
     
    Jens Wille, Jan 25, 2008
    #15
  16. >>> 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
     
    Sharon Phillips, Jan 26, 2008
    #16
  17. 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

    082 415 8283
    skype: andrewtimberlake

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


    -----Original Message-----
    From: Sharon Phillips [mailto:p]
    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, Jan 26, 2008
    #17
  18. 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

    082 415 8283
    skype: andrewtimberlake

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


    -----Original Message-----
    From: Sharon Phillips [mailto:p]
    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!
     
    Andrew Timberlake, Jan 26, 2008
    #18
  19. Ruby Quiz

    James Gray Guest

    Re: Making Change (#154)

    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
     
    James Gray, Jan 26, 2008
    #19
  20. Ruby Quiz

    Pit Capitain Guest

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


    => [5, 3, 3, 3]

    Regards,
    Pit
     
    Pit Capitain, Jan 26, 2008
    #20
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Ruby Quiz

    [QUIZ] Animal Quiz (#15)

    Ruby Quiz, Jan 14, 2005, in forum: Ruby
    Replies:
    11
    Views:
    431
    James Edward Gray II
    Jan 18, 2005
  2. Hal Fulton

    Facebook... only 154 to go?

    Hal Fulton, Oct 11, 2005, in forum: Ruby
    Replies:
    15
    Views:
    190
    Matt Lawrence
    Oct 12, 2005
  3. Ian Evans

    Rubyquiz: Making Change (#154)

    Ian Evans, Jan 30, 2008, in forum: Ruby
    Replies:
    0
    Views:
    114
    Ian Evans
    Jan 30, 2008
  4. Ruby Quiz

    [SUMMARY] Making Change (#154)

    Ruby Quiz, Jan 31, 2008, in forum: Ruby
    Replies:
    0
    Views:
    142
    Ruby Quiz
    Jan 31, 2008
  5. Replies:
    7
    Views:
    191
    -berlin.de
    Aug 22, 2006
Loading...

Share This Page