{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Python: Intro/Misc\n",
    "\n",
    "XKCD about python:\n",
    "![Python](http://imgs.xkcd.com/comics/python.png)\n",
    "\n",
    "www.python.org about python:\n",
    "> Python is a programming language that lets you work more quickly and integrate your systems more effectively.\"\n",
    "\n",
    "\n",
    "Wikipedia about python:\n",
    "> Python is a widely used general-purpose, high-level programming language. Its design philosophy emphasizes code readability, and its syntax allows programmers to express concepts in fewer lines of code than would be possible in languages such as C. The language provides constructs intended to enable clear programs on both a small and large scale.\n",
    ">\n",
    "> Python supports multiple programming paradigms, including object-oriented, imperative and functional programming or procedural styles. It features a dynamic type system and automatic memory management and has a large and comprehensive standard library.\"\n",
    "\n",
    "\n",
    "Notes:\n",
    "- python2 vs python3: be aware! Use **python 2.7** for the exercises\n",
    "- best use [anaconda 2.7](https://www.continuum.io/downloads) as your python distribution\n",
    "- INDENTATION: use **4 spaces**, <font color=\"red\">*do not use tabs*!</font>\n",
    "- Python is different from Java: you don't need classes\n",
    "- [PEP8](http://legacy.python.org/dev/peps/pep-0008/) style guide\n",
    "- Interactive and REPL: python, ipython, bpython\n",
    "- [PyCharm](https://www.jetbrains.com/pycharm/)\n",
    "- help() and ?\n",
    "- type() and dir()\n",
    "- IPython notebook"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "help(range)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "type?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Python: Control Flow"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# if/elif/else\n",
    "a = 6\n",
    "if a > 5:\n",
    "    print \"bigger than 5\"\n",
    "elif a == 5:\n",
    "    print \"FIVE\"\n",
    "else:\n",
    "    print 'something else: ' + str(a)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "a = 4\n",
    "a = \"bigger\" if a > 3 else \"smaller\"\n",
    "a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# Java:\n",
    "# int n = 7\n",
    "# for (int i = 2; i < n; i++) {\n",
    "#   System.out.println(i);\n",
    "# }\n",
    "n = 7\n",
    "for i in range(2,n):\n",
    "    print i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "range(2,10,2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "movies = [\"Her\", \"Moon\", \"Pacific Rim\", \"Robot and Frank\"]\n",
    "print len(movies)\n",
    "for movie in movies:\n",
    "    print movie"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "for i, movie in enumerate(movies):\n",
    "    print i, movie"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "for i, movie in zip(range(len(movies)), movies):\n",
    "    print i, movie"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "print enumerate(movie)\n",
    "print zip(range(len(movies)), movies)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# while\n",
    "i = 0\n",
    "while True:\n",
    "    while True:\n",
    "        print i\n",
    "        i += 1\n",
    "        if i > 5:\n",
    "            break\n",
    "    print \"outer\"\n",
    "    break"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Python: Data Structures"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# numbers\n",
    "print type(1)\n",
    "print type(.1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Strings\n",
    "'this is a string'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "\"this is also a string\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "\"\"\"This is a string as well\n",
    "\n",
    "A multi-line string\n",
    "\"\"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# list\n",
    "i = [1, 2, 3, 4]\n",
    "print list(i)\n",
    "print [2, 4]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "['something', 5, 5.5]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "movies = [\"Her\", \"Moon\", \"Pacific Rim\", \"Robot and Frank\"]\n",
    "movies"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "movies.append(\"Wall-E\")\n",
    "movies"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "movies = movies + [\"Nummer 5\", \"I, Robot\", \"2001\"]\n",
    "movies"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "import copy\n",
    "copy.deepcopy(movies)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# slicing\n",
    "print movies\n",
    "print movies[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "print movies[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "print movies[0:2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "print movies[:2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "print movies[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "print movies[-2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "print movies[3::2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# Dictionaries\n",
    "print dict()\n",
    "print {}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "d = {\"Her\": 4,\n",
    "     \"Moon\": 5,\n",
    "     \"Pacific Rim\": 5,\n",
    "     \"Robot and Frank\": 4.,\n",
    "}\n",
    "d"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "d[\"Her\"]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "\"Her\" in movies"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "d.keys()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "type(d.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "for (key, value) in d.items():\n",
    "    print key, value"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# tuples\n",
    "3, 4"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "(3, 4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "type((3,4))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "t = 3, 4, 3\n",
    "print t[0]\n",
    "print t[1]\n",
    "print t[2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# set\n",
    "set([3, 0, -4, 15, 3, 2, 2, 1, 15])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## List Comprehension Example"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "[i for i in range(10)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "[i*i for i in range(10)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "[i for i in range(10) if i % 2 == 0]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's implement [entropy function](http://en.wikipedia.org/wiki/Entropy_%28information_theory%29#Definition)\n",
    "$$\n",
    "    H(X) = - \\sum_i P(x_i) \\log P(x_i)\n",
    "$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "from math import log\n",
    "\n",
    "X = [.5, .5]\n",
    "\n",
    "def entropy(X):\n",
    "    return -sum([x * log(x) for x in X])\n",
    "\n",
    "\n",
    "entropy(X)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Compute Pi using the [Wallis product](http://en.wikipedia.org/wiki/Wallis_product):\n",
    "$$\n",
    "\\pi \\approx 2 \\prod_{i=1}^{\\infty} \\frac{4i^2}{4i^2 -1}\n",
    "$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import operator\n",
    "\n",
    "def prod(iterable):\n",
    "    return reduce(operator.mul, iterable, 1)\n",
    "\n",
    "\n",
    "def pi(n):\n",
    "    # a**b = a to power b\n",
    "    return 2 * prod([(4 * i**2)/(4 * i**2 - 1) for i in range(1, n)])\n",
    "\n",
    "\n",
    "print pi(2), pi(10), pi(100)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Python: Functions and Classes"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def square(x):\n",
    "    \"\"\"Documentation of square.\"\"\"     \n",
    "    return x * x\n",
    "\n",
    "    \n",
    "square(5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "class Node(object):\n",
    "    \"\"\"Doc of the class.\n",
    "    \n",
    "    Sometimes the constructor is documented here.\n",
    "    \n",
    "    \"\"\"\n",
    "    def __init__(self, value=None, left=None, right=None):\n",
    "        self.value = value\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "    \n",
    "    def cut(self):\n",
    "        \"\"\"Doc of the function cut.\"\"\"\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "\n",
    "        \n",
    "tree = Node(\"lecture\", Node(\"python\"), Node(\"git\", Node(\"ki\")))\n",
    "print tree\n",
    "print tree.value\n",
    "print tree.right.left.value"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "type(None)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "class Node(object):\n",
    "    def __init__(self, value=None, left=None, right=None):\n",
    "        self.value = value\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "    \n",
    "    def cut(self):\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "        \n",
    "    def children(self):\n",
    "        return self.left, self.right\n",
    "    \n",
    "    def __str__(self):\n",
    "        return 'useless str method'\n",
    "        \n",
    "tree = Node(\"lecture\", Node(\"python\"), Node(\"git\"))\n",
    "print tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Doctest and Unittests"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "%load fib.py"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# executing the doctests\n",
    "!python -m doctest -v fib.py"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "%load test_fib.py"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "!python test_fib.py"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "!python -m unittest discover -v"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Python: Misc\n",
    "- [PyCharm](https://www.jetbrains.com/pycharm/)\n",
    "- IPython notebook; [example](http://nbviewer.ipython.org/github/CamDavidsonPilon/Probabilistic-Programming-and-Bayesian-Methods-for-Hackers/blob/master/Chapter1_Introduction/Chapter1.ipynb)\n",
    "- Libraries: numpy and matplotlib"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "np.zeros((3, 3))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "A = np.ones((3, 3))\n",
    "B = np.random.random((3, 3))\n",
    "A + B"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "A * B  # element wise multiplication"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "A.dot(B)  # matrix multiplication\n",
    "np.dot(A, B) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "x = np.matrix( ((1,2), (5, -1)) )\n",
    "y = np.matrix( ((1,2), (5, -1)) )\n",
    "\n",
    "x * y"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "%matplotlib inline\n",
    "import matplotlib.pyplot as plt\n",
    "plt.matshow(A);\n",
    "plt.matshow(B);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Exercises\n",
    "These exercises are meant as feedback for you. You should be able to use python to solve the exercises. You could also try and solve some old *\"Datenstrukturen und Algorithmen\" exercises*.\n",
    "\n",
    "**Again, if you have problems, ASK ME NOW**, (or see me after one of the tutorials).\n",
    "\n",
    "- Write an recursive version of the fibbonacci function that uses memoization.\n",
    "- Write an iterative version of the fibbonacci function.\n",
    "- Write a version that uses tuples (`a, b = b, a+b`)\n",
    "\n",
    "\n",
    "## Project Euler\n",
    "The exercises are taken from [project euler](https://projecteuler.net/)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "\"\"\"\n",
    "Project Euler Problem #1\n",
    "=========================\n",
    "\n",
    "If we list all the natural numbers below 10 that are multiples of 3 or 5,\n",
    "we get 3, 5, 6 and 9. The sum of these multiples is 23.\n",
    "\n",
    "Find the sum of all the multiples of 3 or 5 below 1000.\n",
    "\"\"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "\"\"\"\n",
    "Project Euler Problem #2\n",
    "=========================\n",
    "\n",
    "Each new term in the Fibonacci sequence is generated by adding the\n",
    "previous two terms. By starting with 1 and 2, the first 10 terms will be:\n",
    "\n",
    "                  1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...\n",
    "\n",
    "Find the sum of all the even-valued terms in the sequence which do not\n",
    "exceed four million.\n",
    "\"\"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "\"\"\"\n",
    "Project Euler Problem #4\n",
    "=========================\n",
    "\n",
    "A palindromic number reads the same both ways. The largest palindrome made\n",
    "from the product of two 2-digit numbers is 9009 = 91 * 99.\n",
    "\n",
    "Find the largest palindrome made from the product of two 3-digit numbers.\n",
    "\"\"\""
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}