News & Articles:

Kata: Change Machine

A vending machine has been designed that gives change (sometimes it even dispenses products). It contains a stock of all the usual UK coins, but cannot dispense notes. After each transaction it must calculate the change required, and dispense an appropriate collection of coins. The problem is how many of each coin to dispense.

Background

This is not as easy as it might seem at first glance.

There is obviously a choice here. If the change needed is 56 pence, the machine (among many other possibilities):

  • 1 x 50p, 1 x 5p, 1 x 1p
  • 1 x 50p, 3 x 2p
  • 2 x 20p, 1 x 10p, 1 x 5p, 1 x 1p
  • 56 x 1p

It is clear that the choice between these options should not be made randomly. The machine would not be popular with its users if it always dispensed all their change in pennies, for example.

One simple heuristic might be to always dispense the smallest number of coins possible to make the desired amount. There are plenty of others.

Task

This Kata is to write a program that takes a required amount of change, and displays the best way to make that amount of change. Define “best” as “using the smallest number of coins possible”.

Consider that the machine is of finite size, and therefore can contain only a certain number of each coin. It will also run out of coins over time. It may therefore not always be possible to make every combination of coins. Your program should take account of this.

Consider as a test case the machine trying to give 56p change when it contains 2 x 20p, 1 x 10p, 1 x 5p, 3 x 2p and nothing else. You will quickly note that only one of the three examples given above is possible in this case.

Creative Commons Licence
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

Posted in Technical

Tags: ,