Making change in Ruby

coin_change.rb

# Instructions: run with rspec coin_change.rb
#
#
# Making Change
#  Given a number "x" and a sorted array of coins "coinset", write a function
#  that returns the amounts for each coin in the coinset that sums up to X or
#  indicate an error if there is no way to make change for that x with the given
#  coinset. For example, with x=7 and a coinset of [1,5,10,25], a valid answer
#  would be {1: 7} or {1: 2, 5: 1}. With x = 3 and a coinset of [2,4] it should
#  indicate an error. Bonus points for optimality.

#  Use the following examples to test it out

#  A. x = 6 coinset = [1,5,10,25]
#  B. x = 6, coinset = [3,4]
#  C. x = 6, coinset = [1,3,4]
#  D. x = 6, coinset = [5,7]

NoChangeGiven = Class.new(StandardError)

def optimal_coin_change(coinset, x)
  coinset.reverse!
  cache = Hash.new do |h, current_amount|
    h[current_amount] = if current_amount < coinset.min.to_i
                          []
                        elsif coinset.include?(current_amount)
                          [current_amount]
                        else
                          coinset.reject { |coin| coin > current_amount }
                                 .map { |coin| [coin] + h[current_amount - coin] } # recurse by looking up in the hash
                                 .select { |coins| coins.sum == current_amount }
                                 .min_by(&:size) || [] # keep the smallest number of coins
                        end
  end

  raise NoChangeGiven if cache[x].empty?

  cache[x].reduce(Hash.new(0)) { |a, b| a.merge(b => a[b] + 1) } # count/group by
end

describe 'Getting optimal coin change' do
  subject { optimal_coin_change(coinset, amount) }

  context 'When no change available' do
    let(:coinset) { [100] }
    let(:amount) { 1 }
    it 'should raise an error' do
      expect { subject }.to raise_error(NoChangeGiven)
    end
  end

  context 'When no coins available' do
    let(:coinset) { [] }
    let(:amount) { 1_000 }
    it 'should raise an error' do
      expect { subject }.to raise_error(NoChangeGiven)
    end
  end

  context 'When amount is 0' do
    let(:coinset) { [1, 2, 3, 4] }
    let(:amount) { 0 }
    it 'should raise an error' do
      expect { subject }.to raise_error(NoChangeGiven)
    end
  end

  context 'When no possible change' do
    let(:coinset) { [5, 7] }
    let(:amount) { 6 }
    it 'should raise an error' do
      expect { subject }.to raise_error(NoChangeGiven)
    end
  end

  context 'Valid cases with optimal solutions' do
    context do
      let(:amount) { 6 }
      let(:coinset) { [1, 5, 10, 25] }
      it { expect(subject).to eq(5 => 1, 1 => 1) }
    end

    context do
      let(:amount) { 6 }
      let(:coinset) { [3, 4] }
      it { expect(subject).to eq(3 => 2) }
    end

    context do
      let(:amount) { 6 }
      let(:coinset) { [1, 3, 4] }
      it { expect(subject).to eq(3 => 2) }
    end

    context do
      let(:amount) { 47 }
      let(:coinset) { [1, 5, 10, 20, 50, 100] }
      it { expect(subject).to eq(20 => 2, 5 => 1, 1 => 2) }
    end

    context do
      let(:amount) { 247 }
      let(:coinset) { [1, 5, 10, 20, 50, 100] }
      it { expect(subject).to eq(100 => 2, 20 => 2, 5 => 1, 1 => 2) }
    end

    context do
      let(:amount) { 359 }
      let(:coinset) { [1, 5, 10, 20, 50, 100] }
      it { expect(subject).to eq(100 => 3, 50 => 1, 5 => 1, 1 => 4) }
    end
  end
end