Coins.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Time for change.\n",
    "\n",
    "Somewhere close to the start of the English maths curriculum, pupils learn to work with coins, initially as physical manipulatives, then as icons and eventually as numbers. By the age of seven or eight, pupils are taught to “find different combinations of coins that equal the same amounts of money”. This sounds quite straightforward.\n",
    "\n",
    "Finding the smallest number of coins to make a particular amount of money is something we do without consciously thinking about it, but if you had to teach a child to do this, what method would you suggest? It’s something which machines can do too: vending machines give change; good vending machines give change using the smallest number of coins they can. How would you program a vending machine to do that?\n",
    "\n",
    "A greedy algorithm\n",
    "\n",
    "It’s a problem that lends itself to a greedy algorithm:\n",
    "\n",
    "* start with the largest value coin\n",
    "* keep giving that coin until the amount left is less than the value of * the coin\n",
    "* move on to the next largest value coin and do that again,\n",
    "* keep moving on to the next largest value of coin until there are no more coin values left.\n",
    "\n",
    "Following this algorithm by hand seems to give the answers we expect. E.g. 38p change: 20p, 10p, 5p, 2p, 1p.\n",
    "\n",
    "A näive approach to coding this in Scratch might look a little like this:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "how much money in pence?139\n",
      "You need  6  coins\n"
     ]
    }
   ],
   "source": [
    "total = int(input('how much money in pence? '))\n",
    "coins = 0\n",
    "\n",
    "while total >= 200:\n",
    "    total -= 200\n",
    "    coins += 1\n",
    "while total >= 100:\n",
    "    total -= 100\n",
    "    coins += 1\n",
    "while total >= 50:\n",
    "    total -= 50\n",
    "    coins += 1\n",
    "while total >= 20:\n",
    "    total -= 20\n",
    "    coins += 1\n",
    "while total >= 10:\n",
    "    total -= 10\n",
    "    coins += 1\n",
    "while total >= 5:\n",
    "    total -= 5\n",
    "    coins += 1\n",
    "while total >= 2:\n",
    "    total -= 2\n",
    "    coins += 1\n",
    "while total >= 1:\n",
    "    total -= 1\n",
    "    coins += 1\n",
    "\n",
    "print('You need', coins, 'coins')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Well, it certainly seems to work, but no one is likely to claim this is a particularly elegant implementation - there's just so much repetition here, isn't there? And we've these horrible, hard-coded, magic numbers. \n",
    "Let's pass the coinage system as a list, and just iterate over the list. Here we go:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "How much money in pence? 139\n",
      "You need 6 coins\n"
     ]
    }
   ],
   "source": [
    "def numberofcoins1(amount, coins=[1, 2, 5, 10, 20, 50, 100, 200]):\n",
    "    change = []\n",
    "    while amount > 0 and coins != []:\n",
    "        if amount >= coins[-1]:\n",
    "            change = change + [coins[-1]]\n",
    "            amount -= coins[-1]\n",
    "        else:\n",
    "            del coins[-1]\n",
    "    return len(change)\n",
    "\n",
    "\n",
    "amount = int(input('How much money in pence? '))\n",
    "print('You need', numberofcoins1(amount), 'coins')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Same answers, and essentially the same method, but much easier to maintain, and indeed understand. \n",
    "\n",
    "This works well enough for English coins. We can generalise this though: it’s easy enough to modify it to work with US coinage too, with English pre-decimal (or post-Brexit?) currency, and with the equally Byzantine Galleons, Sickles and Knuts if you find yourself teaching programming at Hogwarts."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "How much money in cents? 39\n",
      "You need 6 American coins\n"
     ]
    }
   ],
   "source": [
    "amount = int(input('How much money in cents? '))\n",
    "print('You need', numberofcoins1(amount, [1, 5, 10, 25]), 'American coins')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Bit coins?\n",
    "\n",
    "But look, it works well enough for this set of coins too: 128, 64, 32, 16, 8, 4, 2, 1. That is, the binary place values for eight bits."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Give me a number in denary below 256: 42\n",
      "That has 3 on bits\n"
     ]
    }
   ],
   "source": [
    "amount = int(input('Give me a number in denary below 256: '))\n",
    "print('That has', numberofcoins1(\n",
    "    amount, [1, 2, 4, 8, 16, 32, 64, 128]), 'on bits')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given the ease with which pupils can find the smallest number of coins for amounts, I think a set of, let’s call them, bit-coins, perhaps first as manipulatives, then as pictures, finally as numbers, could be the easiest way to get pupils converting numbers to binary.\n",
    "\n",
    "The above Python code works well enough for working out the bit values, and could be used for other number bases too – use 64, 8 and 1 to get octal. Use 16 and 1 to get hexadecimal. I think a coin-based model such as this goes a long way to internalise an understanding of the maths here.\n",
    "\n",
    "If we’d like to actually get the binary out, then a little remixing is needed."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Give me a number in denary below 256: 42\n",
      "In binary, that is  00101010\n"
     ]
    }
   ],
   "source": [
    "def decimalToBinary(decimal):\n",
    "    bitValues = [128, 64, 32, 16, 8, 4, 2, 1]\n",
    "    bits = \"\"\n",
    "    for value in bitValues:\n",
    "        if decimal >= value:\n",
    "            bits = bits + \"1\"\n",
    "            decimal = decimal - value\n",
    "        else:\n",
    "            bits = bits + \"0\"\n",
    "    return bits\n",
    "\n",
    "\n",
    "amount = int(input('Give me a number in denary below 256: '))\n",
    "print('In binary, that is ', decimalToBinary(amount))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Alternative approaches\n",
    "\n",
    "Turns out, we can do the whole thing in a single line of code, using integer division and remainders. I don't like this, but what do you think?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "How much money in pence? 139\n",
      "You need 6 coins\n"
     ]
    }
   ],
   "source": [
    "def numberofcoins0(amount):\n",
    "    return amount // 200 + \\\n",
    "        amount % 200 // 100 + \\\n",
    "        amount % 200 % 100 // 50 + \\\n",
    "        amount % 200 % 100 % 50 // 20 + \\\n",
    "        amount % 200 % 100 % 50 % 20 // 10 + \\\n",
    "        amount % 200 % 100 % 50 % 20 % 10 // 5 + \\\n",
    "        amount % 200 % 100 % 50 % 20 % 10 % 5 // 2 + \\\n",
    "        amount % 200 % 100 % 50 % 20 % 10 % 5 % 2\n",
    "\n",
    "\n",
    "amount = int(input('How much money in pence? '))\n",
    "print('You need', numberofcoins0(amount), 'coins')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Functional programmers don't like iterating over lists: they'd rather keep calling a function with smaller and smaller lists of coins. Our base case here is that you can't make change if you don't have any coins."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "How much money in pence? 139\n",
      "You need 6 coins:  [100, 20, 10, 5, 2, 2]\n"
     ]
    }
   ],
   "source": [
    "def numberofcoins2(amount, coins=[1, 2, 5, 10, 20, 50, 100, 200], change=[]):\n",
    "    if len(coins) == 0:\n",
    "        return change\n",
    "    elif amount >= coins[-1]:\n",
    "        return numberofcoins2(amount - coins[-1], coins, change + [coins[-1]])\n",
    "    else:\n",
    "        return numberofcoins2(amount, coins[:-1], change)\n",
    "\n",
    "\n",
    "amount = int(input('How much money in pence? '))\n",
    "print('You need', len(numberofcoins2(amount)),\n",
    "      'coins: ', numberofcoins2(amount))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## However...\n",
    "\n",
    "All this looks great, doesn’t it? We’ve got a general algorithm here to solve all sorts of coin decomposition problems, and have generalised it to convert numbers from to binary and even to other number bases.\n",
    "\n",
    "The problem is, this algorithm doesn’t always work.\n",
    "\n",
    "What about coins worth 1p, 10p, 20p and 25p coins. How would you make 40p? If you follow the greedy algorithm, you’d use a 25p, 10p and five 1p coins, so that’s seven coins in all. If you stop and think a bit, you might decide that just two, 20p coins would be better! How come the greedy algorithm brakes down here?\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "How much money in pence? 40\n",
      "You need these coins:  [25, 10, 1, 1, 1, 1, 1]\n"
     ]
    }
   ],
   "source": [
    "amount = int(input('How much money in pence? '))\n",
    "print('You need these coins:', numberofcoins2(amount, [1, 10, 20, 25]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Or, imagine that we only have 7p and 9p coins. What combination would you use to make 47p? My Python code happily returns five 9p coins, but that’s wrong! You can’t make 47p using just 7p and 9p ‘coins’. Why not? You can, however, make any amount bigger than 47p, although my greedy algorithm gets most of these wrong too."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "How much money in pence? 47\n",
      "You need these coins:  [9, 9, 9, 9, 9]\n"
     ]
    }
   ],
   "source": [
    "amount = int(input('How much money in pence? '))\n",
    "print('You need these coins:', numberofcoins2(amount, [7, 9]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Coming up with an algorithm that works for these situations too is a bit more tricky, but one approach relies on the recursive nature of the problem. Sticking with the English coinage, to make 38p, you could start with a 20p and make 18p, or start with 10p and make 28p, or start with 5p and make 33p, or start with 2p and make 36p, or start with 1p and make 37p. So the smallest number of ways to make 38p has to be one more than the smallest number of ways to make 18p, 28p, 33p, 36p or 37p, whichever is least.\n",
    "\n",
    "Our recursive rule here looks like:\n",
    "```\n",
    "minimumcoins(x) = 1 + minimum (\n",
    "\tminimumcoins(x-200),\n",
    "\tminimumcoins(x-100),\n",
    "\tminumumcoins(x-50),\n",
    "\tminimumcoins(x-20),\n",
    "\tminimumcoins(x-10),\n",
    "    minimumcoins(x-5),\n",
    "    minimumcoins(x-2),\n",
    "    minimumcoins(x-1))\n",
    "```\n",
    "With the base cases that minimumcoins for 200, 100, 50, 20, 10, 5, 2 and 1 are all 1, as the smallest number of coins needed to make 50p is pretty trivial!\n",
    "\n",
    "Generalising this for any set of coin values gives us this recursive Python code:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "How much money in pence? 35\n",
      "You need 3 coins\n",
      "4.538736999999998 seconds\n"
     ]
    }
   ],
   "source": [
    "import time\n",
    "\n",
    "\n",
    "def numberofcoins3(amount, coins=[1, 2, 5, 10, 20, 50, 100, 200]):\n",
    "    minCoins = amount\n",
    "    if minCoins in coins:\n",
    "        return 1\n",
    "    else:\n",
    "        for thisCoin in [coin for coin in coins if coin <= amount]:\n",
    "            numCoins = 1 + numberofcoins3(amount - thisCoin, coins)\n",
    "            if numCoins < minCoins:\n",
    "                minCoins = numCoins\n",
    "        return minCoins\n",
    "\n",
    "\n",
    "amount = int(input('How much money in pence? '))\n",
    "startTime = time.clock()\n",
    "print('You need', numberofcoins3(amount), 'coins')\n",
    "print(time.clock() - startTime, 'seconds')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "There are things we can do to speed this up – using a dictionary to keep track of the minimum coins found so far for each amount we look up helps. If we go to the trouble of keeping track like this, it’s actually faster to build up the dictionary from the bottom up – with English coins, you need 1 coin to make 1p, 1 coin to make 2p, 2 coins to make 3p, 2 coins to make 4p, 1 coin to make 5p, and so on. To find out how many coins you need to make 6p, you need to take the minimum from making 5p (1), 4p (2) or 1p (1) and add on a coin to that, so that’s two coins, as you’d expect."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 68,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "How much money in pence? 39\n",
      "You need 5 coins\n",
      "0.001677999999998292 seconds\n"
     ]
    }
   ],
   "source": [
    "def numberofcoins4(amount, coins=[1, 2, 5, 10, 20, 50, 100, 200]):\n",
    "    table = [float('inf')] * (amount + 1)\n",
    "    table[0] = 0\n",
    "    for value in range(1, amount + 1):\n",
    "        for coin in coins:\n",
    "            if coin <= value:\n",
    "                withCoin = table[value - coin]\n",
    "                if withCoin < float('inf') and withCoin + 1 < table[value]:\n",
    "                    table[value] = withCoin + 1\n",
    "    return table[amount]\n",
    "\n",
    "\n",
    "amount = int(input('How much money in pence? '))\n",
    "startTime = time.clock()\n",
    "print('You need', numberofcoins4(amount), 'coins')\n",
    "print(time.clock() - startTime, 'seconds')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "So, we’ve a simple maths problem that we cover in Year 2 maths lessons, but taking this into computing, we can automate solving this, we can generalise this to a far broader class of problems, we can link this to binary (and other number base) conversion, we can get to grips with some tricky logical bugs, and apply sophisticated techniques like recursion and memorisation. From this example alone, I reckon it’s well worth making these connections between the maths curriculum and computing!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernel_info": {
   "name": "python3"
  },
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.10"
  },
  "nteract": {
   "version": "0.15.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}