> 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