Pastie Support Pastie or read my Pastie << self blog

class ChangeMaker

  def make_change amount, coins
    return nil if amount == 0
    return nil if coins.size == 0

    change_array = []
    remove_duplicate_values(coins) 
    coins.sort!.reverse!
    tempAmount = amount;

    coins.each do |coin|
        temp = coin == 0 ? 0 : amount/coin
        temp.times {change_array << coin}
        amount -= temp*coin
      end

    if amount != 0 
      new_array = make_change_recursively(tempAmount, coins)
      change_array = new_array if new_array.size != 0
    end

    another_change_array = []
    another_change_array = get_change_if_amount_is_multiple_of_any_coin_value(tempAmount,coins,change_array.size)


    return (another_change_array.size < change_array.size and another_change_array.size !=0) \
      ? another_change_array : change_array
  end

  def make_change_recursively amount, coins
    tempAmount =amount
    change_array = []
    coins.shift
    if coins.size == 0 then return []
    end

     coins.each do |coin|
       temp = coin == 0 ? 0 : amount/coin
       temp.times {change_array << coin}
       amount -= temp*coin 
     end
    if amount != 0
      change_array = make_change_recursively tempAmount,coins
    end 
    change_array
  end


  def get_change_if_amount_is_multiple_of_any_coin_value amount,coins, size
    change_array = []
    coins.each do |coin|
      next if coin == 0
      if amount%coin == 0
        temp = amount/coin
        temp.times {change_array << coin} unless temp >= size
        return change_array
      end
    end
    change_array
  end

  def remove_duplicate_values coins
    coins.uniq!
  end

  public :make_change
  private :remove_duplicate_values, :get_change_if_amount_is_multiple_of_any_coin_value, :make_change_recursively
end