Geoff Bones

30 January 2014

Code kata 1: Old money

The kata

Imagine: it’s 1968 – the Beatles, Carnaby St and Austin Powers – except there’s all the technology of 2013 as well. Including vending machines.

But, being 1968, vending machines have to deal with old money. It’s quite simple; I’ll describe it here.

Money is made up of pounds (£), shillings (s) and pence (d).

• 12d = 1s.
• 20s = £1.

The coins and their values are

• Pronounced “haypni”

**Pronounced “threppni bit” or “thruppni bit”

The task

Your job is

1. To write the software that decides how a customer is to receive their change after their purchase. So, given the amount of money the customer should be given, your software should produce the collection of coins that should be given as change. The software must choose a combination that requires the smallest number of coins to be returned. The software doesn’t need to know about the items themselves or their prices.

Examples:

• • The customer requires 1s 4½d in change. The software should return 1 x shilling, 1 x threepenny bit, 1 x penny and 1 x halfpenny.
  • The customer requires 3s in change. The software should return either 1 x half crown and 1 x sixpenny bit or 1 x florin and 1 x shilling. Either is correct.
  • The customer requires 4s in change. The software should return 2 x florin.
  • The customer requires 4s 6d in change. The software should return 1 x half crown and 1 x florin.

2. If you get time, modify the software to make it adjust to the coins the machine is holding.

Examples:

• • The customer requires 4s in change but the machine has no florins. The software should return 1 x half crown, 1 x shilling and 1 x sixpenny bit.
  • The customer requires 3s in change but the machine has no sixpenny bits. The software should return 1 x florin and 1 x shilling.
  • The customer requires 3s in change but the machine has no florins. The software should return 1 x half crown and 1 x sixpenny bit.

The constraints

To make this a bit more interesting wrap all native types. Thus, strings, ints, decimals and so on shouldn’t be exposed in your code except as private class members (and in the corresponding wrapper’s constructor, where necessary).

How did it go?

It was, well, “interesting”.

We caught up afterwards with a few of the pairs who had attempted the kata. None of them had gone on to the second part, so probably the first question on its own would be enough to fill our 90 minute time cap.

One adventurous pair had decided that the problem was perfectly suited to a functional language and so set off to solve it in F#. Their ambition overreached them, which I guess is understandable given that this was their first time to write F#, and I think they were reasonably satisfied to get “Hello, world” compiling.

So what about those who’d actually done the kata? They’d stuck to C#, which is well-known territory for us at Redgate. One pair, for example, had come up with an algorithm that constructed a tree breadth first to explore all the possible coin combinations; the first solution the tree yielded was guaranteed to be one of those with the fewest coins. By pruning the tree of branches that were clearly leading in the wrong direction they’d kept it small enough to solve quickly. Very neat.

Another pair had managed to get something working with a greedy algorithm (always choosing the largest suitable coin). They’d had to adapt it, of course, to handle the special cases where florins should be given rather than half crowns. We’re not sure they were completely happy with this approach, and you could see a certain lack confidence in a couple of methods in their code, which they’d called FudgeFactor(), and – a flash of blinding creativity – FudgeFactor2().

But the aim of the kata wasn’t writing algorithms; it was really about getting a feel for wrapping native types. Did they like the classes they had come up with? Were they helpful or did they get in the way? What about the idea of wrapping up raw types as a coding discipline?

Most pairs had come up with something like a Coin class and an AmountOfMoney class, although each pair had given their classes slightly different roles. One problem the group highlighted was the need to create equality members on each class. Aside from actually writing them (which Resharper will do for you), they clutter the code and distract the reader from the solution itself.

Would they think about wrapping raw types in this way in real code? Perhaps, but there wasn’t a great rush of enthusiasm over it.

We might try this constraint out again in another kata, but perhaps with a simpler problem, and see if the feedback is any different.