```On Jan 27, 2008 7:21 PM, Jes=FAs Gabriel y Gal=E1n <jgabrielygalan / gmail.co=
m> wrote:
> > This week's Ruby Quiz is to complete a change making function with this
> > skeleton:
> >
> >         def make_change(amount, coins =3D [25, 10, 5, 1])
> >
> >         end
> >
> > Your function should always return the optimal change with optimal bein=
g the
> > least amount of coins involved.  You can assume you have an infinite nu=
mber 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

def initialize(amount, usable_coins, coins=3D[])
@remaining_amount =3D amount
@usable_coins =3D usable_coins.sort.reverse.select {|x| x <=3D amount}
@coins =3D 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 =3D=3D 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 =3D Solution.new(@remaining_amount - @usable_coins.first,
@usable_coins, (@coins.dup) << @usable_coins.first)
second =3D Solution.new(@remaining_amount, @usable_coins[1..-1], @coins=
)
[first, second]
end

def is_solution?
@remaining_amount =3D=3D 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 =3D [25, 10, 5, 1])
queue =3D []
solution_so_far =3D nil
length_so_far =3D nil
queue << Solution.new(amount, coins)
until queue.empty?
current =3D queue.shift
# prune branches that would result in a worse solution
next if solution_so_far && current.number_of_coins >=3D length_so_far
if current.is_solution?
solution_so_far =3D current
length_so_far =3D current.number_of_coins
else
queue.push(*current.explode)
end
end
return [] if solution_so_far.nil?
solution_so_far.coins
end

```