Coin Change

coin_change.rb

# Run with `ruby coin_change.rb`


# Use to optimally make some number N from a set of candidate integer 'parts'
class ChangeMaker
  def initialize(choices)
    @choices = choices.sort_by { |n| -n }
  end

  def change(amount)
    bag = []          # holds list of items to return
    remaining_amount = amount

    @choices.each do |thing| # counts down finds biggest item first
      if ((remaining_amount/thing).to_int > 0)
      then (remaining_amount/thing).to_int.times { bag << thing }
        puts "Remaining Amount: #{remaining_amount} | thing: #{thing}"
        remaining_amount = amount - bag.inject(:+)
      end                         # bag.inject(:+) sums array items
    end                           # stackoverflow.com/a/1538801/1148249
    puts "Amount #{amount} >> parts: #{bag}\n\n"
    return bag
  end
end


candidates = [10, 20, 5, 1]
calculator = ChangeMaker.new(candidates)

bag = calculator.change(530)

totals = {}
bag.each do |x|
  if totals.key?(x)
    totals[x] += 1
  else
    totals[x] = 1
  end
end

puts "Showing counts of each. { <part> => <num in bag> }"
puts totals