Algorithmic Problems in Python.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "****\n",
    "# Algorithmic Problems solved in Python\n",
    "****\n",
    "<p style=\"text-align: right\"><i>Jesus Perez Colino<br>First version: November 2013<br>Last revision November 2015</i></p>\n",
    "\n",
    "## About this notebook: \n",
    "****\n",
    "Notebook prepared by **Jesus Perez Colino** Version 0.2, First Released: 25/11/2013, Alpha\n",
    "\n",
    "- This work is licensed under a [Creative Commons Attribution-ShareAlike 3.0 Unported License](http://creativecommons.org/licenses/by-sa/3.0/deed.en_US). This work is offered for free, with the hope that it will be useful.\n",
    "\n",
    "\n",
    "- **Summary**: This notebook is a collection of traditional algorithmic problems for Python. Some of them are well-know in Computer Science (searching, sorting...), and other are more functional programming oriented or mathematically based. It includes examples of list comprenhension, map/reduce functions, generators, decorators, HPC simulations...\n",
    "\n",
    "\n",
    "- **Index**:\n",
    "    - Problem 1: the Sum of Some\n",
    "    - Problem 2: Map / Reduce / Filter Problems\n",
    "    - Problem 3: plural of a list\n",
    "    - Problem 4: counting tokens\n",
    "    - Problem 5: Simplify...\n",
    "    - Problem 6: islice\n",
    "    - Problem 7: compress\n",
    "    - Problem 8: The Quine Problem\n",
    "    - Problem 9: Narcissus program\n",
    "    - Problem 10: Comparing Strings\n",
    "    - Problem 11: A stateful Standard Deviation\n",
    "    - Problem 12: A Linear Congruential Generator of Random Numbers\n",
    "    - Problem 13: A Dict of letters\n",
    "    - Problem 14: Factorial function in functional form\n",
    "    - Problem 15: Quicksort of a list\n",
    "    - Problem 16: Memoizing decorator in Fibonacci generator\n",
    "    - Problem 17: Estimate $\\pi$ by simulation\n",
    "    - Problem 18: Fast sorting by arguments in Numpy\n",
    "    - Problem 19: Multivariate Simulation and Covariance Matrix estimation\n",
    "    - Problem 20: Inverting a dictionary: 1. using zip and 2. using a comprehension\n",
    "    - Problem 21: Generator expressions\n",
    "    - Problem 22: Inheriting from named tuples (collections.namedtuple)\n",
    "    - Problem 23: Double-ended queue with maximum length (collections.deque)\n",
    "    - Problem 24: Using default dictionaries to represent simple trees\n",
    "    - Problem 25: Cartesian products (itertools.product)\n",
    "    - Problem 26: All the methods to Flattening a list\n",
    "    - Problem 27: Inheritance/Multiple\n",
    "    - Problem 28: Roots of a quadratic function\n",
    "    - Problem 29: Ordered dictionaries (collections.OrderedDict)\n",
    "    - Problem 30: Check whether a file exists using Python\n",
    "    - Problem 31: The Knapsack problem using memoization and tested using doctest\n",
    "    - Problem 32: 100 doors\n",
    "    - Problem 33: Roots of a function\n",
    "    - Problem 34: Dictionary from two lists\n",
    "    - Problem 35: Reverse words in a string\n",
    "    - Problem 36: Compare sorting algorithms' performance\n",
    "    - Problem 37: Build your own Stack container\n",
    "    - Problem 38: Sets and operators over sets\n",
    "    - Problem 39: Abstract type\n",
    "    - Problem 40: Temperature Conversion\n",
    "    - Problem 41: The Monty Hall problem by simulation\n",
    "    - Problem 42: Polymorphism\n",
    "    - Problem 43: Regular Expressions\n",
    "    - Problem 44: Static methods\n",
    "    - Problem 45: Generating deprecation warnings with decorators\n",
    "    - Problem 46: Pseudo-currying\n",
    "    - Problem 47: Timeout decorator\n",
    "    - Problem 48: From Numbers to English Words\n",
    "    - Problem 49: Number factorization in primes numbers\n",
    "    - Problem 50: Y-combinator\n",
    "    - Problem 51: Multiprocessing\n",
    "    - Problem 52: Forward Difference\n",
    "    - Problem 53: Perfect Numbers\n",
    "    - Problem 54: Remove duplicate elements\n",
    "    - Problem 55: Anonymous Recursion\n",
    "    - Problem 56: Synchronous concurrency\n",
    "    - Problem 57: Get Rich (Divide and Conquer)\n",
    "    - Problem 58: Zero Sum - Linear\n",
    "    - Problem 59: A number in a range\n",
    "    - Problem 60: A callable class\n",
    "    - Problem 61: Self-caching properties\n",
    "    - Problem 62: Fibonacci in one line\n",
    "    - Problem 63: Run 1000 times an American Roulette in one line of code\n",
    "    - Problem 64: Probability of 5 or more heads from 10 spins of a biased coin\n",
    "    - Problem 65: Empirical Estimation of Intervals of Confidence for a mean\n",
    "    - Problem 66: Single Server Queue simulation\n",
    "    - Problem 67: Day of the last Monday?\n",
    "    \n",
    "    \n",
    "- **Acknowledge**: To create the current notebook, I have inserted many examples from many books, websites... some of them can be found in [Rosetta Code](http://rosettacode.org/wiki/Rosetta_Code), others in [stackoverflow](http://stackoverflow.com), and few of them I created by myself, for fun. It is not my intention to claim any property right... so just have fun, if you like this kind of stuff. \n",
    "\n",
    "\n",
    "- **Python & packages versions** to reproduce the results of this notebook: "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "-------------------- Reproducibility conditions for this notebook -------------------\n",
      "Python version:     2.7.13 |Anaconda custom (x86_64)| (default, Dec 20 2016, 23:05:08) \n",
      "[GCC 4.2.1 Compatible Apple LLVM 6.0 (clang-600.0.57)]\n",
      "Numpy version:      1.11.3\n",
      "IPython version:    5.1.0\n",
      "-------------------------------------------------------------------------------------\n"
     ]
    }
   ],
   "source": [
    "import IPython\n",
    "import numpy as np\n",
    "from sys import version \n",
    "print ' Reproducibility conditions for this notebook '.center(85,'-')\n",
    "print 'Python version:     ' + version\n",
    "print 'Numpy version:      ' + np.__version__\n",
    "print 'IPython version:    ' + IPython.__version__\n",
    "print '-'*85"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "****\n",
    "## Problem 1: the Sum of Some\n",
    "Code a function that given three positive integers, **n, x, y** returns the **sum** of the integers **between 0 and n** (inclusive) that are multiples of **x** or **y** but not both.\n",
    "\n",
    "For example: \n",
    "\n",
    "`foo(8,2,3) = 2 + 3 + 4 + 8 = 17`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def foo(n, x, y):\n",
    "    return sum(filter(lambda i : bool(i%x == 0) ^ bool(i%y == 0) , range(n+1)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "17"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "foo(8, 2, 3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[True, False, True, False, True, False, True, False, True]\n",
      "[True, False, False, True, False, False, True, False, False]\n",
      "[True, False, False, False, False, False, True, False, False]\n",
      "\n",
      "[False, False, True, True, True, False, False, False, True]\n",
      "\n",
      "[2, 3, 4, 8]\n",
      "\n",
      "17\n"
     ]
    }
   ],
   "source": [
    "# have a look to the logic sequence, and check it out, step by step: \n",
    "x = 2\n",
    "y = 3\n",
    "n = 8\n",
    "print map(lambda i: i%x == 0, range(n+1))\n",
    "print map(lambda i: i%y == 0, range(n+1))\n",
    "print map(lambda i: i%x == 0 ^ i%y == 0, range(n+1))\n",
    "print \n",
    "print map(lambda i: bool(i%x == 0) ^ bool(i%y == 0) , range(n+1))\n",
    "print \n",
    "print filter(lambda i: bool(i%x == 0) ^ bool(i%y == 0) , range(n+1))\n",
    "print\n",
    "print sum(filter(lambda i: bool(i%x == 0) ^ bool(i%y == 0) , range(n+1)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "17"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# alternatively, using directly a list comprenhension: \n",
    "\n",
    "def foo(n, x, y):\n",
    "    return sum([ i for i in range(1,n+1) if bool(i%x==0) ^ bool(i%y==0) ])\n",
    "\n",
    "foo(8,2,3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "17"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# or even more twisted and obscure... just only for truely functional 'guys'\n",
    "\n",
    "def foo(n, x, y):\n",
    "    return reduce(lambda x,y : x + y, (filter(lambda i: bool(i%x == 0) ^ bool(i%y == 0) , range(n+1))))\n",
    "\n",
    "foo(8,2,3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 2: Map / Reduce / Filter Problems\n",
    "\n",
    "**2.1.** Code a function that produce the **Mean** of a list using reduce functions"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 183,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5.0\n"
     ]
    }
   ],
   "source": [
    "l = xrange(1,10)\n",
    "print reduce(lambda x, y : x + y ,l) / float(len(l))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def myMean(l):\n",
    "    return reduce(lambda x, y : x + y, l) / float(len(l))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 219,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# or alternatively, directly as a lambda function:\n",
    "\n",
    "myMean = lambda myList : reduce(lambda x,y : x + y, myList) / float(len(myList))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**2.2.** Code a function that produce the **Standard Deviation** of a list using map / reduce"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 225,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def myStd(l):\n",
    "    return (reduce(lambda x,y : x + y , map(lambda x: (x-myMean(l))**2 , l)) / float(len(l)))**.5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 223,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Mean and Standard Deviation, together:\n",
    "\n",
    "myMean = lambda myList : reduce(lambda x, y : x + y, myList) / float(len(myList))\n",
    "\n",
    "myStd = lambda myList : (reduce(lambda x, y : x + y , map(lambda x: (x-myMean(myList))**2 , myList)) \n",
    "                         / float(len(myList)))**.5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 226,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2.0\n"
     ]
    }
   ],
   "source": [
    "print myStd([2,4,4,4,5,5,7,9])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**2.3** Code a function using map/reduce that **sum the square of all interger until n**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "55\n",
      "True\n"
     ]
    }
   ],
   "source": [
    "def mySumSquare(n):\n",
    "    return reduce(lambda x,y : x + y, map(lambda x : x*x, range(n+1)))\n",
    "\n",
    "print mySumSquare(5)\n",
    "print mySumSquare(5) == sum(map(lambda x: x*x, [1, 2, 3, 4, 5]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**2.4.** Determining the **maximum** of a list of numerical values by using reduce:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "102"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mymax = lambda a,b : a if (a > b) else b\n",
    "reduce(mymax, [47,11,42,102,13])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "102"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mylist = [47,11,42,102,13]\n",
    "reduce(lambda a,b : a if (a > b) else b, mylist)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**2.5.** Obtain the nth **fibonacci number** using `reduce` in ONE line"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "fib = lambda n : reduce(lambda x , n : [ x[1] , x[0] + x[1] ], range(n) ,[0,1] )[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55]"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "[fib(i) for i in range(11)]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**2.6.** Write a function called `myreduce` that produce exactly the same result that the function `reduce`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def myreduce(function, iterable, initializer=None):\n",
    "    it = iter(iterable)\n",
    "    if initializer is None:\n",
    "        try:\n",
    "            initializer = next(it)\n",
    "        except StopIteration:\n",
    "            raise TypeError('reduce() of empty sequence with no initial value')\n",
    "    accum_value = initializer\n",
    "    for x in it:\n",
    "        accum_value = function(accum_value, x)\n",
    "    return accum_value"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "18"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "myreduce(lambda x,y : x+y, [1,2,3,4,5], initializer=3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "18"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "reduce(lambda x,y : x+y, [1,2,3,4,5], 3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**2.7** Given a list (as a time series) of prices, provide code that produces a list (or time series) of numbers which is the relative returns of the prices, or equivalently $ P_t \\rightarrow log(P_t / P_{t-1})$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from math import log\n",
    "\n",
    "returns = lambda prices : [ log( x / float(prices[i])) for i, x in enumerate( prices[1:] ) ]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0.02955880224154443,\n",
       " -0.019608471388376313,\n",
       " 0.12981161152199053,\n",
       " -0.1498122782286601,\n",
       " 0.02985296314968113]"
      ]
     },
     "execution_count": 35,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "myprices = [100, 103, 101, 115, 99, 102]\n",
    "returns(myprices)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0.02955880224154443,\n",
       " -0.019608471388376313,\n",
       " 0.12981161152199053,\n",
       " -0.1498122782286601,\n",
       " 0.02985296314968113]"
      ]
     },
     "execution_count": 45,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# alternatively, as a list-comprenhesion\n",
    "\n",
    "myprices = [100, 103, 101, 115, 99, 102]\n",
    "\n",
    "[log(price / float(myprices[i])) for i, price in enumerate (myprices[1:])]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 102,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Original prices:      [100, 103, 101, 115, 99, 102]\n",
      "Relative returns:     ['3.0%', '-2.0%', '13.0%', '-15.0%', '3.0%']\n",
      "Mean of the returns:  0.0\n",
      "Volatility:           144.39\n"
     ]
    }
   ],
   "source": [
    "# Functional Statistical Summary: \n",
    "\n",
    "myprices = [100, 103, 101, 115, 99, 102]\n",
    "myreturns = returns(myprices)\n",
    "myMean = lambda myList : reduce(lambda x, y : x + y, myList) / float(len(myList))\n",
    "myStd = lambda myList : (reduce(lambda x, y : x + y , map(lambda x: (x-myMean(myList))**2 , myList)) \n",
    "                         / float(len(myList)))**.5\n",
    "\n",
    "print 'Original prices:     ', myprices\n",
    "print 'Relative returns:    ', ['{0}%'.format(round(myreturns[i],3)*100) for i in range(len(myreturns))]\n",
    "print 'Mean of the returns: ', round(myMean(myreturns),2)\n",
    "print 'Volatility:          ', round(myStd(myreturns)* 100 * (252 ** .5),2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 3: Plural of a list\n",
    "Make plural of the words in a list of strings"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['cats', 'elephants', 'rats', 'rats', 'cats']\n"
     ]
    }
   ],
   "source": [
    "wordsList = ['cat', 'elephant', 'rat', 'rat', 'cat']\n",
    "print map(lambda word : word + 's', wordsList)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 4: Counting tokens\n",
    "Counting the number in a list of words using map/reduce"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[('cat', 1), ('elephant', 1), ('rat', 1), ('rat', 1), ('cat', 1)]\n"
     ]
    }
   ],
   "source": [
    "wordsList = ['cat', 'elephant', 'rat', 'rat', 'cat']\n",
    "\n",
    "wordCount = map(lambda word : (str(word),1),wordsList)\n",
    "print wordCount\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 1, 1, 1, 1]\n"
     ]
    }
   ],
   "source": [
    "counter = map(lambda x : x[1], wordCount)\n",
    "print counter\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Total Number of words: 5\n"
     ]
    }
   ],
   "source": [
    "print 'Total Number of words:', reduce(lambda x,y : x+y, counter)\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Total Number of words: 5\n"
     ]
    }
   ],
   "source": [
    "# All together: \n",
    "\n",
    "wordCount = map(lambda word : (str(word),1),wordsList)\n",
    "counter = map(lambda x : x[1], wordCount)\n",
    "print 'Total Number of words:', reduce(lambda x,y : x+y, counter)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 61,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      " Total Number of words: 5\n"
     ]
    }
   ],
   "source": [
    "# alternatively (but equally twisted):\n",
    "\n",
    "print 'Total Number of words:',[i+1 for i, x in enumerate (wordsList[:])][-1]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "And, one step more interesting, is to count the number of times that a word appears, per word..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Total Number of words: 5\n",
      "Total Number of different words: 3\n",
      "Word counter:  {'rat': 2, 'elephant': 1, 'cat': 2}\n"
     ]
    }
   ],
   "source": [
    "wordsList = ['cat', 'elephant', 'rat', 'rat', 'cat']\n",
    "\n",
    "def word_dict(wordlist):\n",
    "    mydict = {}\n",
    "    for word in wordlist:\n",
    "        if word in mydict.keys():\n",
    "            mydict[word]+=1\n",
    "        else:\n",
    "            mydict[word]=1\n",
    "    return mydict\n",
    "                \n",
    "print 'Total Number of words:', reduce(lambda x,y : x+y, word_dict(wordsList).values())\n",
    "print 'Total Number of different words:', len(word_dict(wordsList))\n",
    "print 'Word counter: ', word_dict(wordsList)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 5: Simplify..."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Simplify the following expression using list comprehension:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['0: one', '1: two', '2: three']\n"
     ]
    }
   ],
   "source": [
    "i = 0\n",
    "seq = [\"one\", \"two\", \"three\"]\n",
    "for element in seq:\n",
    "    seq[i] = '%d: %s' % (i, seq[i])\n",
    "    i += 1\n",
    "    \n",
    "print seq"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 81,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['0: one', '1: two', '2: three']"
      ]
     },
     "execution_count": 81,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def mytuple(pos, element):\n",
    "    return '{0}: {1}'.format(pos, element)\n",
    "\n",
    "seq = [\"one\", \"two\", \"three\"]\n",
    "\n",
    "[ mytuple(i, element) for i, element in enumerate(seq)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 79,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['0: one', '1: two', '2: three']"
      ]
     },
     "execution_count": 79,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# or much simpler, and elegantly: \n",
    "\n",
    "seq = [\"one\", \"two\", \"three\"]\n",
    "\n",
    "['{0}: {1}'.format([i for i, x in enumerate(seq)][j], [x for x in seq][j]) for j in range(len(seq)) ]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, 1, 2]"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "seq = [\"one\", \"two\", \"three\"]\n",
    "\n",
    "[i for i,x in enumerate(seq)][j], ]\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 6: islice"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**islice** returns an iterator that works over a subgroup of a sequence. \n",
    "\n",
    "Build a function that reads the lines in a standard input, and yields the elements of each line starting from the fifth one, as long as the line has more than four elements"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import itertools\n",
    "def starting_at_five():\n",
    "    value = raw_input().strip()\n",
    "    while value != '':\n",
    "        for el in itertools.islice(value.split(), 4, None):\n",
    "            yield el\n",
    "        value = raw_input().strip()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 2 3 4 5 6 7 8 9 \n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "'5'"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "iter = starting_at_five()\n",
    "iter.next()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'6'"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "iter.next()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'7'"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "iter.next()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'8'"
      ]
     },
     "execution_count": 28,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "iter.next()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 7: Compress"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Write a function that is able to group the duplicate elements from an iterator, as long as they are adjacent. A function can be given to the function for it to compare the elements. Otherwise, the identity comparison is used.\n",
    "\n",
    "For example:\n",
    "\n",
    "`get uuuuuuuuuuuuuuuuuup`\n",
    "\n",
    "will be replaced by:\n",
    "\n",
    "`1g1e1t1 8u1p`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from itertools import groupby\n",
    "\n",
    "def compress(data):\n",
    "    return ((len(list(group)), name)\n",
    "             for name, group in groupby(data))\n",
    "\n",
    "def decompress(data):\n",
    "    return (car * size for size, car in data)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[(1, 'g'), (1, 'e'), (1, 't'), (1, ' '), (18, 'u'), (1, 'p')]\n"
     ]
    }
   ],
   "source": [
    "print list(compress('get uuuuuuuuuuuuuuuuuup'))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'get uuuuuuuuuuuuuuuuuup'"
      ]
     },
     "execution_count": 31,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "compressed = compress('get uuuuuuuuuuuuuuuuuup')\n",
    "''.join(decompress(compressed))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 8: The Quine Problem\n",
    "\n",
    "A Quine is a self-referential program that can, without any external access, output its own source. \n",
    "\n",
    "It is named after the philosopher and logician who studied self-reference and quoting in natural language, as for example in the paradox \"'Yields falsehood when preceded by its quotation' yields falsehood when preceded by its quotation.\"\n",
    "\n",
    "\"Source\" has one of two meanings. It can refer to the text-based program source. For languages in which program source is represented as a data structure, \"source\" may refer to the data structure: quines in these languages fall into two categories: programs which print a textual representation of themselves, or expressions which evaluate to a data structure which is equivalent to that expression.\n",
    "\n",
    "The usual way to code a Quine works similarly to this paradox: The program consists of two identical parts, once as plain code and once quoted in some way (for example, as a character string, or a literal data structure). The plain code then accesses the quoted code and prints it out twice, once unquoted and once with the proper quotation marks added. Often, the plain code and the quoted code have to be nested.\n",
    "\n",
    "**Write a program that outputs its own source code in this way.** If the language allows it, you may add a variant that accesses the code directly. You are not allowed to read any external files with the source code. The program should also contain some sort of self-reference, so constant expressions which return their own value which some top-level interpreter will print out. Empty programs producing no output are not allowed."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Python's `%r` format conversion uses the `repr()` function to return a string containing the source code representation of its argument:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "x = 'x = %r\\nprint(x %% x)'\n",
      "print(x % x)\n"
     ]
    }
   ],
   "source": [
    "x = 'x = %r\\nprint(x %% x)'\n",
    "print(x % x)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "x = 'x = {!r};print(x.format(x))';print(x.format(x))\n"
     ]
    }
   ],
   "source": [
    "x = 'x = {!r};print(x.format(x))'\n",
    "print(x.format(x))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "x = 'x = {!r}'\n"
     ]
    }
   ],
   "source": [
    "# notice the trick: \n",
    "\n",
    "x = 'x = {!r}';print x.format(x)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 9 Narcissus program\n",
    "\n",
    "A narcissist (or Narcissus program) is the decision-problem version of a quine.\n",
    "A quine, when run, takes no input, but produces a copy of its own source code at its output. In contrast, a narcissist reads a string of symbols from its input, and produces no output except a \"1\" or \"accept\" if that string matches its own source code, or a \"0\" or \"reject\" if it does not.\n",
    "\n",
    "For concreteness, in this task we shall assume that symbol = character. The narcissist should be able to cope with any finite input, whatever its length. Any form of output is allowed, as long as the program always halts, and \"accept\", \"reject\" and \"not yet finished\" are distinguishable."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Enter source code: x = 'x = %r\\nprint(x %% x)'; print(x % x)\n",
      "Reject\n"
     ]
    }
   ],
   "source": [
    "# TODO\n",
    "import sys\n",
    "with open(sys.argv[0]) as quine:\n",
    "    code = raw_input(\"Enter source code: \")\n",
    "    if code == quine.read():\n",
    "        print(\"Accept\")\n",
    "    else:\n",
    "        print(\"Reject\")\n",
    " "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 10: Comparing Strings\n",
    "\n",
    "The task is to demonstrate how to compare two strings from within the language and how to achieve a lexical comparison.\n",
    "The task should demonstrate:\n",
    "- Comparing two strings for exact equality\n",
    "- Comparing two strings for inequality (i.e., the inverse of exact equality)\n",
    "- Comparing two strings to see if one is lexically ordered before than the other\n",
    "- Comparing two strings to see if one is lexically ordered after than the other\n",
    "- How to achieve both case sensitive comparisons and case insensitive comparisons within the language\n",
    "- How the language handles comparison of numeric strings if these are not treated lexically\n",
    "\n",
    "Demonstrate any other kinds of string comparisons that the language provides, particularly as it relates to your type system. For example, you might demonstrate the difference between generic/polymorphic comparison and coercive/allomorphic comparison if your language supports such a distinction.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "'YUP' is of type <type 'str'> and 'YUP' is of type <type 'str'>\n",
      "'YUP' is less than or equal to 'YUP'\n",
      "'YUP' is greater than or equal to 'YUP'\n",
      "'YUP' is equal to 'YUP'\n",
      "'YUP' has object identity with 'YUP'\n",
      "\n",
      "'BALL' is of type <type 'str'> and 'BELL' is of type <type 'str'>\n",
      "'BALL' is strictly less than  'BELL'\n",
      "'BALL' is less than or equal to 'BELL'\n",
      "'BALL' is not equal to 'BELL'\n",
      "'BALL' has negated object identity with 'BELL'\n",
      "\n",
      "'24' is of type <type 'str'> and '123' is of type <type 'str'>\n",
      "'24' is strictly greater than  '123'\n",
      "'24' is greater than or equal to '123'\n",
      "'24' is not equal to '123'\n",
      "'24' has negated object identity with '123'\n",
      "\n",
      "24 is of type <type 'int'> and 123 is of type <type 'int'>\n",
      "24 is strictly less than  123\n",
      "24 is less than or equal to 123\n",
      "24 is not equal to 123\n",
      "24 has negated object identity with 123\n",
      "\n",
      "5.0 is of type <type 'float'> and 5 is of type <type 'int'>\n",
      "5.0 is less than or equal to 5\n",
      "5.0 is greater than or equal to 5\n",
      "5.0 is equal to 5\n",
      "5.0 has negated object identity with 5\n"
     ]
    }
   ],
   "source": [
    "def compare(a, b):\n",
    "    print(\"\\n%r is of type %r and %r is of type %r\"\n",
    "          % (a, type(a), b, type(b)))\n",
    "    if a <  b:      print('%r is strictly less than  %r' % (a, b))\n",
    "    if a <= b:      print('%r is less than or equal to %r' % (a, b))\n",
    "    if a >  b:      print('%r is strictly greater than  %r' % (a, b))\n",
    "    if a >= b:      print('%r is greater than or equal to %r' % (a, b))\n",
    "    if a == b:      print('%r is equal to %r' % (a, b))\n",
    "    if a != b:      print('%r is not equal to %r' % (a, b))\n",
    "    if a is b:      print('%r has object identity with %r' % (a, b))\n",
    "    if a is not b:  print('%r has negated object identity with %r' % (a, b))\n",
    " \n",
    "compare('YUP', 'YUP')\n",
    "compare('BALL', 'BELL')\n",
    "compare('24', '123')\n",
    "compare(24, 123)\n",
    "compare(5.0, 5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 11: A stateful standard-deviation\n",
    "\n",
    "Write a **stateful function, class, generator or coroutine** that takes a series of floating point numbers, one at a time, and **returns the running standard deviation of the series**. The task implementation should use the most natural programming style of those listed for the function in the implementation language; the task must state which is being used. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def sd(x):\n",
    "    sd.sum  += x\n",
    "    sd.sum2 += x*x\n",
    "    sd.n    += 1.0\n",
    "    sum, sum2, n = sd.sum, sd.sum2, sd.n\n",
    "    return (sum2/n - (sum/n)**2)**0.5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(2, 0.0)\n",
      "(4, 1.0)\n",
      "(4, 0.9428090415820626)\n",
      "(4, 0.8660254037844386)\n",
      "(5, 0.9797958971132716)\n",
      "(5, 1.0)\n",
      "(7, 1.3997084244475297)\n",
      "(9, 2.0)\n"
     ]
    }
   ],
   "source": [
    "sd.sum = sd.sum2 = sd.n = 0\n",
    "for value in (2,4,4,4,5,5,7,9):\n",
    "    print (value, sd(value))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Using a class instance\n",
    "\n",
    "class SD(object): # Plain () for python 3.x\n",
    "    def __init__(self):\n",
    "        self.sum, self.sum2, self.n = (0,0,0)\n",
    "    def sd(self, x):\n",
    "        self.sum  += x\n",
    "        self.sum2 += x*x\n",
    "        self.n    += 1.0\n",
    "        sum, sum2, n = self.sum, self.sum2, self.n\n",
    "        return (sum2/n - (sum/n)**2)**0.5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(2, 0.0)\n",
      "(4, 1.0)\n",
      "(4, 0.9428090415820626)\n",
      "(4, 0.8660254037844386)\n",
      "(5, 0.9797958971132716)\n",
      "(5, 1.0)\n",
      "(7, 1.3997084244475297)\n",
      "(9, 2.0)\n"
     ]
    }
   ],
   "source": [
    "sd_inst = SD()\n",
    "for value in (2,4,4,4,5,5,7,9):\n",
    "    print (value, sd_inst.sd(value))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Using an extended generator\n",
    "\n",
    "def sdcreator():\n",
    "    sum = sum2 = n = 0\n",
    "    while True:\n",
    "        x = yield (sum2/n - (sum/n)**2)**.5 if n else None\n",
    "        sum  += x\n",
    "        sum2 += x*x\n",
    "        n    += 1.0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(2, 0.0)\n",
      "(4, 1.0)\n",
      "(4, 0.9428090415820626)\n",
      "(4, 0.8660254037844386)\n",
      "(5, 0.9797958971132716)\n",
      "(5, 1.0)\n",
      "(7, 1.3997084244475297)\n",
      "(9, 2.0)\n"
     ]
    }
   ],
   "source": [
    "sd = sdcreator()\n",
    "sd.send(None)\n",
    "for value in (2,4,4,4,5,5,7,9):\n",
    "    print (value, sd.send(value))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 12: A Linear Congruential Generator of Random Numbers"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The **linear congruential generator** is a very simple example (and also a bad example) of a **random number generator**. All linear congruential generators use this formula:\n",
    "\n",
    "$$r_{n + 1} = a \\times r_n + c \\pmod m$$\n",
    "\n",
    "\n",
    "\n",
    "Where:\n",
    "\n",
    "* $r_0$ is a seed.\n",
    "* $r_1$, $r_2$, $r_3$, ..., are the random numbers.\n",
    "* $a$, $c$, $m$ are constants.\n",
    "\n",
    "If one chooses the values of $a$, $c$ and $m$ with care, then the generator produces a uniform distribution of integers from $0$ to $m - 1$.\n",
    "\n",
    "LCG numbers have poor quality. $r_n$ and $r_{n + 1}$ are not independent, as true random numbers would be. Anyone who knows $r_n$ can predict $r_{n + 1}$, therefore LCG is not cryptographically secure. The LCG is still good enough for simple tasks like [[Miller-Rabin primality test]], or [[deal cards for FreeCell|FreeCell deals]]. Among the benefits of the LCG, one can easily reproduce a sequence of numbers, from the same $r_0$. One can also reproduce such sequence with a different programming language, because the formula is so simple.\n",
    "\n",
    "The task is to replicate two historic random number generators. One is the `rand()` function from **BSD libc**, and the other is the `rand()` function from the **Microsoft C Runtime (MSCVRT.DLL)**. Each replica must yield the same sequence of integers as the original generator, when starting from the same seed.\n",
    "\n",
    "In these formulas, the seed becomes $state_0$. The random sequence is $rand_1$, $rand_2$ and so on.\n",
    "\n",
    "BSD formula:\n",
    "\n",
    "* $state_{n + 1} = 1103515245 \\times state_n + 12345 \\pmod{2^{31}}$\n",
    "* $rand_n = state_n$\n",
    "* $rand_n$ is in range 0 to 2147483647.\n",
    "\n",
    "Microsoft formula:\n",
    "\n",
    "* $state_{n + 1} = 214013 \\times state_n + 2531011 \\pmod{2^{31}}$\n",
    "* $rand_n = state_n \\div 2^{16}$\n",
    "* $rand_n$ is in range 0 to 32767"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# notice that we are using a closure: \n",
    "\n",
    "def bsd_rand(seed):\n",
    "    def rand():\n",
    "        rand.seed = (1103515245*rand.seed + 12345) & 0x7fffffff\n",
    "        return rand.seed\n",
    "    rand.seed = seed\n",
    "    return rand\n",
    " \n",
    "def msvcrt_rand(seed):\n",
    "    def rand():\n",
    "        rand.seed = (214013*rand.seed + 2531011) & 0x7fffffff\n",
    "        return rand.seed >> 16\n",
    "    rand.seed = seed\n",
    "    return rand"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[12345, 1406932606, 654583775, 1449466924, 229283573, 1109335178, 1051550459, 1293799192, 794471793, 551188310]\n"
     ]
    }
   ],
   "source": [
    "rand_bsd = bsd_rand(0)\n",
    "print [rand_bsd() for i in range(10)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[{0: 38}, {1: 7719}, {2: 21238}, {3: 2437}, {4: 8855}, {5: 11797}, {6: 8365}, {7: 32285}, {8: 10450}]\n"
     ]
    }
   ],
   "source": [
    "rand_msft = msvcrt_rand(0)\n",
    "print [{i:rand_msft()} for i in range(9)]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 13: A Dict of letters\n",
    "\n",
    "Build a dictionary with all the letters of alphabet enumerated"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{0: 'A',\n",
       " 1: 'B',\n",
       " 2: 'C',\n",
       " 3: 'D',\n",
       " 4: 'E',\n",
       " 5: 'F',\n",
       " 6: 'G',\n",
       " 7: 'H',\n",
       " 8: 'I',\n",
       " 9: 'J',\n",
       " 10: 'K',\n",
       " 11: 'L',\n",
       " 12: 'M',\n",
       " 13: 'N',\n",
       " 14: 'O',\n",
       " 15: 'P',\n",
       " 16: 'Q',\n",
       " 17: 'R',\n",
       " 18: 'S',\n",
       " 19: 'T',\n",
       " 20: 'U',\n",
       " 21: 'V',\n",
       " 22: 'W',\n",
       " 23: 'X',\n",
       " 24: 'Y',\n",
       " 25: 'Z'}"
      ]
     },
     "execution_count": 46,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "{i : chr(65+i) for i in range(26)}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 14: Factorial function in functional form\n",
    "\n",
    "Usually there is two different styles for the implementation of a factorial fuction: first, recursive and second, iterative. **Write the factorial function in a FUNTIONAL FORM**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def factorialR(N):\n",
    "    \"Recursive factorial function\"\n",
    "    assert isinstance(N, int) and N >= 1 \n",
    "    return 1 if N <= 1 else N * factorialR(N-1)\n",
    "\n",
    "def factorialI(N):\n",
    "    \"Iterative factorial function\" \n",
    "    assert isinstance(N, int) and N >= 1 \n",
    "    product = 1\n",
    "    while N >= 1:\n",
    "        product *= N\n",
    "        N-=1 \n",
    "    return product"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 57 µs, sys: 43 µs, total: 100 µs\n",
      "Wall time: 86.1 µs\n",
      "CPU times: user 20 µs, sys: 7 µs, total: 27 µs\n",
      "Wall time: 24.8 µs\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000L"
      ]
     },
     "execution_count": 48,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%time factorialR(100)\n",
    "%time factorialI(100)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Factorial function in a FUNTIONAL FORM:**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 24 µs, sys: 5 µs, total: 29 µs\n",
      "Wall time: 27.9 µs\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000L"
      ]
     },
     "execution_count": 49,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%time reduce(lambda x,y:x*y, range(1,101), 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# or alternatively: \n",
    "\n",
    "from operator import mul \n",
    "def factorialHOF(n):\n",
    "    return reduce(mul, range(1, n+1), 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 18 µs, sys: 0 ns, total: 18 µs\n",
      "Wall time: 21 µs\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000L"
      ]
     },
     "execution_count": 51,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%time factorialHOF(100)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 15: Quicksort of a list\n",
    "\n",
    "Write in a recursive way the quicksort algorithm for a list of numbers"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def quicksort(lst):\n",
    "    \"Quicksort over a list-like sequence\" \n",
    "    if len(lst) == 0:\n",
    "        return lst \n",
    "    pivot = lst[0]\n",
    "    pivots=[x for x in lst if x==pivot]\n",
    "    small = quicksort([x for x in lst if x < pivot]) \n",
    "    large = quicksort([x for x in lst if x > pivot]) \n",
    "    return small + pivots + large"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0.65929156751013385, -1.5108355083499576, -0.77391155894222119, 2.1230386824778988, -1.632787582221124, -0.26306116205918623, 0.00024887102760674053, 1.2149482849162871, 0.83910562520002374, 0.69018482173631734]\n"
     ]
    }
   ],
   "source": [
    "from numpy.random import randn\n",
    "x = list(randn(10))\n",
    "print x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0.65929156751013385, -1.5108355083499576, -0.77391155894222119, 2.1230386824778988, -1.632787582221124, -0.26306116205918623, 0.00024887102760674053, 1.2149482849162871, 0.83910562520002374, 0.69018482173631734]\n",
      "\n",
      "[-1.632787582221124, -1.5108355083499576, -0.77391155894222119, -0.26306116205918623, 0.00024887102760674053, 0.65929156751013385, 0.69018482173631734, 0.83910562520002374, 1.2149482849162871, 2.1230386824778988]\n"
     ]
    }
   ],
   "source": [
    "print x \n",
    "print \n",
    "print quicksort(x)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 16: Memoizing decorator in Fibonacci generator"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from functools import wraps"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def memo(func):\n",
    "    cache = {}\n",
    "    @wraps(func)\n",
    "    def wrap(*args):\n",
    "        if args not in cache:\n",
    "            cache[args]=func(*args)\n",
    "        return cache[args]\n",
    "    return wrap"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "@memo\n",
    "def fibonacci(i):\n",
    "    if i < 2 : return 1\n",
    "    return fibonacci(i-1) + fibonacci(i-2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "89"
      ]
     },
     "execution_count": 58,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "fibonacci(10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[2, 3, 5, 8, 13, 21, 34, 55, 89]"
      ]
     },
     "execution_count": 59,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "[fibonacci(i) for i in xrange(2,11)]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 17: Estimate $\\pi$ by simulation\n",
    "\n",
    "Compute $\\pi$ by taking random numbers as x and y coordinates, and counting how many of them were in the unit circle"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The aproximation to pi with 500000 simulation is 3.140096\n"
     ]
    }
   ],
   "source": [
    "npts = 500000\n",
    "xs = 2 * np.random.rand(npts) - 1\n",
    "ys = 2 * np.random.rand(npts) - 1\n",
    "r = xs**2 + ys**2\n",
    "ninside = (r < 1).sum()\n",
    "print 'The aproximation to pi with {simul} simulation is {pi}'.format(simul = npts, pi=4*ninside/float(npts))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 18: Fast sorting by arguments in Numpy\n",
    " \n",
    " Sort in descending order a numpy array using `argsort`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 61,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "original array: \n",
      "[  7   5   4   8 150   9   0]\n",
      "\n",
      "index of the element of x in descending order: \n",
      "[6 2 1 0 3 5 4]\n",
      "\n",
      "np.array ordering in descending order:\n",
      "[150   9   8   7   5   4   0]\n",
      "\n",
      "np.array ordering in ascending order:\n",
      "[  0   4   5   7   8   9 150]\n"
     ]
    }
   ],
   "source": [
    "import numpy as np\n",
    "\n",
    "x = np.array([7, 5, 4, 8, 150, 9, 0])\n",
    "inds = np.argsort(x)\n",
    "x_descending = x[inds[::-1]]\n",
    "x_ascending = x[inds]\n",
    "print 'original array: \\n', x\n",
    "print \n",
    "print 'index of the element of x in descending order: \\n', inds\n",
    "print \n",
    "print 'np.array ordering in descending order:\\n', x_descending\n",
    "print\n",
    "print 'np.array ordering in ascending order:\\n', x_ascending"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 19: Multivariate Simulation and Covariance Matrix estimation"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 62,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Parameter for the simulation: \n",
      "[[  25.   90.   70.]\n",
      " [  90.  400.   40.]\n",
      " [  70.   40.  400.]]\n",
      "Estimation over simulation: \n",
      "[[  37.66314611  108.64695711   99.09423481]\n",
      " [ 108.64695711  440.41430016  113.17124305]\n",
      " [  99.09423481  113.17124305  495.53016035]]\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "/Users/JPC/anaconda/lib/python2.7/site-packages/IPython/kernel/__main__.py:18: RuntimeWarning: covariance is not positive-semidefinite.\n"
     ]
    }
   ],
   "source": [
    "import numpy as np\n",
    "\n",
    "random_numbers = 100\n",
    "means = np.array([50, 50, 50])\n",
    "corr1_2 = 0.9 \n",
    "corr1_3 = 0.7\n",
    "corr2_3 = 0.1\n",
    "sigma1 = 5\n",
    "sigma2 = 20\n",
    "sigma3 = 20\n",
    "\n",
    "covariance_matrix = np.array([[sigma1 ** 2, corr1_2 * sigma1 * sigma2, corr1_3 * sigma1 * sigma3],\n",
    "             [corr1_2 * sigma1 * sigma2, sigma2 ** 2, corr2_3 * sigma2 * sigma3],\n",
    "             [corr1_3 * sigma1 * sigma3, corr2_3 * sigma2 * sigma3, sigma3 ** 2]])\n",
    "\n",
    "np.random.seed(142)\n",
    "\n",
    "multivariate_simul = np.random.multivariate_normal(means, covariance_matrix, random_numbers)\n",
    "\n",
    "print 'Parameter for the simulation: \\n',covariance_matrix\n",
    "print 'Estimation over simulation: \\n',np.cov(multivariate_simul.T)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 63,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Means by columns: [49.415315565933049, 46.679176632042278, 50.683705762438315]\n",
      "Var by columns: [37.286514648374151, 436.01015715630041, 490.57485874240513]\n"
     ]
    }
   ],
   "source": [
    "# Calculating the means using a list comprenhension\n",
    "\n",
    "means_estimated =[np.mean(multivariate_simul[ :, i]) for i in range(multivariate_simul.shape[1])] \n",
    "print 'Means by columns:', means_estimated\n",
    "var_estimated =[np.var(multivariate_simul[ :, i]) for i in range(multivariate_simul.shape[1])]\n",
    "print 'Var by columns:', var_estimated"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 64,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "#TODO\n",
    "\n",
    "multivariate_simul_centered = np.matrix([map(lambda x : (x - means_estimated[i]), multivariate_simul[:,i]) \n",
    "                                       for i in range(multivariate_simul.shape[1])]).T\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 65,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[  12.47040624   35.9734072    32.81046571]\n",
      " [  35.9734072   145.82279504   37.47141492]\n",
      " [  32.81046571   37.47141492  164.07185911]]\n"
     ]
    }
   ],
   "source": [
    "covMatrix = sum(map(lambda x : np.outer(x.T,x), multivariate_simul_centered))/float(multivariate_simul.size-1)\n",
    "print covMatrix\n",
    "\n",
    "#covMatrix = reduce(lambda x, y : x + y , covMatrix)/float(multivariate_simul.size-1)\n",
    "\n",
    "# TODO"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 20: Inverting a dictionary: 1. using zip and 2. using a comprehension"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 66,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[('a', 1), ('c', 3), ('b', 2), ('d', 4)]"
      ]
     },
     "execution_count": 66,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "m = {'a' : 1, 'b' : 2, 'c' : 3, 'd' : 4}\n",
    "m.items()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 67,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(1, 'a'), (3, 'c'), (2, 'b'), (4, 'd')]"
      ]
     },
     "execution_count": 67,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "zip(m.values(), m.keys())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 68,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{1: 'a', 2: 'b', 3: 'c', 4: 'd'}"
      ]
     },
     "execution_count": 68,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "m_inverted_1 = dict( zip( m.values(), m.keys() ))\n",
    "m_inverted_1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 69,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{1: 'a', 2: 'b', 3: 'c', 4: 'd'}\n"
     ]
    }
   ],
   "source": [
    "m_inverted_2 = {value: key for key, value in m.items()}\n",
    "print m_inverted_2 "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 21: Generator expressions"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 70,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\"Lazy\" result:  0\n",
      "\"Lazy\" result:  1\n",
      "\"Lazy\" result:  4\n",
      "\"Lazy\" result:  9\n",
      "\"Lazy\" result:  16\n",
      "\"Lazy\" result:  25\n",
      "\"Lazy\" result:  36\n",
      "\"Lazy\" result:  49\n",
      "\"Lazy\" result:  64\n",
      "\"Lazy\" result:  81\n"
     ]
    }
   ],
   "source": [
    "# A quite compact 'pythonic' generator expression example:\n",
    "\n",
    "g = (x ** 2 for x in range(10))\n",
    "\n",
    "for n in g:\n",
    "    print '\"Lazy\" result: ', n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 71,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\"Lazy\" result:  0\n",
      "\"Lazy\" result:  1\n",
      "\"Lazy\" result:  4\n",
      "\"Lazy\" result:  9\n",
      "\"Lazy\" result:  16\n",
      "\"Lazy\" result:  25\n",
      "\"Lazy\" result:  36\n",
      "\"Lazy\" result:  49\n",
      "\"Lazy\" result:  64\n",
      "\"Lazy\" result:  81\n"
     ]
    }
   ],
   "source": [
    "# Equivalent to the previous snippet, but more 'verbose':\n",
    "\n",
    "def myg(stop): \n",
    "    z = 0\n",
    "    while z < stop:\n",
    "        yield z**2\n",
    "        z+=1\n",
    "        \n",
    "g = myg(10)\n",
    "for n in g:\n",
    "    print '\"Lazy\" result: ', n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 22: Inheriting from named tuples (`collections.namedtuple`)\n",
    "\n",
    "Define a new object (a named tuple) called `Point` using `collections.namedtuple` and build a method to sum the components of two `points`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 72,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import collections\n",
    "\n",
    "Point = collections.namedtuple('Point', ['x', 'y'])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 73,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Point(x=1.0, y=2.0) 1.0 2.0\n"
     ]
    }
   ],
   "source": [
    "p = Point(x = 1.0, y = 2.0)\n",
    "print p, p.x, p.y"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 74,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Point(collections.namedtuple('PointBase', ['x', 'y'])):\n",
    "        __slots__ = ()\n",
    "        def __add__(self, other):\n",
    "                return Point(x=self.x + other.x, y=self.y + other.y)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 75,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "PointBase(x=3.0, y=5.0)\n"
     ]
    }
   ],
   "source": [
    "p = Point(x=1.0, y=2.0)\n",
    "q = Point(x=2.0, y=3.0)\n",
    "print p + q"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 23: Double-ended queue with maximum length (`collections.deque`)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 76,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "Q = collections.deque()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 77,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "deque([6, 5, 2, 1, 3, 4])"
      ]
     },
     "execution_count": 77,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Q.append(1)\n",
    "Q.appendleft(2)\n",
    "Q.extend([3, 4])\n",
    "Q.extendleft([5, 6])\n",
    "Q"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 78,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0\n",
      "0, 1\n",
      "0, 1, 2\n",
      "1, 2, 3\n",
      "2, 3, 4\n",
      "3, 4, 5\n",
      "4, 5, 6\n",
      "5, 6, 7\n",
      "6, 7, 8\n",
      "7, 8, 9\n"
     ]
    }
   ],
   "source": [
    "last_three = collections.deque(maxlen=3)\n",
    "for i in xrange(10):\n",
    "    last_three.append(i)\n",
    "    print ', '.join(str(x) for x in last_three)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 24: Using default dictionaries to represent simple trees"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 105,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import json\n",
    "import collections"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 106,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "tree = lambda: collections.defaultdict(tree)\n",
    "root = tree()\n",
    "root['menu']['id'] = 'file'\n",
    "root['menu']['value'] = 'File'\n",
    "root['menu']['menuitems']['new']['value'] = 'New'\n",
    "root['menu']['menuitems']['new']['onclick'] = 'new();'\n",
    "root['menu']['menuitems']['open']['value'] = 'Open'\n",
    "root['menu']['menuitems']['open']['onclick'] = 'open();'\n",
    "root['menu']['menuitems']['close']['value'] = 'Close'\n",
    "root['menu']['menuitems']['close']['onclick'] = 'close();'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 107,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{\n",
      "    \"menu\": {\n",
      "        \"id\": \"file\",\n",
      "        \"menuitems\": {\n",
      "            \"close\": {\n",
      "                \"onclick\": \"close();\",\n",
      "                \"value\": \"Close\"\n",
      "            },\n",
      "            \"new\": {\n",
      "                \"onclick\": \"new();\",\n",
      "                \"value\": \"New\"\n",
      "            },\n",
      "            \"open\": {\n",
      "                \"onclick\": \"open();\",\n",
      "                \"value\": \"Open\"\n",
      "            }\n",
      "        },\n",
      "        \"value\": \"File\"\n",
      "    }\n",
      "}\n"
     ]
    }
   ],
   "source": [
    "print json.dumps(root, sort_keys=True, indent=4, separators=(',', ': '))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 25: Cartesian products (`itertools.product`)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 80,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(1, 4)\n",
      "(1, 5)\n",
      "(2, 4)\n",
      "(2, 5)\n",
      "(3, 4)\n",
      "(3, 5)\n"
     ]
    }
   ],
   "source": [
    "import itertools\n",
    "\n",
    "for p in itertools.product([1, 2, 3], [4, 5]):\n",
    "    print p"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 81,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0000\n",
      "0001\n",
      "0010\n",
      "0011\n",
      "0100\n",
      "0101\n",
      "0110\n",
      "0111\n",
      "1000\n",
      "1001\n",
      "1010\n",
      "1011\n",
      "1100\n",
      "1101\n",
      "1110\n",
      "1111\n"
     ]
    }
   ],
   "source": [
    "for p in itertools.product([0, 1], repeat=4):\n",
    "    print ''.join(str(x) for x in p)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 26: All the methods to **Flattening** a list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 82,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "a = [[1, 2], [3, 4], [5, 6]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 83,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 3, 4, 5, 6]"
      ]
     },
     "execution_count": 83,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sum(a, [])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 84,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 3, 4, 5, 6]"
      ]
     },
     "execution_count": 84,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "[x for l in a for x in l]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 85,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 3, 4, 5, 6]"
      ]
     },
     "execution_count": 85,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "list(itertools.chain.from_iterable(a))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 86,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 3, 4, 5, 6, 7, 8]"
      ]
     },
     "execution_count": 86,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a = [1, 2, [3, 4], [[5, 6], [7, 8]]]\n",
    "flatten = lambda x: [y for l in x for y in flatten(l)] if type(x) is list else [x]\n",
    "flatten(a)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 27: Inheritance/Multiple\n",
    "Multiple inheritance allows to specify that one class is a subclass of several other classes. Some languages allow multiple inheritance for arbitrary classes, others restrict it to interfaces, some don't allow it at all.\n",
    "Write two classes (or interfaces) Camera and MobilePhone, then write a class CameraPhone which is both a Camera and a MobilePhone.\n",
    "There is no need to implement any functions for those classes."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 87,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Camera:\n",
    "    pass #functions go here...\n",
    "\n",
    "class MobilePhone:\n",
    "    pass #functions go here...\n",
    "\n",
    "class CameraPhone(Camera, MobilePhone):\n",
    "    pass #functions go here..."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 28: Roots of a quadratic function\n",
    "\n",
    "Write a program to find the roots of a quadratic equation, i.e., solve the equation $ax^2 + bx + c = 0$. Your program must correctly handle non-real roots, but it need not check that $a \\neq 0$.\n",
    "\n",
    "The problem of solving a quadratic equation is a good example of how dangerous it can be to ignore the peculiarities of floating-point arithmetic. The obvious way to implement the quadratic formula suffers catastrophic loss of accuracy when one of the roots to be found is much closer to 0 than the other. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 88,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import math\n",
    "import cmath\n",
    "import numpy"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 89,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def quad_discriminating_roots(a,b,c, entier = 1e-5):\n",
    "    \"\"\"For reference, the naive algorithm which shows complete loss of\n",
    "    precision on the quadratic in question.  (This function also returns a\n",
    "    characterization of the roots.)\"\"\"\n",
    "    \n",
    "    discriminant = b*b - 4*a*c\n",
    "    \n",
    "    a,b,c,d = complex(a), complex(b), complex(c), complex(discriminant)\n",
    "    \n",
    "    root1 = (-b + cmath.sqrt(d))/2./a\n",
    "    root2 = (-b - cmath.sqrt(d))/2./a\n",
    "    \n",
    "    if abs(discriminant) < entier:\n",
    "        return \"real and equal\", abs(root1), abs(root1)\n",
    "    \n",
    "    if discriminant > 0:\n",
    "        return \"real\", root1.real, root2.real\n",
    "    \n",
    "    return \"complex\", root1, root2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 90,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def middlebrook(a, b, c):\n",
    "    try:\n",
    "        q = math.sqrt(a*c)/b\n",
    "        f = .5+ math.sqrt(1-4*q*q)/2\n",
    "    except ValueError:\n",
    "        q = cmath.sqrt(a*c)/b\n",
    "        f = .5+ cmath.sqrt(1-4*q*q)/2\n",
    "    return (-b/a)*f, -c/(b*f)\n",
    " "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 91,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def whatevery(a, b, c):\n",
    "    try:\n",
    "        d = math.sqrt(b*b-4*a*c)\n",
    "    except ValueError:\n",
    "        d = cmath.sqrt(b*b-4*a*c)\n",
    "    if b > 0:\n",
    "        return div(2*c, (-b-d)), div((-b-d), 2*a)\n",
    "    else:\n",
    "        return div((-b+d), 2*a), div(2*c, (-b+d))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 92,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def div(n, d):\n",
    "    \"\"\"Divide, with a useful interpretation of division by zero.\"\"\"\n",
    "    try:\n",
    "        return n/d\n",
    "    except ZeroDivisionError:\n",
    "        if n:\n",
    "            return n*float('inf')\n",
    "        return float('nan')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 93,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "testcases = [\n",
    "    (3, 4, 4/3),    # real, equal\n",
    "    (3, 2, -1),     # real, unequal\n",
    "    (3, 2, 1),      # complex\n",
    "    (1, -1e9, 1),   # ill-conditioned \"quadratic in question\" required by task.\n",
    "    (1, -1e100, 1),\n",
    "    (1, -1e200, 1),\n",
    "    (1, -1e300, 1)]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 94,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Naive:\n",
      "real -0.33333 -1.0\n",
      "real 0.33333 -1.0\n",
      "complex (-0.33333+0.4714j) (-0.33333-0.4714j)\n",
      "real 1e+09 0.0\n",
      "real 1e+100 0.0\n",
      "real nan nan\n",
      "real nan nan\n",
      "\n",
      "Middlebrook:\n",
      "-1.5 -0.33333 \n",
      "(-1.5+0j) (0.33333+0j) \n",
      "(-0.5-0.70711j) (-0.33333+0.4714j) \n",
      "1e+09 1e-09 \n",
      "1e+100 1e-100 \n",
      "1e+200 1e-200 \n",
      "1e+300 1e-300 \n",
      "\n",
      "What Every...\n",
      "-0.33333 -1.0 \n",
      "0.33333 -1.0 \n",
      "(-0.33333+0.4714j) (-0.33333-0.4714j) \n",
      "1e+09 1e-09 \n",
      "1e+100 1e-100 \n",
      "inf 0.0 \n",
      "inf 0.0 \n",
      "\n",
      "Numpy:\n",
      "-1.0 -0.33333 \n",
      "-1.0 0.33333 \n",
      "(-0.33333+0.4714j) (-0.33333-0.4714j) \n",
      "1e+09 1e-09 \n",
      "1e+100 1e-100 \n",
      "1e+200 1e-200 \n",
      "1e+300 0.0 \n"
     ]
    }
   ],
   "source": [
    "print('Naive:')\n",
    "for c in testcases:\n",
    "    print(\"{} {:.5} {:.5}\".format(*quad_discriminating_roots(*c)))\n",
    "\n",
    "print('\\nMiddlebrook:')\n",
    "for c in testcases:\n",
    "    print((\"{:.5} \"*2).format(*middlebrook(*c)))\n",
    "\n",
    "    \n",
    "print('\\nWhat Every...')\n",
    "for c in testcases:\n",
    "    print((\"{:.5} \"*2).format(*whatevery(*c)))\n",
    "\n",
    "    \n",
    "print('\\nNumpy:')\n",
    "for c in testcases:\n",
    "    print((\"{:.5} \"*2).format(*numpy.roots(c)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 29: Ordered dictionaries (`collections.OrderedDict`)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 95,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{'10': 9, '1': 0, '3': 2, '2': 1, '5': 4, '4': 3, '7': 6, '6': 5, '9': 8, '8': 7}\n"
     ]
    }
   ],
   "source": [
    "m = dict((str(x+1), x) for x in range(10))\n",
    "print m"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 96,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "10, 1, 3, 2, 5, 4, 7, 6, 9, 8\n"
     ]
    }
   ],
   "source": [
    "print ', '.join(m.keys())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 97,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[('1', 0), ('2', 1), ('3', 2), ('4', 3), ('5', 4), ('6', 5), ('7', 6), ('8', 7), ('9', 8), ('10', 9)]\n"
     ]
    }
   ],
   "source": [
    "import operator\n",
    "sorted_m_by_values = sorted(m.items(), key=operator.itemgetter(1))\n",
    "print sorted_m_by_values"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 98,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "OrderedDict([('0', 0), ('1', 1), ('2', 2), ('3', 3), ('4', 4), ('5', 5), ('6', 6), ('7', 7), ('8', 8), ('9', 9)])\n"
     ]
    }
   ],
   "source": [
    "m = collections.OrderedDict((str(x), x) for x in range(10))\n",
    "print m"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 99,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "OrderedDict([('10', 10), ('9', 9), ('8', 8), ('7', 7), ('6', 6), ('5', 5), ('4', 4), ('3', 3), ('2', 2), ('1', 1)])\n"
     ]
    }
   ],
   "source": [
    "m = collections.OrderedDict((str(x), x) for x in range(10, 0, -1))\n",
    "print m"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 30: Check whether a file exists using Python"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 100,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "False\n",
      "False\n"
     ]
    }
   ],
   "source": [
    "import os.path\n",
    "file_name = '#############'\n",
    "print os.path.isfile(file_name)\n",
    "print os.path.exists(file_name)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 31: The Knapsack problem using memoization and tested using doctest\n",
    "\n",
    "Any dynamic programming algorithm can be implemented in two ways: by building a table of partial results from the bottom up, or by recursively computing the result from the top down, using **memoization** to avoid computing any partial result more than once.\n",
    "\n",
    "There are two advantages of the top-down approach: *first*, it often results in slightly simpler and clearer code, and *second*, it only computes the partial results that are needed for the particular problem instance (whereas the bottom-up approach computes all partial results even if some of them go unused).\n",
    "\n",
    "Use the `@memoized` decorator from the Python Decorator Library to implement a **top-down** solution for the Knapsack problem, and write a test of the function inside of the docstring (as a doctest).\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 101,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import collections\n",
    "import functools\n",
    "\n",
    "class memoized(object):\n",
    "    '''Decorator: Caches a function's return value each time it is called.\n",
    "    If called later with the same arguments, the cached value is returned\n",
    "    (not reevaluated).\n",
    "    '''\n",
    "    def __init__(self, func):\n",
    "        self.func = func\n",
    "        self.cache = {}    \n",
    "    def __call__(self, *args):\n",
    "        if not isinstance(args, collections.Hashable):\n",
    "            # uncacheable. a list, for instance.\n",
    "            # better to not cache than blow up.\n",
    "            return self.func(*args)\n",
    "        if args in self.cache:\n",
    "            return self.cache[args]\n",
    "        else:\n",
    "            value = self.func(*args)\n",
    "            self.cache[args] = value\n",
    "            return value\n",
    "    def __repr__(self):\n",
    "        '''Return the function's docstring.'''\n",
    "        return self.func.__doc__\n",
    "    def __get__(self, obj, objtype):\n",
    "        '''Support instance methods.'''\n",
    "        return functools.partial(self.__call__, obj)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 102,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Exception reporting mode: Plain\n",
      "Doctest mode is: ON\n"
     ]
    }
   ],
   "source": [
    "%doctest_mode"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 103,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def knapsack(items, maxweight):\n",
    "    \"\"\"\n",
    "    Solve the knapsack problem by finding the most valuable\n",
    "    subsequence of `items` subject that weighs no more than\n",
    "    `maxweight`.\n",
    "\n",
    "    `items` is a sequence of pairs `(value, weight)`, where `value` is\n",
    "    a number and `weight` is a non-negative integer.\n",
    "\n",
    "    `maxweight` is a non-negative integer.\n",
    "\n",
    "    Return a pair whose first element is the sum of values in the most\n",
    "    valuable subsequence, and whose second element is the subsequence.\n",
    "\n",
    "    >>> items = [(4, 12), (2, 1), (6, 4), (1, 1), (2, 2)]\n",
    "    >>> knapsack(items, 15)\n",
    "    (11, [(2, 1), (6, 4), (1, 1), (2, 2)])\n",
    "    \"\"\"\n",
    "\n",
    "    # Return the value of the most valuable subsequence of the first i\n",
    "    # elements in items whose weights sum to no more than j.\n",
    "    @memoized\n",
    "    def bestvalue(i, j):\n",
    "        if i == 0: return 0\n",
    "        value, weight = items[i - 1]\n",
    "        if weight > j:\n",
    "            return bestvalue(i - 1, j)\n",
    "        else:\n",
    "            return max(bestvalue(i - 1, j),\n",
    "                       bestvalue(i - 1, j - weight) + value)\n",
    "\n",
    "    j = maxweight\n",
    "    result = []\n",
    "    for i in xrange(len(items), 0, -1):\n",
    "        if bestvalue(i, j) != bestvalue(i - 1, j):\n",
    "            result.append(items[i - 1])\n",
    "            j -= items[i - 1][1]\n",
    "    result.reverse()\n",
    "    return bestvalue(len(items), maxweight), result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 104,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "TestResults(failed=0, attempted=2)"
      ]
     },
     "execution_count": 104,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import doctest\n",
    "doctest.testmod()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 32: 100 doors\n",
    "\n",
    "**Problem**: \n",
    "\n",
    "You have 100 doors in a row that are all initially closed. \n",
    "\n",
    "You make 100 passes by the doors. \n",
    "\n",
    "The first time through, you visit every door and toggle the door (if the door is closed, you open it; if it is open, you close it). \n",
    "\n",
    "The second time you only visit every 2nd door (door #2, #4, #6, ...). \n",
    "\n",
    "The third time, every 3rd door (door #3, #6, #9, ...), etc, until you only visit the 100th door.\n",
    "\n",
    "**Question**: What state are the doors in after the last pass? Which are open, which are closed?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# quick and easy version (unoptimized)\n",
    "\n",
    "doors = [False] * 100 \n",
    "for i in xrange(100):\n",
    "    for j in xrange(i, 100, i+1):\n",
    "        doors[j] = not doors[j]\n",
    "    print \"Door {0}:\".format(i+1), \"open\" if doors[i]== True else \"close\"\n",
    " "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# optimized version\n",
    "\n",
    "for i in xrange(1, 101):\n",
    "    root = i ** 0.5\n",
    "    print \"Door {0}:\".format(i), 'open' if root == int(root) else 'close'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# In one line, using a list comprehension, item lookup, and is_integer: \n",
    "\n",
    "print '\\n'.join(['Door %s is %s' % (i, ('closed', 'open')[(i**0.5).is_integer()]) for i in xrange(1, 101)])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 33: Roots of a function\n",
    "Create a program that finds and outputs the roots of a given function, range and (if applicable) step width. The program should identify whether the root is exact or approximate.\n",
    "For this example, use $f(x)=x^2-5x+1$.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# defining the Newton-Raphson algorithm:\n",
    "\n",
    "def newton_solver(function, derivative, start, delta):\n",
    "    last_x = start\n",
    "    next_x = last_x + 10 * delta\n",
    "    while abs(last_x - next_x) > delta:\n",
    "        new_y = function(next_x)\n",
    "        print 'f({0}) = {1}'.format(last_x, new_y) # just to check the convergence... for fun\n",
    "        last_x = next_x\n",
    "        next_x = last_x - new_y / derivative(last_x)\n",
    "        \n",
    "    return next_x\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "f(10) = 51.1501\n",
      "f(10.01) = 11.5971989855\n",
      "f(6.60453395473) = 1.99580690572\n",
      "f(5.19180365289) = 0.137432768246\n",
      "f(4.8210843949) = 0.000876473387248\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "4.791287855459265"
      ]
     },
     "execution_count": 49,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "myfunction = lambda x : x * x  - 5 * x  + 1\n",
    "myderivative = lambda x : (myfunction(x + delta) - myfunction(x - delta)) / (2.0 * delta)\n",
    "\n",
    "newton_solver(myfunction, myderivative, start = 10 , delta = 0.001)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 34: Dictionary from two lists\n",
    "\n",
    "Using two list, or arrays, of equal length, create a dictionary or hash table object where the elements from one array (the keys) are linked to the elements of the other (the values)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{'a': 1, 'c': 3, 'b': 2}\n"
     ]
    }
   ],
   "source": [
    "keys = ['a', 'b', 'c']\n",
    "values = [1, 2, 3]\n",
    "hash = {key: value for key, value in zip(keys, values)}\n",
    "print hash"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 35: Reverse words in a string\n",
    "Reverse the order of all tokens in each of a number of strings and display the result; the order of characters within a token should not be modified.\n",
    "\n",
    "**Example**: *“Hey you, Bub!”* would be shown reversed as: *“Bub! you, Hey”*"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "text = '''\\\n",
    "---------- Ice and Fire ------------\n",
    " \n",
    "fire, in end will world the say Some\n",
    "ice. in say Some\n",
    "desire of tasted I've what From\n",
    "fire. favor who those with hold I\n",
    " \n",
    "... elided paragraph last ...\n",
    " \n",
    "Frost Robert -----------------------'''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "------------ Fire and Ice ----------\n",
      "\n",
      "Some say the world will end in fire,\n",
      "Some say in ice.\n",
      "From what I've tasted of desire\n",
      "I hold with those who favor fire.\n",
      "\n",
      "... last paragraph elided ...\n",
      "\n",
      "----------------------- Robert Frost\n"
     ]
    }
   ],
   "source": [
    "for line in text.split('\\n'): print(' '.join(line.split()[::-1]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 36: Compare sorting algorithms' performance\n",
    "Measure a relative performance of sorting algorithms implementations.\n",
    "Plot execution time vs. input sequence length dependencies for various implementation of sorting algorithm and different input sequence types"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Sorting routines to compare:\n",
    "\n",
    "def builtinsort(x):\n",
    "    x.sort()\n",
    "\n",
    "def partition(seq, pivot):\n",
    "    low, middle, up = [], [], []\n",
    "    for x in seq:\n",
    "        if x < pivot:\n",
    "            low.append(x)\n",
    "        elif x == pivot:\n",
    "            middle.append(x)\n",
    "        else:\n",
    "            up.append(x)\n",
    "    return low, middle, up\n",
    "\n",
    "import random\n",
    "def qsortranpart(seq):\n",
    "    size = len(seq)\n",
    "    if size < 2: return seq\n",
    "    low, middle, up = partition(seq, random.choice(seq))\n",
    "    return qsortranpart(low) + middle + qsortranpart(up)\n",
    "\n",
    "def insertion_sort(l):\n",
    "    for i in xrange(1, len(l)):\n",
    "        j = i-1 \n",
    "        key = l[i]\n",
    "        while (l[j] > key) and (j >= 0):\n",
    "           l[j+1] = l[j]\n",
    "           j -= 1\n",
    "        l[j+1] = key\n",
    "        \n",
    "import bisect\n",
    "def insertion_sort_bin(seq):\n",
    "    for i in range(1, len(seq)):\n",
    "        bisect.insort(seq, seq.pop(i), 0, i)\n",
    "        \n",
    "        \n",
    "def qsort(list):\n",
    "    if not list:\n",
    "        return []\n",
    "    else:\n",
    "        pivot = list[0]\n",
    "        less = [x for x in list     if x <  pivot]\n",
    "        more = [x for x in list[1:] if x >= pivot]\n",
    "        return qsort(less) + [pivot] + qsort(more)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Functions to generate sequences to order:\n",
    "\n",
    "def ones(n):\n",
    "    return [1]*n\n",
    " \n",
    "def reversedrange(n):\n",
    "    return reversed(range(n))\n",
    " \n",
    "def shuffledrange(n):\n",
    "    x = range(n)\n",
    "    random.shuffle(x)\n",
    "    return x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import itertools\n",
    "def writedat(filename, x, y, xprecision=3, yprecision=5):\n",
    "    with open(filename,'w') as f:\n",
    "        for a, b in itertools.izip(x, y):\n",
    "            print >> f, \"%.*g\\t%.*g\" % (xprecision, a, yprecision, b)\n",
    "\n",
    "import sys, timeit\n",
    "def usec(function, arguments):\n",
    "    modname, funcname = __name__, function.__name__\n",
    "    timer = timeit.Timer(stmt='%(funcname)s(*args)' % vars(),\n",
    "                         setup='from %(modname)s import %(funcname)s; args=%(arguments)r' % vars())\n",
    "    try:\n",
    "        t, N = 0, 1\n",
    "        while t < 0.2:            \n",
    "            t = min(timer.repeat(repeat=3, number=N))            \n",
    "            N *= 10\n",
    "        microseconds = round(10000000 * t / N, 1) # per loop\n",
    "        return microseconds \n",
    "    except:\n",
    "        timer.print_exc(file=sys.stderr)\n",
    "        raise\n",
    "def nothing(): pass\n",
    "def identity(x): return x\n",
    "\n",
    "\n",
    "def write_timings(npoints=10, maxN=10**4, sort_functions=(builtinsort,insertion_sort, qsort), \n",
    "                  sequence_creators = (ones, range, shuffledrange)):    \n",
    "    Ns = range(2, maxN, maxN//npoints)\n",
    "    for sort in sort_functions:\n",
    "        for make_seq in sequence_creators:\n",
    "            Ts = [usec(sort, (make_seq(n),)) for n in Ns]\n",
    "            writedat('%s-%s-%d-%d.xy' % (sort.__name__,  make_seq.__name__, len(Ns), max(Ns)), Ns, Ts)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "%matplotlib inline\n",
    "import operator\n",
    "import numpy, pylab\n",
    "def plotdd(dictplotdict):\n",
    "    \"\"\"See ``plot_timings()`` below.\"\"\"\n",
    "    symbols = ('o', '^', 'v', '<', '>', 's', '+', 'x', 'D', 'd',\n",
    "              '1', '2', '3', '4', 'h', 'H', 'p', '|', '_')\n",
    "    colors = list('bgrcmyk') # split string on distinct characters\n",
    "    for npoints, plotdict in dictplotdict.iteritems():\n",
    "        for ttle, lst in plotdict.iteritems():            \n",
    "            pylab.hold(False)                                \n",
    "            for i, (label, polynom, x, y) in enumerate(sorted(lst,key=operator.itemgetter(0))):\n",
    "                pylab.plot(x, y, colors[i % len(colors)] + symbols[i % len(symbols)], label='%s %s' % (polynom, label))\n",
    "                pylab.hold(True)\n",
    "                y = numpy.polyval(polynom, x)\n",
    "                pylab.plot(x, y, colors[i % len(colors)], label= '_nolegend_')                \n",
    "            pylab.legend(loc='upper left')\n",
    "            pylab.xlabel(polynom.variable)\n",
    "            pylab.ylabel('log2( time in microseconds )')                \n",
    "            pylab.title(ttle, verticalalignment='bottom')\n",
    "            figname = '_%(npoints)03d%(ttle)s' % vars()\n",
    "            pylab.savefig(figname+'.png')\n",
    "            pylab.savefig(figname+'.pdf')\n",
    "            print figname"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import collections, itertools, glob, re\n",
    "import numpy\n",
    "def plot_timings():\n",
    "    makedict = lambda: collections.defaultdict(lambda: collections.defaultdict(list))\n",
    "    df = makedict()\n",
    "    ds = makedict()\n",
    "    # populate plot dictionaries\n",
    "    for filename in glob.glob('*.xy'):\n",
    "        m = re.match(r'([^-]+)-([^-]+)-(\\d+)-(\\d+)\\.xy', filename)\n",
    "        print filename\n",
    "        assert m, filename\n",
    "        funcname, seqname, npoints, maxN = m.groups()\n",
    "        npoints, maxN = int(npoints), int(maxN)        \n",
    "        a = numpy.fromiter(itertools.imap(float, open(filename).read().split()), dtype='f')\n",
    "        Ns = a[::2]  # sequences lengths\n",
    "        Ts = a[1::2] # corresponding times \n",
    "        assert len(Ns) == len(Ts) == npoints\n",
    "        assert max(Ns) <= maxN\n",
    "        #\n",
    "        logsafe = numpy.logical_and(Ns>0, Ts>0)\n",
    "        Ts = numpy.log2(Ts[logsafe])\n",
    "        Ns = numpy.log2(Ns[logsafe])\n",
    "        coeffs = numpy.polyfit(Ns, Ts, deg=1)\n",
    "        poly = numpy.poly1d(coeffs, variable='log2(N)')\n",
    "        #\n",
    "        df[npoints][funcname].append((seqname, poly, Ns, Ts))\n",
    "        ds[npoints][seqname].append((funcname, poly, Ns, Ts))\n",
    "    # actual plotting\n",
    "    plotdd(df)\n",
    "    plotdd(ds) # see ``plotdd()`` above"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "builtinsort-ones-103-1022.xy\n",
      "builtinsort-range-103-1022.xy\n",
      "builtinsort-shuffledrange-103-1022.xy\n",
      "insertion_sort-ones-103-1022.xy\n",
      "insertion_sort-range-103-1022.xy\n",
      "insertion_sort-shuffledrange-103-1022.xy\n",
      "qsort-ones-103-1022.xy\n",
      "qsort-range-103-1022.xy\n",
      "qsort-shuffledrange-103-1022.xy\n",
      "_103qsort\n",
      "_103insertion_sort\n",
      "_103builtinsort\n",
      "_103shuffledrange\n",
      "_103range\n",
      "_103ones\n"
     ]
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAYIAAAEcCAYAAADKlrO6AAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAIABJREFUeJzsnXlcVWX6wL/vZZHlgoALIIJojmnmVmo1WmJNWpptlmmK\nSpa/ytLGadTUXMom09KpdMrcwiVLs9HIcVfccplS0VFzF/cNF0B2eH5/nMuRKxe4KCjK+/18zkfO\nuz7n3OPzvO/zbkpE0Gg0Gk35xXKrBdBoNBrNrUUbAo1GoynnaEOg0Wg05RxtCDQajaacow2BRqPR\nlHO0IdBoNJpyjjYEGo1GU87RhkCj0WjKOdoQaDQaTTlHGwKNBlBK1VNKxSqlLiql/qeU6mAL/1Yp\nNVEp9YtSKlEptUkpVStPvrpKqeVKqQSl1B9KqRfzxLVTSu2y5TuulPrbrXg2jaYotCHQlHuUUm5A\nDLAEqAK8DcxWStWxJXkJGAH4AweAj2z5vIHlwCxbvs7Av5RSdW35pgK9RcQXqA+suhnPo9EUF20I\nNBp4EPAWkdEikiUiq4FfgC6AAD+JyG8ikg3MBhrb8j0FHBaRaBHJEZHtwE9AJ1t8BlBfKeUrIpdF\nZNtNfSqNxkm0IdBooBpw7JqweCDE9veZPOGpgNX2dw3gAZs76aJS6iLwMhBoi+8ItAOO2NxOD5aK\n9BrNDeJ6qwXQaMoAJ4FQpZSSq9vx1gD2AuGF5DsKrBGRNo4iReQ34FmllAuGu2kuEFZiUms0JYTu\nEWg0sAlIAQYopdyUUhEYbp85gCok3yKgjlKqmy2fm1KqmW0A2U0p1VUpVdHmUkoCskv7QTSa60Eb\nAk25R0QygQ7Ak8A5YAIQKSL7MMYIrj20Q2z5koA2GIPEJ4BTwMeAuy1dN+CwUuoy0BvoWrpPotFc\nH0ofTKPRaDTlG90j0Gg0mnKONgQajUZTzil1Q6CUClVKrbatsPyfUqqvLTzAtiJzn1JqmVLKr7Rl\n0Wg0Gk1+Sn2MQCkVBASJyHallBX4HXgWiALOi8gYpdRAwF9EBpWqMBqNRqPJR6n3CETktG3FJSKS\nDOzBWKjzNBBtSxaNYRw0Go1Gc5O5qWMESqlwoAmwGQgUkdwVm2e4uhpTo9FoNDeRm2YIbG6h+UA/\n2/xrE9tqTj2PVaPRaG4BN2WLCdvujvOBmSKywBZ8RikVJCKnlVLBwFkH+bRx0Gg0mutARApbFW/H\nzZg1pDC2490tIv/ME/Uz0MP2dw9gwbV5AUSkTF3Dhw+/5TLcDjKVVbm0TFqm8iBXcbkZPYIWGEvt\ndyilcrfhfQ8YDcxVSvUCjnB1616NRqPR3ERK3RCIyHoK7nn8pbTr12g0Gk3h6JXFxSQiIuJWi5CP\nsigTlE25tEzOoWVynrIqV3Eo05vO2W8Pr9FoNBpnUEohxRgsvi0PpjHGnzUaTXlGNxJLjtvSEID+\nCDSa8oxuDJYseoxAo9FoyjnaEGg0Gk05RxsCjUajKedoQ6DRaDTlHG0INBqNppyjDYFGo9GUc7Qh\n0Gg0mnKONgQajUZTztGGQKPRaMo52hBoNBpNOUcbAo1GoynnaEOg0Wg05RxtCDQajaacow2BRqPR\nlHNu222oHbFo0Vq++GIZ6emuVKiQRd++bWjf/pGbXoZGo9HcTtwxhmDRorX067eUgwc/MsMOHhwC\n4LQiL4kyNBqN5nbjjnENffHFMjsFDnDw4Ed8+eXym1qGRqPR3G7cMYYgPd1x5yYtzeWmlqHRaDS3\nG3eMIahQIcthuIdH9k0t43bkyJEjWCwWcnJySr2u9PR06tevz5kzZ5zO88ILL7BkyZJSlOrWER4e\nzsqVK68r7xtvvMGoUaMAiI2NJTQ0tMC0R48excfHRx/xqnHIHWMI+vZtw113DbELu+uuwbz99uM3\ntYwLFy7w3HPPYbVaCQ8PZ86cOYWm//DDDwkNDcXPz4/WrVuze/duADIyMujVqxfh4eH4+vrSpEmT\nfMpwwYIF1K9fH19fX+rXr8/ChQvNuLFjx9KgQQN8fX2pVasWn376qdPPcL04I/M333xDq1atCAwM\nBKBnz55YLBb++9//mmkOHDiAxXL10xw4cCBDhw4tERnXrFmDxWLh/fffd+p56tWrl0/B/vrrrzRv\n3hxfX18aNWrEhg0bzLjY2FgsFgs+Pj7mNXPmzALrUEpd9/m7X331VYHvJTw8nFWrVpn3YWFhJCUl\n3fSzfkeMGEFkZORNrVNTfO6YweLcwdwvv3yftDQXPDyyefvtJ4o1yFsSZfTp0wcPDw/Onj3Ltm3b\naN++PY0aNeKee+7Jl/bnn3/m66+/ZsOGDYSFhTF06FAiIyP5/fffycrKIiwsjLVr1xIWFsaiRYvo\n1KkTO3fupEaNGpw9e5auXbvy008/0bZtW/7zn//w4osvEh8fT+XKlQGYOXMmDRs25MCBA7Rp04bQ\n0FBeeuklp5+luBQlM8CkSZOYPHmyXb6AgACGDh3K0qVLHZbbrFkzEhMT+f3337n//vuvW77MzEz6\n9evHgw8+6JRCHDt2LFWrVuXKlStm2IULF+jQoQPffPMNzz//PN999x0dOnTg0KFD+Pn5ARASEsKx\nY8euW86SQCl1y1v/WVmOe9iaMoiIlNnLEC8/BYXfapKTk8Xd3V32799vhnXv3l0GDRrkMP0//vEP\n6dSpk3n/v//9Tzw8PAosv2HDhvLTTz+JiMiGDRukatWqdvFVqlSRTZs2Oczbt29fefvttx3GHT58\nWJRSkp2dLSIiJ06ckA4dOkhAQIDUrl1bJk+ebKZNSUmR7t27i7+/v9SrV08++eQTqV69ulMyx8fH\ni6enp1mPiEjPnj2lf//+EhQUJGvWrBERkf3794tSyq6c1157TUaOHFlgPc7w8ccfy8CBA6Vnz54y\ndOjQQtMeOnRI6tWrJ4sXL7Z7vpiYGLnnnnvs0tapU0emTp0qIiKrV68u9H1cS3h4uHz88cdyzz33\niL+/v0RFRUlaWpqIiEyfPl1atmxpl14pJQcPHhQRkR49epjPkbfebt26icViEU9PT7FarTJ27Nh8\nv3GrVq3k/ffflxYtWoiPj4+0adNGzp8/LyIiqamp0rVrV6lUqZL4+flJs2bN5MyZMyJS+LcxfPhw\n6dixo3Tr1k18fX1lwoQJ4u7uLm5ubmK1WqVx48ZOv5eiKKs6oKxgez9O69o7xjVUFti3bx+urq7U\nrl3bDGvUqBG7du1ymP6xxx5j48aN7N+/n8zMTKKjo3nyyScdpj1z5gz79u2jfv36ADRs2BBXV1d+\n+eUXsrOzWbBgAR4eHjRs2DBfXhFh7dq13HvvvU49R+fOnQkLC+PUqVP8+OOPDB48mNWrVwMwcuRI\njh49yuHDh1m+fDmzZs0qsHV9rcw7d+6kVq1adm4fAC8vLwYPHsyQIUMcFQNAvXr1iIuLc0p+R8TH\nxzN9+nTef/99p1rKb7/9Nh9//DEeHh5Fps3JybH7jc+ePUtQUBC1atWif//+pKSkFJhXRPjuu+9Y\ntmwZBw8eZN++fabfvygKcivNnDmTsLAwfvnlF5KSknj33Xcd5p8zZw7ffvstZ8+eJSMjw3QfRkdH\nk5iYyPHjx7lw4QKTJk3C09MTKPzbAKOX++KLL3L58mV69erF4MGD6dy5M0lJSWzbts2p59LcfLQh\nKEGSk5Px9fW1C/Px8SEpKclh+ubNm9OjRw/uvvtuvLy8mD9/PuPGjcuXLjMzk65du9KzZ0/q1KkD\ngNVqZdKkSbz00kt4eHjQtWtXu/+weRkxYgQAUVFRRT7DsWPH+PXXX/nkk09wd3enUaNGvPrqq8yY\nMQOAefPmMXjwYCpWrEhISAj9+vVzqFgdyXzp0iV8fHzypVVK8X//938cPXq0wEFhq9XKpUuXipS/\nIPr27cuoUaPw9vYu0i//73//GxHhmWeeyRf30EMPcerUKX744QfTeB86dMhU9rkG6/Tp06xatYrf\nf/+d/v37F1iXUoq33nqLkJAQ/P39GTJkSJHjSnlxxqgVVG9UVBS1a9fGw8ODTp06sX37dgDc3d1J\nSEhg//79KKVo0qQJPj4+RX4bAH/+8595+umnAfDw8Mjbu9eUYbQhKEGsViuJiYl2YZcvX3ao/AAm\nTJjAypUrOX78OOnp6QwbNoxHH32U1NRUM01OTg6RkZF4eHgwYcIEM3zr1q307t2bdevWkZmZyZo1\na+jVq1e+VvOECROYNWsWixYtws3NrchnOHnyJAEBAXh7e5thYWFhnDx50ozPO3havXr1fGUUJLO/\nv3+BRtHd3Z3333+f999/36GSTkpKMn3w1/Lkk0+aA7OOlGhMTAzJycm8+OKLAIUqpytXrjBgwAA+\n//xzh/GVKlViwYIFfPbZZwQFBbF06VL+8pe/mO8hMDCQunXrAsaA7ZgxY5g/f77DsnLJ+z7zvuvS\nJigoyPzb09OT5ORkACIjI2nbti2dO3cmJCSEgQMHkpWVVeC3ceLECfPe0fegKftoQ1CC1KlTh6ys\nLA4cOGCGxcXFFeiSWbJkCV26dKFatWpYLBZ69OjBxYsX2bNnD2AorF69enHu3Dnmz5+Pi8vV9Qwr\nV67kwQcf5L777gOgadOmPPDAA6xYscJMM23aNMaMGcPKlSupVq2aU89QrVo1Lly4YCoFMKYehoSE\nABAcHGw3EHrtoGhhMjds2JDDhw/nm6aaq5R79uzJpUuXHCrOPXv20LhxY4cyL168mKSkJJKSkujS\npUu++FWrVvHbb78RHBxMcHAwc+fO5Z///CfPPfdcvrT79+8nPj6ehx9+mODgYDp27MipU6cIDg7m\n6NGjADzyyCNs2bKFhIQEZsyYwR9//EHz5s0dygYUOS03t9zcv3N/K29vbzu30unTp/PlLahncyOz\ng1xdXRk2bBi7du3i119/5ZdffmHGjBmEhIQ4/DbyKv9r673WDagpm+hfqQTx9vbm+eefZ9iwYaSk\npLB+/XpiYmIKnD7XsGFD5s6dy9mzZ8nJyWHmzJlkZWWZYwxvvPEGf/zxBz///DMVKlSwy9uoUSPW\nrVtn9gC2bdvGunXraNSoEQCzZ89myJAhLFu2jPDwcKefITQ0lD//+c+89957pKens2PHDqZNm0a3\nbt0A6NSpEx9//DGXLl3ixIkTTJgwwe4/f2EyV69endq1a7N582YzLG/L3NXVlZEjR/LJJ5/kk2vt\n2rUFjp8UxYcffsj+/fuJi4tj+/btPP300/Tu3Zvp06fnS9ugQQOOHz9OXFwccXFxTJkyhcDAQOLi\n4kyFt23bNjIzM0lMTOTdd98lLCyMxx83phjHxsYSHx+PiHDs2DEGDhzIs88+W6BsIsLEiRM5ceIE\nFy5c4KOPPqJz587A1fGluLg40tLSTBdf3rwF9WwCAwM5ePBgoe+loLyrV69m586dZGdn4+Pjg5ub\nGy4uLlSvXr3Qb6MgOY4cOaLdQ2Wd4ows3+yL22zWkIjIhQsX5NlnnxVvb2+pUaOGzJkzx4yLj48X\nq9Uqx44dExGRK1euSK9evSQwMFB8fX3l/vvvl6VLl4qIyJEjR0QpZc78yL2+++47s7wxY8ZIrVq1\nxGq1Sq1atWTcuHFmXM2aNcXd3d0u7xtvvOFQ5sOHD4vFYjFnlBw/flyeeuopCQgIkLvuuksmTZpk\npr1y5YpERkaKn5+f3HPPPTJq1Ci56667nJZ54sSJdnL07NlT3n//ffM+JydH7r33XrFYLGbYli1b\n5P777y/Gr1A419a5du1asVqtDtOuXr1aQkND7cK6dOkiFStWlIoVK0rnzp3l3LlzZty4ceMkJCRE\nvLy8JDQ0VPr16yfJyckFyhIeHi6jR4+We+65R/z8/KRnz56Smppqxn/00UdSuXJlCQsLk1mzZonF\nYjFnDeV9jmvlXLhwoYSFhYmfn5989tln+X7jiIgIc6aTiMi3334rDz/8sIiIzJkzR+6++27x9vaW\nwMBA6devn1PfxogRIyQyMtLu+RISEqRly5bi7+9for9hWdYBZQGKOWtISRm21LYphI7CdQujjPDV\nV18xd+5cu5kjhZGRkUGTJk1YtWqVuaisKF544QVeffVVnnjiiRsRVXMHoXVA4djej9P+QW0INMXi\n9OnTHDx4kIceeoj9+/fz1FNP8fbbb9O3b99bLZqmHKF1QOEU1xDcMSuLNTeHjIwMXn/9dQ4fPoyf\nnx9dunThzTffvNViaTTllkFRUWxbvJjkCxeonpPD9UwT0D0CjUZz21HedcCgqCiWfv897mlpXAZe\nBtyA+4C2gIJi9QhKfdaQUmqaUuqMUmpnnrARSqnjSqlttks7fzUajcYJBkVFse7f/6ZJWhpPAw8D\nB4HTwGLgeszjzXANTQe+BGbkCRNgnIjkX0ar0Wg0mnzkuoDOnzvH0zk5HAL+C4QBB4C6tnTOTduw\np0hDoJSqDzwChGMo8CPAOhFxvIHONYjIOqVUuKOinRVSo9Foyiu5biBJS+N5DKW9D0gDqgKBtr9d\ngCeAWtdRR4GuIaVUpFJqC/ApEAQcwjACwcCnSqn/KqUKXklSNG8rpeKUUlOVUo73DtBoNJpyyqCo\nKJp4evJ7dDRN0tJ4AUMJnwFSgUYYyr8q8CHQEdgMvHIddRXWI/AHHhMRh5vDKKV8gZ7XUSfAV8AH\ntr8/BD4DejlKmHc1ZUREBBEREddZpUaj0ZR9cnsAldPTaSLC88By4DegAnA3cC9QG+iL4R7qD2wA\nMgD3KlXg3Lli1XlTZg3ZXEMxItKgmHF61pBGo8nHnagD8hqA0DwG4CjQG/gZeByoj+EOWgasALYC\nGYGBRDzxBFvWr2fD3r24urqW/XUESqlgETllu30O2FlYeo1Go7lT+cuf/kRqfDxeWVl2PYCpGAZg\nNXAXMBrDKCzC6B1cAU5bLIQ/8gg/rFiBxWIxDpm5jo3+Sr1HoJSaA7QCKmO4t4YDEUBjjMHnw8D/\niUi+08x1j0Cj0TjidtcBedcBWICngPsxpn/m9gB2YawPqAisBazAMNv9SaUIa9WKkPBwxk+dmk/5\n6y0mNBrNHc/tqgNyp4C6JiURmJLCXRiLwCZhTMtsB5wDOgApGO6gmsA/gDrAvnvuITU9nQcefpjx\nU6cWeMhSiRsCpdQ7GGsBEoEpNrkHiYjjk8ZLEG0INBqNI25HHfCXP/2JCidO8EBqKs0xWv/xGAag\nHkaPoCGwB5gPPASM4aoBSMvIYP0ff5jKv7AzJ0rDEOwQkYZKqbbA68D7wEwRaeJsJdeLNgQajcYR\nt4sOyLsPUE5mJkMwBnjBmPN/2PZvNWAhsBt4ABgL/In8BsBZ/39pbDqXW1h7DAPwvxs5/Uij0Wju\nZPIqf6+sLB4WwQ1jUPQb4C0Mxdsco7X/E3ASqATEAWfc3PBv0YIdx4+zfseOYhmA68UZQ/C7UmoZ\nxoK192zrBwo/e0+j0WjKIbnunxapqbgBTYAlGLNi9gGjMFr6vwETMNYDLMIYAL7i6srBypWp8eST\nzJsyBbh5R306YwhewXiegyJyRSlVCYgqXbE0Go3m9iG3F5Bx8SLvZGSwAkP5r8JYKVsVY3fQMxgK\ntSvGArAjHh74P/ggJ44do8Yjj7Bt8mQsFssNnTl9PRRoCJRS93N1IzsBammXkEaj0Vwl7yygFikp\nNMNw/7wDeAINgCQM988ftjz3AAuAy/XrE968udn6L2oAuDQpcLBYKRWLYQA8MQa0d9iiGgK/ichD\npS7cdQ4Wi8gNv9CSKEOj0ZQOt3qwOK8BeCAlhebAUgwl/yhQHVhvuy5inBEwGXBxc6OqxcL6gAC2\nHjtWaq3/4g4WF+iAEpEIEWmNMY5xn4jcLyL3Y7iJTt64qKWDiPBqn1dv6CMpiTI0Gs2dw6CoKNoG\nBdHDz48W7u78Hh1NizNneDslhXQgE/gIY0bNFSASY9+fbcBxNzcWeXhgad2aal274vbyy2w9dgwX\nF5cy09h0ZoygroiYW0DYZg3VK0WZboj5MfOZt2se7X5pR8cOHW9ZGRqN5vbnWtfPA1z1l+8GAoAR\nGHP/twNzbXGNuer+adisGUop5k6ZYir+smIAcnFmHcH3QDIwC2Mq6cuAVUS6lLpwxXQNiQgPdXqI\nzfU388CuB9g4d2OxX3hJlKHRaEqX0nYNOXL9LMFoOY8BjgFVgE0YhiHGli/XBRRcoYKd+ydX5ptF\nibmG8hCFYfz6Yex6upsyOmtofsx8dvrsBAU7rTv56ZefbkkZGo3m9mRQVBTDW7XizJYttLS5fi4A\nWzCU30ggATiPMSPoZwwj0BbbhnA2F9C17p+y3pi8Y/YaytuSN05uptgt+pIoo6wSERFBZGQkvXo5\nPPahRHnvvfcICgqiX79+TqWPiYlh9uzZfP/996Us2c3n448/5tChQ0yePPlWi4KPjw87d+4kPDz8\nVotyw5RGj2BQVBRnNm/m+b17eSonh/4Ye/8/j7Hh21kMt8h5YBzQ0dub3leuMBmo5uHB6Yceonp4\nOONsLqBbqTNKvEeglGqplFqulNqvlDpsuw7dmJglT96WPHBdLfqSKOPChQs899xzWK1WwsPDmTNn\nToFp09PT+etf/0pISAgBAQH06dOHrKwsuzTff/899erVw2q1Urt2bdavX2/GLViwgPr16+Pr60v9\n+vVZuHBhgXWV1IcZHR1N06ZNqVixIqGhoQwcOJDs7Gwz/ty5c8ycOZPXX38dgNjYWCwWC3369LEr\np2XLlkRHRwPQoUMHdu3axc6d178b+dixY2nQoAG+vr7UqlWLTz/9tMC0u3fvpmnTpgQEBODn50eL\nFi3s3ivAwIEDqVy5MpUrV2bQoEF2z9elSxdCQkLw8/OjZcuWbNmypcC63nvvvVtiBCIiIpg6dapd\nWFJS0m1hBI4cOYLFYiEn5+asW80dCN45dy7P7NnDRlu9o4Bnubpl8j8xpk8eBfp5etL89ddZarVi\nad0a1y5dmLtihbkT6O3WcHTGNTQVwwC2BJrZrualKdT1sGj5IppmN6XV4Vbm1TSnKb8s++WmltGn\nTx88PDw4e/Yss2fP5o033mD37t0O044ePZqtW7eya9cu9u3bx9atWxk1apQZv3z5cgYNGkR0dDTJ\nycmsW7eOWrWME0nPnj1L165dGTduHImJiYwdO5aXX36Z8+fPOy3r9ZCamsrnn39OQkICmzdvZuXK\nlXZK99tvv6V9+/ZUqFDBDPP29mbWrFnEx8ebYdcapi5duvDNN9/ckGwzZ87k0qVLLFmyhAkTJvDD\nDz84TBcSEsK8efNISEjg4sWLdO7cmRdeeMGMnzRpEgsXLmTHjh3s2LGDmJgYJk2aBEBycjIPPPAA\nW7du5eLFi/To0YP27dtz5cqVG5K9pBARcnJybjtFlEvehlBpjwHkzgL639y5tDhzhsEpKQRiuH9O\nAV7AAAwF+Cj2rh+Xzp0ZOGYMqlOn29oAmIhIoRewuag0pXUZ4uWnoPBbTXJysri7u8v+/fvNsO7d\nu8ugQYMcpm/atKnMmzfPvP/uu+8kNDTUvH/ooYdk2rRpDvNu2LBBqlatahdWpUoV2bRpk8P0ERER\nMnXqVBERycnJkQ8//FBq1KghVatWle7du8vly5fNtNHR0RIWFiaVKlUy061YscJhuePGjZMOHTqY\n948++qjMnj3bvF+9erVUr15d+vbtK1FRUWZ4y5YtJTo62u55atas6bCO66Fv377y9ttvF5kuMzNT\nJkyYII0bNzbDHnroIZk8ebJ5P23aNHnwwQcLLMPX11e2bt3qMG748OHSrVs3ERE5fPiwKKXM91u5\ncmX56KOPzLSbN2+W+++/X3x9fSUwMFD69+9vxm3cuFEeeugh8fPzk0aNGklsbKwZ16pVKxkyZIi0\naNFCPD09pWvXruLi4iIeHh5itVrN96CUkoMHD4qIyKVLlyQyMlKqVKkiNWrUkFGjRklOTo6IiEyf\nPl1atGgh7777rvj7+0vNmjVl8eLFRb7L6dOnS61atcTHx0dq1qxpfgeFfW+572Tq1KkSFhYmjzzy\niISFhYlSSqxWq1itVoff9PXqgIE9e8qwRx6RnvfcIx+ALAXJATkIcgFkL8hKkHds4e2DgqSTh4f0\n8fCQjq1bS7+oKMnOzjbfVe6/ZQ3b+3Fe1xaZwDgYZyzGrqj35V7FqeR6r9vNEGzdulW8vLzswj77\n7DM7RZmXpk2byty5c837WbNmiVJKEhMTJSsrS9zd3WX06NFSu3ZtqV69urz11luSmpoqIobRqVat\nmsTExEhWVpb8+9//ltDQUElJSXFYV15DMHXqVKldu7YcPnxYkpOT5fnnn5fIyEgREdm1a5dYrVbZ\nsGGDZGRkyLvvvitubm6ycuVKh+U+88wz8t5775n3VapUkd9++828zzUEp0+fFl9fX9m7d6+I5DcE\nCQkJopSSpKQkxy+3GOTk5Ejjxo1l0qRJhaarWLGiuLq6SlhYmJ3xrlixomzZssW8/+2338THx8dh\nGdu2bRMPDw9JTEx0GD9ixIh8hqB3796SlpYmcXFxUqFCBfnjjz9EROTBBx+UWbNmiYjIlStXTAV4\n/PhxqVSpkqmMly9fLpUqVZLz58+LiGEIatSoIbt375bs7GzJzMy0+71zyWsIIiMj5dlnn5Xk5GQ5\ncuSI1KlTx0w/ffp0cXNzkylTpkhOTo589dVXUq1atULfZXJysvj6+sq+fftEROT06dOya9cuESn8\ne8t9Jz169JCUlBRJS0uTI0eOiFJKsrOzC6yvODogV/m3CQyUdl5essCm5JeCXLb9/TvIxyCLbUbg\nPyD/p5T8Z+5c6RcVlc8AlHVKwxDEYpyWZncVp5LrvW43Q7B27VoJCgqyC/vmm28kIiLCYfqhQ4dK\nixYt5Ny5c3Lq1Clp3ry5WCwWOX36tJw4cUKUUtKsWTM5ffq0nD9/Xlq0aCFDhgwx88fExIiXl5e4\nurqKl5eX/Oc//ylQtryK4dFHH5WvvvrKjNu7d6+4ublJVlaWjBw5Ul5++WUzLiUlRdzd3R0agqlT\np0poaKgkJCSYYW5ubqayF7lqCEREBgwYIC+99JKI5DcEGRkZopSSY8eOFfgMzjJs2DBp3LixZGRk\nFJn2ypWePbPNAAAgAElEQVQrMmDAAGnSpIkZ5uLiYvcM+/btE9vEBTsuX74s9957r4wePbrA8h31\nCE6cOGHGN2/eXH744QcREXnkkUdk+PDhcu7cObsyRo8ebSrOXNq2bWu+v4iICBk+fLhdfEREhEyZ\nMsUuLNcQ5DYy9uzZY8ZNmjTJ/E6nT58utWvXNuOuXLkiSik5c+ZMgc+ZnJwsfn5+Mn/+/HyNkYK+\nt+zsbPOdHD582IzPDSsJQzCwZ0/pWa+e/GyxyGKQzSBxNuV/BORrkCW2++4g/fIYgRdat5acnBzz\nup0oriEocoxAbCuMr71KwCt1x2G1WklMTLQLu3z5Mj4+Pg7TDxkyhCZNmtC4cWNatmzJc889h6ur\nK4GBgXh6egLw9ttvExgYSKVKlejfvz//+c9/ANi6dSu9e/dm3bp1ZGZmsmbNGnr16kVcXFyRcp46\ndYoaNWqY92FhYWRlZXHmzBlOnTpF9erVzThPT08qVaqUr4wFCxYwePBgFi9eTEBAgBnu7+9PUlKS\nw3oHDBjA0qVL2bFjR7643Dx+fn754mbPno2Pjw8+Pj60b9++0GebMGECs2bNYtGiRbi5uRWaFsDL\ny4vRo0ezb98+U65rf8fLly9jtVrt8qWmptKhQwf+/Oc/M3DgwCLryUtQUJBd/cnJyQBMnTqVffv2\nUa9ePZo3b86iRYsAiI+PZ968efj7+5vXhg0bOH36tFlOaGhovnoK8lefP3+ezMzMfN/AiRMnCpQR\nMOV0hLe3Nz/88ANff/011apV46mnnmLv3r1A4d9bYfJfL9f6/zvu2UNmTg5tgVDABVgJhGFs/LbY\nli+tdm1OeXiwyMODhNat+WHFCqcOgbkTcGbWkJ9SarxS6nfb9ZlSquLNEO52o06dOmRlZXHgwAEz\nLC4ujnvvvddheg8PD7788kuOHz/OgQMHCAgIoGnTpoChUPMq5GtZuXIlDz74IPfddx8ATZs25YEH\nHmDFihUF5smlWrVqHDlyxLw/evQorq6uBAUFERwczPHjx8241NRUEhIS7PIvWbKE3r1788svv1C/\nfn27uIYNG5oK4FoqVarEO++8w9ChQwH7wcA9e/YQHh6eT+ECdO3alaSkJJKSkkzl6Ihp06YxZswY\nVq5cSbVq1Qp+AdeQnZ1NTk6OqfDq16/P9u3bzfhrf8P09HSeffZZwsLCzEHkgiiOAqlduzbfffcd\n586dY+DAgbzwwgukpKQQFhZGZGQkFy9eNK+kpCQGDBhQYD2F1Vu5cmXc3NzyfQOFfW/O0KZNG5Yt\nW8bp06epW7cur732GlDw9xYYGOhQ3utVuteuAXjt8mViUlJojeHX/i/Gfv+HMbZ+BrgQFMQpDw/6\nenoS9fHHBHfpgmuXLvywfPlN2wK6LODMk07DOKbyRaATxmZ600tTqNsVb29vnn/+eYYNG0ZKSgrr\n168nJiaGyMhIh+lPnjzJyZMnERE2bdrEqFGjGDlypBkfFRXFl19+yblz57h48SLjx4+nQ4cOADRq\n1Ih169aZPYBt27axbt06GjVqVKScXbp0Yfz48Rw5coTk5GQGDx5M586dsVgsdOzYkZiYGDZu3EhG\nRgYjRoywU9irVq2ia9eu/PTTT6bRyku7du1Ys2ZNgXX379+fjRs3smfPHrvwNWvW0K5duyJlL4jZ\ns2czZMgQli1bVuQUyRUrVrB9+3ays7NJTEykf//+3H333dSuXRuA7t27M27cOE6ePMmJEycYN24c\nPXv2BCAzM5MXXngBLy8vvv322yLlyvvuimLWrFmcO3cOgIoVK6KUwsXFhW7duhETE8OyZcvIzs4m\nLS2N2NhYuxb8tfUEBgZy8OBBh/W4uLjQqVMnhgwZQnJyMvHx8YwfP55u3bo5Leu1nD17loULF3Ll\nyhXc3Nzw9vbGxcUFKPx7c0SVKlWwWCwFyp9LruLP2/q/f+1apu3eTReMnT/BWAy2HZgDtAG+qVCB\nNsCbFgt9vviC4C5dcOncmbYdOzJ+6lSHh8Hf8RTlOwLinAkrjYvbbIxAROTChQvy7LPPire3t9So\nUUPmzJljxsXHx4vVajX94GvXrpXw8HDx8vKSunXrynfffWdXVmZmprz55pvi5+cnQUFB0q9fP0lP\nTzfjx4wZI7Vq1RKr1Sq1atWScePGFSjXtbOGPvjgAwkNDZUqVapIZGSkXLp0yUz77bff2s0aCgkJ\nkfXr14uISOvWrcXNzc2c0WG1WqVdu3Zm3vPnz0v16tXNQe3Vq1fbzYTKldtisdiNETRo0EB27Njh\n3Et2QM2aNcXd3d1OrjfeeMOMr1+/vvl+582bJ3Xr1hWr1SpBQUHSuXNnOXr0qF15AwYMkICAAAkI\nCJCBAwea4bGxsaKUEm9vb7u6ct/PtYwYMcJuYNRisdj5vvP+Lt26dZOqVauK1WqVe++9VxYuXGim\n27x5s7Rq1UoCAgKkSpUq8tRTT5nfkaOB4Y0bN0qdOnXE399f+vXrJyL2g8UXL16Ubt26SZUqVSQ0\nNFQ+/PBD0w/+7bffysMPP2xXnsViMfM64tSpU9KqVSupWLGi+Pn5SevWrc0xiMK+N0fvRMQY56lS\npYr4+fnJ5s2b89UH2Pn+V9n8/Bdt/24DGZ3H/99DKfkPyOsWi/yjf3/pZ7XKC48+etuOARQFxRwj\ncGavoU3A30Vkne2+JTBWyvA21JqSIzk5GX9/fw4cOGDn5y2MIUOGULVqVb2yWFNqKKVYiHH4+1tA\nKsZ++RswNkZri7EPjh8wHuhcuzZBp09zsnlzfli+nL+99hqf2Q6BuRMpjcPrGwMzME5TA2N77R4i\nUvSo5A2iDcGtISYmhsceewwR4W9/+xv//e9/+f3332+1WBqNiVKKE4AvxgZwJ4B0oB3wilJME6Fz\n7dpw/DhVlaL9jBksXbzYVP4id/Z5IyVuCPIUXBFARC5fp2zFRhuCW8Nrr73Gjz/+iIjQrFkz/vWv\nf/GnP/3pVoulKQNYrVaHCnTJkiW0aNHipsmhlGILxr4/y4DPgGcrVGBhejqda9cm+MwZnpg2jSW2\nWXbjbdtt3MnKPy+l0SP4GPhERC7Z7v2Bv4nI0BuS1BnhtCHQaDQOUEqRg9H67yTCzxYLYe+8w9nJ\nk2k7bRpLFy9mnO0IyNz05YnSMATbRaTxNWHbRKTJdcroNNoQaDQaR+QaAke+/3F5zgAur5SGIdgB\nNBeRNNu9J8aZxfULzVgCaEOg0WgcoZSin48PT9ha/+XF9+8sxTUEzhxVORtYqZSahrFBcxTG4LFG\no9HcMtSLL9K2Y0faduxYZo+AvF1warBYKfUk8JjtdrmILC1Vqa7Wq3sEGo0mH0qp23q77dKmNHoE\nYJzNnCUiy5VSXkopHxFxvKGMRqPR3AS0ESg5nNlrqDcwD/jaFlQdWFCaQmk0Go3m5uHMsro+GKeT\nJQKIyD6gamkKpdFoNJqbhzOGIF1E0nNvlFKugHbQazQazR2CM4ZgjVJqCOCllHocw00UU7piaTQa\njeZm4cw6AhegF8YOrgBLgSkOp/OUMHrWkEajcYTWAYVTansN2QoPAEKLs+Gcbf1Be+CsiDTIU84P\nQA3gCNApdwuLa/JqQ6DRaPKhdUDhFNcQODNraI1SytemvH8HJiulxhdDpunAE9eEDcJYj1AH49S4\nQcUoT6PRaDQliDNjBBVFJBF4HpghIs2Bvzhbge0cg4vXBD8NRNv+jgaedbY8jUaj0ZQszhgCF6VU\nMMYxlblHfd5onyxQRHJPrj4DBBaWWKPRaDSlhzOG4AOMAeKDIrJFKXUXsL+kBMg9Vq2kytNoNBpN\n8ShyiwkRmYcxZTT3/iDQ8QbrPaOUChKR07bextmCEo4YMcL8OyIigoiIiBusWqPRaO4sYmNjiY2N\nve78zkwfDQW+wFhdDLAW6Ccix52uRKlwICbPrKExQIKIfKKUGgT4iUi+AePizBoaFBVFhUOH7PYf\nERHSa9Vi9PTpTslZEmVoNJrSR88aKpzS2HRuOsZW1J1s911tYY87KdAcoBVQWSl1DBgGjAbmKqV6\nYZs+6qzABRHRvj2qRw/apqSYYUu8vFB9+97UMjQajeZ2w5keQZyINCoqrDQoTo9AROj/0EOM27wZ\nhTHo0P+BBxi3caPTuxSWRBkajab00T2CwinxdQRAglIqUinlopRyVUp1wzgzukyhlKLtu++yzMsL\ngKVeXjzx978XS4GXRBkajUZzu+GMIYjCcN2cBk4BL9rCyhxtO3ZkSYMGCLC0QQPaPP/8LSmjLBIR\nEcHUqVNvSl3vvfcen3/+udPpY2Ji6Ny5cylKpNFoCqNQQ2DbafQfItJBRKrYrmdE5OhNkq9Y5Lbo\n+/v4XHdL/kbLmDBhAk2bNsXDw4OoqMLt5euvv46Pj495eXh44Ovrmy/d/v378fDwIDIy0gzbvXs3\nTZs2JSAgAD8/P1q0aMH69esLfa6S6NlER0fTtGlTKlasSGhoKAMHDiQ7O9uMP3fuHDNnzuT1118H\njNkMFouFPn362JXTsmVLoqONNYUdOnRg165d7Ny587rlGjt2LA0aNMDX15datWrx6aefFph206ZN\nPP7441SqVImqVavSqVMnTp8+bcavXr2a1q1b4+fnR82aNe3yHj161O438/HxwWKxMH58cRbblzyx\nsbGEhobeUhk0ty+FGgIRyQJqKKUq3CR5bpi2HTvCiy/eUEv+RsoICQnh/fff55VXXiky7ddff01S\nUpJ5denShU6d8o+b9+nTh+bNm9sp8pCQEObNm0dCQgIXL16kc+fOvPDCC8WWt7ikpqby+eefk5CQ\nwObNm1m5cqWd0v32229p3749FSpc/WS8vb2ZNWsW8fHxZti1hqlLly588803NyTbzJkzuXTpEkuW\nLGHChAn88MMPDtNdunSJ119/nfj4eOLj4/Hx8bEz2larlVdffZWxY8fmyxsWFmb3m+3cuROLxULH\njjc6o/r6ycrKumV1a+4MnHENHQbWK6XeV0r9zXb1L23BrhelFOOmTLmh1u+NlPHcc8/xzDPPUKlS\npWLlu3LlCvPnz6dHjx524d9//z3+/v489thjdoNjFStWpGbNmiilyM7OxmKxEBwc7FRdIsKoUaMI\nDw8nMDCQHj16kJiYaMbPmDGDGjVqULlyZTPdypUrAaMX06JFC1xdXalWrRpdu3Zlw4YNZt4lS5bQ\nqlUru/r8/Pzo2bMnI0eOLFCmiIgIFi1aVGB8Ufz973+ncePGWCwW6tSpwzPPPGMnV16eeOIJOnbs\niNVqxdPTkz59+tilbdasGV27ds3XG3BEdHQ0rVq1IiwszGF8amoqPXv2JCAggPr16zN27Fi7lvsn\nn3xC9erV8fX1pW7duqxatQqA9PR03nnnHUJCQggJCeGvf/0rGRkZgNH6r169OmPGjCE4OJiXX36Z\ndu3acfLkSXx8fPD19bXr4Wg0ReGMITiIsbWEBbDaLp/SFOpGKQkXyI2WUdwZDfPnz6dq1ao8/PDD\nZlhiYiLDhw9n/PjxBZbn5+eHp6cnY8aM4ccff3SqrunTpxMdHU1sbCyHDh0iOTmZt956CzBcTn36\n9GHOnDmcOnWKy5cvc/LkyQLfx5o1a7j33nvN+507d3L33XfnSzd48GDmz5/Pvn37HJZTt25djhw5\nQnJyslPPUBgiwtq1a+3kKozipL22nhkzZuQz3nkZOXIkhw8f5tChQyxdupTo6GjzXe7du5eJEyfy\n22+/kZiYyLJlywgPDwfgo48+YsuWLcTFxREXF8eWLVsYNWqUWe6ZM2e4ePEiR48eZcaMGSxevJhq\n1aqRlJREYmIiQUFBxX4eTTlGRMrsZYiXn4LCyxJDhw6Vnj17Op3+0UcflZEjR9qF9e3bV8aMGSMi\nIiNGjJBu3bo5zHvlyhUZMGCANGnSRHJychymiYiIkKlTp5p1ffXVV2bc3r17xc3NTbKysmTkyJHy\n8ssvm3EpKSni7u4uK1euzFfm1KlTJTQ0VBISEswwNzc32bt3r3m/evVqqV69uoiIDBgwQF566SUR\nEWnZsqVER0eb6TIyMkQpJceOHXMof3EYNmyYNG7cWDIyMopMGxcXJwEBAbJ+/fp8ccuXL5fw8PAC\n865du1asVqtcuXKlwDS1atWSpUuXmvfffPON+T72798vVatWlRUrVuST9a677pLFixeb90uXLjVl\nWb16tbi7u0t6eroZn/c9lwduBx1wK7G9H6d1rTPbUC9XSvnluQ9QSi0tNct0hyDF6BEcPXqUNWvW\n0L17dzNs+/btrFy5knfeeafI8ry8vBg9ejT79u1zasD11KlT1KhRw7wPCwsjKyuLM2fOcOrUKapX\nr27GeXp6OnRzLViwgMGDB7N48WICAgLMcH9/f5KSkhzWO2DAAJYuXcqOHTvyxeXm8fPzyxc3e/Zs\nc2C2ffv2hT7bhAkTmDVrFosWLcLNza3QtAcOHKBdu3Z88cUXtGjRotC0joiOjuaFF17Ayzbd2BEn\nT560cwXldSHVrl2bf/7zn4wYMYLAwEC6dOnCqVOnzHzX/kYnT54076tUqYK7u3uxZdZoHOGMa6iK\n5Dk0RkQuoHcLLZLiuJZmzpxJy5YtTbcAGC6XI0eOEBYWRnBwMJ999hnz58+nadOmDsvIzs4mJyen\nUKWUS7Vq1Thy5Ih5f/ToUVxdXQkKCiI4OJjjx6/uHpKamkpCQoJd/iVLltC7d29++eUX6tevbxfX\nsGFD9u7d67DeSpUq8c477zB06FDA3rjt2bOH8PBwrFZrvnxdu3Y1B2cLG0eYNm0aY8aMYeXKlVSr\nVq3gFwDEx8fz+OOPM2zYMLp27VpoWkekpqby448/FuoWAggODubo0auT7PL+DcYg+bp164iPj0cp\nxcCBAwHHv1HeZ7r2+9JrXTQ3gjOGIFspZTZNbPsG5ZSWQLc72dnZpKWlkZWVRXZ2Nunp6XbTKx0x\nY8YMevbsaRfWu3dvDh06RFxcHNu3b+f111+nffv2LF1qdMZWrFjB9u3byc7OJjExkf79+3P33XdT\nu3btImXs0qUL48ePN33ygwcPpnPnzubsl5iYGDZu3EhGRgYjRoywU9irVq2ia9eu/PTTTw6NUrt2\n7VizZk2Bdffv35+NGzeyZ88eu/A1a9bQrl27ImUviNmzZzNkyBA7P3tBnDhxgkcffZS33nqL3r17\n54sXEdLS0sjMzDT2mkpPNwdqc/n3v/9NQEBAkZsgdurUiY8//phLly5x/PhxvvzyS1Np79u3j1Wr\nVpGenk6FChXw8PDAxcUFMH6jUaNGcf78ec6fP88HH3xgN334WgIDA0lISLAb9NdonKYo3xHG6WJH\ngVm26yjwRHH8T9d7cRuOEQwfPlyUUnZXru8/Pj5erFarnR/8119/FavVKsnJyYWWO2LECImMjDTv\n582bJ3Xr1hWr1SpBQUHSuXNnOXr0aIH5844R5OTkyAcffCChoaFSpUoViYyMlEuXLplpv/32WwkL\nC5NKlSrJhx9+KCEhIaYPvXXr1uLm5iZWq9W82rVrZ+Y9f/68VK9eXVJTU0XE8F2HhobayTJmzBix\nWCx2YwQNGjSQHTt2FPoOCqNmzZri7u5uJ9cbb7xhxtevX1++++47ETHepVLKLq2Pj4+ZdvXq1eZv\nZ7FYRCklrVu3tquvbdu2MmzYsCLlSklJke7du4ufn5/Ur19fxo4da/ryd+zYIc2bNxcfHx8JCAiQ\nDh06yKlTp0REJC0tTfr27SvBwcESHBws/fr1M8cEHL1TEZFXXnlFKlWqJP7+/mY5dyplWQeUBSjm\nGIFTZxYrpaoAD2Jsv7NJRG7KFhP6zOJbT3JyMv7+/hw4cMDOZ10YQ4YMoWrVqvTr18+p9DExMcye\nPZvvv//+RkS9LYiNjSUyMpJjx47dalFua7QOKJwSO7xeKVVPRPYope7HMAC5heY21bfeqLBFCqcN\nwS0hJibGXLfwt7/9jf/+97/8/vvvt1qsOwJtCEoGrQMKpyS3oe4PvAZ8huMTxFoXUzbNbcLPP/9M\n9+7dERGaNWtWLlrqNxM9sKspazjlGrpV6B6BRqNxhNYBhVPiB9PYNp5rD4QDLhguIhGRcdcrpEaj\n0WhKFhEhJycHi8WZyaD2OJMjBugBBGBsLVHmt5jQaDSa8kJOTg7Z2dlEvR6FX3U/ol4v/ikBzpxQ\ntkNEGl6vkDeCdg1pNBpHlEcdkJOTY/fcuRtO1r2vLslpyZxLP0eOZw7KopA9UrKuIWCZUqqtiJSp\nbSX0gJtGo7nTyTvXv+59dWnxYAvWbVyHUoqWD7ZkwZIFXFaXwQ3jqgjiLbCnqJLtcaZH8DzGQjIL\nkHlVPsl/gkoJU1CPQKO5GQyKiqLCoUNmo8M9O5sGp0/T7Px5ggIDoU8f6N4dKlY084hcPfdan3et\nuRYRKfR7yG315/79ap9XWbdxHRW8KrD70m5Uuq1HUAFIw1D+AUAwEAbkauWPKPEewTiMxWT/ExG9\ntYSm3BDRvj2qRw/apqSYYaddXDg2ZAhBI0aAg//Q5gl3r7yiz7vW2JGTk8Nrb73GlIlT8rm28rb6\nWz7UEhFhyeolXOACmSoTrgABIK4CVYAQjNHaykAScAaIBy5xXRP7nTEER4Fd2ghoyhVZWbR1cWG/\nq6u5mlKAT5o2ZVwBRiCXth07snTx4jvmvGvNjSMi/OWZv/Bb4m88GfMkz7V/jtfees00AOs3raeC\nVwUOZBzg8LrD5KTlIC5itPD9gbswFL8HkIyh+P+HcZK8BaiO8ZGGcXXpbzFwxjUUDdQEFgO5O2/d\nlOmj2jWkuemcPQtTpsDXX0P16sQ1a8aZyZNpk5rKEi8v1IwZxlGmRVCUC0Bz55PXzTNv4Ty6DO5C\nzos5VJpTCVdcuex1meycbLJTsslxyTG28qyJofi9gCAMpX4aQ/kfBS5jzNk8CVQFsoBTGK4igFwv\n5e6Sdw0dtl3utkujubMQgU2bYOJEWLQIOnaEhQuhSRMaitB/82Ye37yZpQ0aMM7JVr42AuWPvI3W\nnJwcOzfPT2t+IqdpDhyEhMwEQ5N6A34YSr8ShmJPA84C54AdwEUM43AJo0tazfa3Ao5juImqXpVB\nobjL8y4OcKBYst+WK4s1mhIhJQXmzDEMQGIivPkmREWBv79dsiU//sjSV17hienTneoNaO58cnt8\nufpJRHi1z6vm/Za4Ley+tBsXi4vh5vEReAZDuVcAQgFPDEV/BTiEMRUnE8MI+NuufRhKP81WsTuG\nX6aKvTxurm7UcKvB/t/2AyW46VxZQBsCTUlw7eyfgNRUmp44QaPz5/F+/HFj9k+bNlDAikwRof+r\nrzJuyhTd0i/H5FX6r731GpMnTDaV/5HjR9h0fBPZOcYBUdnp2cZeDH4YLf9cH/5ZIAFIxHDzXMZQ\n7DVt8Re5agxcuOrqwYj3UB50jujM9C+nFyqrNgQazTUs+fFHVPfutE1NNcMOubpy/PPPeeTNN50q\nQ/v8yw95dU5uqz9vi//I8SP8nvQ7vR/pzcSYiWRlZ5ElWcZArT/GoG5VDAV/znZlAkeAdKAWV5W+\nH1db/Tnkb+0rcHOxb+07gzYEGk1eEhKQqVO5MGwYAenp5uwfPcdfk5dcQ587dz/3fsrEKbza51UO\nHzvMpuObyMrOIjsrG+kkuG9xJyMww2i1V8QY0E0EDnLVzXMGqGELB8gGUjAUfhqGq+c6W/2FURqb\nzlXF2I46PE96EZFXrktCjeZm8Ntvhu9/wQLU00+zb/hwEkeNom1KCku9vPQc/3JO3m0acuf3T54w\nmb888xc2HttIdk42rr6uBAwPYPavs8nwyIDaGDN2QgCBjD9lGAr+fxjKPQej9V8TY5qnB1AHI99y\nDAMRAMpTYfGyIAguyqXYrf3SwJlZQwuBtRiPkruWQDfTNWWPtDSYN88wAKdPwxtvwP79ULkyD4rQ\nf+FC2hRz9o/m9ufagV2AXm/2AmDKxCnm/H6/YX7EHohF/AT8ILN5JuPPjCenvW1qZyLGtM0wYCmG\nFkzGmObpbSv4JLCfq5ryFGA7wsutqhsB1gCevO/JG2rtlwbOGAJPERlY6pJoNNdLfLwx73/aNGjS\nBIYMgXbtwHYQPOgVv+WVvK39V/u8CsCTTzzJnI1zUFaF/zB/Yo/HIk8Ln//xOdJODKWeCVyGnAs5\nsM1WWDLQBKNlb7WFpWKs6M3AUP65bh6bb7+sKv5rcWZB2Shgo4gsujki2dWtxwg0jsnJgRUrjNb/\n+vXGnj9vvAF16hSYRc/+uXPJ2+rP2/p/7OnH+C3xN3NgV7yFQL9AjnoehXtBJSljk7Y0DIWeaLv+\ngtHqT+Lqwq6zGPv6HMde8SuwWCy4KJcyo/hLfLBYKZWMseQhA73pnOZWc+kSREcbBsDLy5j6+fLL\n4O1ddF707J87ibwDvLmt/rz/tm3Tls5DOyMdBbf/uZEZmGks3MrC0GQpwC4gApgPBGIo/GAMt89p\nDOWfO7jra4Qri8LV4lpmlL4j9KwhzW3PtfP+AaomJXF/cjIPnD0LTz5pGIA//7nQPX80dxbXtvZf\n7fOqOcCb2+qf9OskHm/xOL8c+wWskBmQaSjxBIw9ef7AaP23xVD+jW2F78Be4V+yhdta/G4ubnh6\neuLp4llmlX9eSswQKKXqicgepdR9juJFZOt1yug02hCUT5b8+GO+XT/TlOJYp0786Z//hKCgWyid\n5mbgyNWTq/hfe+s1nmj7BK+Me4WXHn6Jab9PQx4QVKJCfAXLOYuxd89ejH2Tc09SqY3Rys9t8e/g\nqqvHCuSAp5snvh6+3F37bmr51irzCr8gStIQTBaR15RSsTiYJSQi17HZafHQhqB8IsePs+zBB2lz\n4oQ57//d5s35dNMm7da5w7m2tZ+7bfP8mPlEjYvi2YefZe6hubj7u5NcOdlo3Wdh/Jvbos/BUPK5\nrf1c5X/Y9rcVSADlp1BKmb79213556XE1hGIyGu2fyNKQC6HKKWOYAzNZAOZItK8tOrSlHFEIDYW\nJmoW6YUAACAASURBVE5ErVpF3ebN2ZCQQMu0NJZ6edFmwABtBO4wCmr1P9H2CebtmofXcC/mnJpD\n4jeJLDuwjOSIZGYnzkYChcyUTEOx7wCeBjYAbYBlGFs2WzBa+rkDu6dsvn1vVzw9PPEMuz1cPDeL\nWzpGoJQ6DNwvIhcKiNc9gjudpCSYOdMY/AXD9x8ZiVit+qSvO5CCXD1TJk7hm/nf0O/7fngEeHC5\n2mWjeegC/vH+pHilkJ6UbrT+D2Mo/bw+/tyuo7LF25q4Kk1Rr3I9KleqfMe09p2hxFcW3wT0/+7y\nyO7d8K9/wXffwWOPGYagVStz8FeBnvd/G5N3dta1yn/KxCnM/Xku3x/5nvgR8ayRNcSMjuFiykWy\namaRkZphtOTTgNpwKe4S0kGMhVl3GWEcxL7Vn8fd42pxNQd27777znH3lCa3ukdwCGP/vWxgkohM\nviZe9wjuJLKyjH3+J06EPXvgtdegd2+oXt1hcj3v//bCkcIHw9//xT+/4NN5n/KPZf/gnkb3sPPS\nTrIt2bjGu5JVI4uwTWGcDT5L2h9pV108bcFuW/28rf3jgJcxuOvm5mYo/TvIx3+jlMY6AgvQFagp\nIh8opcKAIBHZcmOiglIqWEROKaWqYGxh8baIrMsTrw3BncDp0zB5MkyaBDVrGu6f558H96LPOdLz\n/ssu17b6c5X//Jj59PyiJ290f4M9yXtYfGAxbv5uuCW7keyZTNCOIC4HXCY1LdVw5/wJ1M8KuUfs\nXTy5e/S4AkfAs5In7m7uCKIVfxGUhmvoXxjj8I8CH2AstP4X0PS6JMyDiJyy/XtOKfVvoDmwLm+a\nESNGmH9HREQQERFxo9VqbgYisGGD0fpfsgQ6dTJO/2rUqFjFaCNQtiio1f/5vM+ZfXE2ByccZNOp\nTaS3TGdy3GR8UnzICcwhZGUIp2udhjA4c+QM0kDsWv1yjxjbNOdt7e+2tfbFk7tbaaVfGLGxscTG\nxl53fmd6BNtEpEnuv7awOBEp3v/o/OV6AS4ikqSU8sb4LEaKyLI8aXSP4HbjyhXD7z9xonEC2Jtv\nQs+e4Od3qyXTXAeOWv0TP5/Ip/M+5cPFH9Lw/oYcyjjElctXSHdLp8reKiT5JpFWLQ33X91RQYr0\nmulGi/9pye/qydPqzx3YrVK5CiKiFf8NUBo9gv9v78zjq6quPf5dIQlJIEyRKXDDEJBBQGaERKGt\nilafrdKPWusstlUKfbXP1/rEJ1VsxQEVFWpbsKIoDmiZKoJPERNQ5iECgkyZgBhCEjIPd78/9rlT\nxktIcm5y9/fzuZ87nnMXJPmtddZee60yEXF377LSOM46Pu8v3YGPrF+yUGCZtxMwtDAOH9aLv0uX\nQmIiPPMMXHllrVO/DIFJTcI/79l5bEnfwuLPFrOm7RqWPb2M0MJQyuLLyN2Xy5+v/TMP/fshiIPs\nb7O14CsoyyuDiXgifsET9R+3Uj2HrVSPMgu7duLPFcHtwM3AGOAN4GfAbKXUe01unLkiaHZqau+g\nlKK0f3+efr3KH2hlpU73vPoq7NoF990Hv/419OnTzFYbGkLV9RelFPfNuI9HnnyEzWmbeTPpTT5P\n/ZyI6AgS+iawf8t+Mrpl0P+L/pzqd4qiPkVEHoukd1pvDl9+2BPtD0S3YjYRv200+hWBUuotEdkB\n/Mh66SdKqQMNNdAQ2Ey57rpq7R3WRUUhs2Z5PpSdDYsX69bP3bvrxd+VKyEiwgaLDf5Qk+hPnzGd\nRQsWsfv0bpJSk3jv6/fY2mkrK19byVUXX8V3+77D2dPJsL3DuH/E/dxdcjcAx/KOoeJ0gFZcUcyR\nHkd8on35TuiQ2wE6gjqsF3YH9x1sxD+A8at8VEQ6o8cxhGK1mzC9hlonSin3Rq5qYx23bdPR/6pV\n8NOfagcw9oJrBgyNSE1VVt4Lu/ml+WxJ38LfP/07Kw+uJCwmjIEXDSQhLoENH23gSO8jjP9mPP91\n+39x98q76476ATaAVHgifdf3GcG3l6YoH30SuBs4itfagOk11Hrxbvq2PjKSnvfey/Cvv4YzZ3TP\n/3vvhZgYu800VMFb8F2VPal5qcz/13wWJS8idmAs2RXZjI0dy+Fth8nsmsmYA2PYtnwbK1av4K5/\n3VVd+AU4DCEqBOfFTpPmCVDWrt3EY48t5dChk5SWhlJRsarRF4tvAeKVUmUNN9PQkpg6bRpz587l\n6j17mFReTrujR2HOHLjmGp+pXwb7qCnyf2/Veyw/sRxZIhR0LCA5LZnyynLKMsso71VO+5T2fLvk\nW1b/ezV3Fd8FAgeiDrBi9Qqee/M5ii7R6UCfdA/AcVAViqF5Q+k6wET9duIt+IWFeejYXAHdgIvQ\nPTee4nwbNvhzRfAR8Gul1OmGGH4hmCuCZsbphPXr4ZVXKNu0ieSSEkLnz+fy3/zGbsuCkto207ki\n/xdfeJGtGVtJSk0iOS2Zzw5/RmVIJV3PduWZe54hMS6RXV/ucqd4oo5H8caNb/Dcm8/x9SVfuzdv\nDfhsAJkDMinqY60LmXRPQDFnzkKef34NBQVn0MMSOqMHJoRYzwvRMzQB5lr3jV8++mdgl4ikAKXW\na0opdYO/X2IIcM6ehddfh0WLIDoaZswg7N13WTVrFvNnzLDbuqCkapoHIPNcJsmpybz+xet8EvkJ\ny55ZxtheY0lwJDCa0SRlJlHsKKYwv5DotGjiL43n9rdud0f6RX2KeOS5R8gckOkJGAWO5R9jUNYg\nujq16DPACL+deIQ/Hy25cUAEWvS7ANHoYclR6MWab7nQtnH+HL0UeBpIwbNGYML01sCuXXrxd8UK\nuO46vQfgsstABAHT46eJqat9xvur3mf58eWEvh5KUeciklOTySvNI8GRQMq+FJzdnYzYN4IvZ+uN\n+BNvnkjxJcWAFvxnlz6L0+lkX/S+ukUfUJca0bcDV5rn+PECCguzKS93olQh0Bst/O3Rgj8EXY8b\nAwxGj1lzrdHFAKPRE3hiG2yLP6mhbUqpcQ3+hgvApIaagNJS+OAD7QDS03Xd//Tp0K2b3ZYFFVUj\n/uLyYrZlbiM5NZmk1CQ+OfgJlW0quSj3Ip664ykuj7ucQRcN4sPVH7oXdaOOR7H0pqUopdyvuYg6\nHsWEnAlUdqqsVjZqRN8+fKP9rkA/IAzdTrUjekjypWjhH4jut9EXXZvbBd3Zpz36KqEf0AY4gJ64\ncwI9nee/aYrU0Jci8hdgFZ7UULOUjxoakbQ0Xfe/eDEMHw7//d9w/fUQGgidyFsf9TXLW/LhEt4+\n/TbZf80mKzyLvaf3MqzbMBIcCQytHMrnJz+n2FFMUV4RMZkxDBkzBKWUz6KuK/If0n0IYyvHIsd8\nBb9PXB8j+Dbju7ibjY72e6LTOzHAT4Fn0eIPuhFzKOAAhqP38Q5DN2JQ6IEMG4BM4Hm0JFdYx3QA\nTqKn9Jwf/lwRbMSMqmyZKAWffQavvAJffAG33657/wwebLdlrZqayjgPnTlEclqyjvjTkjiSdYTK\nkEp6Z/Vm6cNLmdB7AlFhUSilmHjzRJ/F3AnfTGDLe1t8SjxduK4Kpv3HNPv+wQY3a9duYtaslzh+\n/CxOZym6mqeL9a4r2gct3MfQgl8KjEOndjqgt2OXWJ8/B3wGHLIe97be34VeIP7AOl8p0BGRdrRv\n7+TcuQ8bfWfxFH9PZggQ8vJ0vn/hQh3xz5ihp4C1b2+3ZUHB8pXLWZ62nPLF5eS3z2dz2mYiwyJJ\njEvUEX/JUB7b+RjFfYrJKc4hJyWHqH5RAKxYvaJaXn9f+318uOZD1m5YW2Pkv2b9GuMIbMblAI4e\nPQd0QqdtCvDsvAMd7XdDXxF0R1f/DECnc7LQUX4a8AqQjZbngUAvdOonD/genTYqJzIyi/j4EfTq\nFc3MmVdx3XVXuL/pfNf26hpef4dS6k0R+T2+VwSCrhqaf17f1ADMFcF5kpKic//vvgtXXaUdwOWX\nu6d+GRpOXames8Vn2Zy22V3GmXw8Gac46Z7TnRfuf4HEuEQcHR3u89QW8YsI98y8h6P51Xs9mby+\n/Xgv7paWFqNUMUqFUFJSgM73u+ZrDET/cLuio/ye1n03oBwt+FHAErTAjwQ2otNFPdDCvxYt/GFA\ne0JC2tKvXzteeuk+H8GvjcbsNRRl3UdjqoQCl/Jy+Ogj7QC++05P/EpJgdiGVxAYfKnae/9Y7jH3\nom5yWjIn8k4wvtd4Eh2JTA6bzPb07RTHFXPu3DnCj4fjGO5wn6uuiH/af0wzYh9guMR///6jlJZ2\nQlfw3Inuv+miEF214wDaAYPQ4l+MFv1MYBO66PJjfAV/G3o/wBS0+J8AIggLi2L48L488cQtfgn/\nheLPGkGiUiqpvteaAnNFUAeZmfC3v+nJXwMH6uj/pz+FsDC7LWtVVDgreP6953l89eOMHj+a4xXH\nAdxpnoS4BC7tfilhbcLqjfYBE/EHOFVLOsvKXBu4XGmeucBL6Ag/Fi3mPdHpnQxgHzpfnwkk4usw\nvKP9UiCCNm0qCA9XtGkTTVhYO/r1a98o4t8UvYbcA2m8XtuplBrdQBv9xjiCKigFX36pF383bIBb\nb9UOYNgwuy1rMdRXzZNfms9X6V+RnJpMcloyWzO2UpFfQXHbYvpn9GfDvA3069yvxnN8sOoDs5jb\nwli7dhMLFqwnI+N7jhw5RElJZ3TUPxU9iHEiWrxd1T59gBx0dU6mdZ+Gjv6vBl5EJ1pcUf9U9Fas\nk0AxIu2Iiopm0KDOTRrtN5ojEJGJwCTgd8B8PBez0cCNFzqhzC/jjCPQFBTAW2/p9E9Fha78ufNO\n6NjRbstaFDXt1k3PT9cpHqua5/CZw4yJHUOCI4HEuESy9mUxY80Mn7r92kTdRPuBT/VNXHEodTfw\nJrqO/zL0yJUTaCEvRAt+unV/LzC7ylmvRkf+LuF/CThrvRdFREQ7hg69qNnSPNC4jmAy8APgV8Bf\nvd46B6xWSh2+EEP9Mi7YHcHBg7ryZ9kymDxZR/8//KFZ/G0g7658l3tfu5fbfnYbRZ2KSEpNoqi8\nyJ3mSYxLZHTP0YS30Yt+/qR6DIGLd7R/4kQaFRVOSkraAUOBnwBbgQeBVHQVTwFa7IcD/0SLf4l1\ntqpiXzXl44r8C4EK4uOj/F7YbQqaIjXUVyl1/EINawhB6QgqKmDNGp3+SUnRu35/9StwOOo/1uBD\nUXmRpylbajIbDm3QTdlyu/KXO//C5X0uZ2CXgbWKukn1tFzmzFnIM8/spbj4F8Cn6Pp9V07fgS7D\nPIVH9E+iRRz0OsBsPOIP1cX+LOHhFYSEhFJWVgFEERnZvslTPv7SFBPKjl+QRQb/yMqCf/xD7/51\nOHT0P20atG1rt2UthlMFp9y5/eS0ZFKyUhjRfQSJjkSGO4fzReYXuilbXiGdMjpx8eiL6zyfqdsP\nbKqWc4aEhBMdPZCcnG6Ulg5CR/tl6CqebsA6dDuGe4BX0Ttyh+OZtuMS/kfRov8JcBda/HcDe4mI\niLLSPA/YLvaNiV8Tyuyi1V8RKAVffaVz/2vXauGfMQNGjar/2CChrlbMB7MPuks4k1KTyCnOYZJj\nkruaZ1zsOCLDIk2Kp5Xgneo5fvwkxcWDcTonAhPQpZk90RuxMoHTwDXo5sllwBw8uX3viP8TPKme\n6lF/ZGRb4uP71bhpK5Bp9CsCQxNQVATvvKMdQH6+Xvx9+WXo3NluywIK78Xd0spSdmTu8GzaSkum\nY9uO7vz+w5MeZkjXIYRISLXz1Fe7bwg8XKJfWhpKbu4psrM7c/r0MCoqZqBFvyt6QbY7sAa4HvgT\n8DiwCB3tX4Mu63RRU8Q/FffYNbYQEbGfyMgO9OvXpdVF/XVR12LxHGBRbQNpRKQnemDN401mXGu7\nIvjuO93z/403YOJEHf1ffTWEVBevYOdM0RmeXfEsL3z+Av2H9ietLI3BFw32qd+PjfZv05yp5mk5\nfPTRl/zxj19w9Gh/KipuQ9emtEWXbPbAI/pPoXfpzqnhVlu0/xR6Y9dSIIu2bZ2Eh7elTx9Hi4v4\n66Mxrwi2A8tFJBzYiV5NEfT/6Gj0jojnLsDW4KCyEtat09H/tm1wzz36vl8/uy0LGJRSHDl7xL2o\nm5yWTMa5DDgDZXFlkAInXztJdNvoBp3fiH1g4Yr209JyycjoSLt2Iykt7UFBgYOysgno/js9rU8v\nA36NLlycg5al69F1+y4qqtx7OwHvaP9GK9pvzxNP/FerEf3GoFZHoJRaA6wREQeQgG6ADZAEzFNK\npTeDfS2XM2dgyRJ9BRATo6P/FSsgMtJuy2ynvLKcXad2edI8qcmEhoSSGJdIYlwiD457kENbD3Hv\nynuhPaRKKuvXrzdpnBaGb3rnNMXF/cjPd/D993FUVv4R3ZsnnPz8k+hSzhTgAeA1tOiDruyBmsXe\nO83jff+U9ZkNREScYOjQaJ54Yo4R/jowi8WNzfbtOvr/17/ghhu0Axg/3m6rbCW3JJctaVvcuf1t\nGduI7xLvrt1PcCQQ1zHOnboxi7stC2/Bz89Px+lsR35+LOnpfSgvvxW98BqGFv7t6OEqi9CiDzqV\nMxff1M7cKu9twhPlf4J3mkfke8LDKwkPb0uXLhEUFFTSs2ePVpfuOR8aLTUkIqHAdPTe6o+VUsle\n781WSs2t7digo6QE3ntPO4DTp+GBB+DwYbjoIrstuyDqa8dQ2zGpeak+1TzHco8xNnYsiY5E/pDw\nBy7rfRmdIjrVeg6zuBvYeAv/2bNZpKcPJidnLrpSB/QCbga6Zh905P6g9XgN2hF4Lz26ZMg72ndF\n9t6PATYQFraPiIhpVm6/JzNn3hmUYt+Y1LVG8BoQiW6Pt0BEvlBKPWS9Nw2Pyw5ejh/Xdf9LlsDo\n0TB7Nvz4x9Cmjd2WXTA1tWOoiQpnBftO7/MR/gpnBQlxCSQ6Erl75N2M6jGKsDb+N8Mz9fuBx9q1\nm5g/fyNHj0aSkdGH8nLXn38ZnvbLW9ATtwD+jie9k+V1pqopHu/HVUX/MSIiThAbW0anTjOIju5K\nRATMnGny+41NXY5gvFJqOICIvAIsFJEPgduaxbJAxemETz/V0X9Sku75k5QEF9e9OamlsWL1Ct7/\n5n1+vObHPuJbUFbg05Ttq/Sv6N2hNwmOBK4dcC1zfziX+M7xF5TCMYu79vP++8k888wBcnIcnD3b\nkfz8QVRWXoFusOa9y/1p4H+tx7vxOIKahB48Yu+dz6/ZAejc/nQj+s1AXeWjB5VSg6u89jj6p9ZN\nKTWwxgMb07hAWiPIzYV//lP3/omK0rn/226Ddu3stqzR8c7Rj/p2FH949A968EpaEgezDzKqxyh3\nfn+SYxIxUTF2m2y4APLyYOHCPfzzn5nk5vYmL68rZWWdUcq1q/1D4Cbr8Rw8kT7UnM8HT07/qSqP\n9XuRka/SrVuoO58fFlaASFsr6q8M2tx+Y9GYTeeWAW8ppT6u8vp09P6CJm98LyLq8cmTUUpR2r8/\nT79uQ6S4Z4+O/t9/H669VjuASZNaZeM3p3Ky//v9LFizgCUHllDZvhIqYWyXsfxs7M9IjEtkTOwY\nIkIj7DbV0EByc2HnTn3bsUPXNqSnVwLplJT0sT71MjDT66g5eMTfW+zBH8GPj+9phL6ZafSmc3Yi\nIkoB66KikKVLmTqtmfLDZWW61PPVV+HECd30bfp06NGjeb6/mSguL2ZrxlZ3Nc/mtM3ERMaQdzSP\n7E7ZpmKnhXP2LCxcuJc33tCRfkFBT6Aj/foVUlDwDZGRp4mJSaOo6Ft2737V68g51B71VxV76NHj\nXmJjI4mO7kp+froR/ACg0VtMiMg0PKMqLWkgD9inlMqq9cBGQgGfDB/O/JtuqvezF0x6Orz2mm7+\nNnQoPPSQLgENbR2dOLIKs9y5/aTUJPZl7WNYt2EkOBK4b9R9LL5hMUmfJXHX7rv0UCYwFTsthDNn\nPFG+63bqVAVKRVNSco37c927TycnpwOnTnlGjkdE3FnlbBVVnnvn8LWoR0beQnx8T6tE824j9i0c\nf9pQr0WP6fncemkKeqdxP+AJpdTSJjNORH3c1FcDSsHGjTr6/+wznfd/8EHtCFowSikOnTnkU82T\nVZjFRMdEd35/fK/xRIVF+Rxn2jEEPtnZvoK/cyecPl1BREQaUVGn6NIlnQcf7MuHH65iw4Ynqxxd\nNbVT02t1R/0m0g98mmIewXrgDlfPIRHpjh7n83Ngk1Lqkguwt77vVv85YQLztzRBWuLcOVi6VC/+\ngs7933EHRDesjYHdlFaUsvPkTp+mbFFhUT5DVy7pegltQlp+aWswkZXlEfsdOyApqYSzZ6Fdu5N0\n6pTBzTfHMGBAAfPmreToUY+Yx8c/SmRkISkpL1Y54xx80z4Am4iIeIeSkkXuV4zwt2yawhEcUEoN\n8XouwH6l1JCa5hk3JiKi1n3wQeNeDezfr6P/d96BH/1IO4DJk1vc4u/Z4rO6kscS/p0ndzIwZiCJ\njkQS4hJIcCTg6GiG2bQkTp3Sgv/228dZv76I/PxeVFaGM3RoCVOndgYOsHz5x6SlPeQ+Jj7+UTp0\nOMuuXQurnS8m5hbOnHm3yqs1XRHAqFHT6datJyUlbYzwtwKaog3151Z66D30GsE0YKOItANyG2am\n/1zdGGsDFRWwcqV2AAcPwv33w7590KtX/ccGAEopjuUe03N1LeE/kXeCCb0mkOBI4LErHmNC7wl0\naNvBblMNfnLypG96Z8cOKC6GuLiznDiRSm6uR4QLC+cyefJUq1Gbr4gfOfIUnTvfVeN39OjRiU6d\nHuXIEe8UTybwkM8aQXz8//Dkk2Z3bjDjjyP4DbqIOMF6/gawwirw/8GFfLmIXAO8CLQB/qGUmlfD\nZxr+BadOwd//rheA+/fX0f+NN0J4eP3H2kiFs4Ldp3b75PcFcad5fjnml1za41JCQ1rHInZrJzPT\nV/A3by7l3LlKd3rn1lsv4sUXh9KvH1xzzfPs2VNd7F9++TFKS2v7eZfW+Grv3t2YOfMqXn75Ma9I\n/26AKq9dY5xAkOPPqEqniCTh+W37ujF2eYlIG+AV4Ep0Y5JtIrJKKXXggk6sFCQn6+h/3Tq4+Wb4\n979hxIgLNbnJyC/N56v0r9zCvzVjK3079SXBkcBPBv2EZ658hr6d+pryzQBHKVi69CtefPE7cnIc\nFBX1oLKyLyEhbRkzBsaMgeHD97N371pych4mNzee3Nx43n//URITp9K//xW1in1JSRvatq1azaPp\n27c9Xbr4Rv7x8f/jFviaRN4Iv8Ebf8pHbwaeBb6wXnpZRB5WSr1/gd89HvjONRNZRJYDP0EPFT1/\nCgth2TLtAEpKdOXPokXQqfbmZnaRlpfmjvST05I5fOYwY2LHkOBI4PcTf8/E3hPpHGmmlQUySkFa\nmm/J5pYtZeTnD8PpvMz9ubi4Z3n11Qlcf70W3qlT3yY1teaI/7rrrqhV7HXkfjVHjlQX/Cef1OWf\nJso3NBR/cguzgXGuPQMi0hX4P+BCHUEvdOMSF+no4aPnx6FDuvLnzTfh8svhuef0InCATP2qdFaS\nkpXiI/xF5UXuNM/tI25ndM/RhLcJ7HRVMKMUpKZWL9kMCdFR/ujR8MtfQmHhS2za9LDPsampD/PK\nK4+5HUFdET/ArFk1i723sNcm+Eb4DQ3FH0cgwPdez8/gaRB8IfiVXpozZ4778ZQpU5gyZYqe+rV2\nrY7+d++G++7Tf5l9+tR6nuaisKzQvVs3KTWJr9K/onv77iQ6Ermy/5XMmTKHgV0GmjRPgKKUbirr\nEvt163JISWmLiJMOHTK46qpIHnywD2PGQGysb7HZiy8W1nhOl8gDdUb8gF9ibwTfUJWNGzeycePG\nBh/vjyNYB3wiIm+jHcAtwMd1H+IXGfi2MXSgrwp88HYEfP89PP20bv3cs6de/F21Ctq2rXpYs3Gq\n4JTPbt1vvv+GS7tfSoIjgQfGPsCbN75J13ZdbbPPUDtKwbFj1SP9iAgd6UdHH+fkyS8pL78DgOzs\nwWzd+ii/+MVUevWqLsb1iTzUHfG7MGJvOF/cQbLFn/70p/M63p99BIKuGkpER/FfKqU+Ol9Dazhv\nKPAt8CMgEz2r7ufei8UiopTTCVu36uh/9Wpd9TNjhv5LbWacysm32d/6VPPkFOcwyTHJvWlrbOxY\nIsPMOMpAY82aTcybt50zZxwUF3enY8fhpKZ2JioK90Ku6+ZqKTV16mzWr69ecz916mOsW1d1x67u\n2f/b335STeRfesk3X7927SZefnmDqdk3NBmNvo/AqhBaYd0aDaVUhYj8Br2XvQ2wuMaKoXHjdPes\nBx6AF17Q83+biZKKErZnbndH/MlpyXRs29Gd33940sMM6TqEEAmM9QiDxumEI0c8Uf769bmkpIzD\n6fSIbY8eb7BgwcXcfvvEWs9TXz6/KvWldbw/Z4TfEEjUNaqygNrz+EopdcG7l6wW13WmmdSf/oRc\ne22zLP5mF2WzOW2z3riVlsSeU3sY0nUICY4E7hhxB3+9/q/ERsc2uR0G/3E69VRQ7zYMu3ZBx46e\nCD80dCVOp++mq1On7uKttx6r0xH4k+qpihF5Q0ukVkeglGrfnIbUxofOEqY1gRNQSnHk7BGd5rGE\nP/NcJpf1vowERwJP/uBJxvcaT/vwgPhvMKBrBFyi77rt2qUvEl2i/8gjuorHe1z0hg3HajxfbZG9\nC3/y+QZDayDgt6Y+u/RZbrr+pguusimvLGfXqV2epmypyYS1CXOneWaMn8HwbsNNU7YAYdWqTcyb\nt8u9Mat9+0tITe1It26eks3Zs/V9fdnChkT24H+qx2Bo6QT8YJqou6NYetPS8+6Fn1eSx5b0LW7h\n3565nf6d+7ubsiXGJRLXMa6JLDecDxUVugWUK73z6ad5HDgQ4TUqEXr2XMwLLwzhllsmnff5/V3E\nNRhaC61uQhmP1z8hSylFal6qz6ato2ePMi52HAmOBBLiEpjYeyIdIzo287/AUJWKCjhwwDe9eokK\nqgAACzxJREFUs3evrsl3pXeWL1/Cjh33Vju2tmodfzCVOoZgoim6j9pLDROyKp2V7D2916f3fnll\nuTvNc8/IexjZYyRhbZp8rHKrZO3aTSxYsJ7S0lDatq1g1qyrGySa5eW667e36O/bB717e0R/2jQY\nNUov7rpYsya1xvPVl9OvC7OIazDUTsA7gsnHJlNBBX/7/G+kROtWDV9nfE2v6F4kxiVy7YBreeqH\nT9G/c3+zW7cRqCmNcuTIo0DdLQzKyuCbb3yrd1JSIC7OI/q33AIjR0KHeurNGprTNxgMDSPgHUHB\npAIOZh9kZI+RFFcUM3P8TN5xvENMVPPtJwgmFixY7+MEwLcpGmjRT0nxjfS/+Qb69fOI/s9/rkW/\nIQPfTLWOwdC8BLwjeOmalxgTO4aI0Ai7TQkKattEdfToeH75Sx3t79+vxzu4RP+OO7Tot2vXODaY\nah2DoXkJeEfwxP0fM2tWpRGBZqCkBEpKutf4XmFhL0aMgHvu0aMdGkv0a8Pk9A2G5iPgHcH69XP9\nylEbzo/iYl2t453eOXQIevS4g+joHZw75+nl5Cm1tNFgg8HQZAR++ajV5eJCSgeDnaIi2LPHd4jK\n4cMwaJBvs7URI3TnTVNqaTC0bFrfPgLLEUyePIeNG+fYa1ALoKhIj2jwjvSPHIEhQzyCP3o0DB+u\nRd9gMLQ+Wt8+AgtTOlidggJf0d+5E44ehaFDteBPmgQzZ8KwYbaObDAYDAFOi3AEpnQQzp2rHumf\nOAGXXKJF/4or4He/08/DzdRLg8FwHgR8amjq1NlBl6POz9ddNb1FPy1Np3NGj/akeC65BMLM5mmD\nwVCFVrdGEMj2NQZ5eTql472Qm56uF269F3KHDDGibzAY/MM4ggAmN9dX8HfsgJMn4dJLPYu4LtEP\nbRFJO4PBEIgYRxAg5OR4RN91f/q0R/Rdt8GDoY0ZgWAwGBoR4whs4MyZ6pF+drZuu+At+hdfbETf\nYDA0PcYRNDHZ2b6Cv2OHjv5Hjaou+s0wZtlgMBiqYRxBI5KVVT3Sz831rdwZMwYGDDCibzAYAgfj\nCBrI6dPVI/2CAo/ou+7j443oGwyGwMY4Aj84edJ3N+6OHbo1Q9VIv39/MLNuDAZDS8M4gipkZlaP\n9EtLfQV/9Gg9VMWIvsFgaA0ErSNQCjIyfAV/5049N9db9MeMgT59jOgbDIbWS1A4AqV0y4WqC7lK\nVRd9h8OIvsFgCC5anSNwOhWpqdUj/ZAQ30XcMWOgd28j+gaDwdDqHEFMjCIsrHqkHxtrRN9gMBhq\notU5gowMRWys3ZYYDAZDy6HVOYJAts9gMBgCkfN1BGZrlMFgMAQ5xhEYDAZDkGMcgcFgMAQ5xhEY\nDAZDkGMcgcFgMAQ5tjgCEZkjIukissu6XWOHHQaDwWCw74pAAfOVUqOs2zqb7DhvNm7caLcJ1QhE\nmyAw7TI2+YexyX8C1a7zwc7UUIvcFxyIP/RAtAkC0y5jk38Ym/wnUO06H+x0BDNFZI+ILBaRTjba\nYTAYDEFNkzkCEdkgIvtquN0ALAL6ASOBk8DzTWWHwWAwGOrG9hYTItIXWK2UGl7De6a/hMFgMDSA\n82kxEdqUhtSGiPRUSp20nt4I7Kvpc+fzDzEYDAZDw7DFEQDzRGQkunroGPArm+wwGAyGoMf21JDB\nYDAY7CUgdxaLyBIROS0iNaaM7EBEHCLyuYh8IyIpIjIrAGyKEJGvRWS3iOwXkb/YbZMLEWljbRZc\nbbctACJyXET2WjZttdseABHpJCIfiMgB6+d3WQDYNMhro+cuEckLkN/1R6y/vX0i8raItA0Am35r\n2ZMiIr+1yYZqWikiXaxinUMist6fqsyAdATA60Cg7TYuB36nlLoEuAyYISJD7DRIKVUC/EApNRIY\nAfxARBLttMmL3wL70em/QEABU6wNjOPtNsbiJeDfSqkh6J/fAZvtQSn1rWujJzAGKAI+stMmq6Dk\nfmC0VVTSBrjVZpuGAdOBccClwPUiEm+DKTVp5R+BDUqpi4H/s57XSUA6AqXUl8BZu+3wRil1Sim1\n23pcgP6jtX12mlKqyHoYjv4DybHRHABEpDfwY+AfBNbGwYCxRUQ6ApcrpZYAKKUqlFJ5NptVlSuB\nI0qpNJvtyEcHYlEiEgpEARn2msRg4GulVIlSqhL4AripuY2oRStvAN6wHr8B/LS+8wSkIwh0rAhl\nFPC1vZaAiISIyG7gNPC5Umq/3TYBLwAPA067DfFCAZ+KyHYRud9uY9D7aL4XkddFZKeI/F1Eouw2\nqgq3Am/bbYRSKge91ygVyARylVKf2msVKcDlVhomCrgO6G2zTS66K6VOW49PA93rO8A4gvNERNoD\nHwC/ta4MbEUp5bRSQ72BK0Rkip32iMj1QJZSahcBFIEDCVa641p0Wu9ym+0JBUYDC5VSo4FC/LiE\nby5EJBz4D+D9ALAlHvhPoC/6Kry9iPzCTpuUUgeBecB64GNgF4EV+ABgzfqtNz1rHMF5ICJhwArg\nLaXUv+y2xxsrrbAWGGuzKZOAG0TkGPAO8EMRWWqzTbj2rSilvkfnvO1eJ0gH0pVS26znH6AdQ6Bw\nLbDD+v+ym7HAZqXUGaVUBfAh+vfMVpRSS5RSY5VSk4Fc4Fu7bbI4LSI9QO/ZArLqO8A4Aj8REQEW\nA/uVUi/abQ+AiFzkqggQkUjgKnRkYhtKqf9RSjmUUv3QqYXPlFJ32mmTiESJSLT1uB1wNbVsYmwu\nlFKngDQRudh66UrgGxtNqsrP0Y48EDgIXCYikdbf4ZXoQgRbEZFu1n0cemOs7Wk0i1XAXdbju4B6\ng1a7NpTViYi8A0wGYkQkDfhfpdTrNpuVANwO7BURl9g+YnML7Z7AGyISgnbqbyql/s9Ge2oiEKqG\nugMfaQ0hFFimlFpvr0kAzASWWWmYI8A9NtsDuJ3llehKHdtRSu2xriq3o9MvO4G/2WsVAB+ISAx6\nIftBpVR+cxvgpZUXubQSeBp4T0TuA44DN9d7HrOhzGAwGIIbkxoyGAyGIMc4AoPBYAhyjCMwGAyG\nIMc4AoPBYAhyjCMwGAyGIMc4AoPBYAhyjCMwBB0i0uDWICKyTEQOWu2HF1tN0FzvXS8ic6zHc0Sk\nUES6Vv1eEWkrIpus/R8Gg+2YX0RDMHIhm2feUkoNttohR6JbEbv4PbDI63m29ZrP9yqlSoEv8aMr\npMHQHBhHYAhaRPOsFd3vFZGbrddDRGShNTBmvYisFZFpAEqpj71OsQ2r46SIOIBwr66PClgC3FLL\nYJBV6DYOBoPtGEdgCGZuQg8VGYFuqfCs1azrJqCPNTDmDmAiVa4irAaEt6M7T4JuQbKzyvkL0M7g\nP2v47t0EQOM0gwGMIzAEN4nA20qThR4uMg4t6u8BWBH+5zUcuxD4QimVbD2PA05W+YwCFgB3We3L\nPW/o9FCIiEQ01j/GYGgoAdl0zmBoJhS1z0yo+rr7uYg8DsQopao2Zat2jFIqT0TeBn5Ty3eYZl8G\n2zFXBIZg5kt0Dj/Equ65Aj11LhmYZq0hdAemYAm2iExHt7G+rcq5TgA9avme+cCv8Aq8rOHrldaV\ngcFgK8YRGIIRV/XOR8BeYA96yPfDVopoBXpwzH7gTXTu3zVPeBHQDdgiIrtEZLb1ejLVB8u4vucM\nephKuNd7o4AtjfvPMhgahmlDbTDUgIi0U0oVWv3mvwYmWU6irmM+A37hmoZWz2f/DGyznJHBYCvm\nisBgqJk11gCiTcAT9TkBi+eAX9f3ISstlIgfk6MMhubAXBEYDAZDkGOuCAwGgyHIMY7AYDAYghzj\nCAwGgyHIMY7AYDAYghzjCAwGgyHIMY7AYDAYgpz/BwHk+bxgD7ICAAAAAElFTkSuQmCC\n",
      "text/plain": [
       "<matplotlib.figure.Figure at 0x106496410>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "\n",
    "sort_functions = [\n",
    "    builtinsort,         # see implementation above\n",
    "    insertion_sort,      # see [[Insertion sort]]\n",
    "    qsort,               # see [[Quicksort]]\n",
    "    ]     \n",
    "\n",
    "import sys\n",
    "sys.setrecursionlimit(10000)\n",
    "write_timings(npoints=100, maxN=1024, # 1 <= N <= 2**10 an input sequence length\n",
    "                 sort_functions=sort_functions,\n",
    "                 sequence_creators = (ones, range, shuffledrange))\n",
    "plot_timings()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 37: Build your own Stack container\n",
    "A **stack** is a container of elements with *last in, first out* access policy. \n",
    "Sometimes it also called **LIFO**. The stack is accessed through its **top**. \n",
    "The basic stack operations are:\n",
    "\n",
    "* **push** stores a new element onto the stack top;\n",
    "* **pop** returns the last pushed stack element, while removing it from the stack;\n",
    "* **empty** tests if the stack contains no elements.\n",
    "\n",
    "Create a stack supporting the basic operations: push, pop, empty."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 76,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "ABC\n",
      "123\n"
     ]
    }
   ],
   "source": [
    "# First implementation: as a linked-list\n",
    "    \n",
    "class Stack:\n",
    "    \n",
    "    def __init__(self):\n",
    "        self._first = None\n",
    "    \n",
    "    def __nonzero__(self):\n",
    "        return self._first is not None \n",
    "    \n",
    "    def push(self, value):\n",
    "        self._first = (value, self._first)\n",
    "    \n",
    "    def pop(self):\n",
    "        if self._first is None:\n",
    "            raise IndexError, \"pop from empty stack\"\n",
    "        value, self._first = self._first\n",
    "        return value\n",
    "    \n",
    "s = Stack()\n",
    "s.push('123')\n",
    "s.push('ABC')\n",
    "print s.pop()\n",
    "print s.pop()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 75,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "ABC\n",
      "123\n"
     ]
    }
   ],
   "source": [
    "# Second implementation: directly as a list\n",
    "\n",
    "class Stack:\n",
    "    \n",
    "    def __init__(self):\n",
    "         self.container = []  \n",
    "\n",
    "    def isEmpty(self):\n",
    "         return self.size() == 0   \n",
    "        \n",
    "    def push(self, item):\n",
    "         self.container.append(item)  \n",
    "\n",
    "    def pop(self):\n",
    "         return self.container.pop()  \n",
    "\n",
    "    def size(self):\n",
    "         return len(self.container)  \n",
    "\n",
    "s = Stack()\n",
    "s.push('123')\n",
    "s.push('ABC')\n",
    "print s.pop()\n",
    "print s.pop()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 38: Sets and operators over sets\n",
    "A **set** is a collection of elements, without duplicates and without order.\n",
    "\n",
    "Show each of these set operations:\n",
    "\n",
    "* Set creation\n",
    "* Test m &isin; S -- \"m is an element in set S\"\n",
    "* A &cup; B -- ''union''; a set of all elements either in set A or in set B.\n",
    "* A &cap; B -- ''intersection''; a set of all elements in ''both'' set A and set B.\n",
    "* A &#x2216; B -- ''difference''; a set of all elements in set A, except those in set B.\n",
    "* A &sube; B -- ''subset''; true if every element in set A is also in set B.\n",
    "* A = B -- ''equality''; true if every element of set A is in set B and vice-versa.\n",
    "\n",
    "As an option, show some other set operations. (If A &sube; B, but A &ne; B, then A is called a true or proper subset of B, written A &sub; B or A &#x228a; B.) \n",
    "As another option, show how to modify a mutable set."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 120,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n"
     ]
    }
   ],
   "source": [
    "s1, s2 = {1, 2, 3, 4}, {3, 4, 5, 6}\n",
    "assert isinstance(s1,set)\n",
    "assert isinstance(s2,set)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 122,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Union: set([1, 2, 3, 4, 5, 6])\n",
      "Intersection: set([3, 4])\n",
      "Difference: set([1, 2])\n",
      "Absolute subset: False\n",
      "Subset: True\n",
      "Membership by elemets of s1 in s2: [False, False, True, True]\n",
      "Membership by elemets of s2 in s1: [True, True, False, False]\n",
      "Equallity: False\n",
      "Inequality: True\n",
      "Mutability: set([99, 1, 2, 3, 4])\n",
      "Mutability: set([1, 2, 3, 4])\n"
     ]
    }
   ],
   "source": [
    "print 'Union:', s1 | s2\n",
    "print 'Intersection:', s1 & s2\n",
    "print 'Difference:', s1 - s2\n",
    "print 'Absolute subset:', s1 < s1\n",
    "print 'Subset:', s1 <= s1\n",
    "print 'Membership by elemets of s1 in s2:', [item in s2 for item in s1]\n",
    "print 'Membership by elemets of s2 in s1:', [item in s1 for item in s2]\n",
    "print 'Equallity:', s1 == s2\n",
    "print 'Inequality:', s1 != s2\n",
    "s1.add(99)\n",
    "print 'Mutability:', s1\n",
    "s1.discard(99)\n",
    "print 'Mutability:', s1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 39: Abstract type\n",
    "\n",
    "**Abstract type** is a type without instances or without definition.\n",
    "\n",
    "For example in **object-oriented (OO) programming** using some languages, abstract types can be partial implementations of other types, which are to be derived there-from. An abstract type may provide implementation of some operations and/or components. Abstract types without any implementation are called **interfaces**. In the languages that do not support *multiple inheritance* (Ada, Java), classes can, nonetheless, inherit from multiple interfaces. The languages with multiple inheritance (like C++) usually make no distinction between partially implementable abstract types and interfaces. Because the abstract type's implementation is incomplete, object-oriented programming languages normally prevent instantiation from them  (instantiation must derived from one of their descendant classes).\n",
    "\n",
    "The term **abstract datatype** also may denote a type, with an implementation provided by the programmer rather than directly by the language (a *built-in* or an inferred type). Here the word *abstract* means that the implementation is abstracted away, irrelevant for the user of the type. Such implementation can and should be hidden if the language supports separation of implementation and specification. This hides complexity while allowing the implementation to change without repercussions on the usage. The corresponding software design practice is said to follow the information hiding principle.\n",
    "\n",
    "It is important not to confuse this *abstractness* (of implementation) with one of the *abstract type*. The latter is abstract in the sense that the set of its values is empty. In the sense of implementation abstracted away, all user-defined types are abstract.\n",
    "\n",
    "**Problem**: show how an abstract type can be declared in Python. If the language makes a distinction between interfaces and partially implemented types illustrate both.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class BaseQueue(object):\n",
    "    def __init__(self):\n",
    "        self.contents = list()\n",
    "        raise NotImplementedError\n",
    "    def Enqueue(self, item):\n",
    "        raise NotImplementedError\n",
    "    def Dequeue(self):\n",
    "        raise NotImplementedError\n",
    "    def Print_Contents(self):\n",
    "        for i in self.contents:\n",
    "            print i,"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In this example we're simply following the Python convention of raising the built-in `NotImplementedError` for each function which must be implemented by our subclasses. This is a **purely virtual** class because all of its methods raise the exception. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from abc import ABCMeta, abstractmethod\n",
    " \n",
    "class BaseQueue():\n",
    "    \n",
    "    __metaclass__ = ABCMeta\n",
    " \n",
    "    def __init__(self):\n",
    "        self.contents = list()\n",
    " \n",
    "    @abstractmethod\n",
    "    def Enqueue(self, item):\n",
    "        pass\n",
    " \n",
    "    @abstractmethod\n",
    "    def Dequeue(self):\n",
    "        pass\n",
    " \n",
    "    def Print_Contents(self):\n",
    "        for i in self.contents:\n",
    "            print i,"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In this second snippet, we've implemented the method `Print_Contents`. This would be inherited by any derived classes. It could be over-ridden, of course. If it's not over-ridden it establishes a requirement that all derived classes provide some \"contents\" attribute which must allow for iteration and printing as shown. Without this method the class would be \"purely virtual\" or \"purely abstract.\" With its inclusion the class becomes **partially implemented**."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 40: Temperature conversion\n",
    "There are quite a number of temperature scales. \n",
    "We will concentrate on 4 of the perhaps best-known ones: Kelvin, Celsius, Fahrenheit and Rankine.\n",
    "The Celsius and Kelvin scales have the same magnitude, but different null points.\n",
    "\n",
    " - 0 degrees Celsius corresponds to 273.15 kelvin\n",
    " - 0 kelvin is absolute zero\n",
    " \n",
    "The Fahrenheit and Rankine scales also have the same magnitude, but different null points\n",
    "\n",
    " - 0 degrees Fahrenheit corresponds to 459.67 degrees Rankine.\n",
    " - 0 degrees Rankine is absolute zero.\n",
    "\n",
    "The Celsius/Kelvin and Fahrenheit/Rankine scales have a ratio of 5 : 9.\n",
    "\n",
    "**Problem : **Write code that accepts a value on any scale, and converts it to values on the three other scales and prints the result."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "toK = {'C': (lambda c: c + 273.15),\n",
    "       'F': (lambda f: (f + 459.67) / 1.8),\n",
    "       'R': (lambda r: r / 1.8),\n",
    "       'K': (lambda k: k) }"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "<value> <K/R/F/C> ? 20 C\n",
      "\n",
      "|| 293.15 Kelvin || 20.0 Celsius || 68.0 Fahrenheit || 527.67 Rankine degrees ||\n",
      "\n"
     ]
    }
   ],
   "source": [
    "magnitude, unit = raw_input('<value> <K/R/F/C> ? ').split()\n",
    "k = toK[str(unit)](float(magnitude))\n",
    "print(\"\\n|| {0} Kelvin || {1} Celsius || {2} Fahrenheit || {3} Rankine degrees ||\\n\".\n",
    "      format(k, k - 273.15, k * 1.8 - 459.67, k * 1.8))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 41: The Monty-Hall problem by simulation\n",
    "Run random simulations of the Monty Hall game. Show the effects of a strategy of the contestant always keeping his first guess so it can be contrasted with the strategy of the contestant always switching his guess.\n",
    "\n",
    "- Suppose you're on a game show and you're given the choice of three doors. Behind one door is a car; behind the others, goats. The car and the goats were placed randomly behind the doors before the show. The rules of the game show are as follows: After you have chosen a door, the door remains closed for the time being. The game show host, Monty Hall, who knows what is behind the doors, now has to open one of the two remaining doors, and the door he opens must have a goat behind it. If both remaining doors have goats behind them, he chooses one randomly. After Monty Hall opens a door with a goat, he will ask you to decide whether you want to stay with your first choice or to switch to the last remaining door. Imagine that you chose Door 1 and the host opens Door 3, which has a goat. He then asks you \"Do you want to switch to Door Number 2?\" Is it to your advantage to change your choice? (Krauss and Wang 2003)\n",
    "\n",
    "Note that the player may initially choose any of the three doors (not just Door 1), that the host opens a different door revealing a goat (not necessarily Door 3), and that he gives the player a second choice between the two remaining unopened doors.\n",
    "\n",
    "**Problem**: Simulate at least a thousand games using three doors for each strategy and show the results in such a way as to make it easy to compare the effects of each strategy."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The player wins 337 times if keep the same door after 1000 simulations\n",
      "The player wins 647 times if switch another door after 1000 simulations\n"
     ]
    }
   ],
   "source": [
    "import random\n",
    " \n",
    "def MontyHall(simulations):    \n",
    "    option_stay = 0  \n",
    "    option_switch = 0 \n",
    "\n",
    "    for simulation in range(simulations):\n",
    "        prize_behind_doors = [1,0,0]           \n",
    "        random.shuffle(prize_behind_doors)     \n",
    "        user = prize_behind_doors[random.randrange(3)] \n",
    "        for door in range(len(prize_behind_doors)): \n",
    "            if prize_behind_doors[door] == 0:\n",
    "                del(prize_behind_doors[door])\n",
    "                break\n",
    " \n",
    "        if user == 1: # if the original choice is 1 then stay adds 1\n",
    "            option_stay += 1\n",
    " \n",
    "        if prize_behind_doors[0] == 1: # if the switched value is 1 then switch adds 1\n",
    "            option_switch += 1\n",
    "        \n",
    "    return (option_stay, option_switch)\n",
    "\n",
    "stay, switch = MontyHall(1000)\n",
    "print \"The player wins {0} times if keep the same door after {1} simulations\".format(stay, simulations) \n",
    "print \"The player wins {0} times if switch another door after {1} simulations\".format(switch, simulations) "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 42: Polymorphism\n",
    "**Problem**: Create two classes `Point(x,y)` and `Circle(x,y,r)` with a polymorphic function print, accessors for (x,y,r), copy constructor, assignment and destructor and every possible default constructors.\n",
    "\n",
    "\n",
    " - In Python, multiple constructors are not needed, because Python supports default values for arguments. \n",
    " - Accessors are not needed because Python attributes are public. It is possible to add managed attributes later without changing the interface and existing client code. \n",
    " - For the print function, use the standard __repr__ methods, used when printing an object. \n",
    " - Destructors are not needed of course."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 62,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Point(object):\n",
    "    def __init__(self, x=0.0, y=0.0):\n",
    "        self.x = x\n",
    "        self.y = y\n",
    "    def __repr__(self):\n",
    "        return '<Point 0x{0} x: {1} y: {2}>'.format(id(self), self.x, self.y)\n",
    "\n",
    "class Circle(object):\n",
    "    def __init__(self, center=None, radius=1.0):\n",
    "        self.center = center or Point()\n",
    "        self.radius = radius\n",
    "    def __repr__(self):\n",
    "        return '<Circle 0x{0} x: {1} y: {2} radius: {3}>'.format(\n",
    "            id(self), self.center.x, self.center.y, self.radius)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 63,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<Point 0x4409425296 x: 0.0 y: 0.0>"
      ]
     },
     "execution_count": 63,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "p1 = Point()\n",
    "p1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 64,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<Point 0x4409425104 x: 3 y: 4>"
      ]
     },
     "execution_count": 64,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Point(3, 4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 65,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<Circle 0x4408592976 x: 3 y: 4 radius: 1.0>"
      ]
     },
     "execution_count": 65,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Circle(Point(3,4))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 66,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1.25\n",
      "3.87\n"
     ]
    }
   ],
   "source": [
    "p = Point(1.25, 3.87)\n",
    "print p.x\n",
    "print p.y"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "or using inheritance..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 72,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Point(object):\n",
    "    def __init__(self, x=0.0, y=0.0):\n",
    "        self.x = x\n",
    "        self.y = y\n",
    "    def __repr__(self):\n",
    "        return '<Point 0x{0} x: {1} y: {2}>'.format(id(self), self.x, self.y)\n",
    "\n",
    "class Circle(Point):\n",
    "    def __init__(self, center=None, radius=1.0):\n",
    "        self.center = center or Point()\n",
    "        self.radius = radius\n",
    "    def __repr__(self):\n",
    "        return '<Circle 0x{0} x: {1} y: {2} radius: {3}>'.format(\n",
    "            id(self), self.center.x, self.center.y, self.radius)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 73,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 73,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "issubclass(Circle, Point)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 43: Regular Expressions\n",
    "**Problem 43.1.** Create a regular expression (regex) that matches `cat` in `My cat is brown`, but not in `category` or `bobcat`. Create another regex that matches cat in `staccato`, but not in any of the three previous subject strings."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 122,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "founded cat\n"
     ]
    }
   ],
   "source": [
    "import re\n",
    "string = \"My cat is brown. category. boobcat\"\n",
    "match = re.search(r'\\bcat\\b', string)\n",
    "if match:\n",
    "    print 'founded', match.group()\n",
    "else:\n",
    "    print 'did not find' "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 119,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "did not find\n"
     ]
    }
   ],
   "source": [
    "string = \"My cat is brown. category. boobcat.\"\n",
    "match = re.search(r'\\Bcat\\B', string)\n",
    "if match:\n",
    "    print 'founded', match.group()\n",
    "else:\n",
    "    print 'did not find' "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 123,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "founded cat\n"
     ]
    }
   ],
   "source": [
    "string = \"My cat is brown. category. boobcat. staccato.\"\n",
    "match = re.search(r'\\Bcat\\B', string)\n",
    "if match:\n",
    "    print 'founded', match.group()\n",
    "else:\n",
    "    print 'did not find' "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Problem 43.2.** Create a regex to find the email address inside the string `xyz alice-b@myemail.com purple monkey`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 130,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "b@myemail\n"
     ]
    }
   ],
   "source": [
    "string = 'purple alice-b@myemail.com monkey dishwasher'\n",
    "match = re.search(r'\\w+@\\w+', string)\n",
    "if match:\n",
    "    print match.group()  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 132,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "alice-b@mymail.com\n",
      "alice-b\n",
      "mymail.com\n"
     ]
    }
   ],
   "source": [
    "string = 'purple alice-b@mymail.com monkey dishwasher'\n",
    "match = re.search('([\\w.-]+)@([\\w.-]+)', string)\n",
    "if match:\n",
    "    print match.group()   ## 'alice-b@google.com' (the whole match)\n",
    "    print match.group(1)  ## 'alice-b' (the username, group 1)\n",
    "    print match.group(2)  ## 'google.com' (the host, group 2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 44: Static methods\n",
    "**Problem**: Is it possible to have static methods in Python so I can call a method from the instance, without initializing a class?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 164,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2\n"
     ]
    }
   ],
   "source": [
    "class MyClass(object):\n",
    "    @staticmethod\n",
    "    def the_static_method(x):\n",
    "        print x\n",
    "\n",
    "MyClass.the_static_method(2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 166,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2\n"
     ]
    }
   ],
   "source": [
    "example = MyClass()\n",
    "example.the_static_method(2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 168,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n"
     ]
    }
   ],
   "source": [
    "# another example: \n",
    "\n",
    "class Date(object):\n",
    "    @staticmethod\n",
    "    def is_date_valid(date_as_string):\n",
    "        day, month, year = map(int, date_as_string.split('-'))\n",
    "        return day <= 31 and month <= 12 and year <= 3999\n",
    "\n",
    "print Date.is_date_valid('11-09-2012')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 180,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n"
     ]
    }
   ],
   "source": [
    "# and that is the long version for the previous example, \n",
    "# where we have to initializer the class... a lot of boilerplate\n",
    "\n",
    "class Date(object):\n",
    "\n",
    "    def __init__(self, date_as_string):\n",
    "        self.date_as_string = str(date_as_string)\n",
    "        \n",
    "    def is_date_valid(self):\n",
    "        day, month, year = map(int, self.date_as_string.split('-'))\n",
    "        return day <= 31 and month <= 12 and year <= 3999\n",
    "    \n",
    "\n",
    "is_date = Date('11-9-2012')\n",
    "print is_date.is_date_valid()    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 45: Generating deprecation warnings with decorators\n",
    "**Problem**: The simplest possible version of a decorator with that functionality is:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def deprecated(func):\n",
    "    def wrapper(*args, **kwargs):\n",
    "        print func.__name__, 'is deprecated'\n",
    "        return func(*args, **kwargs)\n",
    "    return wrapper"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "@deprecated\n",
    "def some_old_function(x,y):\n",
    "    return x + y\n",
    "\n",
    "\n",
    "class SomeClass:\n",
    "    @staticmethod\n",
    "    @deprecated\n",
    "    def some_old_method(x,y):\n",
    "        return x + y"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "some_old_function is deprecated\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "some_old_function(1,1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "some_old_method is deprecated\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "SomeClass.some_old_method(1,1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 46: Pseudo-currying\n",
    "**Problem**: Build a decorator that returns a function that keeps returning functions until all arguments are supplied; then the original function is evaluated."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class curried(object):\n",
    "    def __init__(self, func, *a):\n",
    "        self.func = func\n",
    "        self.args = a\n",
    "\n",
    "    def __call__(self, *a):\n",
    "        args = self.args + a\n",
    "        if len(args) < self.func.func_code.co_argcount:\n",
    "            return curried(self.func, *args)\n",
    "        else:\n",
    "            return self.func(*args)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "@curried\n",
    "def add(a, b, c):\n",
    "    return a + b + c"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "add1 = add(1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "add2 = add1(2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "6\n"
     ]
    }
   ],
   "source": [
    "print add2(3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 47:  Timeout decorator\n",
    "**Problem**: Build a timeout decorator that can be used an alarm signal when a method takes too much time, and simply abort processing. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import signal\n",
    "import functools\n",
    "\n",
    "class TimeoutError(Exception): pass\n",
    "\n",
    "def timeout(seconds, error_message = 'Function call timed out'):\n",
    "    def decorated(func):\n",
    "        def _handle_timeout(signum, frame):\n",
    "            raise TimeoutError(error_message)\n",
    "\n",
    "        def wrapper(*args, **kwargs):\n",
    "            signal.signal(signal.SIGALRM, _handle_timeout)\n",
    "            signal.alarm(seconds)\n",
    "            try:\n",
    "                result = func(*args, **kwargs)\n",
    "            finally:\n",
    "                signal.alarm(0)\n",
    "            return result\n",
    "\n",
    "        return functools.wraps(func)(wrapper)\n",
    "\n",
    "    return decorated"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import time\n",
    "\n",
    "@timeout(1, 'Function slow; aborted')\n",
    "def slow_function():\n",
    "    time.sleep(5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {},
   "outputs": [
    {
     "ename": "TimeoutError",
     "evalue": "Function slow; aborted",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mTimeoutError\u001b[0m                              Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-50-8e418bc74e5d>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m()\u001b[0m\n\u001b[0;32m----> 1\u001b[0;31m \u001b[0mslow_function\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[0;32m<ipython-input-48-6140d7086580>\u001b[0m in \u001b[0;36mwrapper\u001b[0;34m(*args, **kwargs)\u001b[0m\n\u001b[1;32m     13\u001b[0m             \u001b[0msignal\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0malarm\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mseconds\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     14\u001b[0m             \u001b[0;32mtry\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 15\u001b[0;31m                 \u001b[0mresult\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mfunc\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m*\u001b[0m\u001b[0margs\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;34m**\u001b[0m\u001b[0mkwargs\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m     16\u001b[0m             \u001b[0;32mfinally\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     17\u001b[0m                 \u001b[0msignal\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0malarm\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;36m0\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m<ipython-input-49-92cf80206a2c>\u001b[0m in \u001b[0;36mslow_function\u001b[0;34m()\u001b[0m\n\u001b[1;32m      3\u001b[0m \u001b[0;34m@\u001b[0m\u001b[0mtimeout\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;34m'Function slow; aborted'\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      4\u001b[0m \u001b[0;32mdef\u001b[0m \u001b[0mslow_function\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 5\u001b[0;31m     \u001b[0mtime\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0msleep\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;36m5\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[0;32m<ipython-input-48-6140d7086580>\u001b[0m in \u001b[0;36m_handle_timeout\u001b[0;34m(signum, frame)\u001b[0m\n\u001b[1;32m      7\u001b[0m     \u001b[0;32mdef\u001b[0m \u001b[0mdecorated\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mfunc\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      8\u001b[0m         \u001b[0;32mdef\u001b[0m \u001b[0m_handle_timeout\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0msignum\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mframe\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 9\u001b[0;31m             \u001b[0;32mraise\u001b[0m \u001b[0mTimeoutError\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0merror_message\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m     10\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     11\u001b[0m         \u001b[0;32mdef\u001b[0m \u001b[0mwrapper\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m*\u001b[0m\u001b[0margs\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;34m**\u001b[0m\u001b[0mkwargs\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;31mTimeoutError\u001b[0m: Function slow; aborted"
     ]
    }
   ],
   "source": [
    "slow_function()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 48: From Numbers to English Words"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def numToWords(num,join = True):\n",
    "    '''words = {} convert an integer number into words'''\n",
    "    units = ['','one','two','three','four','five','six','seven','eight','nine']\n",
    "    teens = ['','eleven','twelve','thirteen','fourteen','fifteen','sixteen', \\\n",
    "             'seventeen','eighteen','nineteen']\n",
    "    tens = ['','ten','twenty','thirty','forty','fifty','sixty','seventy', \\\n",
    "            'eighty','ninety']\n",
    "    thousands = ['','thousand','million','billion','trillion','quadrillion', \\\n",
    "                 'quintillion','sextillion','septillion','octillion', \\\n",
    "                 'nonillion','decillion','undecillion','duodecillion', \\\n",
    "                 'tredecillion','quattuordecillion','sexdecillion', \\\n",
    "                 'septendecillion','octodecillion','novemdecillion', \\\n",
    "                 'vigintillion']\n",
    "    words = []\n",
    "    if num == 0: words.append('zero')\n",
    "    else:\n",
    "        numStr = str(num)\n",
    "        numStrLen = len(numStr)\n",
    "        groups = int((numStrLen + 2) / 3)\n",
    "        numStr = numStr.zfill(groups * 3)\n",
    "        for i in range(0, groups * 3, 3):\n",
    "            h, t, u = int(numStr[i]), int(numStr[i + 1]), int(numStr[i + 2])\n",
    "            g = groups - ( i/3 + 1)\n",
    "            if h >= 1:\n",
    "                words.append(units[h])\n",
    "                words.append('hundred')\n",
    "            if t > 1:\n",
    "                words.append(tens[t])\n",
    "                if u >= 1: words.append(units[u])\n",
    "            elif t == 1:\n",
    "                if u >= 1: words.append(teens[u])\n",
    "                else: words.append(tens[t])\n",
    "            else:\n",
    "                if u >= 1: words.append(units[u])\n",
    "            if (g >= 1) and ((h + t + u) > 0): words.append(thousands[g]+',')\n",
    "    if join: return ' '.join(words)\n",
    "    return words"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'twelve'"
      ]
     },
     "execution_count": 35,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "numToWords(12)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'one thousand, two hundred thirty four'"
      ]
     },
     "execution_count": 36,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "numToWords(1234)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'one billion, two hundred thirty four million, five hundred sixty seven thousand, eight hundred ninety'"
      ]
     },
     "execution_count": 37,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "numToWords(1234567890)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 49: Number factorization in primes numbers\n",
    "\n",
    "Write a function which returns an array or collection which contains the prime decomposition of a given number, n, greater than 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 76,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# First function: \n",
    "\n",
    "def primes(n):\n",
    "    primfac = []\n",
    "    d = 2\n",
    "    while d * d <= n:\n",
    "        while (n % d) == 0:\n",
    "            primfac.append(d)  \n",
    "            n //= d\n",
    "        d += 1\n",
    "    if n > 1:\n",
    "        primfac.append(n)\n",
    "    return primfac"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 74,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[2, 2, 3, 3, 857]"
      ]
     },
     "execution_count": 74,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "primes(30852)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 86,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Second function: \n",
    "\n",
    "from math import floor\n",
    "\n",
    "def primes(n):\n",
    "    step = lambda x: 1 + (x<<2) - ((x>>1)<<1)\n",
    "    maxq = long(floor(n ** .5))\n",
    "    d = 1\n",
    "    q = n % 2 == 0 and 2 or 3 \n",
    "    while q <= maxq and n % q != 0:\n",
    "        q = step(d)\n",
    "        d += 1\n",
    "    return q <= maxq and [q] + fac(n//q) or [n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 87,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[2, 2, 3, 3, 857]"
      ]
     },
     "execution_count": 87,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "fac(30852)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 88,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Third version (functional version):\n",
    "\n",
    "from math import ceil, sqrt\n",
    "\n",
    "def primes(n):\n",
    "    if n <= 1: return []\n",
    "    prime = next((x for x in range(2, int(ceil(sqrt(n)))+1) if n%x == 0), n)\n",
    "    return [prime] + factor(n//prime)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 89,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[2, 2, 3, 3, 857]"
      ]
     },
     "execution_count": 89,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "factor(30852)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Explanation step by step in the website [invent with python](https://inventwithpython.com/hacking/chapter23.html)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 50: Y-combinator\n",
    "\n",
    "In strict **functional programming** and the **lambda calculus**, functions (lambda expressions) do not have state and are only allowed to refer to arguments of enclosing functions. This rules out the usual definition of a recursive function wherein a function is associated with the state of a variable and this variable's state is used in the body of the function.\n",
    "\n",
    "\n",
    "The **Y-combinator** is itself a stateless function that, when applied to another stateless function, *returns a recursive version of the function*. The Y combinator is the simplest of the class of such functions, called **fixed-point combinators**.\n",
    "\n",
    "\n",
    "**Problem**: define the stateless **Y-combinator** and use it to compute **factorials** and **Fibonacci numbers** from other stateless functions or lambda expressions."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 108,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "Y = lambda f: (lambda x: x(x))(lambda y: f(lambda *args: y(y)(*args)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 109,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "factorial = lambda f: lambda n: (1 if n<2 else n*f(n-1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 110,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880]"
      ]
     },
     "execution_count": 110,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "[ Y(factorial)(i) for i in range(10) ]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 112,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "fibonacci = lambda f: lambda n: 0 if n == 0 else (1 if n == 1 else f(n-1) + f(n-2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 113,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]"
      ]
     },
     "execution_count": 113,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "[ Y(fibonacci)(i) for i in range(10) ]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 51: Multiprocessing\n",
    "\n",
    "Assume we have a collection of numbers, and want to find the one with the largest minimal prime factor (that is, the one that contains relatively large factors). To speed up the search, the factorization should be done in parallel using separate threads or processes, to take advantage of multi-core CPUs.\n",
    "\n",
    "Show how this can be formulated in Python. Parallelize the factorization of those numbers, then search the returned list of numbers and factors for the largest minimal factor, and return that number and its prime factors."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import multiprocessing\n",
    "from math import floor, sqrt\n",
    " \n",
    "numbers = [\n",
    "    112272537195293,\n",
    "    112582718962171,\n",
    "    112272537095293,\n",
    "    115280098190773,\n",
    "    115797840077099,\n",
    "    1099726829285419]\n",
    " \n",
    "def lowest_factor(n, _start=3):\n",
    "    if n % 2 == 0:\n",
    "        return 2\n",
    "    search_max = int(floor(sqrt(n))) + 1\n",
    "    for i in range(_start, search_max, 2):\n",
    "        if n % i == 0:\n",
    "            return i\n",
    "    return n\n",
    " \n",
    "def prime_factors(n, lowest):\n",
    "    pf = []\n",
    "    while n > 1:\n",
    "        pf.append(lowest)\n",
    "        n //= lowest\n",
    "        lowest = lowest_factor(n, max(lowest, 3))\n",
    "    return pf\n",
    "\n",
    "def prime_factors_of_number_with_lowest_prime_factor(numbers):\n",
    "    pool = multiprocessing.Pool(processes=5)\n",
    "    factors = pool.map(lowest_factor,numbers)\n",
    "    low_factor,number = max((l,f) for l,f in zip(factors,numbers))\n",
    "    all_factors = prime_factors(number,low_factor)\n",
    "    return number,all_factors"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "For these numbers:\n",
      "112272537195293  \n",
      "112582718962171  \n",
      "112272537095293  \n",
      "115280098190773  \n",
      "115797840077099  \n",
      "1099726829285419\n",
      "The one with the largest minimum prime factor is 115797840077099:\n",
      "All its prime factors in order are: [544651, 212609249]\n"
     ]
    }
   ],
   "source": [
    "print('For these numbers:')\n",
    "print('  \\n'.join(str(p) for p in numbers))\n",
    "number, all_factors = prime_factors_of_number_with_lowest_prime_factor(numbers)\n",
    "print('The one with the largest minimum prime factor is {}:'.format(number))\n",
    "print('All its prime factors in order are: {}'.format(all_factors))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 52: Forward Difference\n",
    "Provide code that produces a list of numbers which is the n-th order forward difference (or time lag difference in time series), given a non-negative integer (specifying the order) and a list of numbers (or time series). The first-order forward difference of a list of numbers $(A_i)_{i=0\\ldots n}$ is a new list $(B_i)_{i=0\\ldots n-1}$ where $B_i = A_{i+1} - A_i$. Notice that list $B$ should have one fewer element as a result. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "difference = lambda s: [ x - s[i] for i, x in enumerate( s[1:] )]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A = [90, 47, 58, 29, 22, 32, 55, 5, 55, 73]\n",
    "B = difference(A)\n",
    "print B"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 53: Perfect numbers\n",
    "\n",
    "Write a function which says whether a number is perfect.\n",
    "\n",
    "A perfect number is a positive integer that is the sum of its proper positive divisors excluding the number itself. Equivalently, a perfect number is a number that is half the sum of all of its positive divisors (including itself).\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "perf = lambda n: n == sum(i for i in xrange(1, n) if n % i == 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, 6, 28, 496]"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "[i for i in xrange(1000) if perf(i) == True ]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 54: Remove duplicate elements\n",
    "\n",
    "**Problem**: Given an array of items, derive a sequence of elements in which all duplicates are removed.\n",
    "\n",
    "There are basically three approaches seen here:\n",
    "\n",
    "- Insert the elements of the array into a hash table which does not allow duplicates. The complexity is $O(n)$ on average, and $O(n^2)$ worst case. This approach requires a hash function for your type (which is compatible with equality), either built-in in Python (set), or provided by the user.\n",
    "\n",
    "- Sort the elements and remove consecutive duplicate elements. The complexity of the best sorting algorithms is $O(n log n)$. This approach requires that your type be \"comparable\", i.e., have an ordering. Putting the elements into a self-balancing binary search tree is a special case of sorting.\n",
    "\n",
    "- Go through the list, and for each element, check the rest of the list to see if it appears again, and discard it if it does. The complexity is $O(n^2)$. The up-shot is that this always works on any type (provided that you can test for equality).\n",
    "\n",
    "\n",
    "In Python, if all the elements are hashable (this excludes list, dict, set, and other mutable types), we can use a set:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['a', 1, 2, 3, 4, 'd', 'c', 'b']\n"
     ]
    }
   ],
   "source": [
    "items = [1, 2, 3, 'a', 'b', 'c', 2, 3, 4, 'b', 'c', 'd']\n",
    "unique = list(set(items))\n",
    "print unique"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "or if we want to keep the order of the elements"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 2, 3, 'a', 'b', 'c', 4, 'd']\n"
     ]
    }
   ],
   "source": [
    "items = [1, 2, 3, 'a', 'b', 'c', 2, 3, 4, 'b', 'c', 'd']\n",
    "unique = []\n",
    "helperset = set()\n",
    "for x in items:\n",
    "    if x not in helperset:\n",
    "        unique.append(x)\n",
    "        helperset.add(x)\n",
    "        \n",
    "print unique"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "or we can use 'brute force', wich is quite inefficient:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 2, 3, 'a', 'b', 'c', 4, 'd']\n"
     ]
    }
   ],
   "source": [
    "items = [1, 2, 3, 'a', 'b', 'c', 2, 3, 4, 'b', 'c', 'd']\n",
    "unique = []\n",
    "for x in items:\n",
    "    if x not in unique:\n",
    "        unique.append(x)\n",
    "        \n",
    "print unique"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Similar idea, in functional form:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 2, 3, 'a', 'b', 'c', 4, 'd']\n"
     ]
    }
   ],
   "source": [
    "def make_unique(items):\n",
    "    unique = []\n",
    "    map(lambda x: unique.append(x) if (x not in unique) else False, items)\n",
    "    return unique\n",
    "\n",
    "items = [1, 2, 3, 'a', 'b', 'c', 2, 3, 4, 'b', 'c', 'd']\n",
    "unique = make_unique(items)\n",
    "print unique"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "or using a list comprehension:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 2, 3, 'a', 'b', 'c', 4, 'd']\n"
     ]
    }
   ],
   "source": [
    "items = [1, 2, 3, 'a', 'b', 'c', 2, 3, 4, 'b', 'c', 'd']\n",
    "unique = []\n",
    "[(lambda x , unique : unique.append(x) if (x not in unique) else False)(x, unique) for x in items]\n",
    "print unique"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 55: Anonymous recursion\n",
    "\n",
    "While implementing a recursive function, it often happens that we must resort to a separate \"*helper function*\" to handle the actual recursion. This is usually the case when directly calling the current function would waste too many resources (stack space, execution time), cause unwanted side-effects, and/or the function does not have the right arguments and/or return values.\n",
    "\n",
    "Anonymous recursion can also be accomplished using the *Y-combinator* (see problem 50).\n",
    "\n",
    "**Problem**: Write the recursive version of the fibonacci function which checks for a negative argument before doing the actual recursion."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "Y = lambda f: (lambda x: x(x))(lambda y: f(lambda *args: y(y)(*args)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "fib = lambda f: lambda n: None if n < 0 else (0 if n == 0 else (1 if n == 1 else f(n-1) + f(n-2)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[None, None, 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377]"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "[ Y(fib)(i) for i in range(-2, 15) ]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 56: Synchronous concurrency\n",
    "\n",
    "**Problem**: create two concurrent activities (\"*Threads*\" or \"*Tasks*\", not processes.) that share data synchronously. \n",
    "\n",
    "One of the concurrent units will read from a file named \"input.txt\" and send the contents of that file, one line at a time, to the other concurrent unit, which will print the line it receives to standard output. The printing unit must count the number of lines it prints. After the concurrent unit reading the file sends its last line to the printing unit, the reading unit will request the number of lines printed by the printing unit. The reading unit will then print the number of lines printed by the printing unit.\n",
    "\n",
    "This task requires two-way communication between the concurrent units. All concurrent units must cleanly terminate at the end of the program."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# First, let us create the file to read in the code below:\n",
    "file = open(\"input.txt\", \"w\")\n",
    "file.write(\"hello world in the input.txt file\\n\")\n",
    "file.write(\"and another line\\n\")\n",
    "file.close()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "hello world in the input.txt file\n",
      "and another line\n",
      "\n"
     ]
    }
   ],
   "source": [
    "file = open(\"input.txt\", \"r\")\n",
    "print file.read()\n",
    "file.close()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "hello world in the input.txt file\n",
      "and another line\n",
      "2\n"
     ]
    }
   ],
   "source": [
    "import sys\n",
    "from Queue import Queue\n",
    "from threading import Thread\n",
    " \n",
    "lines = Queue(1)\n",
    "count = Queue(1)\n",
    " \n",
    "def read(file):\n",
    "    try:\n",
    "        for line in file:\n",
    "            lines.put(line)\n",
    "    finally:\n",
    "        lines.put(None)\n",
    "    print count.get()\n",
    "\n",
    "def write(file):\n",
    "    n = 0\n",
    "    while 1:\n",
    "        line = lines.get()\n",
    "        if line is None:\n",
    "            break\n",
    "        file.write(line)\n",
    "        n += 1\n",
    "    count.put(n)\n",
    "\n",
    "reader = Thread(target=read, args=(open('input.txt'),))\n",
    "writer = Thread(target=write, args=(sys.stdout,))\n",
    "reader.start()\n",
    "writer.start()\n",
    "reader.join()\n",
    "writer.join()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 57: Get Rich (Divide and Conquer) \n",
    "\n",
    "**Problem**: From the following list of prices, taken from 10 consecutive market sessions, write a function that take as input that prices and return the maximum possible profit, selecting the buy and sell prices from inside the list.\n",
    "\n",
    "prices = [10, 1, 15, 3, 9, 12, 2, 6, 12, 8]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def profit(prices):\n",
    "    if len(prices)<= 1:\n",
    "        return 0\n",
    "    \n",
    "    midIndex = len(prices)/2\n",
    "    leftProfit = profit(prices[:midIndex])\n",
    "    rightProfit = profit(prices[midIndex:])\n",
    "    \n",
    "    buy = min(prices[:midIndex])\n",
    "    sell = max(prices[midIndex:])\n",
    "    midProfit = sell - buy\n",
    "    return max(leftProfit, rightProfit, midProfit)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "14"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "prices = [10, 1, 15, 3, 9, 12, 2, 6, 12, 8]\n",
    "profit(prices)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 58: Zero Sum - Linear\n",
    "\n",
    "**Problem**: Given an array of numbers, the continuous subsequences of that array where the sum of all its elements are zero"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import collections\n",
    " \n",
    "def ZeroSum(numbers):\n",
    "    \"\"\"Yields a continuous subsequence that sums up to zero.\"\"\"\n",
    "    # Mapping of running sum to indexes it occurs.\n",
    "    running_sums = collections.defaultdict(list)\n",
    "    total = 0 # Adds a initial sum of 0 at the beginning of array.\n",
    "    running_sums[total].append(-1)\n",
    "    for i in range(len(numbers)):\n",
    "        total += numbers[i]\n",
    "        running_sums[total].append(i)\n",
    "    for total, indexes in running_sums.iteritems():\n",
    "        if len(indexes) <= 1:\n",
    "            continue\n",
    "        prev = None\n",
    "        for n in indexes:\n",
    "            if prev is None:\n",
    "                prev = n\n",
    "            else:\n",
    "                yield numbers[prev+1:n+1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[3, -1, -2], [-1, -2, 5, -2]]"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "list(ZeroSum([-7, 3, -1, -2, 5, -2]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 59: A number in a range\n",
    "\n",
    "**Problem**: Build a method inside a Range class, that allow to check if a number belongs to this range"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Range:\n",
    "    def __init__(self, a, b=None, step=1):\n",
    "        if b is not None:\n",
    "            self.start = a\n",
    "            self.end = b\n",
    "        else:\n",
    "            self.start = 0\n",
    "            self.end = a\n",
    "        self.step = step\n",
    "\n",
    "    def __contains__(self, num):\n",
    "        return self.start <= num < self.end and not (num - self.start) % self.step"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[5, 12, 19, 26]"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "range(5,30,7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "5 in Range(5, 30, 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "15 in Range(5, 30, 7)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 60: A callable class\n",
    "\n",
    "**Problem**: Write a class that act as a simple counter variable every time that that is called, using the special function `__call__` "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class CallCounter:\n",
    "    def __init__(self):\n",
    "        self.count = 0\n",
    "    def __call__(self, *args, **kwargs):\n",
    "        self.count += 1\n",
    "        return 'Number of calls so far: %s' % self.count\n",
    "    def reset(self):\n",
    "        self.count = 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'Number of calls so far: 1'"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "counter = CallCounter()\n",
    "counter()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'Number of calls so far: 3'"
      ]
     },
     "execution_count": 28,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "counter()\n",
    "counter()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'Number of calls so far: 4'"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "counter()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 61: Self-caching properties\n",
    "\n",
    "**Problem**: Build a class that include the special methods that allows to accessing the object's namespace dictionary, such as `__getattr__()` and `__setattr__()` "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class myobject(object):\n",
    "    def __getattr__(self, name):\n",
    "        try:\n",
    "            return self.__dict__[name]\n",
    "        except KeyError:\n",
    "            raise AttributeError('%s object has no attribute named %s' % (\n",
    "                self.__class__.__module__, name))\n",
    "\n",
    "    def __setattr__(self, name, value):\n",
    "        self.__dict__[name] = value\n",
    "\n",
    "    def __delattr__(self, name):\n",
    "        try:\n",
    "            del self.__dict__[name]\n",
    "        except KeyError:\n",
    "            raise AttributeError('%s object has no attribute named %s' % (\n",
    "                self.__class__.__module__, name))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "<__main__.myobject instance at 0x106238488>\n"
     ]
    }
   ],
   "source": [
    "me = myobject()\n",
    "print me"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 62: Fibonacci sequence in one line\n",
    "\n",
    "**Problem**: Write in one line the code to estimate the Fibonacci sequence, of lenght 10. \n",
    "\n",
    "**Clue**: use map-reduce "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from functools import reduce"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "list(map(lambda n : reduce(lambda x,n : [x[1], x[0] + x[1]], range(n), [0,1])[0], range(10)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 63: Run 1000 times an American Roulette in one line of code\n",
    "\n",
    "**Problem**: Write a line of code that simulate 1000 times, and count the results, of an American roulette (18 red, 18 black and 2 green) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import Counter\n",
    "from random import choice"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Counter({'black': 479, 'green': 55, 'red': 465})"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    " Counter([choice(('red '*18).split()+('black '*18).split()+('green '*2).split()) for i in range(999)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Counter({'black': 481, 'green': 58, 'red': 460})"
      ]
     },
     "execution_count": 34,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Another version, more elegant:\n",
    "\n",
    "Counter([choice(list(Counter(red=18, black=18, green=2).elements()))for i in range(999)])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 64: Probability of 5 or more heads from 10 spins of a biased coin\n",
    "\n",
    "**Problem**: Estimate by simulation the probability of getting more that 5 heads throwing 10 times a biased coin (60% head vs. 40% tails)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 72,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from collections import Counter\n",
    "from random import choice"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 73,
   "metadata": {},
   "outputs": [],
   "source": [
    "experiment = lambda : Counter([choice(list(Counter(head=6, tails=4).elements()))for i in range(9)])['head']>=5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 74,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.73485"
      ]
     },
     "execution_count": 74,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "n = 100000\n",
    "[experiment() for i in range(n)].count(True)/float(n)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 65: Empirical Estimation of Intervals of Confidence for a mean\n",
    "\n",
    "**Problem**: Estimate by Bootstraping (random sampling with replacement) 90% intervals of confidence of a mean."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 94,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Actual mean:50.0\n",
      "90% Interval of confidence for the mean: 45.21,54.75\n"
     ]
    }
   ],
   "source": [
    "from random import choice\n",
    "import numpy as np\n",
    "\n",
    "def bootstrap(data):\n",
    "    return [choice(data) for i in range(len(data))]\n",
    "\n",
    "data = range(101)\n",
    "n = 10000\n",
    "means = sorted([np.mean(bootstrap(data)) for i in range(n)])\n",
    "\n",
    "print 'Actual mean:{}'.format(np.mean(data))\n",
    "print '90% Interval of confidence for the mean: {0:.2f},{1:.2f}'.format(means[500], means[-500])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 66: Single Server Queue simulation\n",
    "\n",
    "**Problem**: Estimate the average waiting time in a queue that increase 1 client every 5.5 seconds and the service time in average is 5 sec. with 0.5 standard deviation"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 118,
   "metadata": {},
   "outputs": [],
   "source": [
    "from random import gauss, expovariate\n",
    "from numpy import mean, median, std"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 119,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "average_arrival_interval = 5.5\n",
    "average_service_time = 5.0\n",
    "stdev_service_time = 0.5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 120,
   "metadata": {},
   "outputs": [],
   "source": [
    "num_waiting = 0\n",
    "arrivals = []\n",
    "starts = []\n",
    "arrival = service_end = 0.0\n",
    "\n",
    "for i in range(20000):\n",
    "\n",
    "    if arrival <= service_end:\n",
    "        num_waiting+=1\n",
    "        arrival += expovariate(1./average_arrival_interval)\n",
    "        arrivals.append(arrival)\n",
    "    else:\n",
    "        num_waiting-=1\n",
    "        service_start = service_end if num_waiting else arrival\n",
    "        service_time = gauss(average_service_time, stdev_service_time)\n",
    "        service_end = service_start + service_time\n",
    "        starts.append(service_start)\n",
    "        \n",
    "        \n",
    "waits = [start - arrival for arrival, start in zip(arrivals, starts)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 125,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Mean wait: 23.3\n",
      "Median wait: 14.5\n",
      "Max. wait: 149.7\n"
     ]
    }
   ],
   "source": [
    "print 'Mean wait: {0:.1f}'.format(mean(waits))\n",
    "print 'Median wait: {0:.1f}'.format(median(waits))\n",
    "print 'Max. wait: {0:.1f}'.format(max(waits))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 67: Day of the last Monday?\n",
    "\n",
    "**Problem**: Estimate the day-month-year of the last monday "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [],
   "source": [
    "from datetime import datetime, timedelta\n",
    "\n",
    "weekdays = ['Monday', 'Tuesday', 'Wednesday', 'Thursday', 'Friday', 'Saturday', 'Sunday']\n",
    "\n",
    "def get_previous_byday(dayname, start_date=None):\n",
    "    if start_date is None:\n",
    "        start_date = datetime.today()\n",
    "    day_num = start_date.weekday()\n",
    "    day_num_target = weekdays.index(dayname)\n",
    "    days_ago = (7 + day_num - day_num_target) % 7 \n",
    "    if days_ago == 0:\n",
    "        days_ago = 7\n",
    "    target_date = start_date - timedelta(days=days_ago)\n",
    "    print \"Day: {0}, Month: {1}, Year: {2}\".format(target_date.day, target_date.month, target_date.year)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Day: 12, Month: 2, Year: 2018\n"
     ]
    }
   ],
   "source": [
    "target_date = get_previous_byday('Monday')"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python [default]",
   "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": 2
}