Nowadays supermarket customers can check out themselves and scan products themselves. Many obviously pay by card but I was interested to see how a cash dispensing till would work.

I have written some Python code to simulate the whole setup. We start with a till that has a distibution of coins (1000 1p etc). The key function is change(), which given a price and total paid (difference rem) has to issue the right coin change. It finds the largest coin below the rem and then works from largest to smallest to issue correct change. This way we try to avoid running out of small coins. This large-to-small algorithm is very simple and probably close how humans would do it. One improvement could be to under-sample coins that we have few off in the till.

The trickiest bit (draw()) is simulating what a customer would give in change. I had to add some randomness to it to stock up small coins (10% of time customer gives exact change in 1, 2 or 5p coins). Without this part the till will run out of change very quickly.

I work a lot with global variables in this example as I don’t have to handle function IO so much.

 

In this example I want to show the principles of dynamic programming and recursion in a simple example. Imagine you have coins of different values and you want to count the many ways that those coins can make up 200 pennies/cents. To solve this problem we use a recursive function which grows like a tree. You start with the biggest coins first.

Define a function add() which first loops through all coins. If we have an empty current set or the current coin is less or equal the last coin in the current set, then continue: if the sum of the set plus the proposed coin is less than 200, then add the current coin to the set and pass the new set to add(); if the sum of the set plus the current coin equals 200, add the coin to the set and add the new set to the set of solutions (do nothing if 200 is exceeded). Finally print the length of all solutions which is 73682.

This a recursive setup where add() references itself – you pass a current unfinished set to this function.

Here is the code in Python (v3) – it takes 7 seconds on repl.it.