Pairing exercise: Make fewest change

pair.rb

require 'rubygems'
require 'rspec'

class Mchange
  def self.make(amount, coins = [10, 25, 5, 1])
    if amount > 0
      fewest_coins(amount, coins.sort.reverse)
    else
      []
    end
  end
  
  def self.fewest_coins(amount, coins)
    combinations = self.combinations(amount, coins).map do |combi|
      coin_quantity_into_change(combi)
    end
    combinations.min {|a, b| a.size <=> b.size }
  end
  
  def self.combinations(amount, coins)
    return [{coins.first => amount}] if coins.size == 1
    result = []
    c = coins.first
    (amount / c).downto(0) do |coin_quantity|
      combi = {c => coin_quantity}
      a = amount - c * coin_quantity
      self.combinations(a, coins[1..-1]).each do |sub_combinations|
        result << combi.merge(sub_combinations)
      end
    end
    result
  end

  def self.coin_quantity_into_change(coin_quantity)
    result = []
    coin_quantity.each do |coin, quantity|
      result += [coin] * quantity
    end
    result
  end
end

describe "Mchange" do
  
  it "should accept 0" do
    Mchange.make(0).should == []
  end
  
  it "should return a single coin" do
    Mchange.make(1).should == [1]
  end
  
  it "should return multiple coins" do
    Mchange.make(2).should == [1, 1]
  end
  
  it "should sort coins descending" do
    Mchange.make(25).should == [25]
  end
  
  it "should pass the acceptance criterias" do
    Mchange.make(14).should == [10, 1, 1, 1, 1]
    Mchange.make(26).should == [25, 1]
    Mchange.make(36).should == [25, 10, 1]
  end
  
  it "should accept specific coins" do
    Mchange.make(14, [25, 10, 5, 1]).should == [10, 1, 1, 1, 1]
  end
  
  it "should accept coins in custom denomination and return the fewest number of coins" do
    Mchange.make(14, [10, 7, 1]).should == [7 ,7]
    Mchange.make(17, [10, 7, 1]).should == [10, 7]
  end
  
  it "should not give the highest possible quantity of the biggest coins" do
    Mchange.make(24, [10, 7, 1]).should == [10, 7, 7] # instead of [10, 10, 1, 1, 1, 1]
  end

  it "could also work with other combinations of the same length!" do
    class Array; def sum; self.reduce(:+); end; end
    
    result = Mchange.make(21, [10, 7, 1])
    result.should       == [10, 10,  1]
    result.sum.should   == [ 7,  7,  7].sum
    result.size.should  == [ 7,  7,  7].size
  
    result = Mchange.make(42, [10, 7, 1])
    result.should       == [10, 10, 10, 10,  1,  1]
    result.sum.should   == [10, 10,  7,  7,  7,  1].sum
    result.size.should  == [10, 10,  7,  7,  7,  1].size
    result.sum.should   == [ 7,  7,  7,  7,  7,  7].sum
    result.size.should  == [ 7,  7,  7,  7,  7,  7].size
  end
  
  context "unit tests" do
  
    describe "coin_quantity_into_change" do
      
      it "ignores keys that have a value of 0" do
        Mchange.coin_quantity_into_change(1 => 0).should == []
      end
      
      it "multiplies the keys with their values and adds it into an array" do
        Mchange.coin_quantity_into_change(25 => 1, 10 => 2, 5 => 3).should == [25, 10, 10, 5, 5, 5]
      end
    end
  end
end