Making Change

This is a solution to Ruby Quiz #154. The quiz goal is to write a method that takes an amount and an array of coins and returning a minimal list of coins that totals the desired amount.

# A solution to RubyQuiz #154.

# Given an amount and a set of coins, the make_change method finds the
# shortest combination of coins that equals the amount, if it's
# possible.

# See http://www.rubyquiz.com/quiz154.html for details.

# The latest version of this solution can also be found at
# http://learnruby.com/examples/ruby-quiz-154.shtml .

# Basically it does a breadth-first search by using a search tree,
# where the depth of a node in the tree equates to how many coins are
# used.  The search tree is pruned by not building off of nodes with a
# total that exceeds the desired total or nodes that come to a total
# that has already been found by a previous node.  Further, the search
# tree is minimized by avoiding coin combinations that could be
# permutations of others.  This is achieved by only adding coins that
# appear at the same position or later from the coinage as we descend
# the tree.  For example, if the coinage is [25, 10, 5, 1], then
# descending the tree, all 25 coins will appear before all 10 coins,
# and so forth.

# Note: the coinage does not have to be in any particular order (e.g.,
# sorted), but the list of coins returned will have the coins in the
# same order as in the given coinage.


Node = Struct.new("Node", :parent, :coin, :total, :starting_coin)

def make_change(amount, coinage = [25, 10, 5, 1])
  root = Node.new(nil, nil, 0, 0)  # root of tree with no coins
  found_totals = { 0 => root }     # track totals found to prune search
  queue = [root]                   # leaves to process breadth-first

  # process items from queue in a tree breadth-first order until
  # nothing left to process or right total is found
  catch(:found) do
    until queue.empty?
      node = queue.shift
      node.starting_coin.upto(coinage.size - 1) do |index|
        coin = coinage[index]
        new_total = node.total + coin
        next if new_total > amount || found_totals[new_total]  # prune
        new_node = Node.new(node, coin, new_total, index)
        found_totals[new_total] = new_node
        throw :found if new_total == amount
        queue << new_node
      end
    end
  end

  return nil if found_totals[amount].nil?  # no solution found

  # walk up tree and build array of coins used
  result = []
  cursor = found_totals[amount]
  until cursor.coin.nil?
    result << cursor.coin
    cursor = cursor.parent
  end
  result.reverse!  # reverse so coins in same order as coinage provided
end