[SUMMARY] Making Change (#154)

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

  1. Ruby Quiz

    Ruby Quiz Guest

    One submitter commented that our solutions were pretty complex. The reason for
    that is that we all sat around dreaming up pathological edge cases that took a
    long time to solve without some complex code. The good news is that such cases
    don't generally come up in the day to day change making of most countries.

    Let's begin with a peek at a non-complicated solution from Ilan Berci:

    def make_change(amount, coins = [25,10,5,1])
    coins.sort.
    reverse.
    map{|coin| f = amount/coin; amount %= coin; Array.new(f){coin} }.
    flatten
    end

    This approach uses a greedy algorithm. We call it greedy because it always
    tries to move as close to the end result as possible with each step. In this
    particular case, that is accomplished by working from the biggest coins to the
    smallest and always grabbing as many of each type of coin as possible without
    going over our limit.

    This technique is trivial and it works for all change made in the U.S., plus
    many other countries. It doesn't work for the fictional second test case given
    in the quiz though, returning [10, 1, 1, 1, 1].

    That's where the complexity began to creep in.

    If we're going to get right answers for any combination of coins, we will have
    to search all possible combinations. Doing that for certain sets of coins can
    take a long time and we would really rather it be fast. To get speed we will
    have to use something smarter than a brute force algorithm that checks all the
    combinations.

    Before I show the smarter approaches though, it's important to note that you
    likely wouldn't need to be this clever to make change in any country. The
    reason is simple: we don't usually give change for large amounts since we tend
    to just use non-coin funds for that. That keeps the search space small enough
    that advanced techniques aren't too important. Of course, it's still fun to
    explore the possibilities.

    This problem actually turns out to be famous in computer science. It's called
    the Knapsack Problem. Once you know that you can apply the techniques often
    used on that problem, the most popular of which is to use a dynamic programming
    algorithm. ("Dynamic programming" has a different meaning here than we often
    use in Ruby circles about code writing code.)

    The trick to a dynamic programming algorithm is to remember the smaller pieces
    of a bigger problem once we've figured them out and reuse them as much as
    possible without having to repeat the work. You can do that while working your
    way up to a solution or down from a solution, but the top-down approach, often
    called memoization, is pretty popular.

    Here's some code from Carl Porth that implements simple memoization using a
    Hash:

    def make_change(amount, coins = [25, 10, 5, 1])
    coins.sort! { |a, b| b <=> a }

    # memoize solutions
    optimal_change = Hash.new do |hash, key|
    hash[key] = if key < coins.min
    []
    elsif coins.include?(key)
    [key]
    else
    coins.
    # prune unhelpful coins
    reject { |coin| coin > key }.

    # prune coins that are factors of larger coins
    inject([]) {|mem, var| mem.any? {|c| c%var == 0} ? mem : mem+[var]}.

    # recurse
    map { |coin| [coin] + hash[key - coin] }.

    # prune unhelpful solutions
    reject { |change| change.sum != key }.

    # pick the smallest, empty if none
    min { |a, b| a.size <=> b.size } || []
    end
    end

    optimal_change[amount]
    end

    First, have a look at the structure of this code. It doesn't really seem to do
    much from the outside. It sort!()s the coins from biggest to smallest, defines
    a Hash, and indexes into the Hash to magically come up with the answer. The
    magic is in the definition of the Hash.

    To understand how this works, you just have to think of the main problem in
    smaller slices. Say we want to make 39 cents of change with U.S. coins. Here's
    how the problem breaks down:

    make_change(39)
    [25] + make_change(39 - 25)
    [25, 10] + make_change(39 - 25 - 10)
    [25, 10, 1] + make_change(39 - 25 - 10 - 1)

    # ...

    Carl's magic Hash does exactly this process. Have a look at this line of code
    plucked from the middle of the Hash definition:

    # ...

    # recurse
    map { |coin| [coin] + hash[key - coin] }.

    # ...

    That's the exact pattern I showed above.

    The memoization part is basically automatic here, thanks to how Ruby's Hash
    works. When you provide a default block to the constructor like this, it will
    be called the first time some key is accessed that the Hash doesn't know. That
    block can assign a value for the key though, as Carl does in this code, and then
    all future attempts to access the same key are a simple Hash lookup (bypassing
    all of the work in the block). That makes sure that once we have found some
    coin combination, we never have to find it again.

    What are all the rest of those lines in Carl's solution though? Pruning.
    That's the other trick for getting speed when searching a big space. Throw out
    everything you possibly can to make the work as small as possible. Carls throws
    out coins that are bigger than the current amount remaining, coins that are
    factors of larger coins we could use, and change combinations that don't add up
    to what we need. This makes for less work and makes the code go faster.

    Paolo Bonzini submitted another dynamic programming approach that was one of the
    faster solutions we saw. It's a bottom-up approach in contrast to the
    memoization we just saw. It prunes the space, orders the combinations checked
    to find smaller counts faster, and avoids building a bunch of coin Arrays as it
    works (Ruby's GC will slow you down when it kicks in). Eric I. submitted a
    small enhancement to the code that made it even faster. The downside of all
    this is that it's a little harder still to follow.

    Let's see how that modified version works:

    def make_change(a, list = [25, 10, 5, 1])
    return nil if a < 0
    return nil if a != a.floor

    parents = Array.new(a + 1)
    parents[0] = 0
    worklist = [[0, 0]]
    while parents[a].nil? && !worklist.empty? do
    base, starting_index = worklist.shift
    starting_index.upto(list.size - 1) do |index|
    coin = list[index]
    tot = base + coin
    if tot <= a && parents[tot].nil?
    parents[tot] = base
    worklist << [tot, index]
    end
    end
    end

    return nil if parents[a].nil?
    result = []
    while a > 0 do
    parent = parents[a]
    result << a - parent
    a = parent
    end
    result.sort!.reverse!
    end

    The main work here is done in the second chunk of code and to break that down,
    you need to know two things. First, the parents Array holds values at the index
    of a given amount for the previously used total. That sounds a lot more
    complicated than it is. For example, in the make_change(11, [10, 1]) call,
    parents ends up looking like this:

    [0, 0, nil, nil, nil, nil, nil, nil, nil, nil, 0, 10]

    It may not look like it, but the answer is hidden in there! To find it, you
    start at the desired total (as an index) parents[11]. That's 10, which is the
    previous total. So, to find the last coin, we can just subtract them which
    gives us the 1. Then we move to that previous amount at parents[10]. That's a
    zero and subtracting again gives us 10, the other coin needed. This process I
    just described is exactly what the third chunk of code does after a solution has
    been found in the second chunk.

    The second thing you need to understand is how it searches for solutions.
    Essentially, the worklist Array holds the progress so far. Each bit of work in
    there is shift()ed off, added to, and appended back on to the end if there's
    more work to do. This is the classic pattern for unrolling recursion into an
    iterative solution.

    Now each piece of work in worklist is the total we are currently on, plus an
    index for the last coin added. The total we are currently on represents the
    work we need to do. We can add coins to that to find new totals. The index for
    the last coin added just keeps us from repeating work by checking larger coins
    than we've already covered. (This solution assumes the coins are in order from
    biggest to smallest.) That's one example of the pruning done here. The other
    is the if conditional that only adds work below the desired total.

    It's important to think about how using a queue works here. First it will hold
    a single zero coin total at the front. In processing that, one coin totals will
    be added onto the back. When we reach those, the code will begin to add two
    coin totals. This means we are performing a breadth-first search from the
    smallest coin count solutions to the largest. This ensures that the first right
    answer we see is the best and saves us any needless work.

    My thanks to all who worked so hard to make sure we can quickly calibrate absurd
    sums of change. I'm sure we are collectively eliminating the need for paper
    money thanks to our fun and games.

    Tomorrow we will tackle a current hot topic in the Ruby community...
     
    Ruby Quiz, Jan 31, 2008
    #1
    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. daveh551

    Making Validation Summary visible

    daveh551, Oct 22, 2008, in forum: ASP .Net
    Replies:
    1
    Views:
    529
    Gregory A. Beamer \(Cowboy\) - MVP
    Oct 23, 2008
  2. Hal Fulton

    Facebook... only 154 to go?

    Hal Fulton, Oct 11, 2005, in forum: Ruby
    Replies:
    15
    Views:
    188
    Matt Lawrence
    Oct 12, 2005
  3. Ruby Quiz

    [QUIZ] Making Change (#154)

    Ruby Quiz, Jan 25, 2008, in forum: Ruby
    Replies:
    102
    Views:
    917
    Amey Dhoke
    Jan 31, 2008
  4. Ian Evans

    Rubyquiz: Making Change (#154)

    Ian Evans, Jan 30, 2008, in forum: Ruby
    Replies:
    0
    Views:
    110
    Ian Evans
    Jan 30, 2008
  5. Replies:
    7
    Views:
    186
    -berlin.de
    Aug 22, 2006
Loading...

Share This Page