money changer

moeny_changer.rb

require 'rspec'

class MoneyChanger

  def initialize(notes=[200,100,50,20,10,5,2,1])
    @notes = notes.uniq.sort.reverse
  end

  def change(amount)
    possible_notes = @notes.select {|n| n <= amount}

    min_size = amount / possible_notes.first
    max_size = amount / possible_notes.last

    min_size.upto(max_size) do |i|
      combinations = possible_notes.repeated_combination(i)
      results = combinations.find {|c| c.reduce(:+) == amount }
      return results unless results.nil?
    end
    nil
  end

end

describe MoneyChanger do
  let(:changer) { MoneyChanger.new }

  it "returns correct value with default notes" do
    changer.change(100).should == [100]
    changer.change(112).should ==  [100,10,2]
    changer.change(1984).should == [200,200,200,200,200,200,200,200,200,100,50,20,10,2,2]
  end

  it "returns correct value with custom notes" do
    changer = MoneyChanger.new([10,7,1])
    changer.change(15).should == [7,7,1]
    changer.change(14).should == [7,7]
    changer.change(13).should == [10,1,1,1]
  end

  it "works with possible time-consuming cases" do
    changer = MoneyChanger.new([1_000_000_000,1])
    changer.change(1_000_000_001).should == [1_000_000_000,1]

    changer = MoneyChanger.new([1_000_000_000, 1_000_000, 1_000, 1])
    changer.change(3_003_000_009).should == [1_000_000_000,1_000_000_000,1_000_000_000,1_000_000,1_000_000,1_000_000,1,1,1,1,1,1,1,1,1]
  end
end