{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "c10434cf",
   "metadata": {},
   "outputs": [],
   "source": [
    "# dynamic programming algorithm for the cashier problem,\n",
    "# specification see below\n",
    "#\n",
    "def cashier_dynamic(amount, coin_types):\n",
    "    previous_value = [None for i in range(amount+1)]\n",
    "    \n",
    "    present_level_values = [amount]    \n",
    "    while previous_value[0] is None:\n",
    "        next_level_values = []\n",
    "        for i in present_level_values:\n",
    "            \n",
    "            for j in coin_types:\n",
    "                remainder = i - j\n",
    "                \n",
    "                if remainder >= 0 and previous_value[remainder] is None:\n",
    "                    previous_value[remainder] = i\n",
    "                    next_level_values.append(remainder)\n",
    "        present_level_values = next_level_values\n",
    "    \n",
    "    coins = []\n",
    "    remainder = 0\n",
    "    while remainder != amount:\n",
    "        coins.append(previous_value[remainder] - remainder)\n",
    "        remainder = previous_value[remainder]\n",
    "    return coins"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "0319f69d",
   "metadata": {},
   "outputs": [],
   "source": [
    "# greedy algorithm for the cashier problem\n",
    "#\n",
    "# arguments and precondition:\n",
    "#  * amount is a natural number, given in the smallest currency unit (e.g., pence)\n",
    "#  * coin_types is a sorted list of integers, indicating what kinds of coins exist (e.g., [1, 2, 5, ...])\n",
    "#    note that we assume that this list is already sorted\n",
    "# the amount is such that it can in principle be expressed as a sum of coin values, e.g., 9 = 5 + 2 + 2\n",
    "#\n",
    "# remark: a set can contain each value only once,\n",
    "# and it can by design be efficiently traversed in a sorted order\n",
    "#\n",
    "# return value:\n",
    "#  * a list containing coin values that add up to the requested amount\n",
    "#  * this must be the shortest possible list, i.e., we want to use as few coins as possible\n",
    "#\n",
    "# summary:\n",
    "#  * the greedy algorithm keeps appending the list by the\n",
    "#    largest possible coin without exceeding the requested amount\n",
    "#  * when the amount is reached, it returns the finalized list\n",
    "#\n",
    "def cashier_greedy(amount, coin_types):\n",
    "    coins = []\n",
    "    remainder = amount\n",
    "    while remainder >= coin_types[0]:\n",
    "        for i in range(len(coin_types)-1, -1, -1):\n",
    "            if remainder >= coin_types[i]:\n",
    "                coins.append(coin_types[i])\n",
    "                remainder -= coin_types[i]\n",
    "                break\n",
    "    return coins"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "5b44fbd1",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "standard coin types: [1, 2, 5, 10, 20, 50, 100, 200]\n",
      "alternative coin types: [1, 8, 27, 64, 125, 216, 343, 512]\n",
      "\n",
      "amount x = 740\n",
      "standard coins are returned as follows:\n",
      "\t[200, 200, 200, 100, 20, 20]\n",
      "\tsum: 740\n",
      "alternative coins are returned as follows:\n",
      "\t[512, 216, 8, 1, 1, 1, 1]\n",
      "\tsum: 740\n"
     ]
    }
   ],
   "source": [
    "# using the greedy algorithm\n",
    "#\n",
    "import random\n",
    "\n",
    "types_standard = [1, 2, 5, 10, 20, 50, 100, 200]\n",
    "types_alternative = [n*n*n for n in range(1, 9)]\n",
    "print(\"standard coin types:\", types_standard)\n",
    "print(\"alternative coin types:\", types_alternative)\n",
    "\n",
    "x = random.randint(1, 1000)\n",
    "coins_standard = cashier_greedy(x, types_standard)\n",
    "coins_alternative = cashier_greedy(x, types_alternative)\n",
    "\n",
    "print(\"\\namount x =\", x)\n",
    "print(\"standard coins are returned as follows:\\n\\t\", coins_standard,\\\n",
    "      \"\\n\\tsum: \", sum(coins_standard), sep=\"\")\n",
    "print(\"alternative coins are returned as follows:\\n\\t\", coins_alternative,\\\n",
    "      \"\\n\\tsum: \", sum(coins_alternative), sep=\"\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "0a58dad2",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "standard coin types: [1, 2, 5, 10, 20, 50, 100, 200]\n",
      "alternative coin types: [1, 8, 27, 64, 125, 216, 343, 512]\n",
      "\n",
      "amount x = 1\n",
      "standard coins are returned as follows:\n",
      "\t[1]\n",
      "\tsum: 1\n",
      "alternative coins are returned as follows:\n",
      "\t[1]\n",
      "\tsum: 1\n"
     ]
    }
   ],
   "source": [
    "# using the dynamic programming algorithm\n",
    "#\n",
    "import random\n",
    "\n",
    "types_standard = [1, 2, 5, 10, 20, 50, 100, 200]\n",
    "types_alternative = [n*n*n for n in range(1, 9)]\n",
    "print(\"standard coin types:\", types_standard)\n",
    "print(\"alternative coin types:\", types_alternative)\n",
    "\n",
    "x = random.randint(1, 1000)\n",
    "coins_standard = cashier_dynamic(x, types_standard)\n",
    "coins_alternative = cashier_dynamic(x, types_alternative)\n",
    "\n",
    "print(\"\\namount x =\", x)\n",
    "print(\"standard coins are returned as follows:\\n\\t\", coins_standard,\\\n",
    "      \"\\n\\tsum: \", sum(coins_standard), sep=\"\")\n",
    "print(\"alternative coins are returned as follows:\\n\\t\", coins_alternative,\\\n",
    "      \"\\n\\tsum: \", sum(coins_alternative), sep=\"\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "51181853",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Greedy: [9, 1, 1, 1]\n",
      "Dynamic programming: [4, 4, 4]\n"
     ]
    }
   ],
   "source": [
    "# test 12 with [1, 4, 9, 16]\n",
    "#\n",
    "print(\"Greedy:\", cashier_greedy(12, [1, 4, 9, 16]))\n",
    "print(\"Dynamic programming:\", cashier_dynamic(12, [1, 4, 9, 16]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "2e1f5054",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.9.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}