Coin Change Kata

Posted by in Node.js, Tech on Nov 10th, 2012 | 2 comments

At the SCNA conference this year, I was reminded of the importance of practice for craftsmen.

In one of the breaks, there was a “kata battle” where two people were competing to see who could get a complete implementation of the Coin Change Kata working first.

The Coin Change Kata exercise should produce the minimal amount of change for a given amount.

For instance, If the input is: $0.99, the output should be: 3 quarters, 2 dimes, and 4 pennies.

I was inspired to take this on myself and sharpen the saw.

You can find my node.js implementation here.

There are 10 commits that demonstrate each step of the red-green-refactor process.

The first version of the code is simple and hardcoded. This is always a great starting place:

1
2
3
4

var Change = {}
module.exports = Change
 
Change.makeChange = function(amount) { return [] }

It returns a valid result when the amount is 0, but for any other amount, the result is not valid. Not terribly useful yet.

# node
> var Change = require('./change')
> Change.makeChange(0)
[]
> Change.makeChange(1)
[]
> // WRONG! Should be: [1]

By the third iteration, I’ve introduced recursion into the mix to keep the code concise. This is the foundation for the final version, 7 commits later.

1
2
3
4
5
6
7
8

var Change = {}
module.exports = Change
 
Change.makeChange = function(amount, change) {
  if (amount <= 0) return change
  change.push(1)
  return Change.makeChange(amount-1, change)
}

This solution produces the correct result for amounts 0 – 4, but incorrect for any other amount.

# node
> var Change = require('./change')
> Change.makeChange(4,[])
[ 1, 1, 1, 1 ]
> Change.makeChange(5,[])
[ 1, 1, 1, 1, 1 ]
> // WRONG! Should be: [5]

Continuing to iterate, I arrived at my solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14

var Change = {}
module.exports = Change
 
var getDenom = function(amount, types) {
  for (var i = 0; i < types.length; i++) {
    if (Math.floor(amount/types[i])) return types[i]
  }
}
 
Change.makeChange = function(amount, change) {
  if (amount <= 0) return change
  var denom = getDenom(amount, [25, 10, 5, 1])
  return Change.makeChange(amount-denom, change.concat(denom))
}

All amount values return the proper result:

# node
> var Change = require('./change')
> Change.makeChange(0,[])
[]
> Change.makeChange(1,[])
[ 1 ]
> Change.makeChange(6,[])
[ 5, 1 ]
> Change.makeChange(11,[])
[ 10, 1 ]
> Change.makeChange(16,[])
[ 10, 5, 1 ]
> Change.makeChange(41,[])
[ 25, 10, 5, 1 ]
> Change.makeChange(99,[])
[ 25, 25, 25, 10, 10, 1, 1, 1, 1 ]
> // FTW!!!

Aside from the joy in working through a problem like this (nerd alert!), I was left with two important takeaways (which are really reiterations or reinforcements of past lessons):

  1. Using simple language constructs can often be favorable to a “fancy” solution
  2. There is value in refining tests for readability and extensibility as you go

At one point along the way, I was trying to refine my getDenom function. I wasn’t happy with the if-else if-else construct. So, I tried to write something better using some fancier constructs.

Here’s where I started:

1
2
3
4
5
6

var getDenom = function(amount) {
  if (Math.floor(amount/25))      return 25
  else if (Math.floor(amount/10)) return 10
  else if (Math.floor(amount/5))  return 5
  else                            return 1
}

Here was my attempt to make it better:

1
2
3
4
5
6
7
8
9
10
11

var getDenom = function(amount) {
  var denom = 1;
  [25, 10, 5].some(function(moolah) {
    if (Math.floor(amount/moolah)) {
      denom = moolah
      return true
    } else
      return false
  })
  return denom
}

Yikes! (it works, believe it or not).

Here’s where I ended up:

1
2
3
4
5

var getDenom = function(amount, types) {
  for (var i = 0; i < types.length; i++) {
    if (Math.floor(amount/types[i])) return types[i]
  }
}

In the end, a simple 3-line “for” loop proved to be the solution I was looking for. It also makes calling the function more expressive:

> getDenom(99, [25, 10, 5, 1])
25

In the final version of getDenom, the array of valid types is passed in with the call. This keeps the function concise and makes it easy to add to the list of types.

In the main body of the code, getDenom is only called once, so this approach is acceptable. If it needed to be called more often, it would make sense to move the types array into the function.

An early iteration of my test looked like this:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

describe('make change 3', function() {
  it('0', function(done) {
    expect(Change.makeChange(0,[])).to.eql([])
    done()
  })
 
  it('1', function(done) {
    expect(Change.makeChange(1,[])).to.eql([1])
    done()
  })
 
  it('2', function(done) {
    expect(Change.makeChange(2,[])).to.eql([1, 1])
    done()
  })
})

I knew that I would need a bunch more test cases as I worked my way through the problem to show that my code worked for a bunch of significant amounts. I also knew that this test would get more and more verbose. My colleague, JP, re-architected my test file to look like this:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

describe('make change 4', function() {
  var tests = [
    { input: 0,  expected: [] },
    { input: 1,  expected: [1] },
    { input: 2,  expected: [1, 1] },
    { input: 3,  expected: [1, 1, 1] },
    { input: 4,  expected: [1, 1, 1, 1] }
  ]
 
  _.each(tests, function(test) {
    it(test.input, function() {
      expect(Change.makeChange(test.input, [])).to.eql(test.expected)
    })
  })
})

This reduced repetition in the code and made it very easy to add additional tests. It also makes the output of the tests nice and readable.

# make
 
  make change
    ✓ 0 
    ✓ 1 
    ✓ 2 
    ✓ 3 
    ✓ 4 
 
  ✔ 5 tests complete (10ms)

For the next round of development, I needed to make the code work for amounts greater than 4. I simply changed the tests to this:

1
2
3
4
5
6
7
8
9

var tests = [
  { input: 0,  expected: [] },
  { input: 1,  expected: [1] }
  { input: 2,  expected: [1, 1] },
  { input: 3,  expected: [1, 1, 1] },
  { input: 4,  expected: [1, 1, 1, 1] },
  { input: 5,  expected: [5] },
  { input: 6,  expected: [5, 1] }
]

My test failed and I was off to fix the code.

# make
 
  make change
    ✓ 0 
    ✓ 1 
    ✓ 2 
    ✓ 3 
    ✓ 4 
    1) 5
    2) 6
 
  ✖ 2 of 7 tests failed:
 
  1) make change 5:
     Error: expected [ 1, 1, 1, 1, 1 ] to sort of equal [ 5 ]
 
  2) make change 6:
     Error: expected [ 1, 1, 1, 1, 1, 1 ] to sort of equal [ 5, 1 ]

There was a lot of value for my development effort and for other people reading my code by making these changes to the test.

Can you refine the implementation or the tests to make a better solution? Clone the project, make it better and let me know what you came up with in the comments.



2 Responses to “ “Coin Change Kata”

  1. David Turner says:
    November 19, 2012 at 8:12 am

    Note that your solution works for the US coin denominations but doesn’t work in general. For example, if you have coins of denomination 1, 3 and 4 cents, your algorithm makes up 6 cents as [4,1,1] whereas the minimal number of coins for this is [3,3]. It’s not clear whether this is part of the Kata – YAGNI?

    Reply

Leave a Reply