Code Kata – Make Change, Solving and Refactoring

I recently went through a Code Kata with my friend @koriroys. The kata is called "Make Change" and objective is to take a random integer and return the value of that integer in coins. If you give me 100 pennies I give you back 4 quarters. If you give me 61 pennies I give you back 2 quarters, 1 dime, and 1 penny.

It was a fun little exercise, not terribly difficult to solve but a great one for refactoring. Kori gave me some good tips and techniques for refactoring and I will demonstrate a few of those in this post.

First off I will give you the tests. Take the tests and come back after you have them all passing. Don't perfect your solution, just solve it as quickly as you can.

Tests

require 'rspec'

describe Changer do
  it 'can change one quarter' do
    Changer.make_change(25).should == [25]
  end

  it 'can change multiple quarters' do
    Changer.make_change(50).should == [25, 25]
  end

  it 'can change one dime' do
    Changer.make_change(10).should == [10]
  end

  it 'can change multiple dimes' do
    Changer.make_change(20).should == [10, 10]
  end

  it 'can change small complex amounts' do
    Changer.make_change(7).should == [5, 1, 1]
  end

  it 'can change large complex amounts' do
    Changer.make_change(68).should == [25, 25, 10, 5, 1, 1, 1]
  end
end

Version 1

This is the first solution I came up with.

class Changer

  def self.make_change(cents)

    change = []

    (cents / 25).times do
      change << 25
      cents -= 25
    end

    (cents / 10).times do
      change << 10
      cents -= 10
    end

    (cents / 5).times do
      change << 5
      cents -= 5
    end

    cents.times do
      change << 1
    end

    change
  end
end

As you can see it's fairly repititive. I store the coins in an array called change. Then for each possible coin value I create a loop. For every loop I have to know how many times the loop should run, it should only run as many times as the coin value can be extracted from the total number of cents. Look at the first loop. If there are 100 cents, 100 / 25 will give you four. That loop will only run 4 times and you will end up shoving 4 quarters into the change array. Each time a quarter is shoved into the change array, the total number of cents decreases by 25. Every one of these loops works the same way.

At this point it's obvious that all four of these loops that do the same thing should be moved into one loop. Before we can do that we have to identify which pieces inside each loop are changing every time. In other words when looking at these loops what part do you see that is not the same in every single loop? Hopefully you said the value of the coin. The value of the coin changes in every loop. It changes from 25 to 10 to 5 to 1. You may have also noticed that the last loop is slightly different. The reason for this being that once we get down to pennies, it is no longer necesseary to track the number of cents remaining. We are just throwing every cent left into the change array as a penny. But it is not significantly different so you should give it no special attention.

We've established that the value of the coin changes every time. I see the number 25 three times in the first loop, the number 10 three times in the second loop and so on and so on. Let's swap all those numbers out with a variable called coin_value and then set the value of the variable before each loop. Technically this makes the program larger, but our goal is to make it easier to throw all of this logic into one loop and making all those numbers into the same variable is a good start.

Version 2

class Changer

  def self.make_change(cents)

    change = []

    coin_value = 25

    (cents / coin_value).times do
      change << coin_value
      cents -= coin_value
    end

    coin_value = 10

    (cents / coin_value).times do
      change << coin_value
      cents -= coin_value
    end

    coin_value = 5

    (cents / coin_value).times do
      change << coin_value
      cents -= coin_value
    end

    coin_value = 1

    cents.times do
      change << coin_value
    end

    change
  end
end

Okay great we have removed all those hard coded numbers and replaced them with a variable. Now we are setting the variable value before each loop. Now look at the code again. What is changing every time? The coin value is still changing every time but it is not hard coded into every loop which means we are getting closer to turning all these loops into one single loop. We just need to find a way to iterate over these 4 four different coin values. How might we iterate over 4 different items? Perhaps putting these four items into any array then doing a .each on them?

Version 3

class Changer

  def self.make_change(cents)

    change = []

    [25,10,5,1].each do |coin_value|
      (cents / coin_value).times do
        change << coin_value
        cents -= coin_value
      end
    end

    change
  end
end

Nice! All the tests are still passing and we have reduced this down to one loop. We could stop here but Kori showed me a nice way to get rid of that change array that we are setting at the beginning and returning at the end of the method. We can use a method called .with_object. So .each becomes .each.with_object([]). Passing the array [] as the argument for .with_object.

Version 4

class Changer

  def self.make_change(cents)

    [25,10,5,1].each.with_object([]) do |coin_value, change|
      (cents / coin_value).times do
        change << coin_value
        cents -= coin_value
      end
    end

  end
end

And the above code is where I stopped. Can you reduce the code above and maintain readability? Share your code in the comments or with a link to a gist.