The Setup
This kata is a spin on the old backpack problem. Please give feedback on both the kata itself as well as my solution. I'm not sure if the kata needs to lead the student more or if this is a good open-ended problem. My original intent with this kata was to practice using Hashes. This is why the output is required to be in the form of a hash. That detail led me to create the Change class which inherits from Hash. I think of this as an implementation detail of my solution but I'm considering making it part of the kata. Thanks for your input/reading.
The Kata
CashRegister Kata
Create a CashRegister class
- detail: It that is initialized with an Array of Integers
- detail: Each integer in the array represents the value of a type of coin in the cash register
- detail: You can assume that there are an infinite number of coins in the cash register
- detail: The cash register should default to 25, 10, 5 and 1 cent pieces, if no argument is provided.
- detail: The cash register should throw an error if it initialized with an argument that is not an array of integers
- example: CashRegister.new([25,10,5,1])
completed (Y|n):
Create a make_change() method
- detail: It takes an positive integer as an argument.
- detail: It returns a hash showing the smallest combination of coins which sum to that number.
- detail: If a non integer argument is passed in, make_change() should throw an error.
- detail: The hash should have an entry for every coin in the cash register.
- detail: If a coin is not used, it's value should be zero.
- example: CashRegister.new().make_change(123) evaluates to: {'25' => 4, '10' => 2, '5' => 0, '1' => 3}
- example: CashRegister.new([10,7,1]).make_change(14) evaluates to: {'10' => 0, '7' => 2, '1' => 0}
completed (Y|n):
Congratulations!
- Create a CashRegister class 00:21:08
- Create a make_change() method 01:12:09
---------------------------------------------------------------------- --------
Total Time taking CashRegister kata: 01:33:17
The Specs
1 require 'spec_helper'
2 require 'cashregister'
3
4 describe CashRegister do
5 describe "#new" do
6 subject(:cash_register) { CashRegister.new }
7 let(:bad_argument) { 'A' }
8 let(:bad_array_argument) { [10, 5, 'A', 'B', 'C'] }
9
10 it "should instantiate" do
11 expect { CashRegister.new }.to_not raise_exception
12 end
13 it 'should default to 25,10,5,1' do
14 CashRegister.new.coins.should eq([25,10,5,1])
15 end
16 it 'should reset the coins without reinitialization' do
17 cash_register = CashRegister.new
18 cash_register.coins = [10,5]
19 cash_register.coins.should eq([10,5])
20 end
21 it 'should take an Array of Integers as an argument' do
22 expect { CashRegister.new([25,10,5,1]) }.to_not raise_exception
23 end
24 it 'should throw an error with a bad argument' do
25 expect { CashRegister.new(bad_argument) }.to raise_exception
26 end
27 it 'should throw an error with a bad array argument' do
28 expect { CashRegister.new(bad_array_argument) }.to raise_exception
29 end
30 end
31
32 describe '.make_change()' do
33 subject(:make_change) { cash_register.make_change(amount) }
34 let(:cash_register) { CashRegister.new(coins) }
35 let(:coins) { [25,10,5,1] }
36 let(:amount) { 123 }
37
38 it { should eq({25 => 4, 10 => 2, 5 => 0, 1 => 3}) }
39
40 context 'crazy foreign coins' do
41 let(:coins) { [10,7,1] }
42 let(:amount) { 14 }
43
44 it { should eq({10 => 0, 7 => 2, 1 => 0}) }
45 end
46
47 context 'can\'t make change' do
48 let(:coins) { [2] }
49 let(:amount) { 3 }
50
51 it { should be_nil }
52 end
53
54 context 'memoized zero case' do
55 let(:amount) { 0 }
56
57 it { should eq({25 => 0, 10 => 0, 5 => 0, 1 => 0}) }
58 end
59
60 context 'memoized base case' do
61 let(:amount) { 5 }
62
63 it { should eq({25 => 0, 10 => 0, 5 => 1, 1 => 0}) }
64 end
65 context 'memoized base case' do
66 let(:amount) { 6 }
67
68 it { should eq({25 => 0, 10 => 0, 5 => 1, 1 => 1}) }
69 end
70 end
71 end
72
73 describe Change do
74 subject!(:change) { Change.new(coins) }
75 let(:coins) { [25,10,5,1] }
76
77 describe '#new' do
78
79 it 'should instantiate' do
80 expect { change }.to_not raise_exception
81 end
82 it { should eq({25 => 0, 10 => 0, 5 => 0, 1 => 0}) }
83 end
84
85 describe '.add' do
86 it 'adds coins to the Hash' do
87 change.add(25).should eq({25 => 1, 10 => 0, 5 => 0, 1 => 0})
88 end
89 end
90
91 describe '.value' do
92 its(:value) { should eq(0) }
93
94 it 'is 25 when there is one quarter' do
95 change.add(25).value.should eq(25)
96 end
97 end
98
99 describe '.count' do
100 its(:count) { should eq(0) }
101
102 it 'counts the number of coins' do
103 change.add(25).count.should eq(1)
104 change.add(25).add(10).count.should eq(2)
105 end
106 end
107 end
The Code
1 class CashRegister
2 attr_reader :coins
3
4 def coins=(coins=[25,10,5,1])
5 if (
6 coins.class != Array ||
7 coins.map { |coin| coin.class.ancestors.include?(Integer) }.include?(false)
8 )
9 raise Exception
10 end
11
12 @optimal_change = Hash.new do |hash, key|
13 hash[key] =
14 if (key < coins.min)
15 Change.new(coins)
16 elsif (coins.include?(key))
17 Change.new(coins).add(key)
18 else
19 coins.map do |coin|
20 hash[key - coin].add(coin)
21 end.reject do |change|
22 change.value != key
23 end.min { |a,b| a.count <=> b.count }
24 end
25 end
26
27 @coins = coins
28 end
29
30 alias :initialize :coins=
31
32 def make_change(amount)
33 return(@optimal_change[amount])
34 end
35 end
36
37 class Change < Hash
38 def initialize(coins)
39 coins.map do |coin|
40 self.merge!({coin => 0})
41 end
42 end
43
44 def add(coin)
45 self.merge({coin => self[coin] + 1})
46 end
47
48 def value
49 self.map do |key, value|
50 key.to_i * value
51 end.reduce(:+)
52 end
53
54 def count
55 self.values.reduce(:+)
56 end
57 end
