# Cash Register Kata

## 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 }
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
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
96     end
97   end
98
99   describe '.count' do
100     its(:count) { should eq(0) }
101
102     it 'counts the number of coins' do
105     end
106   end
107 end


## The Code

  1 class CashRegister
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))
18         else
19           coins.map do |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
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


Duck typing - the ruby language is duck-typed, and should be written that way. Checks on an object's class are frowned upon. If something wants to be an integer, and is prepared to go the distance - don't discourage it! I understand that the requirement says 'should throw an error if it initialized with an argument that is not an array of integers', so I guess for the sake of argument asking coins.is_a?(Array) is OK, but for the numbers themselves, a more rubyish way of asking would be:

raise Exception unless coins.is_a?(Array) && coins.all?(&:integer?)


I like the way you fill the @optimal_change hash, though I wish you had named your parameters better - key is an obfuscated choice. Also, you could have refactored it into a method

Having is not inheriting - Your Change class is curious - you opted for it to inherit from Hash instead of having a Hash, and then you override count to do something not very Hash-y... The names you chose for this class are very generic and obfuscated... I would have written that class like this:

class Change
def initialize(coins = Hash.new(0))
@coins = coins
@coins.default = 0
end

# changes the value of this instance
@coins[coin] = @coins[coin] + 1
self
end

# does not change the value of this instance
end

def total_value
@coins.map { |coin, number| coin * number }.reduce(:+)
end

def coin_count
@coins.values.reduce(:+)
end
end

• Great answer. I actually did rename the Hash parameters to 'optimal_change' and 'amount'. Definitely going to refactor it into a method. Feb 26 '14 at 1:10

Edit: I just completed changes to the code and explanation to fix problems that @Jonah spotted. Thanks, Jonah. I believe it is working correctly now, but I hope readers will let me know if they find any other problems.

• the specs are quite good for testing the specified edge cases, but I think you might beef them up for testing whether the algorithm actually produces optimal solutions.

• I think you missed a few edge cases that were not called for, but are needed (see code below). I don't recall seeing what make_change returns when there is no way to change a particular amount. (I chose nil).

• When raising an exception, make it more specific (e.g, ArgumentError) and include an explanatory message.

• in the Change class, none of the self.'s are needed. When no receiver is specified, the default is self. There are only a couple of situations where you need to preface a method being referenced (as opposed to a class method being defined) with self.. One is where you wish to reference an instance variable with an accessor, as self.ivar = 7. Without self., Ruby would assume ivar is a local variable. The other situation is where you need to convert an instance to its class, as self.class.my_cl_method. self. is required here to tell Ruby you mean the class method rather than the class keyword.

• Change#value can be simplified a little: def value; reduce(0) { |t,(k,v)| t + k.to_i * v }; end.
• I had difficulty following the CashRegister#make_change, but it doesn't appear to implement a dynamic programming algorithm, though you did observe that that ('knapsack') is what is needed. [Edit: I was incorrect about that. I just didn't understand that part of the code.] Please correct me if I am wrong about that.
• I ran a few tests with your code and in some cases it failed. Here's one: CashRegister.new([2,5,12,18,35,36]).make_change(67). This raised an exception that indicated that hash[key - coin] in hash[key - coin].add(coin) was nil. (The solution is given below.)

Regarding the code that follows:

• I didn't see the need for a Change class, but I have no objection to there being one, though (as @Uri noted), there doesn't seem to be an advantage to subclassing Hash.

• I used recursion to obtain minimal change, but the problem does not intrinsically call for recursion; a loop would work as well, but I thought the use of recursion made it easier to understand what's going on.

Here's an approach you could use:

class CashRegister
def initialize(coins = [1,5,25,50])
check_coins(coins)
@coins = coins.reject(&:zero?)
# All coins, if any are now positive
end

def make_change(amt)
check_amt_to_change(amt)

# Check edge cases
return (amt.zero? ? {} : nil) if @coins.empty?
return Hash[@coins.map(&:to_s).product([0])] if amt == 0
return nil if @coins.max == 0
coin = @coins.first
return ((amt % coin).zero? ? {coin.to_s => amt/coin} : nil) if @coins.size == 1

# To reach this point amt > 0 and @coins.size > 1

# Construct hash to record solution.  If the coins are c0, c1,...,cn, and x,
# 0 <= x <= amt, change[ci][x] => {tot: t, ncoin: n}, where t equals the minimum
# number of coins c0 through ci needed to change x and n is the number of coin ci
# of that total.  This is only computed for those values of x for which it is possible
# to make change using coins c0 through ci. change is first computed for coin c0,
# then for coins, c1, and so on.  For the last coin, m = n-1, it is only necessary to
# calculate change[cm][x] for x = amt.

@change = {}

# Compute @change for the first coin.
coins = @coins.dup
coin = coins.shift
@change[coin] = (0..amt/coin).each_with_object({}) { |i,h|
h[i*coin] = {tot: i, ncoin: i} }

# Compute the solution for each of the remaining coins.
minimum_change(amt, coin, coins)

retrieve_solution(amt)
end

private

def check_coins(coins)
raise ArgumentError, "arg in coins(arg) must be an array" unless (coins.is_a? Array)
raise ArgumentError, "elements of of arr in coins(arr) must be non-negative integers" \
unless coins.all? { |c| (c.is_a? Integer) && (c >= 0) }
end

def check_amt_to_change(amt)
raise ArgumentError, "amount to be changed must be a non-negative integer" \
unless ((amt.is_a? Integer) && (amt >= 0))
end

def minimum_change(amt, last_coin, remaining_coins)
coin = remaining_coins.shift
first = (remaining_coins.empty? ? amt : 0)
@change[coin] = (first..amt).each_with_object({}) do |x,h|
best = nil
(0..x/coin).each do |i|
if (lc = @change[last_coin][x-i*coin])
best = {tot: i+lc[:tot], ncoin: i} if (best.nil? || i+lc[:tot] < best[:tot])
end
end
h[x] = best unless best.nil?
end
minimum_change(amt, coin, remaining_coins) if remaining_coins.any?
end

def retrieve_solution(amt)
return nil if @change[@coins.last].empty?
x = amt
@coins.reverse.each_with_object({}) do |coin,h|
k = @change[coin][x][:ncoin]
h[coin.to_s] = k
x -= k * coin
end
end
end


Some test results

cr = CashRegister.new([1,5,10,25])
amt
123  (9) => {"25"=>4, "10"=>2, "5"=>0, "1"=>3}
100  (4) => {"25"=>4, "10"=>0, "5"=>0, "1"=>0}
199 (13) => {"25"=>7, "10"=>2, "5"=>0, "1"=>4}
23  (5) => {"25"=>0, "10"=>2, "5"=>0, "1"=>3}
0  (0) => {"1"=>0, "5"=>0, "10"=>0, "25"=>0}

cr = CashRegister.new([7,12,25,34]
amt
68  (2) => {"34"=>2,  "25"=>0, "12"=>0, "7"=>0}
233 (10) => {"34"=>1,  "25"=>7, "12"=>2, "7"=>0}
848 (26) => {"34"=>22, "25"=>4, "12"=>0, "7"=>0}
47  (6) => {"34"=>0,  "25"=>0, "12"=>1, "7"=>5}

cr = CashRegister.new([2,5,12,18,35,36])
amt
67  (4) => {"36"=>0, "35"=>1 , "18"=>1, "12"=>1, "5"=>0, "2"=>1}
233  (7) => {"36"=>5, "35"=>1 , "18"=>1, "12"=>0, "5"=>0, "2"=>0}
848 (24) => {"36"=>8, "35"=>16, "18"=>0, "12"=>0, "5"=>0, "2"=>0}
47  (2) => {"36"=>0, "35"=>1 , "18"=>0, "12"=>1, "5"=>0, "2"=>0}
3 (nil)

cr = CashRegister.new([1,5,10,25,100,500,1000])
amt
9332 (16) => {"1000"=>9,  "500"=>0, "100"=>3, "25"=>1, "10"=>0, "5"=>1, "1"=>2}
18445 (25) => {"1000"=>18, "500"=>0, "100"=>4, "25"=>1, "10"=>2, "5"=>0, "1"=>0}
9999 (23) => {"1000"=>9,  "500"=>1, "100"=>4, "25"=>3, "10"=>2, "5"=>0, "1"=>4}
23  (5) => {"1000"=>0,  "500"=>0, "100"=>0, "25"=>0, "10"=>2, "5"=>0, "1"=>3}
0  (0) => {"1"=>0, "5"=>0, "10"=>0, "25"=>0, "100"=>0, "500"=>0, "1000"=>0}

cr = CashRegister.new([])
amt
0 => {}
23 =>    # nil

• Thanks Cary. These are great points. The dynamic programming is encapsulated here: hash[key - coin].add(coin). The block argument to Hash.new() is executed if there is ever a mis in a hash lookup. So, each coin is added to the optimal change for the amount minus the value of the coin. This will recurse down until it bottoms out on one of the base cases. Feb 27 '14 at 21:44
• Re: CashRegister.new([2,5,12,18,35,36]).make_change(67), This was due to not handling amounts < coins.min well. I took your advice and returned nil if change cannot be made. Then, added a few tests to make sure that change is not nil. Thanks! Feb 27 '14 at 22:06
• You may wish to edit your question to add the corrected code, and to add a few comments to explain the algorithm you are using for the make_change calculation. Feb 28 '14 at 3:30
• I'm confused by your spec for 67 => {"36"=>0, "35"=>1, "18"=>0, "12"=>2, "5"=>0, "2"=>4}. I'm getting {36=>0, 35=>1, 18=>1, 12=>1, 5=>0, 2=>1}. What am I missing? Thanks. Feb 28 '14 at 5:40
• @Jonah, it appears I'm the one missing something, namely a penny on 848 =>. Also, I'm over by six cents on 233 =>, and some solutions aren't optimal. I'll fix it tomorrow. Thanks. Feb 28 '14 at 6:01