{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Programming strategies\n",
"\n",
"## Recursion\n",
"\n",
"Recursive humor:\n",
"* ***recursion***: *see recursion*\n",
"* *To understand recursion first you have to understand recursion.*\n",
"\n",
"Recursive abbreviations:\n",
"* GNU: GNU's not Unix,\n",
"* PHP: PHP Hypertext Preprocessor, \n",
"* WINE: WINE Is Not an Emulator,\n",
"* TikZ: TikZ is kein Zeichenprogramm.\n",
"\n",
"Examples:\n",
"* [tower of Hanoi](https://en.wikipedia.org/wiki/Tower_of_Hanoi)\n",
"* Fibonacci numbers\n",
"* Pascal triangle (binomial coefficients)\n",
"\n",
"## Dynamic programming\n",
"\n",
"To solve a problem with\n",
"1. resursion, by reducing a problem to a similar but smaller problems,\n",
"1. but to avoid recursion, store the previously calculated results in a table."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Fibonacci numbers\n",
"The Fibonacci numbers are defined with a recursive formula. We will write a function which calculates the Fibonacci numbers.\n",
"First a non-efficient way, then a more efficient way.\n",
"\n",
"To measure the runtime of the functions we use the `time` module's `time.time()` function. This gives the current time in seconds.\n",
"\n",
"The `fibonacci.counter` is a member of the `fibonacci` function object.\n",
"We use that to count how many times this function way called.\n",
"\n",
"#### Recursive solution"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"import time\n",
"def recursive_fib(n):\n",
" recursive_fib.counter += 1\n",
" if n <= 1:\n",
" return n\n",
" else:\n",
" return recursive_fib(n-1) + recursive_fib(n-2)\n",
"recursive_fib.counter = 0\n",
"start = time.time()\n",
"print recursive_fib(33)\n",
"print time.time() - start\n",
"print recursive_fib.counter"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"This is terribly slow, the function is called more times than the result itself.\n",
"You can avoid the lots of function calls just by memorizing the previous results in a list.\n",
"\n",
"#### Iterative solution"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"import time\n",
"def dp_fib1(n):\n",
" f = [0, 1]\n",
" for i in range(n-1):\n",
" f.append(f[-2]+f[-1])\n",
" return f[-1]\n",
"start = time.time()\n",
"for i in range(99):\n",
" dp_fib1(1000)\n",
"print dp_fib1(1000)\n",
"print (time.time() - start)/100.0"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"It is even more efficient if you store only the last two values."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"import time\n",
"def dp_fib2(n):\n",
" f = [0, 1]\n",
" for i in range(n-1):\n",
" f = [f[1], f[0] + f[1]]\n",
" return f[1]\n",
"start = time.time()\n",
"for i in range(99):\n",
" dp_fib2(1000)\n",
"print dp_fib2(1000)\n",
"print (time.time() - start)/100.0"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Tower of Hanoi\n",
"\n",
"Exercise: given three rods with disks on them. The disks have an increasing radius and the rules are:\n",
"* you can move only one disk at a time\n",
"* bigger disk cannot be on top of a smaller disk\n",
"\n",
"Move a stack of disks from one rod to an other!\n",
"\n",
"Recursive solution: if you want to move $n$ disks from rod $A$ to rod $B$ then\n",
"* first you have to move the top $n-1$ disks from rod $A$ to rod $C$\n",
"* then move the bottom disk to rod $B$\n",
"* finally move the $n-1$ disks from rod $C$ to their final position to rod $B$\n",
"\n",
"This solution is easy to programming but not that efficient.\n",
"#### Recursive solution"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"def hanoi(n, source, destination, auxiliary):\n",
" if n>0:\n",
" hanoi(n-1, source, auxiliary, destination)\n",
" print \"move disk no.{0} from {1} to {2}\".format(n, source, destination)\n",
" hanoi(n-1, auxiliary, destination, source)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"hanoi(3,\"A\",\"B\",\"C\")"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The non-recursive solution is more efficient but harder to write the code."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Exchange\n",
"Let's say that you have a given type of bank notes: $\\$1, \\$2, \\$5, \\$10$ and so on.\n",
"\n",
"You want to pay a given amount of money with the least possible number of banknotes.\n",
"For example paying $\\$10$ with 10 times a one dollar note is not optimal.\n",
"But paying $\\$8$ is optimal with $\\$1+\\$2+\\$5$\n",
"\n",
"Suppose that you have unlimited number of banknotes, find the optimal number of banknotes to pay a given amount of money!\n",
"\n",
"The ***greedy algorithm*** works in this case:\n",
"* Find the biggest note which covers not more than the target amount\n",
"* Subtract that from the target amount\n",
"* Continue until the target is $\\$0$\n",
"\n",
"Although, this failes of the banknotes are different: for example if you have $\\$1, \\$5, \\$8, \\$10, \\$20$\n",
"then it is easier to pay in $\\$8+\\$8+\\$8$ notes than $\\$20+\\$1+\\$1+\\$1+\\$1$ (which is solution of the greedy algorithm).\n",
"\n",
"#### Recursive solution\n",
"Note that the possible coins are stored in a global variable."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"import time\n",
"def recursive_exchange(target):\n",
" recursive_exchange.counter += 1\n",
" n_coins_min = float('inf')\n",
" if target in coins:\n",
" return 1\n",
" else:\n",
" for coin in coins:\n",
" if coin > target:\n",
" break\n",
" number_of_coins = 1 + recursive_exchange(target - coin)\n",
" if number_of_coins < n_coins_min:\n",
" n_coins_min = number_of_coins\n",
" return number_of_coins\n",
"\n",
"recursive_exchange.counter = 0\n",
"coins = [1,2,5,10,20]\n",
"start = time.time()\n",
"print recursive_exchange(34)\n",
"print time.time() - start\n",
"print recursive_exchange.counter"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"recursive_exchange.counter = 0\n",
"ermek = [1,8,5,10,20]\n",
"start = time.time()\n",
"print recursive_exchange(24)\n",
"print time.time() - start\n",
"print recursive_exchange.counter"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"It works OK but there is a faster solution.\n",
"\n",
"#### Dynamic programming\n",
"Not only calculate the optimal coins for a given target, but all smaller amounts also.\n",
"We will store the optimal coin numbers from 0 up to the target value.\n",
"In this way you don't have to calculate the same thing twice.\n",
"\n",
"Let's go through the possible coins and try to pay the amount with that coin.\n",
" \n",
" optimal(target) = coin + optimal(target-coin)\n",
"\n",
"And look for the optimum by selecting the smallest over all coins.\n",
"\n",
"In formula for example with coins $\\$1, \\$2, \\$5$ and the total amount of $\\$24$:\n",
"$$\\texttt{optimal[24]}=1+\\min\\left\\{\\begin{array}{l}\\texttt{optimal[24-1]}\\\\\\texttt{optimal[24-5]}\\\\\\texttt{optimal[24-10]}\\end{array}\\right\\}$$"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"def dynamic_exchange(target):\n",
" global table\n",
" table = [0]*(target+1)\n",
" for t in range(1, target+1):\n",
" min_coins = float('inf')\n",
" for coin in coins:\n",
" if coin > t:\n",
" break\n",
" if table[t-coin] + 1 < min_coins:\n",
" min_coins = table[t-coin] + 1\n",
" table[t] = min_coins\n",
"\n",
" return table[target]"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"coins = [1,2,5,10]\n",
"start = time.time()\n",
"print dynamic_exchange(24)\n",
"print time.time() - start"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"print table"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"coins = [1,2,5,8,10]\n",
"start = time.time()\n",
"print dynamic_exchange(24)\n",
"print time.time() - start"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"print table"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"coins = [5,10,20,50]\n",
"start = time.time()\n",
"print dynamic_exchange(84)\n",
"print time.time() - start"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"print table"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Partitions\n",
"Exercise: How many ways can you decompose an integer into sum of positive integers (order matters)?\n",
"For example you can write $3 = 1+1+1 = 1+2 = 2+1$, there are four ways to decompose.\n",
"We will solve this with recursion and with dynamic programming."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"def sums(n):\n",
" if n == 0:\n",
" return [[]]\n",
" if n == 1:\n",
" return [[1]]\n",
" else:\n",
" sumlist = []\n",
" for i in range(1,n+1):\n",
" L = [i]\n",
" for l in sums(n-i):\n",
" sumlist.append(L + l)\n",
" return sumlist\n",
"for s in sums(4):\n",
" print \" + \".join(str(x) for x in s)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"def sums_d(n):\n",
" global table\n",
" table = [[[]], [[1]]]\n",
" if n == 0 or n == 1:\n",
" return table[n]\n",
" for i in range(2, n+1):\n",
" sumlist = [[i]]\n",
" for j in range(1, i):\n",
" for l in table[i - j]:\n",
" sumlist.append([j] + l)\n",
" table.append(sumlist)\n",
" return table[n]"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"for s in sums_d(4):\n",
" print \" + \".join(str(x) for x in s)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"print table"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Finite-state machines\n",
"### Escaped characters\n",
"\n",
"How python parses a string like this?"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"print \"\\\"Hello\\\"\\nbackslash: \\\\not a new line\""
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"For a backslash character the parser goes into a listening state which means that the next character is treated differently.\n",
"\n",
"Let's say that you read the string character-by-character and have a state variable `s=0`.\n",
"\n",
"* If you encounter a backslash and `s=0`: set `s=1`\n",
"* If you encounter `n t \"` or `'` and `s=1` then\n",
" * you have a special character\n",
" * if you encounter a backslash when `s=1` then it is still a special character\n",
" * in these cases reset `s=0`\n",
"* if you encounter any other character then just set `s=0`"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"sample = r\"\\\"Hello\\\"\\nbackslash: \\\\not a new line\"\n",
"s = 0\n",
"for i in sample:\n",
" if i == \"\\\\\":\n",
" if s == 0:\n",
" s = 1\n",
" else:\n",
" print \"\\\\\"\n",
" s = 0\n",
" elif i in 'nt\"\\'':\n",
" if s == 1:\n",
" s = 0\n",
" print i\n",
" else:\n",
" s = 0"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Parenthesis\n",
"Count how many parentheis are in a formula.\n",
"Let's start with `s=0` and increase `s` whenever you find a `\"(\"` and decrease it when you find a `\")\"`.\n",
"\n",
"If the counter becomes negative then some of the parenthesis are wrong.\n",
"Or if the counter is not 0 at the end of the string then the parenthesis are wrong, too."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": []
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 2",
"language": "python",
"name": "python2"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 2
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython2",
"version": "2.7.14"
}
},
"nbformat": 4,
"nbformat_minor": 1
}