10
\$\begingroup\$

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
\$\endgroup\$
3
\$\begingroup\$

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
  def add!(coin)
    @coins[coin] = @coins[coin] + 1
    self
  end

  # does not change the value of this instance
  def add(coin)
    Change.new(@coins.dup).add!(coin)
  end

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

  def coin_count
    @coins.values.reduce(:+)
  end
end
\$\endgroup\$
  • \$\begingroup\$ Great answer. I actually did rename the Hash parameters to 'optimal_change' and 'amount'. Definitely going to refactor it into a method. \$\endgroup\$ – user341493 Feb 26 '14 at 1:10
3
\$\begingroup\$

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.

I have just a few comments about your code:

  • 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.)
  • A few well-placed comments would have been helpful.

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
\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – user341493 Feb 27 '14 at 21:44
  • \$\begingroup\$ 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! \$\endgroup\$ – user341493 Feb 27 '14 at 22:06
  • \$\begingroup\$ 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. \$\endgroup\$ – Cary Swoveland Feb 28 '14 at 3:30
  • \$\begingroup\$ 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. \$\endgroup\$ – Jonah Feb 28 '14 at 5:40
  • \$\begingroup\$ @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. \$\endgroup\$ – Cary Swoveland Feb 28 '14 at 6:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.