From: "Jesús Gabriel y Galán" <jgabrielygalan@...>
Date: 2008-01-29T18:10:57+09:00
Subject: Re: [QUIZ] Making Change (#154)

On Jan 27, 2008 7:21 PM, Jesús Gabriel y Galán <jgabrielygalan@gmail.com> wrote:
> > 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.

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

I've had 5 minutes and I solved this issue. I wanted shift/push
but I was using pop/push so was trying the combinations
of lower coins before the big ones, leading to more tests
than necessary. Now this case finds a solution with the 100000
coin and quickly prunes the rest. Still having problems with the
2**n stuff but I'm pretty sure I won't have time to look at it anymore...

Anyway, fun quiz as usual, thanks for this.

Jesus.


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?
    current = queue.shift
    # 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