david_stutz_deepmind.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#variables\n",
    "#control\n",
    "#functions\n",
    "#classes\n",
    "#errors\n",
    "#built-functions\n",
    "#built-data\n",
    "#patterns\n",
    "#exercises"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Variables and Data Types <a id=\"variables\"></a>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Start with letter or underscore; can contain `[a-zA-Z_0-9]`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 111,
   "metadata": {},
   "outputs": [
    {
     "ename": "SyntaxError",
     "evalue": "invalid syntax (<ipython-input-111-b29d97cf0e61>, line 1)",
     "output_type": "error",
     "traceback": [
      "\u001b[0;36m  File \u001b[0;32m\"<ipython-input-111-b29d97cf0e61>\"\u001b[0;36m, line \u001b[0;32m1\u001b[0m\n\u001b[0;31m    1x = 1\u001b[0m\n\u001b[0m     ^\u001b[0m\n\u001b[0;31mSyntaxError\u001b[0m\u001b[0;31m:\u001b[0m invalid syntax\n"
     ]
    }
   ],
   "source": [
    "1x = 1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Keywords forbidden!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 114,
   "metadata": {},
   "outputs": [
    {
     "ename": "SyntaxError",
     "evalue": "invalid syntax (<ipython-input-114-0251f39d4826>, line 1)",
     "output_type": "error",
     "traceback": [
      "\u001b[0;36m  File \u001b[0;32m\"<ipython-input-114-0251f39d4826>\"\u001b[0;36m, line \u001b[0;32m1\u001b[0m\n\u001b[0;31m    class = 1\u001b[0m\n\u001b[0m          ^\u001b[0m\n\u001b[0;31mSyntaxError\u001b[0m\u001b[0;31m:\u001b[0m invalid syntax\n"
     ]
    }
   ],
   "source": [
    "class = 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 112,
   "metadata": {},
   "outputs": [],
   "source": [
    "_x = 1\n",
    "__x = 1\n",
    "X = 1\n",
    "_X = 1\n",
    "x1 = 1\n",
    "x_ = 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "int"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "x = 1 # every variable has identity and type"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "94629651431872"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "id(x)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "int"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "type(x)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "type"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "type(type(x)) # type itself has a type"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "<class 'int'>\n",
      "<class 'float'>\n",
      "<class 'type'>\n",
      "<class 'str'>\n",
      "<class 'NoneType'>\n",
      "<class 'ellipsis'>\n",
      "<class 'NotImplementedType'>\n"
     ]
    }
   ],
   "source": [
    "print(type(1))\n",
    "print(type(1.))\n",
    "print(type(bool))\n",
    "print(type(None))\n",
    "print(type(...))\n",
    "print(type(NotImplemented))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Immutable sequences:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "<class 'str'>\n",
      "<class 'tuple'>\n",
      "<class 'bytes'>\n"
     ]
    }
   ],
   "source": [
    "print(type('test'))\n",
    "print(type((1, 2)))\n",
    "print(type(b'test'))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "ename": "TypeError",
     "evalue": "'str' object does not support item assignment",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mTypeError\u001b[0m                                 Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-7-5641c1706352>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m\u001b[0m\n\u001b[1;32m      1\u001b[0m \u001b[0mx\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0;34m'test'\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 2\u001b[0;31m \u001b[0mx\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;36m0\u001b[0m\u001b[0;34m]\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0;34m'a'\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m      3\u001b[0m \u001b[0mx\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;31mTypeError\u001b[0m: 'str' object does not support item assignment"
     ]
    }
   ],
   "source": [
    "x = 'test'\n",
    "x[0] = 'a'\n",
    "x"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Mutable:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "<class 'list'>\n",
      "<class 'bytearray'>\n"
     ]
    }
   ],
   "source": [
    "print(type([1]))\n",
    "print(type(bytearray(b'abs')))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Immutable"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "All types except `list`, `dict` and `set` are immutable."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "94629651431872\n",
      "94629651431904\n"
     ]
    }
   ],
   "source": [
    "x = 1\n",
    "print(id(x))\n",
    "x += 1\n",
    "print(id(x))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Pointers"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Immutable objects are not pointers; all other objects are; everything is an object:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n",
      "True\n",
      "94022425039296\n"
     ]
    }
   ],
   "source": [
    "print(isinstance(1, object))\n",
    "print(isinstance(bool, object))\n",
    "# ...\n",
    "x = 1\n",
    "print(id(x))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Conversion to Bool"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "def check_conversion(value):\n",
    "    print('True' if value else 'False')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n",
      "False\n",
      "True\n",
      "False\n",
      "True\n",
      "False\n",
      "False\n",
      "True\n",
      "True\n",
      "True\n",
      "False\n",
      "True\n",
      "False\n",
      "True\n",
      "False\n"
     ]
    }
   ],
   "source": [
    "check_conversion('a')\n",
    "check_conversion('')\n",
    "check_conversion(1)\n",
    "check_conversion(0)\n",
    "check_conversion([1])\n",
    "check_conversion([])\n",
    "check_conversion(None)\n",
    "check_conversion(NotImplemented) # True!\n",
    "check_conversion(...) # True!\n",
    "check_conversion({1})\n",
    "check_conversion({})\n",
    "check_conversion((1))\n",
    "check_conversion(())\n",
    "check_conversion(b'0')\n",
    "check_conversion(b'')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Sets"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Bytes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Lists"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 81,
   "metadata": {},
   "outputs": [],
   "source": [
    "x = [1,2,3,4,5]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 82,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "6"
      ]
     },
     "execution_count": 82,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "x.append(6)\n",
    "x.pop() # Stack"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 83,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 2, 3, 4, 5]\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "[1, 4, 9, 16, 25]"
      ]
     },
     "execution_count": 83,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "x = [xi**2 for xi in x]\n",
    "x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 85,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 4, 9, 16, 25]"
      ]
     },
     "execution_count": 85,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "x = [1, 2, 3, 4, 5]\n",
    "x = list(map(lambda x: x**2, x))\n",
    "x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 94,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, 1, 2, 3, 4, 5]"
      ]
     },
     "execution_count": 94,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "x = [1, 2, 3, 4, 5]\n",
    "x.insert(0, 0)\n",
    "x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 96,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[2, 3, 4, 5]"
      ]
     },
     "execution_count": 96,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "x = [1, 2, 3, 4, 5]\n",
    "x.remove(1)\n",
    "x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 97,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 3, 4, 5]"
      ]
     },
     "execution_count": 97,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "x = [5, 4, 1, 3, 2]\n",
    "x.sort()\n",
    "x"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Dictionaries"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Implemented as hash tables in Python!**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Casting"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "1\n",
      "1.9\n",
      "True\n",
      "False\n"
     ]
    }
   ],
   "source": [
    "print(int(1.2))\n",
    "print(int(1.9))\n",
    "print(str(1.9))\n",
    "print(bool(1.9))\n",
    "print(bool(0.0))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [
    {
     "ename": "TypeError",
     "evalue": "'float' object is not iterable",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mTypeError\u001b[0m                                 Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-32-0cc1fb1ee87e>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m\u001b[0m\n\u001b[0;32m----> 1\u001b[0;31m \u001b[0mprint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mlist\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;36m1.2\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[0;31mTypeError\u001b[0m: 'float' object is not iterable"
     ]
    }
   ],
   "source": [
    "print(list(1.2)) # list, tuple, set need something iterable"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[97, 98, 115]\n"
     ]
    }
   ],
   "source": [
    "print(list(b'abs'))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "bytearray(b'abc')\n"
     ]
    }
   ],
   "source": [
    "print(bytearray(list(b'abc')))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "<class 'float'>\n"
     ]
    }
   ],
   "source": [
    "print(type(1 + 1.2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {},
   "outputs": [
    {
     "ename": "TypeError",
     "evalue": "unsupported operand type(s) for +: 'type' and 'int'",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mTypeError\u001b[0m                                 Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-49-609b5fbb010b>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m\u001b[0m\n\u001b[0;32m----> 1\u001b[0;31m \u001b[0mprint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mtype\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mbool\u001b[0m \u001b[0;34m+\u001b[0m \u001b[0;36m1\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;31m# Pythonw ill complain if it should not be done!\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m      2\u001b[0m \u001b[0mprint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mtype\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34mb'a'\u001b[0m \u001b[0;34m+\u001b[0m \u001b[0;36m1\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;31mTypeError\u001b[0m: unsupported operand type(s) for +: 'type' and 'int'"
     ]
    }
   ],
   "source": [
    "print(type(bool + 1)) # Pythonw ill complain if it should not be done!\n",
    "print(type(b'a' + 1))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Bits and Shits"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0b10001001\n",
      "00000000000000000000000010001001\n",
      "<class 'str'>\n"
     ]
    }
   ],
   "source": [
    "print(bin(137))\n",
    "print(bin(137)[2:].zfill(32))\n",
    "print(type(bin(137)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "137\n",
      "137\n"
     ]
    }
   ],
   "source": [
    "print(int(bin(137), 2))\n",
    "print(int(bin(137)[2:].zfill(32), 2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0x89\n",
      "137\n"
     ]
    }
   ],
   "source": [
    "print(hex(137))\n",
    "print(int(hex(137), 16))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 63,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0b10001001\n",
      "0b100010010 274\n",
      "0b1000100 68\n"
     ]
    }
   ],
   "source": [
    "print(bin(137))\n",
    "print(bin(137 << 1), int(bin(137 << 1), 2)) # shifts to the left!\n",
    "print(bin(137 >> 1), int(bin(137 >> 1), 2)) # shifts to the right!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 73,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "10001001\n",
      "b10001010\n",
      "-138\n",
      "10001001\n",
      "00000000\n",
      "01110110\n",
      "11111111\n"
     ]
    }
   ],
   "source": [
    "print(bin(137)[2:].zfill(8))\n",
    "print(bin(~137)[2:].zfill(8))\n",
    "print(~137)\n",
    "print(bin(137|0)[2:].zfill(8))\n",
    "print(bin(137&0)[2:].zfill(8))\n",
    "print(bin(137^255)[2:].zfill(8))\n",
    "print(bin(255)[2:].zfill(8))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Operations"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Operators:\n",
    "* Arithmetic, `+ - * / **`\n",
    "* Comparisons, `> < >= <= ==`\n",
    "* Bit-Wise, `| & ^`\n",
    "* Boolean, `and or not`\n",
    "* Membership, `is in`\n",
    "* **There is no `++ --`**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Priority:\n",
    "* `**` stronger on left, not on right\n",
    "* all comparisons equal priority, less than arithmetic"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Control Flow  <a id=\"control\"></a>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* `if for while` statements should be clear\n",
    "* there is no `do while` \n",
    "* there is no `switch`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 100,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 2, 4, 5]\n"
     ]
    }
   ],
   "source": [
    "# Iterating over copies\n",
    "x = [1, 2, 3, 4, 5]\n",
    "for xi in x.copy():\n",
    "    if xi == 3:\n",
    "        x.remove(xi)\n",
    "print(x)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 105,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "complete\n"
     ]
    }
   ],
   "source": [
    "for x in range(10):\n",
    "    continue\n",
    "else:\n",
    "    print('complete')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 104,
   "metadata": {},
   "outputs": [],
   "source": [
    "for x in range(10):\n",
    "    if x == 5:\n",
    "        break\n",
    "else:\n",
    "    print('complete')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Functions <a id=\"functions\"></a>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 110,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "<class 'function'>\n",
      "test\n",
      "None\n",
      "<code object test at 0x7fcaa81f8b70, file \"<ipython-input-110-5391932a6e37>\", line 1>\n"
     ]
    }
   ],
   "source": [
    "def test():\n",
    "    pass\n",
    "print(type(test))\n",
    "print(test.__name__)\n",
    "print(test.__doc__)\n",
    "print(test.__code__)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 118,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n"
     ]
    },
    {
     "ename": "TypeError",
     "evalue": "test() missing 1 required positional argument: 'x'",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mTypeError\u001b[0m                                 Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-118-00e4bee9bcc4>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m\u001b[0m\n\u001b[1;32m      2\u001b[0m     \u001b[0mprint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mx\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      3\u001b[0m \u001b[0mtest\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 4\u001b[0;31m \u001b[0mtest\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[0;31mTypeError\u001b[0m: test() missing 1 required positional argument: 'x'"
     ]
    }
   ],
   "source": [
    "def test(x):\n",
    "    print(x)\n",
    "test(1)\n",
    "test()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 119,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2\n",
      "1\n"
     ]
    }
   ],
   "source": [
    "def test(x=1):\n",
    "    print(x)\n",
    "test(2)\n",
    "test()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 121,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n"
     ]
    }
   ],
   "source": [
    "y = 1\n",
    "def test(x=y):\n",
    "    print(x)\n",
    "y = 2\n",
    "test()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 125,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1]\n",
      "[1, 1]\n",
      "[1, 1, 1]\n"
     ]
    }
   ],
   "source": [
    "def test(x=[]): # default value only evaluated once!\n",
    "    x.append(1)\n",
    "    print(x)\n",
    "test()\n",
    "test()\n",
    "test()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 1 1\n",
      "1 2 2\n",
      "1 1 2\n",
      "1 2 1\n",
      "1 1 1\n"
     ]
    }
   ],
   "source": [
    "# Order only matters for positional arguments:\n",
    "def test(x, y=1, z=1):\n",
    "    print(x, y, z)\n",
    "test(1)\n",
    "test(1, 2, 2)\n",
    "test(1, z=2)\n",
    "test(1, y=2)\n",
    "test(x=1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "ename": "TypeError",
     "evalue": "test() got multiple values for argument 'x'",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m--------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mTypeError\u001b[0m                                Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-3-79578ced9695>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m\u001b[0m\n\u001b[0;32m----> 1\u001b[0;31m \u001b[0mtest\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mx\u001b[0m\u001b[0;34m=\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[0;31mTypeError\u001b[0m: test() got multiple values for argument 'x'"
     ]
    }
   ],
   "source": [
    "test(1, x=1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1,2,3,4\n",
      "1,2,3,4,a=1,c=3,b=2\n",
      "1,y=2,z=3\n"
     ]
    }
   ],
   "source": [
    "def test(x, *args, **kwargs): # *args is positional parameter list, **kwargs is dictionary\n",
    "    ret = str(x)\n",
    "    for arg in args:\n",
    "        ret += ',' + str(arg)\n",
    "    for key in kwargs:\n",
    "        ret += ',' + str(key) + '=' + str(kwargs[key])\n",
    "    print(ret)\n",
    "test(1, 2, 3, 4)\n",
    "test(1, 2, 3, 4, a=1, b=2, c=3)\n",
    "test(1, y=2, z=3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "ename": "TypeError",
     "evalue": "test() missing 1 required positional argument: 'x'",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m--------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mTypeError\u001b[0m                                Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-11-171943288b1c>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m\u001b[0m\n\u001b[0;32m----> 1\u001b[0;31m \u001b[0mtest\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0ma\u001b[0m\u001b[0;34m=\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mb\u001b[0m\u001b[0;34m=\u001b[0m\u001b[0;36m2\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mc\u001b[0m\u001b[0;34m=\u001b[0m\u001b[0;36m3\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[0;31mTypeError\u001b[0m: test() missing 1 required positional argument: 'x'"
     ]
    }
   ],
   "source": [
    "test(a=1, b=2, c=3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Requiring only positional or keyword arguments:\n",
    "\n",
    "**only Pyhon 3.8**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "ename": "SyntaxError",
     "evalue": "invalid syntax (<ipython-input-15-d6f72a50a4e4>, line 1)",
     "output_type": "error",
     "traceback": [
      "\u001b[0;36m  File \u001b[0;32m\"<ipython-input-15-d6f72a50a4e4>\"\u001b[0;36m, line \u001b[0;32m1\u001b[0m\n\u001b[0;31m    def only_arg(arg, /):\u001b[0m\n\u001b[0m                      ^\u001b[0m\n\u001b[0;31mSyntaxError\u001b[0m\u001b[0;31m:\u001b[0m invalid syntax\n"
     ]
    }
   ],
   "source": [
    "def only_arg(arg, /):\n",
    "    print(arg)\n",
    "def only_kwarg(*, arg):\n",
    "    print(arg)\n",
    "def combined(arg, /, standard, *, kwarg):\n",
    "    print(arg, standard, kwarg)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "ename": "NameError",
     "evalue": "name 'only_arg' is not defined",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m--------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mNameError\u001b[0m                                Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-16-af9dc33e9917>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m\u001b[0m\n\u001b[0;32m----> 1\u001b[0;31m \u001b[0monly_arg\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0marg\u001b[0m\u001b[0;34m=\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[0;31mNameError\u001b[0m: name 'only_arg' is not defined"
     ]
    }
   ],
   "source": [
    "only_arg(arg=1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "ename": "NameError",
     "evalue": "name 'only_kwarg' is not defined",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m--------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mNameError\u001b[0m                                Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-17-b30d8fb3c693>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m\u001b[0m\n\u001b[0;32m----> 1\u001b[0;31m \u001b[0monly_kwarg\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[0;31mNameError\u001b[0m: name 'only_kwarg' is not defined"
     ]
    }
   ],
   "source": [
    "only_kwarg(1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "ename": "NameError",
     "evalue": "name 'combined' is not defined",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m--------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mNameError\u001b[0m                                Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-18-52c335583a3d>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m\u001b[0m\n\u001b[0;32m----> 1\u001b[0;31m \u001b[0mcombined\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;36m2\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;36m3\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[0;31mNameError\u001b[0m: name 'combined' is not defined"
     ]
    }
   ],
   "source": [
    "combined(1, 2, 3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "ename": "NameError",
     "evalue": "name 'combined' is not defined",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m--------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mNameError\u001b[0m                                Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-19-8d3acec57771>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m\u001b[0m\n\u001b[0;32m----> 1\u001b[0;31m \u001b[0mcombined\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0marg\u001b[0m\u001b[0;34m=\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mstandard\u001b[0m\u001b[0;34m=\u001b[0m\u001b[0;36m2\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mkwarg\u001b[0m\u001b[0;34m=\u001b[0m\u001b[0;36m3\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[0;31mNameError\u001b[0m: name 'combined' is not defined"
     ]
    }
   ],
   "source": [
    "combined(arg=1, standard=2, kwarg=3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 2 3\n"
     ]
    }
   ],
   "source": [
    "def test(x, y, z=3):\n",
    "    print(x, y, z)\n",
    "values = {'x': 1, 'y': 2}\n",
    "test(**values)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Lambda Functions"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "4\n"
     ]
    }
   ],
   "source": [
    "def make_function(n):\n",
    "    return lambda x: x**n\n",
    "square = make_function(2)\n",
    "print(square(2))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Example:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, 1, 4, 9, 16, 25, 36, 49, 64, 81]"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "list(map(lambda x: x**2, range(10)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### functools"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 3 4\n"
     ]
    }
   ],
   "source": [
    "import functools\n",
    "def test(x, y=2, z=3):\n",
    "    print(x, y, z)\n",
    "test2 = functools.partial(test, 1)\n",
    "test2(3, 4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [
    {
     "ename": "TypeError",
     "evalue": "test() got multiple values for argument 'x'",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m--------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mTypeError\u001b[0m                                Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-28-18e0ae291813>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m\u001b[0m\n\u001b[1;32m      3\u001b[0m     \u001b[0mprint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mx\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0my\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mz\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      4\u001b[0m \u001b[0mtest2\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mfunctools\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mpartial\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mtest\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mx\u001b[0m\u001b[0;34m=\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;31m# Mirrors the behavior of positional/keyword arguments of test!\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 5\u001b[0;31m \u001b[0mtest2\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;36m3\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;36m4\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[0;31mTypeError\u001b[0m: test() got multiple values for argument 'x'"
     ]
    }
   ],
   "source": [
    "import functools\n",
    "def test(x, y=2, z=3):\n",
    "    print(x, y, z)\n",
    "test2 = functools.partial(test, x=1) # Mirrors the behavior of positional/keyword arguments of test!\n",
    "test2(3, 4)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Overloading"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Overoading (as in C++) not supported!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "2 2\n"
     ]
    }
   ],
   "source": [
    "def test(x, y=None):\n",
    "    if y is None:\n",
    "        print(x)\n",
    "    else:\n",
    "        print(x + 1, y)\n",
    "test(1)\n",
    "test(1, 2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Function Scopes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* modules, functions, classes, generator expressions and comprehensions define scopes\n",
    "* if, while, switch statements etc. do **not** define scopes!\n",
    "* there is no block scope!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 2\n"
     ]
    },
    {
     "ename": "NameError",
     "evalue": "name 'c' is not defined",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m--------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mNameError\u001b[0m                                Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-36-228d15ccc221>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m\u001b[0m\n\u001b[1;32m      5\u001b[0m     \u001b[0mc\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0;36m3\u001b[0m \u001b[0;31m## also global\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      6\u001b[0m \u001b[0mprint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0ma\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mb\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 7\u001b[0;31m \u001b[0mprint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mc\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[0;31mNameError\u001b[0m: name 'c' is not defined"
     ]
    }
   ],
   "source": [
    "a = 1 # global\n",
    "if a == 1:\n",
    "    b = 2 ## also global\n",
    "if a == 2:\n",
    "    c = 3 ## also global\n",
    "print(a, b)\n",
    "print(c)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n"
     ]
    }
   ],
   "source": [
    "def test():\n",
    "    print(a)\n",
    "test()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2\n",
      "1\n"
     ]
    }
   ],
   "source": [
    "def test():\n",
    "    a = 2 # will be a local (new) variable, not the global one\n",
    "    print(a)\n",
    "test()\n",
    "print(a)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2\n",
      "2\n"
     ]
    }
   ],
   "source": [
    "def test():\n",
    "    global a\n",
    "    a = 2\n",
    "    print(a)\n",
    "test()\n",
    "print(a)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### More on Scopes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Scopes:\n",
    "* local scope, searched first\n",
    "* scopes of enclosing functions, searched starting with the nearest enclosing scope\n",
    "* next-t-last scope contains current module's names\n",
    "* outermost scope contains built-in stuff"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 66,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "after local: test\n",
      "after nonlocal: nonlocal\n",
      "after global: nonlocal\n",
      "in global scope: global\n"
     ]
    }
   ],
   "source": [
    "def scope():\n",
    "    def test_local():\n",
    "        a = 'local' # local a\n",
    "    def test_nonlocal():\n",
    "        nonlocal a # the a defined in scope function\n",
    "        a = 'nonlocal'\n",
    "    def test_global():\n",
    "        global a\n",
    "        a = 'global' # the a defined on module/global level != nonlocal a\n",
    "    \n",
    "    a = 'test'\n",
    "    test_local()\n",
    "    print('after local: %s' % a)\n",
    "    test_nonlocal()\n",
    "    print('after nonlocal: %s' % a)\n",
    "    test_global()\n",
    "    print('after global: %s' % a)\n",
    "scope()\n",
    "print('in global scope: %s' % a)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Call by Reference or Value?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Python is call-by-assignment:\n",
    "* the parameter passed is a reference to an object, but the reference is passed by value\n",
    "* some data types are not mutable"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0\n"
     ]
    }
   ],
   "source": [
    "def change_int(i):\n",
    "    i = 1\n",
    "i = 0\n",
    "change_int(i)\n",
    "print(i)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 2, 3, 4, 5]\n"
     ]
    }
   ],
   "source": [
    "def change_list(l):\n",
    "    l.append(5)\n",
    "l = [1,2,3,4]\n",
    "change_list(l)\n",
    "print(l)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 2, 3, 4]\n"
     ]
    }
   ],
   "source": [
    "def change_list(l):\n",
    "    l = [5,6,7] # reference is a value and cannot be changed!\n",
    "l = [1,2,3,4]\n",
    "change_list(l)\n",
    "print(l)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Works for numpy arrays, too:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[1. 0.]\n",
      " [0. 0.]]\n"
     ]
    }
   ],
   "source": [
    "import numpy\n",
    "def change_array(a):\n",
    "    a[0,0] = 1\n",
    "a = numpy.zeros((2,2))\n",
    "change_array(a)\n",
    "print(a)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[0. 0.]\n",
      " [0. 0.]]\n"
     ]
    }
   ],
   "source": [
    "import numpy\n",
    "def change_array(a):\n",
    "    a = numpy.ones((2, 2))\n",
    "a = numpy.zeros((2,2))\n",
    "change_array(a)\n",
    "print(a)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Closures"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Hello\n"
     ]
    }
   ],
   "source": [
    "def test(msg):\n",
    "    def returned():\n",
    "        print(msg)\n",
    "    return returned\n",
    "msg = test('Hello')\n",
    "msg()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Generators"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "2\n",
      "3\n",
      "<generator object test at 0x7fb82f5344c0>\n",
      "1\n",
      "2\n",
      "3\n"
     ]
    },
    {
     "ename": "StopIteration",
     "evalue": "",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m--------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mStopIteration\u001b[0m                            Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-55-40bae186875d>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m\u001b[0m\n\u001b[1;32m     10\u001b[0m \u001b[0mprint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mnext\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mt\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     11\u001b[0m \u001b[0mprint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mnext\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mt\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 12\u001b[0;31m \u001b[0mprint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mnext\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mt\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[0;31mStopIteration\u001b[0m: "
     ]
    }
   ],
   "source": [
    "def test():\n",
    "    yield 1\n",
    "    yield 2\n",
    "    yield 3\n",
    "for t in test():\n",
    "    print(t)\n",
    "t = test()\n",
    "print(t)\n",
    "print(next(t))\n",
    "print(next(t))\n",
    "print(next(t))\n",
    "print(next(t))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "2\n",
      "4\n",
      "<generator object test at 0x7fb82f534150>\n",
      "1\n",
      "2\n",
      "4\n"
     ]
    },
    {
     "ename": "StopIteration",
     "evalue": "",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m--------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mStopIteration\u001b[0m                            Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-57-2fbf5d172c3e>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m\u001b[0m\n\u001b[1;32m     16\u001b[0m \u001b[0mprint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mnext\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mt\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     17\u001b[0m \u001b[0mprint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mnext\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mt\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 18\u001b[0;31m \u001b[0mprint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mnext\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mt\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[0;31mStopIteration\u001b[0m: "
     ]
    }
   ],
   "source": [
    "# Local variales are remembered between yields\n",
    "def test():\n",
    "    n = 1\n",
    "    yield n\n",
    "    \n",
    "    n += 1\n",
    "    yield n\n",
    "    \n",
    "    n += 2\n",
    "    yield n\n",
    "for t in test():\n",
    "    print(t)\n",
    "t = test()\n",
    "print(t)\n",
    "print(next(t))\n",
    "print(next(t))\n",
    "print(next(t))\n",
    "print(next(t))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0\n",
      "1\n",
      "2\n"
     ]
    }
   ],
   "source": [
    "def test():\n",
    "    for i in range(3):\n",
    "        yield i\n",
    "for t in test():\n",
    "    print(t)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 64,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0, 1, 2]\n",
      "<generator object <genexpr> at 0x7fb82f5346d0>\n",
      "[0, 1, 2]\n"
     ]
    }
   ],
   "source": [
    "# Comprehensions and generators:\n",
    "xs = [i for i in range(3)]\n",
    "gen = (i for i in range(3))\n",
    "print(xs)\n",
    "print(gen)\n",
    "print(list(gen))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 65,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0\n",
      "1\n",
      "2\n"
     ]
    }
   ],
   "source": [
    "for x in xs:\n",
    "    print(x)\n",
    "for x in gen:\n",
    "    print(x)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Classes <a id=\"classes\"></a>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Class objects:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 76,
   "metadata": {},
   "outputs": [],
   "source": [
    "class MyClass:\n",
    "    a = 1\n",
    "    def f(self):\n",
    "        print(a) # just to illustrate implicit usage of global\n",
    "        print(self.a) # self. required to avoid global"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 77,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "<bound method MyClass.f of <__main__.MyClass object at 0x7fb8a96f3240>>\n"
     ]
    }
   ],
   "source": [
    "# class objects support instantiation and attribute reference\n",
    "x = MyClass() # instantiation\n",
    "print(x.a) # attribute\n",
    "print(x.f) # attribute"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 78,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n"
     ]
    }
   ],
   "source": [
    "# data attributes do not need to be declared\n",
    "x.count = 1\n",
    "print(x.count)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 80,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "1\n",
      "2\n"
     ]
    }
   ],
   "source": [
    "# method objects\n",
    "x.f()\n",
    "xf = x.f\n",
    "xf()\n",
    "x.a = 2\n",
    "xf()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Class and Instance Variables"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Class variables = static members (as in C++):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 83,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "2\n",
      "1\n",
      "3\n"
     ]
    }
   ],
   "source": [
    "class MyClass:\n",
    "    a = 1 # note that this is immutable\n",
    "    \n",
    "    def __init__(self, b):\n",
    "        self.b = b\n",
    "x = MyClass(2)\n",
    "print(x.a)\n",
    "print(x.b)\n",
    "y = MyClass(3)\n",
    "print(y.a)\n",
    "print(y.b)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 84,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "2\n"
     ]
    }
   ],
   "source": [
    "# as a is immutable, it's instance specific\n",
    "y.a = 2\n",
    "print(x.a)\n",
    "print(y.a)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 87,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "2\n"
     ]
    }
   ],
   "source": [
    "# same if class variable is modified in class\n",
    "class MyClass:\n",
    "    a = 1\n",
    "    def change(self, a):\n",
    "        self.a = a\n",
    "x = MyClass()\n",
    "y = MyClass()\n",
    "y.change(2)\n",
    "print(x.a)\n",
    "print(y.a)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 88,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 2]\n",
      "[1, 2]\n"
     ]
    }
   ],
   "source": [
    "class MyClass:\n",
    "    a = [1] # not immutable, so shared\n",
    "    def append(self, b):\n",
    "        self.a.append(b)\n",
    "x = MyClass()\n",
    "y = MyClass()\n",
    "y.append(2)\n",
    "print(x.a)\n",
    "print(y.a)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 91,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2\n",
      "3\n",
      "2\n"
     ]
    }
   ],
   "source": [
    "# also note directly accessing class vairable without instance!\n",
    "class MyClass:\n",
    "    a = 1\n",
    "x = MyClass()\n",
    "MyClass.a = 2 # has an effect on x!!!\n",
    "y = MyClass()\n",
    "y.a = 3\n",
    "print(x.a)\n",
    "print(y.a)\n",
    "print(MyClass.a)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 96,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "f1\n",
      "f2\n"
     ]
    },
    {
     "ename": "TypeError",
     "evalue": "f2() missing 1 required positional argument: 'self'",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m--------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mTypeError\u001b[0m                                Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-96-e9fd9aab6486>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m\u001b[0m\n\u001b[1;32m     13\u001b[0m \u001b[0;31m# note that this doe snot work\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     14\u001b[0m \u001b[0my\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mf\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mf2\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 15\u001b[0;31m \u001b[0my\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mf\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[0;31mTypeError\u001b[0m: f2() missing 1 required positional argument: 'self'"
     ]
    }
   ],
   "source": [
    "# same behavior for functions\n",
    "def f1(self): # self important here!\n",
    "    print('f1')\n",
    "def f2(self):\n",
    "    print('f2')\n",
    "class MyClass:\n",
    "    f = f1\n",
    "x = MyClass()\n",
    "y = MyClass()\n",
    "y.f = lambda: print('f2')\n",
    "x.f()\n",
    "y.f()\n",
    "# note that this doe snot work\n",
    "y.f = f2\n",
    "y.f()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 97,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "f2\n",
      "f2\n"
     ]
    }
   ],
   "source": [
    "def f1(self): # self important here!\n",
    "    print('f1')\n",
    "def f2(self):\n",
    "    print('f2')\n",
    "class MyClass:\n",
    "    f = f1\n",
    "x = MyClass()\n",
    "MyClass.f = f2 # here the f2 definition if self works!\n",
    "y = MyClass()\n",
    "x.f()\n",
    "y.f()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Private Variables and Name Mangling"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Python does not support private or protected variables.**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 106,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n"
     ]
    }
   ],
   "source": [
    "class MyClass:\n",
    "    def __init__(self, a=1):\n",
    "        self._a = a\n",
    "x = MyClass()\n",
    "print(x._a)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 110,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['_MyClass__a', '__class__', '__delattr__', '__dict__', '__dir__', '__doc__', '__eq__', '__format__', '__ge__', '__getattribute__', '__gt__', '__hash__', '__init__', '__le__', '__lt__', '__module__', '__ne__', '__new__', '__reduce__', '__reduce_ex__', '__repr__', '__setattr__', '__sizeof__', '__str__', '__subclasshook__', '__weakref__']\n",
      "1\n"
     ]
    },
    {
     "ename": "AttributeError",
     "evalue": "'MyClass' object has no attribute '__a'",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m--------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mAttributeError\u001b[0m                           Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-110-4e6690c35468>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m\u001b[0m\n\u001b[1;32m      5\u001b[0m \u001b[0mprint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mdir\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mx\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      6\u001b[0m \u001b[0mprint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mx\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0m_MyClass__a\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 7\u001b[0;31m \u001b[0mprint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mx\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0m__a\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[0;31mAttributeError\u001b[0m: 'MyClass' object has no attribute '__a'"
     ]
    }
   ],
   "source": [
    "class MyClass:\n",
    "    def __init__(self, a=1):\n",
    "        self.__a = a\n",
    "x = MyClass()\n",
    "print(dir(x))\n",
    "print(x._MyClass__a)\n",
    "print(x.__a)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 116,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['_MyClass__f', '__class__', '__delattr__', '__dict__', '__dir__', '__doc__', '__eq__', '__format__', '__ge__', '__getattribute__', '__gt__', '__hash__', '__init__', '__le__', '__lt__', '__module__', '__ne__', '__new__', '__reduce__', '__reduce_ex__', '__repr__', '__setattr__', '__sizeof__', '__str__', '__subclasshook__', '__weakref__', 'f']\n",
      "f\n",
      "f\n",
      "['_MyClass__f', '__class__', '__delattr__', '__dict__', '__dir__', '__doc__', '__eq__', '__format__', '__ge__', '__getattribute__', '__gt__', '__hash__', '__init__', '__le__', '__lt__', '__module__', '__ne__', '__new__', '__reduce__', '__reduce_ex__', '__repr__', '__setattr__', '__sizeof__', '__str__', '__subclasshook__', '__weakref__', 'f']\n",
      "specific f\n",
      "f\n"
     ]
    }
   ],
   "source": [
    "class MyClass:\n",
    "    def f(self):\n",
    "        print('f')\n",
    "    __f = f\n",
    "class MySpecificClass(MyClass):\n",
    "    def f(self):\n",
    "        print('specific f')\n",
    "x = MyClass()\n",
    "#print(dir(x))\n",
    "x.f()\n",
    "x._MyClass__f()\n",
    "x = MySpecificClass()\n",
    "#print(dir(x))\n",
    "x.f()\n",
    "x._MyClass__f()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Inheritance"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 104,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n",
      "True\n",
      "False\n",
      "False\n"
     ]
    }
   ],
   "source": [
    "# checking inheritance\n",
    "print(isinstance(int, object))\n",
    "print(issubclass(bool, int))\n",
    "print(issubclass(int, bool))\n",
    "# that does not work with type\n",
    "print(type(bool) == int)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 103,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2 3\n"
     ]
    }
   ],
   "source": [
    "class MyClass:\n",
    "    a = 1\n",
    "    def __init__(self, b):\n",
    "        self.b = b\n",
    "class MySpecificClass(MyClass):\n",
    "    a = 2 # overwrites above\n",
    "    def __init__(self, b): # overwrites bove\n",
    "        self.b = b + 1\n",
    "x = MySpecificClass(2)\n",
    "print(x.a, x.b)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Structs"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Option A"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 119,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2 2 3\n"
     ]
    }
   ],
   "source": [
    "class Struct:\n",
    "    x = 1\n",
    "    y = 2\n",
    "    z = 3\n",
    "s = Struct()\n",
    "s.x = 2\n",
    "print(s.x, s.y, s.z)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Option B (Tuples)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 122,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 2 3\n"
     ]
    }
   ],
   "source": [
    "from collections import namedtuple\n",
    "Struct = namedtuple('Struct', 'x y z')\n",
    "s = Struct(1, 2, 3)\n",
    "print(s.x, s.y, s.z)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Option C (Python 3.7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 123,
   "metadata": {},
   "outputs": [
    {
     "ename": "SyntaxError",
     "evalue": "invalid syntax (<ipython-input-123-9c2429057b32>, line 3)",
     "output_type": "error",
     "traceback": [
      "\u001b[0;36m  File \u001b[0;32m\"<ipython-input-123-9c2429057b32>\"\u001b[0;36m, line \u001b[0;32m3\u001b[0m\n\u001b[0;31m    x: float = 0\u001b[0m\n\u001b[0m     ^\u001b[0m\n\u001b[0;31mSyntaxError\u001b[0m\u001b[0;31m:\u001b[0m invalid syntax\n"
     ]
    }
   ],
   "source": [
    "@dataclass\n",
    "class Struct:\n",
    "    x: float = 0\n",
    "    y: float = 1\n",
    "    z: float = 2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Enums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 124,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "E.x E.y E.z\n"
     ]
    }
   ],
   "source": [
    "from enum import Enum\n",
    "E = Enum('E', 'x y z')\n",
    "print(E.x, E.y, E.z)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Decorators"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 126,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2\n",
      "2\n",
      "2\n"
     ]
    }
   ],
   "source": [
    "class MyClass:\n",
    "    def __init__(self, a):\n",
    "        self.a = a\n",
    "    @classmethod\n",
    "    def from_b(cls, b):\n",
    "        return cls(b - 1)\n",
    "    @staticmethod\n",
    "    def a_from_b(b):\n",
    "        return b - 1\n",
    "x = MyClass(2)\n",
    "y = MyClass.from_b(3)\n",
    "print(x.a)\n",
    "print(y.a)\n",
    "print(MyClass.a_from_b(3))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 132,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3\n",
      "3 4\n"
     ]
    }
   ],
   "source": [
    "class MyClass:\n",
    "    def __init__(self, a):\n",
    "        self.a = a\n",
    "    @property\n",
    "    def b(self):\n",
    "        return self.a + 1\n",
    "    @b.setter\n",
    "    def b(self, b):\n",
    "        self.a = b - 1\n",
    "    @b.deleter\n",
    "    def b(self):\n",
    "        del self.a\n",
    "x = MyClass(2)\n",
    "print(x.b)\n",
    "x.b = 4\n",
    "print(x.a, x.b)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Abstract Classes and Interfaces"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**There are no explicit abstract classes and interfaces!**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 139,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "error\n",
      "f\n"
     ]
    }
   ],
   "source": [
    "class MyAbstractClass:\n",
    "    def f(self):\n",
    "        raise NotImplementedError\n",
    "class MyClass:\n",
    "    def f(self):\n",
    "        print('f')\n",
    "x = MyAbstractClass()\n",
    "try:\n",
    "    x.f()\n",
    "except NotImplementedError as e:\n",
    "    print('error')\n",
    "y = MyClass()\n",
    "y.f()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Multiple Inheritance"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 143,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "2\n",
      "1 2\n"
     ]
    }
   ],
   "source": [
    "class MyParent:\n",
    "    def __init__(self, a):\n",
    "        self.a = a\n",
    "class MyChild1(MyParent):\n",
    "    def __init__(self, a):\n",
    "        self.a = a + 1\n",
    "class MyChild2(MyParent):\n",
    "    def __init__(self, a, b):\n",
    "        super(MyChild2, self).__init__(a)\n",
    "        self.b = b\n",
    "x = MyParent(1)\n",
    "print(x.a)\n",
    "y = MyChild1(1)\n",
    "print(y.a)\n",
    "z = MyChild2(1, 2)\n",
    "print(z.a, z.b)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 145,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "f\n",
      "g\n"
     ]
    }
   ],
   "source": [
    "class MyParent:\n",
    "    def __init__(self, a):\n",
    "        self.a = a\n",
    "class MyMixin1:\n",
    "    def f(self):\n",
    "        print('f')\n",
    "class MyMixin2:\n",
    "    def g(self):\n",
    "        print('g')\n",
    "class MyChild(MyParent,MyMixin1,MyMixin2):\n",
    "    pass\n",
    "x = MyChild(1)\n",
    "print(x.a)\n",
    "x.f()\n",
    "x.g()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 146,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "doing A's stuff\n",
      "doing B's stuff\n",
      "doing A's stuff\n",
      "doing C's stuff\n",
      "doing D's stuff\n"
     ]
    }
   ],
   "source": [
    "class A(object):\n",
    "    def do_your_stuff(self):\n",
    "        print(\"doing A's stuff\")\n",
    "\n",
    "class B(A):\n",
    "    def do_your_stuff(self):\n",
    "        A.do_your_stuff(self)\n",
    "        print(\"doing B's stuff\")\n",
    "\n",
    "class C(A):\n",
    "    def do_your_stuff(self):\n",
    "        A.do_your_stuff(self)\n",
    "        print(\"doing C's stuff\")\n",
    "\n",
    "class D(B,C):\n",
    "    def do_your_stuff(self):\n",
    "        B.do_your_stuff(self)\n",
    "        C.do_your_stuff(self)\n",
    "        print(\"doing D's stuff\")\n",
    "d = D()\n",
    "d.do_your_stuff()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Avoiding Inheritence"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Inheritance not required for polymorphism!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Magic Classes"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 147,
   "metadata": {},
   "outputs": [],
   "source": [
    "class MyClass:\n",
    "    def __init__(self, a):\n",
    "        self.a = a\n",
    "        print('__init__')\n",
    "    # includes __eq__, __ne__, __lt__, __gt__ etc.\n",
    "    def __cmp__(self, other):\n",
    "        if self.a < other.a:\n",
    "            return -1\n",
    "        else if self.a == other.a:\n",
    "            return 0\n",
    "        else:\n",
    "            return 1\n",
    "    # arithmetics, __pos__, __round__ etc.\n",
    "    def __neg__(self):\n",
    "        self.a = -self.a\n",
    "    def __round__(self): # as __ceil__, __floor__ ...\n",
    "        self.a = round(self.a)\n",
    "    def __add__(self, other):\n",
    "        return MyClass(self.a + other.a)\n",
    "    # type conversions\n",
    "    def __str__(self):\n",
    "        return str(self.a)\n",
    "    def __float__(self):\n",
    "        return float(self.a)\n",
    "    def __del__(self):\n",
    "        prit('__del__')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 155,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n"
     ]
    }
   ],
   "source": [
    "class MyClass:\n",
    "    def __init__(self):\n",
    "        self.l = dict()\n",
    "    def __len__(self):\n",
    "        return len(self.l)\n",
    "    def __getattr__(self, key):\n",
    "        assert key in self.l.keys()\n",
    "        return self.l[key]\n",
    "    def __setattr(self, key, value):\n",
    "        self.l[key] = value\n",
    "l = MyClass()\n",
    "l.test = 1\n",
    "print(l.test)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 159,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "2\n"
     ]
    }
   ],
   "source": [
    "class MyClass:\n",
    "    def __init__(self):\n",
    "        self.l = []\n",
    "    def __len__(self):\n",
    "        return len(self.l)\n",
    "    def __getitem__(self, index):\n",
    "        assert index >= 0 and index < len(self)\n",
    "        return self.l[index]\n",
    "    def __setitem__(self, index, value):\n",
    "        assert index >= 0 and index < len(self)\n",
    "        self.l[index] = value\n",
    "    def append(self, value):\n",
    "        self.l.append(value)\n",
    "l = MyClass()\n",
    "l.append(1)\n",
    "print(l[0])\n",
    "l[0] = 2\n",
    "print(l[0])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Errors <a id=\"errors\"></a>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* `AssertionError`\n",
    "* `AttributeError`\n",
    "* `EOFError`\n",
    "* `ImportError`\n",
    "* `KeyError`\n",
    "* `Keyboardinterrupt`\n",
    "* `NotImplementedError`\n",
    "* `ValueError`\n",
    "* ..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 160,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "B\n",
      "C\n",
      "D\n"
     ]
    }
   ],
   "source": [
    "class B(Exception):\n",
    "    pass\n",
    "\n",
    "class C(B):\n",
    "    pass\n",
    "\n",
    "class D(C):\n",
    "    pass\n",
    "\n",
    "for cls in [B, C, D]:\n",
    "    try:\n",
    "        raise cls()\n",
    "    except D:\n",
    "        print(\"D\")\n",
    "    except C:\n",
    "        print(\"C\")\n",
    "    except B:\n",
    "        print(\"B\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Built-In Functions  <a id=\"built-functions\"></a>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 162,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "2\n",
      "1\n",
      "3\n",
      "2\n",
      "1\n",
      "2\n",
      "2.718281828459045\n"
     ]
    }
   ],
   "source": [
    "# arithmetic\n",
    "import math\n",
    "print(abs(-1))\n",
    "print(max([1,2]))\n",
    "print(min([1,2]))\n",
    "print(sum([1,2]))\n",
    "print(round(1.5))\n",
    "print(math.floor(1.5))\n",
    "print(math.ceil(1.2))\n",
    "print(math.exp(1))\n",
    "# ..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 165,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "None\n",
      "1\n"
     ]
    }
   ],
   "source": [
    "class MyClass:\n",
    "    def __init__(self):\n",
    "        self.a = 1\n",
    "        self.b = 2\n",
    "x = MyClass()\n",
    "print(getattr(x, 'a'))\n",
    "print(getattr(x, 'c', None))\n",
    "setattr(x, 'b', 1)\n",
    "print(getattr(x, 'b'))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 166,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n"
     ]
    }
   ],
   "source": [
    "def f():\n",
    "    pass\n",
    "print(callable(f))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Built-In Data Structures <a id=\"built-data\"></a>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### List and Stacks"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Queues"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Design Patterns <a id=\"patterns\"></a>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 172,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0\n",
      "140429016797480\n",
      "140429016797480\n"
     ]
    }
   ],
   "source": [
    "# Singleton\n",
    "counter = 0\n",
    "class Singleton:\n",
    "    instance = None\n",
    "    def __init__(self):\n",
    "        global counter\n",
    "        print(counter)\n",
    "        counter += 1\n",
    "    @staticmethod\n",
    "    def get_instance():\n",
    "        if Singleton.instance is None:\n",
    "            Singleton.instance = Singleton()\n",
    "        return Singleton.instance\n",
    "singleton1 = Singleton.get_instance()\n",
    "singleton2 = Singleton.get_instance()\n",
    "print(id(singleton1))\n",
    "print(id(singleton2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Factory\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Exercises <a id=\"exercises\"></a>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "1.1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "x = 'ab'\n",
    "len(x)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "False\n",
      "True\n",
      "True\n"
     ]
    }
   ],
   "source": [
    "# brute force approach\n",
    "def unique_characters(string):\n",
    "    string = list(string)\n",
    "    string = sorted(string)\n",
    "    for i in range(1, len(string)):\n",
    "        if string[i - 1] == string[i]:\n",
    "            return False\n",
    "    return True\n",
    "print(unique_characters('Hello'))\n",
    "print(unique_characters('David'))\n",
    "print(unique_characters('abcdef'))\n",
    "# Question: does upper/lower case count as differnt?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "False\n",
      "True\n",
      "True\n"
     ]
    }
   ],
   "source": [
    "# Hash-based approach\n",
    "def unique_characters(string):\n",
    "    characters = dict()\n",
    "    for i in range(len(string)):\n",
    "        characters[string[i]] = 0\n",
    "    \n",
    "    for i in range(len(string)):\n",
    "        characters[string[i]] += 1\n",
    "    \n",
    "    for i in range(len(string)):\n",
    "        if characters[string[i]] > 1:\n",
    "            return False\n",
    "    return True\n",
    "print(unique_characters('Hello'))\n",
    "print(unique_characters('David'))\n",
    "print(unique_characters('abcdef'))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "1.2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{'a': 3, 'b': 1}\n",
      "False\n",
      "{'b': 2, 'a': 2}\n",
      "True\n"
     ]
    }
   ],
   "source": [
    "# brute force\n",
    "def check_permutation(a, b):\n",
    "    if len(a) != len(b):\n",
    "        return False\n",
    "    \n",
    "    characters = dict()\n",
    "    for i in range(len(a)):\n",
    "        if a[i] not in characters.keys():\n",
    "            characters[a[i]] = 0\n",
    "        characters[a[i]] += 1\n",
    "\n",
    "    for i in range(len(b)):\n",
    "        if b[i] not in characters.keys():\n",
    "            return False\n",
    "        characters[b[i]] -= 1\n",
    "    \n",
    "    for key in characters.keys():\n",
    "        if characters[key] != 0:\n",
    "            return False\n",
    "        \n",
    "    return True\n",
    "print(check_permutation('aaab', 'aabb'))\n",
    "print(check_permutation('bbaa', 'aabb'))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "1.3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "ab\n"
     ]
    }
   ],
   "source": [
    "x = ['a', 'b']\n",
    "x = ''.join(x)\n",
    "print(x)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Hello%20World!\n"
     ]
    }
   ],
   "source": [
    "def urlify(string):\n",
    "    string = list(string)\n",
    "    i = 0\n",
    "    while i < len(string):\n",
    "        if string[i] == ' ':\n",
    "            string[i] = '%'\n",
    "            string.insert(i + 1, '0')\n",
    "            string.insert(i + 1, '2')\n",
    "            i += 2\n",
    "        i += 1\n",
    "    return ''.join(string)\n",
    "print(urlify('Hello World!'))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "1.4"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n"
     ]
    }
   ],
   "source": [
    "def check_permutation_palindrome(string):\n",
    "    characters = dict()\n",
    "    for i in range(len(string)):\n",
    "        if not string[i] in characters:\n",
    "            characters[string[i]] = 0\n",
    "        characters[string[i]] += 1\n",
    "        \n",
    "    count = 0\n",
    "    for i in range(len(string)):\n",
    "        if characters[string[i]] != 2 and string[i] != ' ':\n",
    "            count += 1\n",
    "    \n",
    "    if count == 0 or count == 1:\n",
    "        return True\n",
    "    else:\n",
    "        return False\n",
    "print(check_permutation_palindrome('tact coa'))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "1.5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "False\n",
      "True\n"
     ]
    }
   ],
   "source": [
    "# does not work\n",
    "def hamming_distance(a, b):\n",
    "    if abs(len(a) - len(b)) > 1:\n",
    "        return False\n",
    "    \n",
    "    if len(b) > len(a):\n",
    "        swap = a\n",
    "        a = b\n",
    "        b = swap\n",
    "    \n",
    "    changes = abs(len(a) - len(b))\n",
    "    for i in range(len(a) - 1):\n",
    "        if a[i] != b[i]:\n",
    "            changes += 1\n",
    "    \n",
    "    if changes > 1:\n",
    "        return False\n",
    "    else:\n",
    "        return True\n",
    "print(hamming_distance('pale', 'ple'))\n",
    "print(hamming_distance('pale', 'bale'))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0 0 p p\n",
      "1 1 a l\n",
      "2 1 l l\n",
      "3 2 e e\n",
      "True\n",
      "True\n"
     ]
    }
   ],
   "source": [
    "def hamming_distance(a, b):\n",
    "    # two casesL euqal length, length differene one\n",
    "    # in case of length difference, insertion and removal can be handled the same\n",
    "    if len(a) == len(b):\n",
    "        # replacement\n",
    "        return hamming_distance_replacement(a, b)\n",
    "    elif len(a) == len(b) + 1:\n",
    "        return hamming_distance_insertion(a, b)\n",
    "    elif len(b) == len(a) + 1:\n",
    "        return hamming_distance_insertion(b, a)\n",
    "    else:\n",
    "        return False\n",
    "def hamming_distance_replacement(a, b):\n",
    "    assert len(a) == len(b)\n",
    "    \n",
    "    first = False\n",
    "    for i in range(len(a)):\n",
    "        if a[i] != b[i]:\n",
    "            if not first:\n",
    "                first = True\n",
    "            else:\n",
    "                return False\n",
    "    \n",
    "    return True\n",
    "def hamming_distance_insertion(a, b):\n",
    "    assert len(a) == len(b) + 1\n",
    "    \n",
    "    a_i = 0\n",
    "    b_i = 0\n",
    "    first = False\n",
    "    \n",
    "    while a_i < len(a) and b_i < len(b):\n",
    "        if b[b_i] != a[a_i]:\n",
    "            if not first:\n",
    "                a_i += 1\n",
    "                first = True\n",
    "            else:\n",
    "                return False\n",
    "        else:\n",
    "            a_i += 1\n",
    "            b_i += 1\n",
    "    \n",
    "    return True\n",
    "print(hamming_distance('pale', 'ple'))\n",
    "print(hamming_distance('pale', 'bale'))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "1.6"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "a2b1c4a3\n",
      "Hello\n",
      "H1e1l6o1\n"
     ]
    }
   ],
   "source": [
    "# Question: lower and upper-case handled differently?\n",
    "def compress(string):\n",
    "    compressed = ''\n",
    "    current_count = 1\n",
    "    current_character = string[0]\n",
    "    for i in range(1, len(string)):\n",
    "        if string[i] == current_character:\n",
    "            current_count += 1\n",
    "        else:\n",
    "            compressed += str(current_character) + str(current_count)\n",
    "            current_character = string[i]\n",
    "            current_count = 1\n",
    "    \n",
    "    # handle last one!\n",
    "    compressed += str(current_character) + str(current_count)\n",
    "    \n",
    "    if len(compressed) < len(string):\n",
    "        return compressed\n",
    "    else:\n",
    "        return string\n",
    "print(compress('aabccccaaa'))\n",
    "print(compress('Hello'))\n",
    "print(compress('Hellllllo'))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "1.7"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[2, 0], [3, 1]]\n"
     ]
    }
   ],
   "source": [
    "def rotate_image(array):\n",
    "    assert isinstance(array, list)\n",
    "    assert len(array) > 0\n",
    "    assert isinstance(array[0], list)\n",
    "    assert len(array) == len(array[0]) # square matrix\n",
    "    \n",
    "    n = len(array)\n",
    "    \n",
    "    # initialize output\n",
    "    output = []\n",
    "    for i in range(n):\n",
    "        output.append([0]*n)\n",
    "    \n",
    "    for i in range(n):\n",
    "        for j in range(n):\n",
    "            # i is row and j is column\n",
    "            # rotating to the right means new row is j and new column is n - i - 1\n",
    "            output[j][n - i - 1] = array[i][j]\n",
    "    \n",
    "    return output\n",
    "print(rotate_image([[0, 1], [2, 3]]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[12, 8, 4, 0], [13, 9, 5, 1], [14, 10, 6, 2], [15, 11, 7, 3]]\n"
     ]
    }
   ],
   "source": [
    "def rotate_image_inplace(array):\n",
    "    assert isinstance(array, list)\n",
    "    assert len(array) > 0\n",
    "    assert isinstance(array[0], list)\n",
    "    assert len(array) == len(array[0]) # square matrix\n",
    "    \n",
    "    for i in range(n):\n",
    "        for j in range(i, n):\n",
    "            # i is row and j is column\n",
    "            # rotating to the right means new row is j and new column is n - i - 1\n",
    "            swap = array[j][n - i - 1]\n",
    "            array[j][n - i - 1] = array[i][j]\n",
    "            array[i][j] = swap\n",
    "    return array\n",
    "print(rotate_image([[0, 1, 2, 3], [4, 5, 6, 7], [8, 9, 10, 11], [12, 13, 14, 15]]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "1.8"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[0, 0, 0], [0, 0, 5], [0, 0, 0]]\n"
     ]
    }
   ],
   "source": [
    "def set_zero(array):\n",
    "    # asserts\n",
    "    \n",
    "    m = len(array)\n",
    "    n = len(array[0])\n",
    "    \n",
    "    zero_rows = [False]*m\n",
    "    zero_columns = [False]*n\n",
    "    \n",
    "    for i in range(m):\n",
    "        for j in range(n):\n",
    "            if array[i][j] == 0:\n",
    "                zero_rows[i] = True\n",
    "                zero_columns[j] = True\n",
    "    \n",
    "    for i in range(m):\n",
    "        for j in range(n):\n",
    "            if zero_rows[i] or zero_columns[j]:\n",
    "                array[i][j] = 0\n",
    "    \n",
    "    return array\n",
    "print(set_zero([[0, 1, 2], [3, 4, 5], [6, 0, 8]]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "1.9"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def is_substring(substring, string):\n",
    "    return string.find(substring) >= 0\n",
    "def naive_rotate_string(string, rotated_string):\n",
    "    assert len(string) == len(rotated_string):\n",
    "        \n",
    "    for i in range(len(rotated_string)):\n",
    "        if is_substring(rotated_string[i:] + rotated_string[:i], string):\n",
    "            return True\n",
    "    \n",
    "    return False"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Questions for string problems:\n",
    "* How to handle white space?\n",
    "* How to handle upper/lower case characters?\n",
    "    * Can I convert to lower/upper case first?\n",
    "* Can you give an example?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0 1 2 3 \n"
     ]
    }
   ],
   "source": [
    "# singly linked list\n",
    "class SinglyLinkedList:\n",
    "    def __init__(self, value, succ=None):\n",
    "        self.value = value\n",
    "        self.succ = succ\n",
    "def print_linked_list(head):\n",
    "    output = ''\n",
    "    while head is not None:\n",
    "        output += str(head.value) + ' '\n",
    "        head = head.succ\n",
    "    print(output)\n",
    "def singly_linked_from_list(l):\n",
    "    assert len(l) > 0\n",
    "    \n",
    "    head = SinglyLinkedList(l[0])\n",
    "    pred = head\n",
    "    \n",
    "    for i in range(1, len(l)):\n",
    "        element = SinglyLinkedList(l[i])\n",
    "        pred.succ = element\n",
    "        \n",
    "        pred = element\n",
    "            \n",
    "    return head\n",
    "l = singly_linked_from_list([0, 1, 2, 3])\n",
    "print_linked_list(l)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0 1 2 3 \n",
      "0 1 3 \n"
     ]
    }
   ],
   "source": [
    "def singly_linked_delete(head, value):\n",
    "    if head.value == value:\n",
    "        return head.succ\n",
    "    \n",
    "    current = head\n",
    "    while current.succ is not None:\n",
    "        if current.succ.value == value:\n",
    "            current.succ = current.succ.succ\n",
    "        else:\n",
    "            current = current.succ\n",
    "    return head\n",
    "l = singly_linked_from_list([0, 1, 2, 3])\n",
    "print_linked_list(l)\n",
    "print_linked_list(singly_linked_delete(l, 2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0 1 2 3 \n"
     ]
    }
   ],
   "source": [
    "class DoublyLinkedList:\n",
    "    def __init__(self, value, succ=None, pred=None):\n",
    "        self.value = value\n",
    "        self.pred = pred\n",
    "        self.succ = succ\n",
    "def doubly_linked_from_list(l):\n",
    "    assert len(l) > 0\n",
    "    \n",
    "    head = DoublyLinkedList(l[0])\n",
    "    pred = head\n",
    "    \n",
    "    for i in range(1, len(l)):\n",
    "        element = DoublyLinkedList(l[i])\n",
    "        \n",
    "        pred.succ = element\n",
    "        element.pred = pred\n",
    "        \n",
    "        pred = element\n",
    "    \n",
    "    return head\n",
    "print_linked_list(doubly_linked_from_list([0, 1, 2, 3])) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0 1 3 \n"
     ]
    }
   ],
   "source": [
    "def doubly_linked_delete(element):\n",
    "    element.pred.succ = element.succ\n",
    "    \n",
    "l = doubly_linked_from_list([0, 1, 2, 3])\n",
    "doubly_linked_delete(l.succ.succ)\n",
    "print_linked_list(l)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "2.1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0 1 2 3 4 \n"
     ]
    }
   ],
   "source": [
    "# worst case is quadratic, does not use a buffer\n",
    "def naive_remove_duplicates(head):    \n",
    "    current = head\n",
    "    while current is not None:\n",
    "        inner_current = current.succ\n",
    "        while inner_current is not None:\n",
    "            if inner_current.value == current.value:\n",
    "                inner_current.pred.succ = inner_current.succ\n",
    "            inner_current = inner_current.succ\n",
    "        current = current.succ\n",
    "l = doubly_linked_from_list([0, 1, 1, 2, 3, 4, 3, 0])\n",
    "naive_remove_duplicates(l)\n",
    "print_linked_list(l)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 70,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0 1 2 3 4 \n"
     ]
    }
   ],
   "source": [
    "# solution with buffer or hash table?\n",
    "def buffer_remove_duplicates(head):\n",
    "    buffer = dict()\n",
    "    current = head\n",
    "    while current is not None:\n",
    "        if current.value not in buffer:\n",
    "            buffer[current.value] = 0\n",
    "        buffer[current.value] += 1\n",
    "    \n",
    "    current = head.succ\n",
    "    while current is not None:\n",
    "        if buffer[current.value] > 1:\n",
    "            current.pred.succ = current.succ\n",
    "        current = current.succ\n",
    "l = doubly_linked_from_list([0, 1, 1, 2, 3, 4, 3, 0])\n",
    "naive_remove_duplicates(l)\n",
    "print_linked_list(l)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "2.2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 69,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "4\n",
      "1\n",
      "3\n"
     ]
    }
   ],
   "source": [
    "def singly_linked_len(head):\n",
    "    length = 0\n",
    "    while head is not None:\n",
    "        head = head.succ\n",
    "        length += 1\n",
    "    return length\n",
    "l = singly_linked_from_list([0, 1, 2, 3])\n",
    "print(singly_linked_len(l))\n",
    "def singly_linked_kth_to_last(head, k):\n",
    "    length = singly_linked_len(l)\n",
    "    current = head\n",
    "    count = 0\n",
    "    \n",
    "    while current is not None:\n",
    "        if count == length - k:\n",
    "            return current\n",
    "        current = current.succ\n",
    "        count += 1\n",
    "    \n",
    "    return None\n",
    "l = singly_linked_from_list([0, 1, 2, 3])\n",
    "print(singly_linked_kth_to_last(l, 3).value)\n",
    "print(singly_linked_kth_to_last(l, 1).value)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "2.3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 77,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0 1 3 \n",
      "0 2 3 \n"
     ]
    }
   ],
   "source": [
    "def singly_linked_delete_middle(element):\n",
    "    pred = None\n",
    "    current = element\n",
    "    while current.succ is not None:\n",
    "        current.value = current.succ.value\n",
    "        pred = current\n",
    "        current = current.succ\n",
    "    pred.succ = None\n",
    "l = singly_linked_from_list([0, 1, 2, 3])\n",
    "singly_linked_delete_middle(l.succ.succ)\n",
    "print_linked_list(l)\n",
    "l = singly_linked_from_list([0, 1, 2, 3])\n",
    "singly_linked_delete_middle(l.succ)\n",
    "print_linked_list(l)\n",
    "# better solution: just move current value over to the next and delete next (with access to current)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "2.4"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "7 9 5 6 10 11 3 2 \n",
      "2 3 5 7 9 6 10 11 \n",
      "2 3 10 6 5 9 7 11 \n",
      "2 3 6 5 7 9 10 11 \n"
     ]
    }
   ],
   "source": [
    "def doubly_linked_partition(head, value):\n",
    "    assert head.succ is not None\n",
    "    assert head.pred is None\n",
    "    \n",
    "    current = head.succ\n",
    "    while current is not None:\n",
    "        if current.value < value:\n",
    "            # remember for next element\n",
    "            current_succ = current.succ\n",
    "            \n",
    "            # delete current position\n",
    "            assert current.pred is not None\n",
    "            current.pred.succ = current.succ\n",
    "            if current.succ is not None:\n",
    "                current.succ.pred = current.pred\n",
    "            \n",
    "            # add current before head\n",
    "            current.pred = None\n",
    "            current.succ = head\n",
    "            head.pred = current\n",
    "            \n",
    "            # set as new head\n",
    "            head = current\n",
    "            \n",
    "            current = current_succ\n",
    "        else:\n",
    "            current = current.succ\n",
    "    \n",
    "    return head\n",
    "l = doubly_linked_from_list([7, 9, 5, 6, 10, 11, 3, 2])\n",
    "print_linked_list(l)\n",
    "l = doubly_linked_partition(l, 6)\n",
    "print_linked_list(l)\n",
    "l = doubly_linked_from_list([7, 9, 5, 6, 10, 11, 3, 2])\n",
    "l = doubly_linked_partition(l, 11)\n",
    "print_linked_list(l)\n",
    "l = doubly_linked_from_list([7, 9, 5, 6, 10, 11, 3, 2])\n",
    "l = doubly_linked_partition(l, 9)\n",
    "print_linked_list(l)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "2.5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "9 1 2 \n"
     ]
    }
   ],
   "source": [
    "def sum_lists(h1, h2):\n",
    "    assert h1 is not None\n",
    "    assert h2 is not None\n",
    "    \n",
    "    # h1 and h2 in reverse order\n",
    "    # length does not need to be the same\n",
    "    \n",
    "    t1 = h1\n",
    "    t2 = h2\n",
    "    \n",
    "    l1 = 1\n",
    "    l2 = 1\n",
    "    \n",
    "    while t1.succ is not None:\n",
    "        l1 += 1\n",
    "        t1 = t1.succ\n",
    "    while t2.succ is not None:\n",
    "        l2 += 1\n",
    "        t2 = t2.succ\n",
    "        \n",
    "    # current values\n",
    "    c1 = t1\n",
    "    c2 = t2\n",
    "    \n",
    "    c = None # current element\n",
    "    last = None # tail of new list\n",
    "    overhang = 0\n",
    "    for l in range(max(l1, l2)):\n",
    "        result = overhang\n",
    "        if c1 is not None:\n",
    "            result += c1.value\n",
    "        if c2 is not None:\n",
    "            result += c2.value\n",
    "        overhang = result//10\n",
    "        result = result%10\n",
    "        #print(result, overhang)\n",
    "        \n",
    "        c = DoublyLinkedList(result)\n",
    "        c.succ = last\n",
    "        c.pred = None\n",
    "        \n",
    "        if last is not None:\n",
    "            last.pred = c\n",
    "            \n",
    "        last = c\n",
    "        \n",
    "        if c1 is not None:\n",
    "            c1 = c1.pred\n",
    "        if c2 is not None:\n",
    "            c2 = c2.pred\n",
    "    \n",
    "    # handle last overhang\n",
    "    if overhang > 0:\n",
    "        c = DoublyLinkedList(overhang)\n",
    "    \n",
    "        c.succ = last\n",
    "        c.pred = None\n",
    "\n",
    "        if last is None:\n",
    "            last = c\n",
    "        else:\n",
    "            last.pred = c\n",
    "    \n",
    "    return c\n",
    "h1 = doubly_linked_from_list([6, 1, 7])\n",
    "h2 = doubly_linked_from_list([2, 9, 5])\n",
    "r = sum_lists(h1, h2)\n",
    "print_linked_list(r)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "2.6"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n",
      "True\n",
      "False\n"
     ]
    }
   ],
   "source": [
    "def is_palindrome(head):\n",
    "    tail = head\n",
    "    while tail.succ is not None:\n",
    "        tail = tail.succ\n",
    "    \n",
    "    t = tail\n",
    "    h = head\n",
    "    \n",
    "    while t is not None and h is not None:\n",
    "        if t.value != h.value:\n",
    "            return False\n",
    "        t = t.pred\n",
    "        h = h.succ\n",
    "\n",
    "    return True\n",
    "l = doubly_linked_from_list([1, 2, 3, 3, 2, 1])\n",
    "print(is_palindrome(l))\n",
    "l = doubly_linked_from_list([1, 2, 3, 2, 1])\n",
    "print(is_palindrome(l))\n",
    "l = doubly_linked_from_list([1, 2, 3, 3, 4, 1])\n",
    "print(is_palindrome(l))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "2.7"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Element:\n",
    "    def __init__(self, value):\n",
    "        self.value = value\n",
    "def is_intersection(h1, h2):\n",
    "    # naive approach\n",
    "    c1 = h1\n",
    "    while c1 is not None:\n",
    "        c2 = h2\n",
    "        while c2 is not None:\n",
    "            if id(c1.value) == id(c2.value):\n",
    "                return True\n",
    "            c2 = c2.succ\n",
    "        \n",
    "        c1 = c1.succ\n",
    "    return False\n",
    "three = Element(3)\n",
    "l1 = doubly_linked_from_list([Element(1), Element(2), Element(3), three, Element(4), Element(5)])\n",
    "l2 = doubly_linked_from_list([Element(6), Element(7), Element(8), three, Element(9)])\n",
    "l3 = doubly_linked_from_list([Element(6), Element(7), Element(8), Element(9)])\n",
    "print(is_intersection(l1, l2))\n",
    "print(is_intersection(l1, l3))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "2.8"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "False\n"
     ]
    }
   ],
   "source": [
    "def detect_loop(head):\n",
    "    assert head is not None\n",
    "    \n",
    "    c1 = head\n",
    "    while c1.succ is not None:\n",
    "        c2 = head\n",
    "        while c2 is not None and id(c2) != id(c1):\n",
    "            if id(c1.succ) == id(c2):\n",
    "                return True\n",
    "            c2 = c2.succ\n",
    "        c1 = c1.succ\n",
    "    return False#\n",
    "l5 = SinglyLinkedList(5)\n",
    "l4 = SinglyLinkedList(4, l5)\n",
    "l3 = SinglyLinkedList(3, l4)\n",
    "l2 = SinglyLinkedList(2, l3)\n",
    "l1 = SinglyLinkedList(1, l2)\n",
    "#l5.succ = l3\n",
    "print(detect_loop(l1))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n",
      "0 \n",
      "2 1 0 \n",
      "2\n",
      "1\n",
      "0\n",
      "True\n"
     ]
    }
   ],
   "source": [
    "# lists are, of course cheating, so implementing stacks as linked lists makes more sense\n",
    "class StackElement:\n",
    "    def __init__(self, value, next=None):\n",
    "        self.value = value\n",
    "        self.next = next\n",
    "class Stack:\n",
    "    def __init__(self):\n",
    "        self.top = None\n",
    "    def push(self, value):\n",
    "        element = StackElement(value, self.top)\n",
    "        self.top = element\n",
    "    def pop(self):\n",
    "        assert not self.empty()\n",
    "        element = self.top\n",
    "        self.top = element.next\n",
    "        return element.value\n",
    "    def peek():\n",
    "        assert not self.empty()\n",
    "        return self.top.value\n",
    "    def empty(self):\n",
    "        return self.top == None\n",
    "    def print(self):\n",
    "        ret = ''\n",
    "        current = self.top\n",
    "        while current is not None:\n",
    "            ret += str(current.value) + ' '\n",
    "            current = current.next\n",
    "        return ret\n",
    "stack = Stack()\n",
    "print(stack.empty())\n",
    "stack.push(0)\n",
    "print(stack.print())\n",
    "stack.push(1)\n",
    "stack.push(2)\n",
    "print(stack.print())\n",
    "print(stack.pop())\n",
    "print(stack.pop())\n",
    "print(stack.pop())\n",
    "print(stack.empty())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n",
      "0 \n",
      "0\n",
      "1\n",
      "2\n",
      "True\n"
     ]
    }
   ],
   "source": [
    "class QueueElement:\n",
    "    def __init__(self, value, next=None):\n",
    "        self.value = value\n",
    "        self.next = next\n",
    "class Queue:\n",
    "    def __init__(self):\n",
    "        self.first = None\n",
    "        self.last = None\n",
    "    def add(self, value):\n",
    "        element = QueueElement(value)\n",
    "        if self.last is not None:\n",
    "            self.last.next = element\n",
    "        self.last = element\n",
    "        if self.first is None:\n",
    "            self.first = self.last\n",
    "    def remove(self):\n",
    "        assert not self.empty()\n",
    "        if id(self.first) == id(self.last):\n",
    "            self.last = None\n",
    "        element = self.first\n",
    "        self.first = self.first.next\n",
    "        return element.value\n",
    "    def empty(self):\n",
    "        return self.last is None and self.first is None\n",
    "    def print(self):\n",
    "        ret = ''\n",
    "        current = self.first\n",
    "        while current is not None:\n",
    "            ret += str(current.value) + ' '\n",
    "            current = current.next\n",
    "        return ret\n",
    "queue = Queue()\n",
    "print(queue.empty())\n",
    "queue.add(0)\n",
    "print(queue.print())\n",
    "queue.add(1)\n",
    "queue.add(2)\n",
    "print(queue.remove())\n",
    "print(queue.remove())\n",
    "print(queue.remove())\n",
    "print(queue.empty())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "3.1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 70,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0, 3, 6, 1, 4, 7, 2, 5, 8, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] [6, 7, 8]\n"
     ]
    }
   ],
   "source": [
    "class Stacks:\n",
    "    def __init__(self, n, reserve=100):\n",
    "        self.n = n\n",
    "        self.tops = [None]*self.n\n",
    "        self.array = [0]*100\n",
    "    def pop(self, k):\n",
    "        assert k < self.n\n",
    "        value = self.array[self.tops[k]]\n",
    "        if self.tops[k] - self.n >= 0:\n",
    "            self.tops[k] -= self.n\n",
    "        else:\n",
    "            self.tops[k] = None\n",
    "        return value\n",
    "    def push(self, k, value):\n",
    "        assert k < self.n\n",
    "        if self.tops[k] is None:\n",
    "            self.tops[k] = k\n",
    "        else:\n",
    "            self.tops[k] += self.n\n",
    "        self.array[self.tops[k]] = value\n",
    "    def empty(self, k):\n",
    "        assert k < self.n\n",
    "        return self.tops[n] is None\n",
    "stacks = Stacks(3)\n",
    "stacks.push(0, 0)\n",
    "stacks.push(0, 1)\n",
    "stacks.push(0, 2)\n",
    "stacks.push(1, 3)\n",
    "stacks.push(1, 4)\n",
    "stacks.push(1, 5)\n",
    "stacks.push(2, 6)\n",
    "stacks.push(2, 7)\n",
    "stacks.push(2, 8)\n",
    "print(stacks.array, stacks.tops)\n",
    "assert stacks.pop(0) == 2\n",
    "assert stacks.pop(1) == 5\n",
    "assert stacks.pop(2) == 8\n",
    "assert stacks.pop(0) == 1\n",
    "assert stacks.pop(1) == 4\n",
    "assert stacks.pop(2) == 7\n",
    "assert stacks.pop(0) == 0\n",
    "assert stacks.pop(1) == 3\n",
    "assert stacks.pop(2) == 6"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "3.2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 82,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2 8 3 5 4 \n",
      "2 2\n",
      "3 8\n",
      "3 3\n",
      "4 5\n",
      "4 4\n"
     ]
    }
   ],
   "source": [
    "class MinStackElement:\n",
    "    def __init__(self, value, next1=None, next2=None):\n",
    "        self.value = value\n",
    "        self.next1 = next1\n",
    "        self.next2 = next2\n",
    "class MinStack:\n",
    "    def __init__(self):\n",
    "        self.top = None\n",
    "        self.min = None\n",
    "    def push(self, value):\n",
    "        element = MinStackElement(value)\n",
    "        element.next1 = self.top\n",
    "        self.top = element\n",
    "        \n",
    "        if self.min is None or value < self.min.value:\n",
    "            element.next2 = self.min\n",
    "            self.min = element\n",
    "    def pop(self):\n",
    "        assert not self.empty()\n",
    "        if id(self.min) == id(self.top):\n",
    "            self.min = self.min.next2\n",
    "        value = self.top.value\n",
    "        self.top = self.top.next1\n",
    "        return value\n",
    "    def get_min(self):\n",
    "        assert not self.empty()\n",
    "        return self.min.value\n",
    "    def empty(self):\n",
    "        assert (self.top is None and self.min is None) or (self.top is not None and self.min is not None)\n",
    "        return self.top is None\n",
    "    def print(self):\n",
    "        ret = ''\n",
    "        current = self.top\n",
    "        while current is not None:\n",
    "            ret += str(current.value) + ' '\n",
    "            current = current.next1\n",
    "        return ret\n",
    "minstack = MinStack()\n",
    "minstack.push(4)\n",
    "minstack.push(5)\n",
    "minstack.push(3)\n",
    "minstack.push(8)\n",
    "minstack.push(2)\n",
    "print(minstack.print())\n",
    "print(minstack.get_min(), minstack.pop())\n",
    "print(minstack.get_min(), minstack.pop())\n",
    "print(minstack.get_min(), minstack.pop())\n",
    "print(minstack.get_min(), minstack.pop())\n",
    "print(minstack.get_min(), minstack.pop())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "3.3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 99,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n",
      "0 \n",
      "2 1 0 \n",
      "2\n",
      "1\n",
      "0\n",
      "True\n"
     ]
    }
   ],
   "source": [
    "class StackElement:\n",
    "    def __init__(self, value, next=None):\n",
    "        self.value = value\n",
    "        self.next = next\n",
    "class Stack:\n",
    "    def __init__(self):\n",
    "        self.top = None\n",
    "        self.n = 0\n",
    "    def push(self, value):\n",
    "        element = StackElement(value, self.top)\n",
    "        self.top = element\n",
    "        self.n += 1\n",
    "    def pop(self):\n",
    "        assert not self.empty()\n",
    "        element = self.top\n",
    "        self.top = element.next\n",
    "        self.n -= 1\n",
    "        return element.value\n",
    "    def peek(self):\n",
    "        assert not self.empty()\n",
    "        return self.top.value\n",
    "    def empty(self):\n",
    "        return self.top == None\n",
    "    def print(self):\n",
    "        ret = ''\n",
    "        current = self.top\n",
    "        while current is not None:\n",
    "            ret += str(current.value) + ' '\n",
    "            current = current.next\n",
    "        return ret\n",
    "stack = Stack()\n",
    "print(stack.empty())\n",
    "stack.push(0)\n",
    "print(stack.print())\n",
    "stack.push(1)\n",
    "stack.push(2)\n",
    "print(stack.print())\n",
    "print(stack.pop())\n",
    "print(stack.pop())\n",
    "print(stack.pop())\n",
    "print(stack.empty())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 100,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "4 3 2 1 0 \n",
      "6 5 \n",
      "\n",
      "4 3 2 1 0 \n",
      "\n"
     ]
    }
   ],
   "source": [
    "class SetOfStacks:\n",
    "    def __init__(self, n = 5):\n",
    "        self.n = n\n",
    "        self.stacks = []\n",
    "    def push(self, value):\n",
    "        if len(self.stacks) == 0:\n",
    "            self.stacks.append(Stack())\n",
    "        if self.stacks[-1].n >=5 :\n",
    "            stack = Stack()\n",
    "            self.stacks.append(stack)\n",
    "        \n",
    "        self.stacks[-1].push(value)\n",
    "    def pop(self):\n",
    "        value = self.stacks[-1].pop()\n",
    "        if self.stacks[-1].empty():\n",
    "            if len(self.stacks) > 1:\n",
    "                del self.stacks[-1]\n",
    "    def empty(self):\n",
    "        return len(self.stacks) == 1 and self.stacks[-1].empty()\n",
    "    def print(self):\n",
    "        ret = ''\n",
    "        for stack in self.stacks:\n",
    "            ret += stack.print() + '\\n'\n",
    "        return ret\n",
    "sstacks = SetOfStacks()\n",
    "sstacks.push(0)\n",
    "sstacks.push(1)\n",
    "sstacks.push(2)\n",
    "sstacks.push(3)\n",
    "sstacks.push(4)\n",
    "sstacks.push(5)\n",
    "sstacks.push(6)\n",
    "print(sstacks.print())\n",
    "sstacks.pop()\n",
    "sstacks.pop()\n",
    "print(sstacks.print())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "3.4"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 101,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0\n",
      "\n",
      "1 2 3 \n",
      "5 4 \n",
      "1 2 3 \n",
      "5 4 \n",
      "\n",
      "\n",
      "5 \n"
     ]
    }
   ],
   "source": [
    "class QueueFromStacks:\n",
    "    # naive: for any add, just reorder one of the stacks to keep the first element on top\n",
    "    def __init__(self):\n",
    "        self.oldest = Stack()\n",
    "        self.newest = Stack()\n",
    "    def add(self, value):\n",
    "        self.newest.push(value)\n",
    "    def remove(self):\n",
    "        if self.oldest.empty():\n",
    "            while not self.newest.empty():\n",
    "                value = self.newest.pop()\n",
    "                self.oldest.push(value)\n",
    "        return self.oldest.pop()\n",
    "    def print(self):\n",
    "        ret = self.newest.print() + '\\n'\n",
    "        ret += self.oldest.print()\n",
    "        return ret\n",
    "queue = QueueFromStacks()\n",
    "queue.add(0)\n",
    "queue.add(1)\n",
    "queue.add(2)\n",
    "queue.add(3)\n",
    "print(queue.remove())\n",
    "print(queue.print())\n",
    "queue.add(4)\n",
    "queue.add(5)\n",
    "print(queue.print())\n",
    "queue.remove()\n",
    "queue.remove()\n",
    "queue.remove()\n",
    "print(queue.print())\n",
    "queue.remove()\n",
    "print(queue.print())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "3.5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 104,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 2 3 4 5 6 7 8 9 \n"
     ]
    }
   ],
   "source": [
    "def sort_stack(stack):\n",
    "    tstack = Stack()\n",
    "    last = 0\n",
    "\n",
    "    stop = False\n",
    "    max_min_value = -1e20\n",
    "    while not stop:\n",
    "        # find minimum element\n",
    "        min_value = 1e20\n",
    "        while not stack.empty():\n",
    "            value = stack.pop()\n",
    "            if value < min_value:\n",
    "                min_value = value\n",
    "            tstack.push(value)\n",
    "        \n",
    "        # add items back to stack without minimum item\n",
    "        first = True\n",
    "        while not tstack.empty() and tstack.peek() is not None:\n",
    "            value = tstack.pop()\n",
    "            if value != min_value:\n",
    "                stack.push(value)\n",
    "        \n",
    "        if tstack.empty():\n",
    "            tstack.push(min_value)\n",
    "            tstack.push(None)\n",
    "        else:\n",
    "            tstack.pop() # remove None\n",
    "            tstack.push(min_value)\n",
    "            tstack.push(None)\n",
    "            \n",
    "        if stack.empty():\n",
    "            stop = True\n",
    "    \n",
    "    assert tstack.peek() is None\n",
    "    tstack.pop()\n",
    "    \n",
    "    while not tstack.empty():\n",
    "        value = tstack.pop()\n",
    "        stack.push(value)\n",
    "stack = Stack()\n",
    "stack.push(5)\n",
    "stack.push(7)\n",
    "stack.push(2)\n",
    "stack.push(3)\n",
    "stack.push(9)\n",
    "stack.push(1)\n",
    "stack.push(8)\n",
    "stack.push(4)\n",
    "stack.push(6)\n",
    "sort_stack(stack)\n",
    "print(stack.print())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "4"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 113,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3 1 4 0 5 2 \n",
      "0 1 3 4 2 5 \n",
      "3 4 1 5 2 0 "
     ]
    }
   ],
   "source": [
    "class BinaryTree:\n",
    "    def __init__(self, value, left=None, right=None):\n",
    "        self.value = value\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "def inorder_traversal(root):\n",
    "    if root is None:\n",
    "        return\n",
    "    inorder_traversal(root.left)\n",
    "    print(str(root.value) + ' ', end='')\n",
    "    inorder_traversal(root.right)\n",
    "def preorder_traversal(root):\n",
    "    if root is None:\n",
    "        return\n",
    "    print(str(root.value) + ' ', end='')\n",
    "    preorder_traversal(root.left)\n",
    "    preorder_traversal(root.right)\n",
    "def postorder_traversal(root):\n",
    "    if root is None:\n",
    "        return\n",
    "    postorder_traversal(root.left)\n",
    "    postorder_traversal(root.right)\n",
    "    print(str(root.value) + ' ', end='')\n",
    "#    0\n",
    "#  1   2\n",
    "# 3 4 5 -\n",
    "# in: 3 1 4 0 5 2\n",
    "# pre 0 1 3 4 2 5\n",
    "# post 3 4 1 4 5 2 0\n",
    "rl = BinaryTree(5)\n",
    "lr = BinaryTree(4)\n",
    "ll = BinaryTree(3)\n",
    "r = BinaryTree(2, rl)\n",
    "l = BinaryTree(1, ll, lr)\n",
    "root = BinaryTree(0, l, r)\n",
    "inorder_traversal(root)\n",
    "print()\n",
    "preorder_traversal(root)\n",
    "print()\n",
    "postorder_traversal(root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 114,
   "metadata": {},
   "outputs": [],
   "source": [
    "# TODO min heap\n",
    "# TODO trie\n",
    "# TODO general graph + BFS, DFS"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 119,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[9]\n",
      "[3, 9]\n",
      "[3, 5, 9]\n",
      "[1, 3, 9, 5]\n",
      "[-2, 1, 3, 5, 9]\n",
      "[-2, 1, 3, 5, 9, 10]\n",
      "[-2, 1, 3, 2, 9, 10, 5]\n",
      "-2\n"
     ]
    }
   ],
   "source": [
    "class MinHeap:\n",
    "    def __init__(self):\n",
    "        self.nodes = []\n",
    "    def add(self, value):\n",
    "        self.nodes.append(value)\n",
    "        self.update(len(self.nodes) - 1)\n",
    "    def update(self, i):\n",
    "        while i > 0 and self.nodes[i] < self.nodes[i//2]:\n",
    "            swap = self.nodes[i//2]\n",
    "            self.nodes[i//2] = self.nodes[i]\n",
    "            self.nodes[i] = swap\n",
    "            i = i//2\n",
    "        print(self.nodes)\n",
    "    def min(self):\n",
    "        return self.nodes[0]\n",
    "heap = MinHeap()\n",
    "heap.add(9)\n",
    "heap.add(3)\n",
    "heap.add(5)\n",
    "heap.add(1)\n",
    "heap.add(-2)\n",
    "heap.add(10)\n",
    "heap.add(2)\n",
    "print(heap.min())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 129,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "2\n",
      "3\n",
      "4\n",
      "5\n",
      "1\n",
      "3\n",
      "4\n",
      "5\n",
      "2\n"
     ]
    }
   ],
   "source": [
    "class Node:\n",
    "    def __init__(self, value):\n",
    "        self.value = value\n",
    "        self.visited = False\n",
    "        self.marked = False\n",
    "        self.adjacent = []\n",
    "    def visit(self):\n",
    "        self.visited = True\n",
    "        print(self.value)\n",
    "    @staticmethod\n",
    "    def from_matrix(values, adjacency):\n",
    "        assert len(values) == len(adjacency)\n",
    "        assert len(adjacency) == len(adjacency[0])\n",
    "        \n",
    "        nodes = []\n",
    "        for i in range(len(values)):\n",
    "            nodes.append(Node(values[i]))\n",
    "        for i in range(len(adjacency)):\n",
    "            for j in range(len(adjacency[0])):\n",
    "                if adjacency[i][j] > 0:\n",
    "                    nodes[i].adjacent.append(nodes[j])\n",
    "        \n",
    "        return nodes\n",
    "def reset(nodes):\n",
    "    for node in nodes:\n",
    "        node.visited = False\n",
    "        node.marked = False\n",
    "def bfs(node):\n",
    "    queue = Queue()\n",
    "    queue.add(node)\n",
    "    node.marked = True\n",
    "    while not queue.empty():\n",
    "        current_node = queue.remove()\n",
    "        for adjacent_node in current_node.adjacent:\n",
    "            if not adjacent_node.marked:\n",
    "                queue.add(adjacent_node)\n",
    "                adjacent_node.marked = True\n",
    "        current_node.visit()\n",
    "def dfs(node):\n",
    "    stack = Stack()\n",
    "    stack.push(node)\n",
    "    node.marked = True\n",
    "    while not stack.empty():\n",
    "        current_node = stack.pop()\n",
    "        for adjacent_node in current_node.adjacent:\n",
    "            if not adjacent_node.marked:\n",
    "                stack.push(adjacent_node)\n",
    "                adjacent_node.marked = True\n",
    "        current_node.visit()\n",
    "graph = Node.from_matrix([1, 2, 3, 4, 5], [[0, 1, 1, 0, 0], [1, 0, 0, 0, 0], [1, 0, 0, 1, 0], [0, 0, 1, 0, 1], [0, 0, 0, 1, 0]])\n",
    "bfs(graph[0])\n",
    "reset(graph)\n",
    "dfs(graph[0])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "4.1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 134,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "2\n",
      "3\n",
      "True\n",
      "3\n",
      "1\n",
      "2\n",
      "3\n",
      "True\n",
      "1\n",
      "2\n",
      "3\n",
      "4\n",
      "False\n"
     ]
    }
   ],
   "source": [
    "def directed_route(graph, i1, i2):\n",
    "    reset(graph)\n",
    "    n1 = graph[i1]\n",
    "    n2 = graph[i2]\n",
    "    \n",
    "    bfs(n1)\n",
    "    \n",
    "    if n2.visited:\n",
    "        return True\n",
    "    \n",
    "    reset(graph)\n",
    "    \n",
    "    bfs(n2)\n",
    "    \n",
    "    if n1.visited:\n",
    "        return True\n",
    "    \n",
    "    return False\n",
    "graph = Node.from_matrix([1, 2, 3, 4], [[0, 1, 0, 0], [0, 0, 1, 0], [0, 0, 0, 0], [0, 0, 0, 0]])\n",
    "print(directed_route(graph, 0, 2))\n",
    "print(directed_route(graph, 2, 0))\n",
    "print(directed_route(graph, 0, 3))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "4.2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 143,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0 1 2 3 4 5 6 7 8 9 "
     ]
    }
   ],
   "source": [
    "def minimal_tree(array):\n",
    "    if len(array) == 0:\n",
    "        return None\n",
    "    \n",
    "    root_index = len(array)//2\n",
    "    root_value = array[root_index]\n",
    "    root = BinaryTree(root_value)\n",
    "    \n",
    "    left = minimal_tree(array[:root_index])\n",
    "    right = minimal_tree(array[root_index + 1:])\n",
    "    \n",
    "    root.left = left\n",
    "    root.right = right\n",
    "    \n",
    "    return root\n",
    "array = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]\n",
    "root = minimal_tree(array)\n",
    "inorder_traversal(root)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "4.3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 154,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "4\n",
      "5 \n",
      "2 8 \n",
      "1 4 7 9 \n",
      "0 3 6 \n",
      "\n"
     ]
    }
   ],
   "source": [
    "def list_of_depths(root, depth=0, depths=[]):\n",
    "    if root is None:\n",
    "        return\n",
    "    if len(depths) <= depth:\n",
    "        depths.append([])\n",
    "    depths[depth].append(root)\n",
    "    list_of_depths(root.left, depth=depth + 1, depths=depths)\n",
    "    list_of_depths(root.right, depth=depth + 1, depths=depths)\n",
    "    return depths\n",
    "def print_list_of_depths(depths):\n",
    "    ret = ''\n",
    "    for nodes in depths:\n",
    "        for node in nodes:\n",
    "            ret += str(node.value) + ' '\n",
    "        ret += '\\n'\n",
    "    print(ret)\n",
    "array = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]\n",
    "root = minimal_tree(array)\n",
    "depths = list_of_depths(root)\n",
    "print(len(depths))\n",
    "print_list_of_depths(depths)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "4.4"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 162,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(3, True)\n",
      "(3, True)\n",
      "(4, False)\n"
     ]
    }
   ],
   "source": [
    "def check_balanced(root):\n",
    "    if root is None:\n",
    "        return 0, True\n",
    "    \n",
    "    left_depth, left_balanced = check_balanced(root.left)\n",
    "    right_depth, right_balanced = check_balanced(root.right)\n",
    "    \n",
    "    #print(root.value, left_depth, right_depth)\n",
    "    return max(left_depth, right_depth) + 1, left_balanced and right_balanced and (left_depth == right_depth)\n",
    "array = [0, 1, 2, 3, 4, 5, 6]\n",
    "root = minimal_tree(array)\n",
    "print(check_balanced(root))\n",
    "array = [0, 1, 2, 3, 4, 5, 6]\n",
    "root = minimal_tree(array)\n",
    "root.left.left = BinaryTree(7)\n",
    "print(check_balanced(root))\n",
    "array = [0, 1, 2, 3, 4, 5, 6]\n",
    "root = minimal_tree(array)\n",
    "root.left.left = BinaryTree(7)\n",
    "root.left.left.left = BinaryTree(8)\n",
    "print(check_balanced(root))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "4.5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 176,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0 1 2 3 4 5 6 \n",
      "True\n",
      "12 0 1 2 3 4 5 6 \n",
      "False\n"
     ]
    }
   ],
   "source": [
    "def validate_bst(root):    \n",
    "    if root is None:\n",
    "        return True\n",
    "    \n",
    "    validated_left = validate_bst(root.left)\n",
    "    validated_right = validate_bst(root.right)\n",
    "    \n",
    "    validated_root = True\n",
    "    if root.left is not None:\n",
    "        validated_root = validated_root and (root.left.value <= root.value)\n",
    "    if root.right is not None:\n",
    "        validated_root = validated_root and (root.right.value > root.value)  \n",
    "    \n",
    "    #print(root.value, validated_left, validated_right, validated_root)\n",
    "    return validated_left and validated_right and validated_root\n",
    "array = [0, 1, 2, 3, 4, 5, 6]\n",
    "root = minimal_tree(array)\n",
    "inorder_traversal(root)\n",
    "print()\n",
    "print(validate_bst(root))\n",
    "array = [0, 1, 2, 3, 4, 5, 6]\n",
    "root = minimal_tree(array)\n",
    "root.left.left.left = BinaryTree(12)\n",
    "inorder_traversal(root)\n",
    "print()\n",
    "print(validate_bst(root))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "4.6"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 177,
   "metadata": {},
   "outputs": [],
   "source": [
    "# parent if right is None\n",
    "# or left most hcild of right child"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "4.7"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 191,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "4\n",
      "5\n",
      "1\n",
      "0\n",
      "3\n",
      "2\n"
     ]
    }
   ],
   "source": [
    "class InOutNode:\n",
    "    def __init__(self, value):\n",
    "        self.value = value\n",
    "        self.i = []\n",
    "        self.o = []\n",
    "        self.marked = False\n",
    "def build_order(projects, dependencies):\n",
    "    nodes = []\n",
    "    for project in projects:\n",
    "        nodes.append(InOutNode(project))\n",
    "    for dependency in dependencies:\n",
    "        # (i, j)\n",
    "        # node i depends on node j\n",
    "        i = dependency[0]\n",
    "        j = dependency[1]\n",
    "        nodes[i].i.append(nodes[j])\n",
    "        nodes[j].o.append(nodeſ[i])\n",
    "    \n",
    "    for node in nodes:\n",
    "        if not node.marked and len(node.i) == 0:\n",
    "            queue = Queue()\n",
    "            queue.add(node)\n",
    "            node.marked = True\n",
    "            while not queue.empty():\n",
    "                current_node = queue.remove()\n",
    "                for adjacent_node in current_node.o:\n",
    "                    if not adjacent_node.marked:\n",
    "                        queue.add(adjacent_node)\n",
    "                        adjacent_node.marked = True\n",
    "                print(current_node.value)\n",
    "build_order([0, 1, 2, 3, 4, 5], [(3, 0), (1, 5), (3, 1), (0, 5), (2, 3)])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "4.9"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 210,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2 1 0 4 \n",
      "2\n",
      "1\n",
      "0\n",
      "4\n",
      "['2410', '2104', '2410', '2104']\n"
     ]
    }
   ],
   "source": [
    "def bst_sequences(root):\n",
    "    print(root.value)\n",
    "    if root.left is None and root.right is None:\n",
    "        return [str(root.value)]\n",
    "    \n",
    "    sequences = []\n",
    "    left_sequences = []\n",
    "    right_sequences = []\n",
    "    \n",
    "    if root.left is not None:\n",
    "        left_sequences = bst_sequences(root.left)\n",
    "    else:\n",
    "        left_sequences = ['']\n",
    "        \n",
    "    if root.right is not None:\n",
    "        right_sequences = bst_sequences(root.right)\n",
    "    else:\n",
    "        right_sequences = ['']\n",
    "        \n",
    "    for right_sequence in right_sequences:\n",
    "        for left_sequence in left_sequences:\n",
    "            sequences.append(str(root.value) + right_sequence + left_sequence)\n",
    "            sequences.append(str(root.value) + left_sequence + right_sequence)\n",
    "    \n",
    "    return sequences\n",
    "array = [0, 1, 2, 4]\n",
    "root = minimal_tree(array)\n",
    "preorder_traversal(root)\n",
    "print()\n",
    "print(bst_sequences(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "General good practices:\n",
    "* Start with an example, maybe ask for it.\n",
    "* Choose an appropriate name for the method.\n",
    "* Appropriate names for variables, even if coding is longer.\n",
    "* Comments to include thoughts on special cases.\n",
    "* Include asserts in the function to check input parameters."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.9.12"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}