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

This is my solution. It explores a tree where each candidate solution
will generate two others: one using the coin with the maximum possible
value, and another one where the maximum one is not used. When it
finds a solution It prunes candidates that would generate worse
solutions.

class Solution

attr_reader :remaining_amount, :coins, :usable_coins

def initialize(amount, usable_coins, coins=[])

@remaining_amount = amount

@usable_coins = usable_coins.sort.reverse.select {|x| x <= amount}

@coins = coins

end

def explode

# check if this is an invalid branch or already a solution

return [] if @usable_coins.empty?

return [] if @usable_coins.last > @remaining_amount

return [] if @remaining_amount == 0

# generate two possible scenarios: use a coin of the highest value
and generate a Solution with less remaining amount

# but the same set of usable_coins or remove the highest value and
generate a Solution with the same remaining amount

# but less usable_coins

first = Solution.new(@remaining_amount - @usable_coins.first,
@usable_coins, (@coins.dup) << @usable_coins.first)

second = Solution.new(@remaining_amount, @usable_coins[1..-1], @coins)

[first, second]

end

def is_solution?

@remaining_amount == 0

end

def number_of_coins

@coins.length

end

def to_s
"[#{@coins.inspect}, #{@remaining_amount}, #{@usable_coins.inspect}]"
end

end

def make_change(amount, coins = [25, 10, 5, 1])

queue = []

solution_so_far = nil

length_so_far = nil

queue << Solution.new(amount, coins)

until queue.empty?
queue.each {|x| print x}
puts

current = queue.pop

# prune branches that would result in a worse solution

next if solution_so_far && current.number_of_coins >= length_so_far

if current.is_solution?

solution_so_far = current

length_so_far = current.number_of_coins

else

queue.push(*current.explode)

end

end

return [] if solution_so_far.nil?

solution_so_far.coins

end

I am having problems with the 100001, [100000, 1] situation when I
think I shouldn't so there might be a bug in there. Didn't have time
to check it yet. I'll try to find the problem if I have time.

Regards,

Jesus.

```