```> 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 have two solutions. One is short and sweet, but since it doesn't use
memoization at all, it is only suitable for small problems. I include
it here because I like how succinct it is.

def make_change_aux(amount, coins)
return [[]] if amount == 0
return [] if coins.empty? or amount < 0
return make_change_aux(amount - coins[0], coins).collect {
|n| n << coins[0]
} + make_change_aux(amount, coins[1 .. -1])
end

def make_change(amount, coins = [25, 10, 5, 1])
return make_change_aux(amount, coins).sort {
|a, b| a.size <=> b.size
}.first
end

My second solution uses a M*N in time and space algorithm by building
a table with M rows (one for each amount) and N columns (one for each
coin value). It fills in the table top-to-bottom, keeping the value in
a cell equal to the fewest number of coins so far needed to make that
amount M using only coins[0..N]. The optimal solution is in table[-1]
[-1] if it exists.

def make_change(amount, coins = [25, 10, 5, 1])
return []  if amount <= 0
return nil if coins == nil

coins = [nil] + coins # Use 1-based indexing
table = [[0] * coins.size]
amount.times { table << Array.new(coins.size) }

for i in 1 ... table.size do
for j in 1 ... table[i].size do
coin = coins[j]
poss = [table[i][j - 1]]
if i >= coin && table[i - coin][j] then
poss << table[i - coin][j] + 1
end
table[i][j] = poss.compact.sort.first
end
end

# Walk the solution from the last index to the first
return nil unless table[-1][-1]

soln = []
i = table.size - 1
j = table[i].size - 1

while i > 0 && j > 0 do
if table[i][j - 1] == table[i][j] then
j -= 1
else
soln << coins[j]
i -= coins[j]
end
end

return soln
end

This was reasonably fast on most inputs; the pathological inputs with
thousands of coins and an amount in the thousands slows it down quite
a bit though.

-JJ

```