Algorithmic Problems in Python3.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "****\n",
    "# Algorithmic Problems solved in Python 3.7 (cont.)\n",
    "****\n",
    "<p style=\"text-align: right\"><i>Jesus Perez Colino<br>First version: November 2018<br></i></p>\n",
    "\n",
    "## About this notebook: \n",
    "****\n",
    "Notebook prepared by **Jesus Perez Colino** Version 0.2, First Released: 25/11/2018, Alpha\n",
    "\n",
    "- This work is licensed under a [Creative Commons Attribution-ShareAlike 3.0 Unported License](http://creativecommons.org/licenses/by-sa/3.0/deed.en_US). This work is offered for free, with the hope that it will be useful.\n",
    "\n",
    "\n",
    "- **Summary**: \n",
    "\n",
    ">This notebook is a **continuation** of the previous notebooks in algorithmic problems, but this time for Python 3.7. Some of them are well-know in Computer Science (searching, sorting, recursion, dynamic programming...), and other are more functional programming oriented or mathematically based. It includes examples of list comprenhension, map/reduce functions, generators, decorators, HPC simulations...\n",
    "\n",
    "\n",
    "- **Index**:\n",
    "\n",
    "\n",
    "    Problem 1: Is Fibonacci? (... starting with a classic)\n",
    "    Problem 2: Charles Babbage's homage\n",
    "    Problem 3: Dynamic programming \n",
    "    Problem 4: Knapsack problem (another classical)\n",
    "    Problem 5: Customizing String Formatting\n",
    "    Problem 6: Implementing a Data Model or Type System using Descriptors\n",
    "    Problem 7: Calling a Method on an Object given the Name as a string\n",
    "    Problem 8: Making Classes Support Comparison Operations Problem\n",
    "    Problem 9: Implementing a Priority Queue\n",
    "    Problem 10: Finding the Largest and the Smallest\n",
    "    Problem 11: Keeping the Last N Items\n",
    "    Problem 12: Mapping Keys to Multiple Values in a Dictionary\n",
    "    Problem 13: Keeping Dictionaries in Order\n",
    "    Problem 14: Calculating with dictionaries\n",
    "    Problem 15: Finding Commonalities in Two Dictionaries\n",
    "    Problem 16: Removing Duplicates from a Sequence while Maintaining Order\n",
    "    Problem 17: Determining the Most Frequently Occurring Items in a Sequence\n",
    "    Problem 18: Sorting a List of Dictionaries by a Common Key\n",
    "    Problem 19: Sorting Objects Without Native Comparison Support\n",
    "    Problem 20: Grouping Records Together Based on a Field\n",
    "    Problem 21: Filtering Sequence Elements\n",
    "    Problem 22: Test for Palindromic Permutations\n",
    "    Problem 23: Compute the Intersection of Two Sorted Arrays\n",
    "    Problem 24: Kadene's algorithm (... another classic)\n",
    "    Problem 25: Merge two Sorted Lists\n",
    "    Problem 26: Root Square of the Conditional Values of a dictionary\n",
    "    Problem 27: More about Palindromes...\n",
    "    Problem 28: Reversing integers\n",
    "    Problem 29: Find two elements that sum equal the target...\n",
    "    Problem 30: Count the number of ways to traverse a 2D array\n",
    "    Problem 31: Find the Longest Common Prefix\n",
    "    Problem 32: Maximum subarray\n",
    "    Problem 33: Maximum Depth of a Binary Tree\n",
    "    Problem 34: Sum root-to-leaf path in a Binary Tree\n",
    "    Problem 35: Find a root-to-leaf path with a specified sum in a Binary Tree"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "-------------------- Reproducibility conditions for this notebook -------------------\n",
      "Mon Dec 09 2019 \n",
      "\n",
      "CPython 3.7.4\n",
      "IPython 7.8.0\n",
      "\n",
      "numpy 1.16.5\n",
      "scipy 1.3.1\n",
      "matplotlib 3.1.1\n",
      "pandas 0.25.1\n",
      "\n",
      "compiler   : MSC v.1915 64 bit (AMD64)\n",
      "system     : Windows\n",
      "release    : 10\n",
      "machine    : AMD64\n",
      "processor  : Intel64 Family 6 Model 94 Stepping 3, GenuineIntel\n",
      "CPU cores  : 8\n",
      "interpreter: 64bit\n",
      "-------------------------------------------------------------------------------------\n"
     ]
    }
   ],
   "source": [
    "import IPython\n",
    "import numpy as np\n",
    "np.random.seed(12345)\n",
    "import pandas as pd\n",
    "import matplotlib.pyplot as plt\n",
    "import watermark\n",
    "\n",
    "import warnings\n",
    "warnings.filterwarnings('ignore')\n",
    "\n",
    "%load_ext watermark\n",
    "%matplotlib inline\n",
    "\n",
    "print(' Reproducibility conditions for this notebook '.center(85,'-'))\n",
    "%watermark -n -v -m -p numpy,scipy,matplotlib,pandas\n",
    "print('-'*85)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<a id=Problem 1: Is Fibonacci?><\\a>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 1: Is Fibonacci?\n",
    "\n",
    "Given a list of integers `mylist`, write a program to determine if any of the elements in `mylist` is an element of the Fibonacci sequence."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [],
   "source": [
    "def solve(mylist):\n",
    "    \n",
    "    fib_list = [0, 1]\n",
    "    fib_next = fib_list[-2] + fib_list[-1]\n",
    "    \n",
    "    while fib_next < max(mylist)+1:\n",
    "        fib_list.append(fib_next)\n",
    "        fib_next =  fib_list[-2] + fib_list[-1]\n",
    "        \n",
    "    for element in mylist:\n",
    "        if element in fib_list: print('{} is in the Fib. sequence'.format(element))\n",
    "        else: print('{} is not in the Fib. sequence'.format(element))\n",
    "            \n",
    "    return"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2 is in the Fib. sequence\n",
      "3 is in the Fib. sequence\n",
      "4 is not in the Fib. sequence\n",
      "5 is in the Fib. sequence\n",
      "6 is not in the Fib. sequence\n",
      "7 is not in the Fib. sequence\n",
      "8 is in the Fib. sequence\n",
      "34 is in the Fib. sequence\n"
     ]
    }
   ],
   "source": [
    "my_list = [2,3,4,5,6,7,8,34]\n",
    "solve(my_list)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "34"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# just for fun... here the simplest version to obtain the Fibonacci sequence\n",
    "# Notice that this version is not storing the whole sequence\n",
    "\n",
    "def fib(n):\n",
    "    if n <= 1: return n\n",
    "    fib_minus_2, fib_minus_1 = 0, 1\n",
    "    for _ in range(2,n):\n",
    "        fib_next = fib_minus_2 + fib_minus_1\n",
    "        fib_minus_2, fib_minus_1 = fib_minus_1 , fib_next\n",
    "    return fib_next\n",
    "\n",
    "fib(10)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 element of fib. seq. is 0\n",
      "2 element of fib. seq. is 1\n",
      "3 element of fib. seq. is 1\n",
      "4 element of fib. seq. is 2\n",
      "5 element of fib. seq. is 3\n",
      "6 element of fib. seq. is 5\n",
      "7 element of fib. seq. is 8\n",
      "8 element of fib. seq. is 13\n",
      "9 element of fib. seq. is 21\n",
      "10 element of fib. seq. is 34\n"
     ]
    }
   ],
   "source": [
    "# and also, more fun... Fibonacci sequence in one line:\n",
    "\n",
    "from functools import reduce\n",
    "\n",
    "fib = lambda n : reduce(lambda fib , n : [ fib[1] , fib[0] + fib[1] ], range(n-1) ,[0,1])[0]\n",
    "\n",
    "for i in range(10):\n",
    "    print(f'{i+1} element of fib. seq. is {fib(i+1)}')\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 2: Charles Babbage's homage\n",
    "\n",
    "Charles Babbage (1791 - 1871) loooking ahead to the sorts of problems his Analytical Engine would be able to solve, gave this example:\n",
    "> What's the smallest positive integer whose square ends in the digits 269,696?\n",
    "\n",
    "He thought the answer might be 99,736, whose square is 9,947,269,696 but he could not be certain..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "25264 squared is equal to 638269696 and it ends in  269696\n"
     ]
    }
   ],
   "source": [
    "x = [x for x in range(100000) if (x*x) % 1000000 == 269696][0]\n",
    "print(x, 'squared is equal to', x*x, 'and it ends in ', str(x*x)[-6:])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 75,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "25264 squared is equal to 638269696 and it ends in  269696\n"
     ]
    }
   ],
   "source": [
    "x = [x for x in range(100000) if str(x*x)[-6:]== '269696'][0]\n",
    "print(x, 'squared is equal to', x*x, 'and it ends in ', str(x*x)[-6:])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 3: Dynamic programming\n",
    "\n",
    "Find the number of sets of integers in `[ 2, 4, 6, 10 ]` that add up to `16`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {},
   "outputs": [],
   "source": [
    "# First solution: recursive version (no optimal)\n",
    "\n",
    "def recursive(array, total, i): \n",
    "    if total == 0 : \n",
    "        return 1\n",
    "    elif total < 0 : \n",
    "        return 0\n",
    "    elif i < 0 : \n",
    "        return 0\n",
    "    elif total < array[i]: \n",
    "        return recursive(array, total, i-1)\n",
    "    else: \n",
    "        return recursive(array, total - array[i], i-1) + recursive(array, total, i-1)\n",
    "    \n",
    "\n",
    "def count_set(array, total):\n",
    "    return recursive(array, total, len(array)-1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "metadata": {},
   "outputs": [],
   "source": [
    "myarray = [2,4,6,10]\n",
    "total_sum = 16"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 63,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 63,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\n",
    "count_set(myarray, total_sum)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Second solution: dynamic programming solution (memoizing)\n",
    "\n",
    "def count_sets_dp(array, total):\n",
    "    mem = {}\n",
    "    return dp(array, total, len(array)-1, mem)\n",
    "\n",
    "def dp(array, total, i, mem):\n",
    "    key = str(total) + ':' + str(i)\n",
    "    if key in mem:\n",
    "        return mem[key]\n",
    "    elif total == 0:\n",
    "        return 1\n",
    "    elif total < 0:\n",
    "        return 0\n",
    "    elif i < 0:\n",
    "        return 0\n",
    "    elif total < array[i]:\n",
    "        to_return = dp(array, total, i-1, mem)\n",
    "    else: \n",
    "        to_return = dp(array, total-array[i], i-1, mem) \\\n",
    "                    + dp(array, total, i-1, mem)\n",
    "        \n",
    "    mem[key] = to_return\n",
    "    return to_return\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 62,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 62,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\n",
    "count_sets_dp(a, total_sum)    \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 4: Knapsack problem (another classical)\n",
    "\n",
    "Given a set of items, each with a weight and a value, determine the number of each item to include in a collection, so that the total weight is less or equal to a given limit and the total value is as larger as possible."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [],
   "source": [
    "# list of items: tuple of tuples of ('name', weight, value)\n",
    "\n",
    "items = (\n",
    "    (\"map\", 9, 150), (\"compass\", 13, 35), (\"water\", 153, 200), (\"sandwich\", 50, 160),\n",
    "    (\"glucose\", 15, 60), (\"tin\", 68, 45), (\"banana\", 27, 60), (\"apple\", 39, 40),\n",
    "    (\"cheese\", 23, 30), (\"beer\", 52, 10), (\"suntan cream\", 11, 70), (\"camera\", 32, 30),\n",
    "    (\"t-shirt\", 24, 15), (\"trousers\", 48, 10), (\"umbrella\", 73, 40),\n",
    "    (\"waterproof trousers\", 42, 70), (\"waterproof overclothes\", 43, 75),\n",
    "    (\"note-case\", 22, 80), (\"sunglasses\", 7, 20), (\"towel\", 18, 12),\n",
    "    (\"socks\", 4, 50), (\"book\", 30, 10),\n",
    "    )\n",
    "\n",
    "max_weight = 400"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [],
   "source": [
    "def total_value(items, max_weight):\n",
    "    return sum([x[2] for x in items]) if sum([x[1] for x in items])<max_weight else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Recursive dynamic algorithmic solution\n",
    "\n",
    "cache = {}\n",
    "def solve(items, max_weight):\n",
    "    if not items:\n",
    "        return()\n",
    "    if (items, max_weight) not in cache:\n",
    "        head = items[0]\n",
    "        tail = items[1:]\n",
    "        include = (head,) + solve(tail, max_weight - head[1])\n",
    "        dont_include = solve(tail, max_weight)\n",
    "        if total_value(include, max_weight) > total_value(dont_include, max_weight):\n",
    "            answer = include\n",
    "        else:\n",
    "            answer = dont_include\n",
    "        cache[(items, max_weight)] = answer\n",
    "    return cache[(items, max_weight)]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "items: \n",
      "map\n",
      "compass\n",
      "water\n",
      "sandwich\n",
      "glucose\n",
      "banana\n",
      "suntan cream\n",
      "waterproof trousers\n",
      "waterproof overclothes\n",
      "note-case\n",
      "sunglasses\n",
      "socks\n",
      "====================\n",
      "value:  1030\n",
      "weight:  396\n",
      "====================\n"
     ]
    }
   ],
   "source": [
    "cache = {}\n",
    "solution = solve(items, max_weight)\n",
    "\n",
    "print('items: ')\n",
    "for x in solution: print(x[0])\n",
    "print('='*20)\n",
    "print('value: ', total_value(solution, max_weight))\n",
    "print('weight: ', sum([x[1] for x in solution]))\n",
    "print('='*20)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 5: Customizing String Formatting\n",
    "Build a Date class, with year, month and day as inputs, that is able to return the date in multiple formats, using an external format dictionary."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 62,
   "metadata": {},
   "outputs": [],
   "source": [
    "_formats = {\n",
    "    'ymd' : '{d.year}--{d.month}--{d.day}',\n",
    "    'mdy' : '{d.month}//{d.day}//{d.year}',\n",
    "    'dmy' : '{d.day}||{d.month}||{d.year}'\n",
    "    }"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 63,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Date(object):\n",
    "    def __init__(self, year, month, day):\n",
    "        self.year = year\n",
    "        self.month = month\n",
    "        self.day = day\n",
    "    def __format__(self, code):\n",
    "        if code == '':\n",
    "            code = 'ymd'\n",
    "        fmt = _formats[code]\n",
    "        return fmt.format(d=self)\n",
    "    def __str__(self):\n",
    "        return format(d,'ymd')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 64,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2012--12--21\n"
     ]
    }
   ],
   "source": [
    "d = Date(2012, 12, 21)\n",
    "print(d)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 65,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'The date is 2012--12--21'"
      ]
     },
     "execution_count": 65,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "f\"The date is {format(d)}\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 66,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'The date is 12//21//2012'"
      ]
     },
     "execution_count": 66,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "f\"The date is {format(d, 'mdy')}\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 67,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'The date is 21||12||2012'"
      ]
     },
     "execution_count": 67,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "f\"The date is {format(d, 'dmy')}\"\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 6: Implementing a Data Model or Type System using Descriptors\n",
    "\n",
    "You want to define several kinds of data structures, but want to enforce constraints on the values that are allowed to be assigned to certain attributes."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 88,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Base class. Uses a descriptor to set a value\n",
    "\n",
    "class Descriptor(object):\n",
    "    def __init__(self, name=None, **opts):\n",
    "        self.name = name\n",
    "        for key, value in opts.items():\n",
    "            setattr(self, key, value)\n",
    "    def __set__(self, instance, value):\n",
    "        instance.__dict__[self.name] = value"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 169,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Descriptor for enforcing types\n",
    "\n",
    "class Typed(Descriptor):\n",
    "    expected_type = type(None)\n",
    "    def __set__(self, instance, value):\n",
    "        if not isinstance(value, self.expected_type):\n",
    "            raise TypeError('expected ' + str(self.expected_type))\n",
    "        super().__set__(instance, value)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 90,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Unsigned(Descriptor):\n",
    "    def __set__(self, instance, value):\n",
    "        if value < 0:\n",
    "            raise ValueError('Expected >= 0')\n",
    "        super().__set__(instance, value)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 91,
   "metadata": {},
   "outputs": [],
   "source": [
    "class MaxSized(Descriptor):\n",
    "    def __init__(self, name=None, **opts):\n",
    "        if 'size' not in opts:\n",
    "            raise TypeError('missing size option')\n",
    "        super().__init__(name, **opts)\n",
    "    def __set__(self, instance, value):\n",
    "        if len(value) >= self.size:\n",
    "            raise ValueError('size must be < ' + str(self.size))\n",
    "        super().__set__(instance, value)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "These classes should be viewed as basic building blocks from which you construct a data model or type system. \n",
    "\n",
    "Continuing, here is some code that implements some different kinds of data:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 92,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Integer(Typed):\n",
    "    expected_type = int\n",
    "\n",
    "class UnsignedInteger(Integer, Unsigned):\n",
    "    pass\n",
    "\n",
    "class Float(Typed):\n",
    "    expected_type = float\n",
    "\n",
    "class UnsignedFloat(Float, Unsigned):\n",
    "    pass\n",
    "\n",
    "class String(Typed):\n",
    "    expected_type = str\n",
    "\n",
    "class SizedString(String, MaxSized):\n",
    "    pass"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 158,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Stock(list):\n",
    "    # Specify constraints\n",
    "    name = SizedString('name',size=8)\n",
    "    shares = UnsignedInteger('shares')\n",
    "    price = UnsignedFloat('price')\n",
    "    def __init__(self, name, shares, price):\n",
    "        self.name = name\n",
    "        self.shares = shares\n",
    "        self.price = price\n",
    "    def __str__(self):\n",
    "        return f\"{[self.name, self.shares, self.price]}\"\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 162,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['GOOG', 10, 11.1]\n"
     ]
    }
   ],
   "source": [
    "s = Stock('GOOG', 10, 11.1)\n",
    "print(s)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 167,
   "metadata": {},
   "outputs": [
    {
     "ename": "TypeError",
     "evalue": "expected <class 'str'>",
     "output_type": "error",
     "traceback": [
      "\u001b[1;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[1;31mTypeError\u001b[0m                                 Traceback (most recent call last)",
      "\u001b[1;32m<ipython-input-167-4aedaa8da14a>\u001b[0m in \u001b[0;36m<module>\u001b[1;34m\u001b[0m\n\u001b[1;32m----> 1\u001b[1;33m \u001b[0ms\u001b[0m \u001b[1;33m=\u001b[0m \u001b[0mStock\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;36m11.1\u001b[0m\u001b[1;33m,\u001b[0m \u001b[1;36m11.1\u001b[0m\u001b[1;33m,\u001b[0m \u001b[1;36m11.1\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m      2\u001b[0m \u001b[0mprint\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0ms\u001b[0m\u001b[1;33m)\u001b[0m \u001b[1;31m# <<<--- It should print an error\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n",
      "\u001b[1;32m<ipython-input-166-0a74c2b7dc12>\u001b[0m in \u001b[0;36m__init__\u001b[1;34m(self, name, shares, price)\u001b[0m\n\u001b[0;32m     17\u001b[0m \u001b[1;32mclass\u001b[0m \u001b[0mStock\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mobject\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m     18\u001b[0m     \u001b[1;32mdef\u001b[0m \u001b[0m__init__\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mself\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mname\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mshares\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mprice\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m---> 19\u001b[1;33m         \u001b[0mself\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mname\u001b[0m \u001b[1;33m=\u001b[0m \u001b[0mname\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m     20\u001b[0m         \u001b[0mself\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mshares\u001b[0m \u001b[1;33m=\u001b[0m \u001b[0mshares\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m     21\u001b[0m         \u001b[0mself\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mprice\u001b[0m \u001b[1;33m=\u001b[0m \u001b[0mprice\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n",
      "\u001b[1;32m<ipython-input-89-2f031351459e>\u001b[0m in \u001b[0;36m__set__\u001b[1;34m(self, instance, value)\u001b[0m\n\u001b[0;32m      5\u001b[0m     \u001b[1;32mdef\u001b[0m \u001b[0m__set__\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mself\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0minstance\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mvalue\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m      6\u001b[0m         \u001b[1;32mif\u001b[0m \u001b[1;32mnot\u001b[0m \u001b[0misinstance\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mvalue\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mself\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mexpected_type\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m----> 7\u001b[1;33m             \u001b[1;32mraise\u001b[0m \u001b[0mTypeError\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;34m'expected '\u001b[0m \u001b[1;33m+\u001b[0m \u001b[0mstr\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mself\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mexpected_type\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m      8\u001b[0m         \u001b[0msuper\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0m__set__\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0minstance\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mvalue\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n",
      "\u001b[1;31mTypeError\u001b[0m: expected <class 'str'>"
     ]
    }
   ],
   "source": [
    "s = Stock(11.1, 11.1, 11.1)\n",
    "\n",
    "print(s) # <<<--- It should print an Type ERROR "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Another approach is to use a class decorator, like this:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 166,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Class decorator to apply constraints\n",
    "def check_attributes(**kwargs):\n",
    "    def decorate(cls):\n",
    "        for key, value in kwargs.items():\n",
    "            if isinstance(value, Descriptor):\n",
    "                value.name = key\n",
    "                setattr(cls, key, value)\n",
    "            else:\n",
    "                setattr(cls, key, value(key))\n",
    "        return cls\n",
    "    return decorate"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 166,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Example\n",
    "@check_attributes(name=SizedString(size=8),\n",
    "                  shares=UnsignedInteger,\n",
    "                  price=UnsignedFloat)\n",
    "class Stock(object):\n",
    "    def __init__(self, name, shares, price):\n",
    "        self.name = name\n",
    "        self.shares = shares\n",
    "        self.price = price"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Or, with an additional twist, a class decorator approach can also be used as a replacement for mixin classes, multiple inheritance, and tricky use of the super() function. Here is an alternative formulation of this recipe that uses class decorators:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 171,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Base class. Uses a descriptor to set a value\n",
    "class Descriptor(object):\n",
    "    def __init__(self, name=None, **opts):\n",
    "        self.name = name\n",
    "        for key, value in opts.items():\n",
    "            setattr(self, key, value)\n",
    "    def __set__(self, instance, value):\n",
    "        instance.__dict__[self.name] = value"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 172,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Decorator for applying type checking\n",
    "def Typed(expected_type, cls=None):\n",
    "    if cls is None:\n",
    "        return lambda cls: Typed(expected_type, cls)\n",
    "    super_set = cls.__set__\n",
    "    def __set__(self, instance, value):\n",
    "        if not isinstance(value, expected_type):\n",
    "            raise TypeError('expected ' + str(expected_type))\n",
    "        super_set(self, instance, value)\n",
    "    cls.__set__ = __set__\n",
    "    return cls\n",
    "\n",
    "# Decorator for unsigned values\n",
    "def Unsigned(cls):\n",
    "    super_set = cls.__set__\n",
    "    def __set__(self, instance, value):\n",
    "        if value < 0:\n",
    "            raise ValueError('Expected >= 0')\n",
    "        super_set(self, instance, value)\n",
    "    cls.__set__ = __set__\n",
    "    return cls\n",
    "\n",
    "# Decorator for allowing sized values\n",
    "def MaxSized(cls):\n",
    "    super_init = cls.__init__\n",
    "    def __init__(self, name=None, **opts):\n",
    "        if 'size' not in opts:\n",
    "            raise TypeError('missing size option')\n",
    "        super_init(self, name, **opts)\n",
    "    cls.__init__ = __init__\n",
    "    super_set = cls.__set__\n",
    "    def __set__(self, instance, value):\n",
    "        if len(value) >= self.size:\n",
    "            raise ValueError('size must be < ' + str(self.size))\n",
    "        super_set(self, instance, value)\n",
    "    cls.__set__ = __set__\n",
    "    return cls"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 173,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Specialized descriptors\n",
    "\n",
    "@Typed(int)\n",
    "class Integer(Descriptor):\n",
    "    pass\n",
    "\n",
    "@Unsigned\n",
    "class UnsignedInteger(Integer):\n",
    "    pass\n",
    "\n",
    "@Typed(float)\n",
    "class Float(Descriptor):\n",
    "    pass\n",
    "\n",
    "@Unsigned\n",
    "class UnsignedFloat(Float):\n",
    "    pass\n",
    "\n",
    "@Typed(str)\n",
    "class String(Descriptor):\n",
    "    pass\n",
    "\n",
    "@MaxSized\n",
    "class SizedString(String):\n",
    "    pass"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 7: Calling a Method on an Object Given the Name As a String\n",
    "\n",
    "You have the name of a method that you want to call on an object stored in a string and you want to execute the method."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 175,
   "metadata": {},
   "outputs": [],
   "source": [
    "import math\n",
    "\n",
    "class Point(object):\n",
    "    def __init__(self, x, y):\n",
    "        self.x = x\n",
    "        self.y = y\n",
    "    def __repr__(self):\n",
    "        return 'Point({!r:},{!r:})'.format(self.x, self.y)\n",
    "    def distance(self, x, y):\n",
    "        return math.hypot(self.x - x, self.y - y)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 182,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3.605551275463989"
      ]
     },
     "execution_count": 182,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "p = Point(2, 3)\n",
    "p.distance(0,0)       # <- Usual call of method"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 180,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3.605551275463989"
      ]
     },
     "execution_count": 180,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "d = getattr(p, 'distance')(0, 0)     # <- Calls p.distance(0, 0) as string\n",
    "d"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 181,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.0"
      ]
     },
     "execution_count": 181,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "getattr(p, 'distance')(2, 3)     # Calls p.distance(0, 0)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 8: Making Classes Support Comparison Operations Problem\n",
    "\n",
    "You’d like to be able to compare instances of your class using the standard comparison operators (e.g., >=, !=, ⇐, etc.), but without having to write a lot of special methods."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 189,
   "metadata": {},
   "outputs": [],
   "source": [
    "from functools import total_ordering\n",
    "class Room(object):\n",
    "    def __init__(self, name, length, width):\n",
    "        self.name = name\n",
    "        self.length = length\n",
    "        self.width = width\n",
    "        self.square_feet = self.length * self.width\n",
    "\n",
    "@total_ordering\n",
    "class House(object):\n",
    "    def __init__(self, name, style):\n",
    "        self.name = name\n",
    "        self.style = style\n",
    "        self.rooms = list()\n",
    "    @property\n",
    "    def living_space_footage(self):\n",
    "        return sum(r.square_feet for r in self.rooms)\n",
    "    def add_room(self, room):\n",
    "        self.rooms.append(room)\n",
    "    def __str__(self):\n",
    "        return '{}: {} square foot {}'.format(self.name, self.living_space_footage, self.style)\n",
    "    def __eq__(self, other):\n",
    "        return self.living_space_footage == other.living_space_footage\n",
    "    def __lt__(self, other):\n",
    "        return self.living_space_footage < other.living_space_footage\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 190,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Build a few houses, and add rooms to them\n",
    "h1 = House('house1', 'Cape')\n",
    "h1.add_room(Room('Master Bedroom', 14, 21))\n",
    "h1.add_room(Room('Living Room', 18, 20))\n",
    "h1.add_room(Room('Kitchen', 12, 16))\n",
    "h1.add_room(Room('Office', 12, 12))\n",
    "\n",
    "h2 = House('house2', 'Ranch')\n",
    "h2.add_room(Room('Master Bedroom', 14, 21))\n",
    "h2.add_room(Room('Living Room', 18, 20))\n",
    "h2.add_room(Room('Kitchen', 12, 16))\n",
    "\n",
    "h3 = House('house3', 'Split')\n",
    "h3.add_room(Room('Master Bedroom', 14, 21))\n",
    "h3.add_room(Room('Living Room', 18, 20))\n",
    "h3.add_room(Room('Office', 12, 16))\n",
    "h3.add_room(Room('Kitchen', 15, 17))\n",
    "houses = [h1, h2, h3]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 191,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Is house1 bigger than house2?:  True\n"
     ]
    }
   ],
   "source": [
    "print('Is house1 bigger than house2?: ', h1 > h2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 192,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Is house2 smaller than house3?:  True\n"
     ]
    }
   ],
   "source": [
    "print('Is house2 smaller than house3?: ', h2 < h3) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 193,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Is house2 greater than or equal to house1? False\n"
     ]
    }
   ],
   "source": [
    "print('Is house2 greater than or equal to house1?', h2 >= h1) "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 9: Implementing a Priority Queue\n",
    "\n",
    "Implement a queue that **sorts items by a given priority**, and always **returns the item with the highest priority** on each pop operation"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "import heapq\n",
    "\n",
    "class PriorityQueue(object):\n",
    "    def __init__(self):\n",
    "        self._queue = []\n",
    "        self._index = 0\n",
    "    def push(self, item, priority):\n",
    "        heapq.heappush(self._queue, (-priority, self._index, item))\n",
    "        self._index += 1\n",
    "    def pop(self):\n",
    "        return heapq.heappop(self._queue)[-1]\n",
    "    def __repr__(self):\n",
    "        return f\"queue element: {self._queue} index: {self._index}\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Item(object):\n",
    "    def __init__(self, name):\n",
    "        self.name = name\n",
    "    def __repr__(self):\n",
    "        return 'Item({!r})'.format(self.name)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "queue element: [(-1, 0, Item('foo'))] index: 1"
      ]
     },
     "execution_count": 31,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "q = PriorityQueue()\n",
    "q.push(Item('foo'), 1)\n",
    "q"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "queue element: [(-5, 1, Item('bar')), (-1, 0, Item('foo'))] index: 2"
      ]
     },
     "execution_count": 32,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "q.push(Item('bar'), 5)\n",
    "q"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "queue element: [(-5, 1, Item('bar')), (-1, 0, Item('foo')), (-4, 2, Item('spam'))] index: 3"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "q.push(Item('spam'), 4)\n",
    "q"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "queue element: [(-5, 1, Item('bar')), (-1, 0, Item('foo')), (-4, 2, Item('spam')), (-1, 3, Item('grok'))] index: 4"
      ]
     },
     "execution_count": 34,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "q.push(Item('grok'), 1)\n",
    "q"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Item('bar')\n",
      "Item('spam')\n",
      "Item('foo')\n",
      "Item('grok')\n"
     ]
    }
   ],
   "source": [
    "print(q.pop())\n",
    "print(q.pop())\n",
    "print(q.pop())\n",
    "print(q.pop())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 10: Finding the Largest and the Smallest\n",
    "\n",
    "Make a list of the largest or smallest N items in a collection."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [],
   "source": [
    "portfolio = [\n",
    "   {'name': 'IBM', 'shares': 100, 'price': 91.1},\n",
    "   {'name': 'AAPL', 'shares': 50, 'price': 543.22},\n",
    "   {'name': 'FB', 'shares': 200, 'price': 21.09},\n",
    "   {'name': 'HPQ', 'shares': 35, 'price': 31.75},\n",
    "   {'name': 'YHOO', 'shares': 45, 'price': 16.35},\n",
    "   {'name': 'ACME', 'shares': 75, 'price': 115.65}\n",
    "]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[{'name': 'YHOO', 'shares': 45, 'price': 16.35},\n",
       " {'name': 'FB', 'shares': 200, 'price': 21.09},\n",
       " {'name': 'HPQ', 'shares': 35, 'price': 31.75}]"
      ]
     },
     "execution_count": 40,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import heapq\n",
    "\n",
    "cheap = heapq.nsmallest(3, portfolio, key=lambda s: s['price'])\n",
    "cheap"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[{'name': 'AAPL', 'shares': 50, 'price': 543.22},\n",
       " {'name': 'ACME', 'shares': 75, 'price': 115.65},\n",
       " {'name': 'IBM', 'shares': 100, 'price': 91.1}]"
      ]
     },
     "execution_count": 41,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "expensive = heapq.nlargest(3, portfolio, key=lambda s: s['price'])\n",
    "expensive"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 11: Keeping the Last N Items\n",
    "\n",
    "Keep a limited history of the last few items seen during iteration or during some other kind of processing"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "deque([1, 2, 3])"
      ]
     },
     "execution_count": 42,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from collections import deque\n",
    "\n",
    "q = deque(maxlen=3)\n",
    "q.append(1)\n",
    "q.append(2)\n",
    "q.append(3)\n",
    "q"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "deque([10, 20, 30])"
      ]
     },
     "execution_count": 44,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "q.append(10)\n",
    "q.append(20)\n",
    "q.append(30)\n",
    "q"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {},
   "outputs": [],
   "source": [
    "def search(lines, pattern, history=5):\n",
    "    previous_lines = deque(maxlen=history)\n",
    "    for line in lines:\n",
    "        if pattern in line:\n",
    "            yield line, previous_lines\n",
    "        previous_lines.append(line)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "with open('somefile.txt') as f:\n",
    "    for line, prevlines in search(f, 'python', 5):\n",
    "        for pline in prevlines:\n",
    "            print(pline, end='')\n",
    "        print(line, end='')\n",
    "        print('-'*20)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 12: Mapping Keys to Multiple Values in a Dictionary\n",
    "\n",
    "You want to make a dictionary that maps keys to more than one value (a so-called \"multidict\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {},
   "outputs": [],
   "source": [
    "# A dictionary is a mapping where each key is mapped to a single value. \n",
    "# If you want to map keys to multiple values, you need to store the multiple \n",
    "# values in another container such as a list or set. \n",
    "\n",
    "d = {\n",
    "   'a' : [1, 2, 3],\n",
    "   'b' : [4, 5]\n",
    "}\n",
    "\n",
    "e = {\n",
    "   'a' : {1, 2, 3},\n",
    "   'b' : {4, 5}\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defaultdict(list, {'a': [1, 2], 'b': [4]})"
      ]
     },
     "execution_count": 48,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from collections import defaultdict\n",
    "\n",
    "d = defaultdict(list)\n",
    "d['a'].append(1)\n",
    "d['a'].append(2)\n",
    "d['b'].append(4)\n",
    "\n",
    "d"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defaultdict(set, {'a': {1, 2}, 'b': {4}})"
      ]
     },
     "execution_count": 49,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "d = defaultdict(set)\n",
    "d['a'].add(1)\n",
    "d['a'].add(2)\n",
    "d['b'].add(4)\n",
    "\n",
    "d"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'a': [1, 2], 'b': [4]}"
      ]
     },
     "execution_count": 51,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "d = {}    # A regular dictionary\n",
    "d.setdefault('a', []).append(1)\n",
    "d.setdefault('a', []).append(2)\n",
    "d.setdefault('b', []).append(4)\n",
    "d"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 13: Keeping Dictionaries in Order\n",
    "\n",
    "Create a dictionary, and you also want to control the order of items when iterating or serializing"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "foo 1\n",
      "bar 2\n",
      "spam 3\n",
      "grok 4\n"
     ]
    }
   ],
   "source": [
    "#To control the order of items in a dictionary, you can use an OrderedDict from the collections module. \n",
    "#It exactly preserves the original insertion order of data when iterating.\n",
    "\n",
    "from collections import OrderedDict\n",
    "\n",
    "d = OrderedDict()\n",
    "d['foo'] = 1\n",
    "d['bar'] = 2\n",
    "d['spam'] = 3\n",
    "d['grok'] = 4\n",
    "\n",
    "# Outputs \"foo 1\", \"bar 2\", \"spam 3\", \"grok 4\"\n",
    "for key in d:\n",
    "    print(key, d[key])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 14: Calculating with dictionaries\n",
    "\n",
    "Perform various calculations (e.g., minimum value, maximum value, sorting, etc.) on a dictionary of data"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "metadata": {},
   "outputs": [],
   "source": [
    "prices = {\n",
    "   'ACME': 45.23,\n",
    "   'AAPL': 612.78,\n",
    "   'IBM': 205.55,\n",
    "   'HPQ': 37.20,\n",
    "   'FB': 10.75\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 65,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'FB'"
      ]
     },
     "execution_count": 65,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "min(prices, key=lambda k: prices[k])  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 66,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'AAPL'"
      ]
     },
     "execution_count": 66,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "max(prices, key=lambda k: prices[k]) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(10.75, 'FB')"
      ]
     },
     "execution_count": 55,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "min_price = min(zip(prices.values(), prices.keys()))\n",
    "min_price"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(612.78, 'AAPL')"
      ]
     },
     "execution_count": 57,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "max_price = max(zip(prices.values(), prices.keys()))\n",
    "max_price"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(10.75, 'FB'),\n",
       " (37.2, 'HPQ'),\n",
       " (45.23, 'ACME'),\n",
       " (205.55, 'IBM'),\n",
       " (612.78, 'AAPL')]"
      ]
     },
     "execution_count": 58,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "prices_sorted = sorted(zip(prices.values(), prices.keys()))\n",
    "prices_sorted"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 64,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[(45.23, 'ACME'), (612.78, 'AAPL'), (205.55, 'IBM'), (37.2, 'HPQ'), (10.75, 'FB')]\n"
     ]
    }
   ],
   "source": [
    "x = list(zip(prices.values(), prices.keys()))\n",
    "print(x)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 15: Finding Commonalities in Two Dictionaries\n",
    "\n",
    "You have two dictionaries and want to find out what they might have in common (same keys, same values, etc.)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 67,
   "metadata": {},
   "outputs": [],
   "source": [
    "a = {\n",
    "   'x' : 1,\n",
    "   'y' : 2,\n",
    "   'z' : 3\n",
    "}\n",
    "\n",
    "b = {\n",
    "   'w' : 10,\n",
    "   'x' : 11,\n",
    "   'y' : 2\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 72,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'x', 'y'}"
      ]
     },
     "execution_count": 72,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Find keys in common\n",
    "a.keys() & b.keys()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 71,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'z'}"
      ]
     },
     "execution_count": 71,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Find keys in a that are not in b\n",
    "a.keys() - b.keys() "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 70,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{('y', 2)}"
      ]
     },
     "execution_count": 70,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Find (key,value) pairs in common\n",
    "a.items() & b.items()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 73,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'x': 1, 'y': 2}"
      ]
     },
     "execution_count": 73,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Make a new dictionary with certain keys removed\n",
    "c = {key:a[key] for key in a.keys() - {'z', 'w'}}\n",
    "# c is {'x': 1, 'y': 2}\n",
    "c"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 16: Removing Duplicates from a Sequence while Maintaining Order\n",
    "\n",
    "Eliminate the duplicate values in a sequence, but preserve the order of the remaining items"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 93,
   "metadata": {},
   "outputs": [],
   "source": [
    "def dedupe(items):\n",
    "    seen = set()\n",
    "    for item in items:\n",
    "        if item not in seen:\n",
    "            yield item\n",
    "            seen.add(item)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 94,
   "metadata": {},
   "outputs": [],
   "source": [
    "a = [1, 5, 2, 1, 9, 1, 5, 10]\n",
    "set_a = set(a)\n",
    "duplicates_ordered = list(dedupe(a))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 95,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Original list:  [1, 5, 2, 1, 9, 1, 5, 10]\n",
      "Set of original list:  {1, 2, 5, 9, 10}\n",
      "Ordered set of original list:  [1, 5, 2, 9, 10]\n"
     ]
    }
   ],
   "source": [
    "print(\"Original list: \", a)\n",
    "print(\"Set of original list: \", set_a)\n",
    "print(\"Ordered set of original list: \", duplicates_ordered)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 96,
   "metadata": {},
   "outputs": [],
   "source": [
    "# If you are trying to eliminate duplicates in a sequence of unhashable types (such as dicts), \n",
    "# you can make a slight change to this recipe, as follows:\n",
    "\n",
    "def dedupe(items, key=None):\n",
    "    seen = set()\n",
    "    for item in items:\n",
    "        val = item if key is None else key(item)\n",
    "        if val not in seen:\n",
    "            yield item\n",
    "            seen.add(val)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 103,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[{'x': 1, 'y': 2}, {'x': 1, 'y': 3}, {'x': 2, 'y': 4}]"
      ]
     },
     "execution_count": 103,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "b = [ {'x':1, 'y':2}, {'x':1, 'y':3}, {'x':1, 'y':2}, {'x':2, 'y':4}]\n",
    "\n",
    "list(dedupe(b, key=lambda d: (d['x'],d['y'])))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 17: Determining the Most Frequently Occurring Items in a Sequence\n",
    "\n",
    "Given a sequence of items, determine the most frequently occurring items in the sequence"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 104,
   "metadata": {},
   "outputs": [],
   "source": [
    "words = [\n",
    "   'look', 'into', 'my', 'eyes', 'look', 'into', 'my', 'eyes',\n",
    "   'the', 'eyes', 'the', 'eyes', 'the', 'eyes', 'not', 'around', 'the',\n",
    "   'eyes', \"don't\", 'look', 'around', 'the', 'eyes', 'look', 'into',\n",
    "   'my', 'eyes', \"you're\", 'under'\n",
    "]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 105,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[('eyes', 8), ('the', 5), ('look', 4)]\n"
     ]
    }
   ],
   "source": [
    "from collections import Counter\n",
    "\n",
    "word_counts = Counter(words)\n",
    "top_three = word_counts.most_common(3)\n",
    "print(top_three)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 134,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[(8, 'eyes'), (5, 'the'), (4, 'look')]\n"
     ]
    }
   ],
   "source": [
    "word_counts = {}\n",
    "for word in words:\n",
    "    if word not in word_counts.keys():\n",
    "        word_counts[word]=1\n",
    "    else:\n",
    "        word_counts[word]+=1\n",
    "\n",
    "words_counts_sorted = sorted(zip(word_counts.values(), word_counts.keys()), reverse=True)\n",
    "top_three = words_counts_sorted[:3]\n",
    "print(top_three)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 18: Sorting a List of Dictionaries by a Common Key\n",
    "\n",
    "Given a list of dictionaries, sort the entries according to one or more of the dictionary values"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 135,
   "metadata": {},
   "outputs": [],
   "source": [
    "rows = [\n",
    "    {'fname': 'Brian', 'lname': 'Jones', 'uid': 1003},\n",
    "    {'fname': 'David', 'lname': 'Beazley', 'uid': 1002},\n",
    "    {'fname': 'John', 'lname': 'Cleese', 'uid': 1001},\n",
    "    {'fname': 'Big', 'lname': 'Jones', 'uid': 1004}\n",
    "]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 137,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[{'fname': 'Big', 'lname': 'Jones', 'uid': 1004}, {'fname': 'Brian', 'lname': 'Jones', 'uid': 1003}, {'fname': 'David', 'lname': 'Beazley', 'uid': 1002}, {'fname': 'John', 'lname': 'Cleese', 'uid': 1001}]\n"
     ]
    }
   ],
   "source": [
    "from operator import itemgetter\n",
    "\n",
    "rows_by_fname = sorted(rows, key=itemgetter('fname'))\n",
    "print(rows_by_fname)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 138,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[{'fname': 'John', 'lname': 'Cleese', 'uid': 1001}, {'fname': 'David', 'lname': 'Beazley', 'uid': 1002}, {'fname': 'Brian', 'lname': 'Jones', 'uid': 1003}, {'fname': 'Big', 'lname': 'Jones', 'uid': 1004}]\n"
     ]
    }
   ],
   "source": [
    "rows_by_uid = sorted(rows, key=itemgetter('uid'))\n",
    "print(rows_by_uid)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 139,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[{'fname': 'David', 'lname': 'Beazley', 'uid': 1002}, {'fname': 'John', 'lname': 'Cleese', 'uid': 1001}, {'fname': 'Big', 'lname': 'Jones', 'uid': 1004}, {'fname': 'Brian', 'lname': 'Jones', 'uid': 1003}]\n"
     ]
    }
   ],
   "source": [
    "rows_by_lfname = sorted(rows, key=itemgetter('lname','fname'))\n",
    "print(rows_by_lfname)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 19: Sorting Objects Without Native Comparison Support\n",
    "\n",
    "Sort objects of the same class, but they don’t natively support comparison operations"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 140,
   "metadata": {},
   "outputs": [],
   "source": [
    "class User(object):\n",
    "    def __init__(self, user_id):\n",
    "        self.user_id = user_id\n",
    "    def __repr__(self):\n",
    "        return 'User({})'.format(self.user_id)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 142,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[User(23), User(3), User(99)]"
      ]
     },
     "execution_count": 142,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "users = [User(23), User(3), User(99)]\n",
    "users"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 143,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[User(3), User(23), User(99)]"
      ]
     },
     "execution_count": 143,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sorted(users, key=lambda u: u.user_id) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 144,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[User(3), User(23), User(99)]"
      ]
     },
     "execution_count": 144,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from operator import attrgetter\n",
    "sorted(users, key=attrgetter('user_id')) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 145,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "User(3)"
      ]
     },
     "execution_count": 145,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "min(users, key=lambda u: u.user_id) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 146,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "User(99)"
      ]
     },
     "execution_count": 146,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "max(users, key=lambda u: u.user_id) "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 20: Grouping Records Together Based on a Field\n",
    "Given a sequence of dictionaries or instances and you want to iterate over the data in groups based on the value of a particular field, such as date."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 147,
   "metadata": {},
   "outputs": [],
   "source": [
    "rows = [\n",
    "    {'address': '5412 N CLARK', 'date': '07/01/2012'},\n",
    "    {'address': '5148 N CLARK', 'date': '07/04/2012'},\n",
    "    {'address': '5800 E 58TH', 'date': '07/02/2012'},\n",
    "    {'address': '2122 N CLARK', 'date': '07/03/2012'},\n",
    "    {'address': '5645 N RAVENSWOOD', 'date': '07/02/2012'},\n",
    "    {'address': '1060 W ADDISON', 'date': '07/02/2012'},\n",
    "    {'address': '4801 N BROADWAY', 'date': '07/01/2012'},\n",
    "    {'address': '1039 W GRANVILLE', 'date': '07/04/2012'},\n",
    "]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 151,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[{'address': '5412 N CLARK', 'date': '07/01/2012'}, {'address': '4801 N BROADWAY', 'date': '07/01/2012'}, {'address': '5800 E 58TH', 'date': '07/02/2012'}, {'address': '5645 N RAVENSWOOD', 'date': '07/02/2012'}, {'address': '1060 W ADDISON', 'date': '07/02/2012'}, {'address': '2122 N CLARK', 'date': '07/03/2012'}, {'address': '5148 N CLARK', 'date': '07/04/2012'}, {'address': '1039 W GRANVILLE', 'date': '07/04/2012'}]\n"
     ]
    }
   ],
   "source": [
    "from operator import itemgetter\n",
    "from itertools import groupby\n",
    "\n",
    "# Sort by the desired field first\n",
    "rows.sort(key=itemgetter('date'))\n",
    "print(rows)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 149,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "07/01/2012\n",
      "     {'address': '5412 N CLARK', 'date': '07/01/2012'}\n",
      "     {'address': '4801 N BROADWAY', 'date': '07/01/2012'}\n",
      "07/02/2012\n",
      "     {'address': '5800 E 58TH', 'date': '07/02/2012'}\n",
      "     {'address': '5645 N RAVENSWOOD', 'date': '07/02/2012'}\n",
      "     {'address': '1060 W ADDISON', 'date': '07/02/2012'}\n",
      "07/03/2012\n",
      "     {'address': '2122 N CLARK', 'date': '07/03/2012'}\n",
      "07/04/2012\n",
      "     {'address': '5148 N CLARK', 'date': '07/04/2012'}\n",
      "     {'address': '1039 W GRANVILLE', 'date': '07/04/2012'}\n"
     ]
    }
   ],
   "source": [
    "# Iterate in groups\n",
    "for date, items in groupby(rows, key=itemgetter('date')):\n",
    "    print(date)\n",
    "    for i in items:\n",
    "        print('    ', i)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 21: Filtering Sequence Elements\n",
    "\n",
    "Given a sequence of data, extract values or reduce the sequence using some criteria"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 152,
   "metadata": {},
   "outputs": [],
   "source": [
    "mylist = [1, 4, -5, 10, -7, 2, 3, -1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 155,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 4, 10, 2, 3]"
      ]
     },
     "execution_count": 155,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "comprehension_positives = [n for n in mylist if n > 0] \n",
    "comprehension_positives"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 156,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "4\n",
      "10\n",
      "2\n",
      "3\n"
     ]
    }
   ],
   "source": [
    "generator_positives = (n for n in mylist if n > 0)\n",
    "for x in generator_positives:\n",
    "    print(x)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 157,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['1', '2', '-3', '4', '5']\n"
     ]
    }
   ],
   "source": [
    "values = ['1', '2', '-3', '-', '4', 'N/A', '5']\n",
    "\n",
    "def is_int(val):\n",
    "    try:\n",
    "        x = int(val)\n",
    "        return True\n",
    "    except ValueError:\n",
    "        return False\n",
    "\n",
    "ivals = list(filter(is_int, values))\n",
    "print(ivals) "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 22: Test for Palindromic Permutations\n",
    "Write a program to test whether the letters forming a string can be permuted to form a palindrome. For example, 'edified' can be permuted to form 'deified'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import Counter\n",
    "\n",
    "# the TRICK here is to realize that a string can be permuted to form a palindrome if and only if\n",
    "# the number of chars whose frequencies is odd is at most 1\n",
    "\n",
    "def can_form_palindrome(my_string):\n",
    "    return sum(x % 2 for x in Counter(my_string).values())<=1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n",
      "True\n",
      "True\n"
     ]
    }
   ],
   "source": [
    "print(can_form_palindrome('edified'))\n",
    "print(can_form_palindrome('level'))\n",
    "print(can_form_palindrome('rotator'))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Counter({'l': 2, 'e': 2, 'v': 1})"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Counter('level')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 23: Compute the Intersection of Two Sorted Arrays\n",
    "Write a program which takes as input two sorted arrays, and returns a new array containins elements that present in both"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Brute force solution: a 'loop join'of O(n*m) complexity\n",
    "\n",
    "def intersec (A, B):\n",
    "    return [a for i, a in enumerate (A) if (i==0 or a!=A[i-1]) and a in B]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[5, 6, 8]"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "x = [2,3,3,5,5,6,7,7,8,12]\n",
    "y = [5,5,6,8,8,9,10,10]\n",
    "\n",
    "intersec(x, y)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Linear time solution O(n+m): by simultaneously advancing throught the two arrays in increasing order\n",
    "\n",
    "def intersec(A, B):\n",
    "    i, j, intersection_AB = 0, 0, []\n",
    "    while i < len(A) and j < len(B):\n",
    "        if A[i] == B[j]:\n",
    "            if i == 0 or A[i]!=A[i-1]:\n",
    "                intersection_AB.append(A[i])\n",
    "            i, j = i+1, j+1\n",
    "        elif A[i] < B[j]:\n",
    "            i += 1 \n",
    "        else:\n",
    "            j += 1\n",
    "    return intersection_AB"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[5, 6, 8]"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "x = [2,3,3,5,5,6,7,7,8,12]\n",
    "y = [5,5,6,8,8,9,10,10]\n",
    "\n",
    "intersec(x, y)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 24: Kadene's algorithm (another classic)\n",
    " Write a program that takes an array denoting the daily stock price, and returns the maximum profit that could be made by buying and then selling one share of the stock\n",
    " "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "def buy_and_sell_stock(prices):\n",
    "    min_price_so_far, max_profit = float('inf'), 0.0\n",
    "    for price in prices:\n",
    "        max_profit_sell_today = price - min_price_so_far\n",
    "        max_profit = max(max_profit, max_profit_sell_today)\n",
    "        min_price_so_far = min(min_price_so_far, price)\n",
    "    return max_profit"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "30"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "prices = [310, 315, 275, 295, 260, 270, 290, 230, 255, 250]\n",
    "buy_and_sell_stock(prices)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 25: Merge two Sorted List\n",
    "Write a program that takes two lists, assumed to be sorted and returns their merge."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The original list 1 is : [1, 2, 5, 6, 9]\n",
      "The original list 2 is : [3, 4, 7, 8, 10]\n"
     ]
    }
   ],
   "source": [
    "test_list1 = [1, 2, 5, 6, 9 ] \n",
    "test_list2 = [3, 4, 7, 8, 10] \n",
    "  \n",
    "# printing original lists  \n",
    "print (\"The original list 1 is : \" + str(test_list1)) \n",
    "print (\"The original list 2 is : \" + str(test_list2)) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [],
   "source": [
    "def merge_sorted_lists(test_list1, test_list2):\n",
    "    size_1 = len(test_list1) \n",
    "    size_2 = len(test_list2) \n",
    "    res = [] \n",
    "    i, j = 0, 0\n",
    "\n",
    "    while i < size_1 and j < size_2: \n",
    "        if test_list1[i] < test_list2[j]: \n",
    "            res.append(test_list1[i]) \n",
    "            i += 1\n",
    "        else: \n",
    "            res.append(test_list2[j]) \n",
    "            j += 1\n",
    "\n",
    "    res = res + test_list1[i:] + test_list2[j:] \n",
    "    return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The combined sorted list is : [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]\n"
     ]
    }
   ],
   "source": [
    "  \n",
    "print (\"The combined sorted list is : \" + str(merge_sorted_lists(test_list1, test_list2))) "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 26: Root Square of the Conditional Values of a dictionary \n",
    "\n",
    "Write a list comprenhension that return the root square of the values of a dictionary conditional to his key is an integer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {},
   "outputs": [],
   "source": [
    "mydict = {'a':123, 12.123:120, '01':1241, 0:121, 1:144}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[11.0, 12.0]"
      ]
     },
     "execution_count": 45,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "[v**.5 for k, v in mydict.items() if isinstance(k, int)]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 27: More about Palindromes\n",
    "\n",
    "Determine whether an integer is a palindrome. An integer is a palindrome when it reads the same backward as forward."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "def isPalindrome( x: int) -> bool:\n",
    "    if x < 0 or (x % 10 ==0 and x != 0):\n",
    "        return False\n",
    "    reverted_number = 0\n",
    "    num = x\n",
    "    while x > reverted_number:\n",
    "        reverted_number = reverted_number * 10 + num % 10\n",
    "        num = int(num/10)\n",
    "        \n",
    "    return x == reverted_number or x == reverted_number/10"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "isPalindrome(987656789)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "isPalindrome(11)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 28: Reversing integers \n",
    "\n",
    "Given a 32-bit signed integer, reverse digits of an integer. Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: (−2^31,  2^31 - 1). For the purpose of this problem, assume that your function returns 0 when the reversed integer overflows."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "def reverse(x):\n",
    "    INT_MAX = 2 ** 31 - 1\n",
    "    INT_MIN = -2 ** 31\n",
    "    if x >= 0 :\n",
    "        sol = int(str(x)[::-1])\n",
    "        if (sol > INT_MAX ):\n",
    "            return 0\n",
    "        else:\n",
    "            return sol\n",
    "    else: \n",
    "        sol = int(str(abs(x))[::-1])*(-1)\n",
    "        if (sol < INT_MIN) :\n",
    "            return 0\n",
    "        else:\n",
    "            return sol"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "-321"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "reverse(-123)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "21"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "reverse(120)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 29: Find two elements that sum equal the target...\n",
    "\n",
    "Given an array of integers, return indices of the two numbers such that they add up to a specific target.\n",
    "\n",
    "You may assume that each input would have exactly one solution, and you may not use the same element twice."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "# A 'brut-force' solution\n",
    "\n",
    "def TwoSum(nums, target):\n",
    "    for i, num in enumerate(nums):\n",
    "        rest_nums = nums[i+1:]\n",
    "        if (target - num) in rest_nums :\n",
    "            return [i, rest_nums.index(target - num) + i + 1] \n",
    "    return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, 3]"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "twoSum([0,4,3,0], 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[2, 4]"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "twoSum([-1,-2,-3,-4,-5], -8)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, 1]"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "twoSum([-18,12,3,0], -6)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 30: Count the number of ways to traverse a 2D array\n",
    "\n",
    "How many ways can you go from the top-left to bottom-right in a 2D (n,m)-array, if all the movements must either go right or down.\n",
    "\n",
    "Solution should be O(nm) in time complexity and space complexity"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {},
   "outputs": [],
   "source": [
    "def number_of_ways(n: int,m: int) -> int:\n",
    "    def compute_number_of_ways_to_xy(x,y):\n",
    "        if x == y == 0: \n",
    "            return 1\n",
    "        if number_of_ways[x][y] == 0:\n",
    "            ways_top = 0 if x == 0 else compute_number_of_ways_to_xy(x-1, y) # coming from the right\n",
    "            ways_left = 0 if y == 0 else compute_number_of_ways_to_xy(x, y-1) # coming from the top\n",
    "            number_of_ways[x][y] = ways_top + ways_left # caching in a matrix\n",
    "        return number_of_ways[x][y]\n",
    "    \n",
    "    number_of_ways = [[0] * m for _ in range(n)]\n",
    "    return compute_number_of_ways_to_xy(n-1, m-1)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "6"
      ]
     },
     "execution_count": 49,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "number_of_ways(3,3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 31: Find the Longest Common Prefix\n",
    "Write a function to find the longest common prefix string amongst an array of strings.\n",
    "\n",
    "If there is no common prefix, return an empty string \"\"."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "def longestCommonPrefix(strs):\n",
    "    if not strs: return \"\"\n",
    "    if len(strs)==0: return \"\"\n",
    "    if len(strs)==1: return strs[0]\n",
    "    min_len = min(map(lambda x:len(x), strs))\n",
    "    if min_len == 0 : return \"\"\n",
    "    matrix = [[char for char in word] for word in strs ]\n",
    "    for j in range(min_len):\n",
    "        for i in range(len(matrix)-1):\n",
    "            if matrix[i][j]==matrix[i+1][j]:\n",
    "                pass\n",
    "            else:\n",
    "                return strs[i][:j]\n",
    "    return strs[i][:min_len]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'ab'"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "strs = [\"abab\", \"aba\", \"abc\"]\n",
    "longestCommonPrefix(strs)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'a'"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "strs = [\"abca\",\"aba\",\"aaab\"]\n",
    "longestCommonPrefix(strs)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'fl'"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "strs = [\"flower\",\"flow\",\"flight\"]\n",
    "longestCommonPrefix(strs)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 32: Maximum subarray\n",
    "Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum (the O(n) solution)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {},
   "outputs": [],
   "source": [
    "def maxSubArray(nums):\n",
    "    if not nums: return 0\n",
    "    if len(nums) == 0: return 0\n",
    "    else:\n",
    "        max_seen = max_end = float('-Inf')\n",
    "        for num in nums:\n",
    "            max_end = max(num, num + max_end)\n",
    "            max_seen = max(max_seen, max_end)\n",
    "        return max_seen"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "6"
      ]
     },
     "execution_count": 41,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nums = [-2,1,-3,4,-1,2,1,-5,4]\n",
    "maxSubArray(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "-1"
      ]
     },
     "execution_count": 42,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nums = [-2,-1]\n",
    "maxSubArray(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "-1"
      ]
     },
     "execution_count": 43,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nums = [-2,-3,-1]\n",
    "maxSubArray(nums)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 33: Maximum Depth of a Binary Tree\n",
    "\n",
    "Given a binary tree, find its maximum depth."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Definition for a binary tree node.\n",
    "\n",
    "class TreeNode:\n",
    "    def __init__(self, x):\n",
    "        self.val = x\n",
    "        self.left = None\n",
    "        self.right = None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "def maxDepth( root: TreeNode) -> int:\n",
    "    if root is None:\n",
    "        return 0\n",
    "    else:\n",
    "        lDepth = maxDepth(root.left)\n",
    "        rDepth = maxDepth(root.right)\n",
    "        if (lDepth > rDepth):\n",
    "            return lDepth + 1\n",
    "        else: \n",
    "            return rDepth + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "root = TreeNode(3) \n",
    "root.left = TreeNode(9) \n",
    "root.right = TreeNode(20) \n",
    "root.left.left = TreeNode(15) \n",
    "root.left.right = TreeNode(7) \n",
    "\n",
    "maxDepth(root)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 34: Sum root-to-leaf path in a Binary Tree\n",
    "\n",
    "Given a binary tree which each node contains a binary digit, write a program which return the sum of binary values represented by root-to-leaf paths"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Definition for a binary tree node.\n",
    "\n",
    "class TreeNode:\n",
    "    def __init__(self, x):\n",
    "        self.val = x\n",
    "        self.left = None\n",
    "        self.right = None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [],
   "source": [
    "def sum_root_to_leaf(tree):\n",
    "    def sum_root_to_leaf_helper(tree, partial_path_sum=0):\n",
    "        if not tree:\n",
    "            return 0\n",
    "        partial_path_sum = partial_path_sum + tree.val\n",
    "        if not tree.left and not tree.right: # leaf\n",
    "            return partial_path_sum\n",
    "        return (sum_root_to_leaf_helper(tree.left, partial_path_sum) +\n",
    "               sum_root_to_leaf_helper(tree.right, partial_path_sum))\n",
    "    \n",
    "    return sum_root_to_leaf_helper(tree)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [],
   "source": [
    "root = TreeNode(1) \n",
    "root.left = TreeNode(0) \n",
    "root.right = TreeNode(1) \n",
    "root.left.left = TreeNode(1) \n",
    "root.left.right = TreeNode(1) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "6"
      ]
     },
     "execution_count": 36,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sum_root_to_leaf(root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {},
   "outputs": [],
   "source": [
    "root = TreeNode(1) \n",
    "root.left = TreeNode(1) \n",
    "root.right = TreeNode(1) \n",
    "root.left.left = TreeNode(1) \n",
    "root.left.right = TreeNode(0) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "7"
      ]
     },
     "execution_count": 40,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sum_root_to_leaf(root)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 35: Find a root-to-leaf path with a specified sum in a Binary Tree\n",
    "\n",
    "Given a binary tree, write a program which checks if there exists (boolean) a leaf whose path weight equals a given integer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Definition for a binary tree node.\n",
    "\n",
    "class TreeNode:\n",
    "    def __init__(self, x):\n",
    "        self.val = x\n",
    "        self.left = None\n",
    "        self.right = None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "def has_path_sum(tree, remaining_weight):\n",
    "    if not tree: \n",
    "        return False\n",
    "    if not tree.left and not tree.right: # leaf\n",
    "        return remaining_weight == tree.val\n",
    "    \n",
    "    return (has_path_sum(tree.left, remaining_weight - tree.val)\n",
    "           or has_path_sum(tree.right, remaining_weight - tree.val))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "root = TreeNode(3) \n",
    "root.left = TreeNode(9) \n",
    "root.right = TreeNode(20) \n",
    "root.left.left = TreeNode(15) \n",
    "root.left.right = TreeNode(7) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "False\n",
      "False\n",
      "True\n",
      "True\n",
      "True\n"
     ]
    }
   ],
   "source": [
    "print(has_path_sum(root, 3))\n",
    "print(has_path_sum(root, 12))\n",
    "print(has_path_sum(root, 19))\n",
    "print(has_path_sum(root, 23))\n",
    "print(has_path_sum(root, 27))"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "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.6.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}