# 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

``````