iterables.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 🐍Python Tricks - Iterables"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This notebook is the practical part of Pluralsight Guides: [Python Tricks - Iterable - Part 1](https://www.pluralsight.com/guides/python-tricks-iterable-part-1) and [Python Tricks - Iterable - Part 2](https://www.pluralsight.com/guides/python-tricks-iterable-part-2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Table of Content:\n",
    "* [Construct Iterator](#anchor1)\n",
    "* [Construct Generator](#anchor2)\n",
    "* [Comprehension](#anchor3)\n",
    "* [lambda](#anchor4)\n",
    "* [map](#anchor5)\n",
    "* [reduce](#anchor6)\n",
    "* [zip](#anchor7)\n",
    "* [Unpacking](#anchor8)\n",
    "* [sum](#anchor9)\n",
    "* [max & min](#anchor10)\n",
    "* [any & all](#anchor11)\n",
    "* [Customize iterable in bisect](#anchor12)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "***"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Construct Iterator <a name=\"anchor1\"></a>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Inspiration:\n",
    "```python\n",
    "\"\"\"construct iterator to make sure check every char only once by 'in' \"\"\"\n",
    "# L392: check if s is subsequence of t. s = \"abc\", t = \"ahbgdc\", return true.\n",
    "def is_subsequence(s: str, t: str) -> bool:\n",
    "    t = iter(t)\n",
    "    return all(c in t for c in s)\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Construct Generator <a name=\"anchor2\"></a>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`generator` is a kind of iterable you can only iterate over once. generators do not store all the values in memory, they generate the values on the fly."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Inspirations:\n",
    "```python\n",
    "\"\"\"generate all combinations of coins which sum to target amount\"\"\"\n",
    "def get_coin_changes(coins: List[int], amount[int]) -> List[List[int]]:\n",
    "    for i, coin in enumerate(coins):\n",
    "        if coin == amount:\n",
    "            yield (coin,)\n",
    "        elif coin < amount:\n",
    "            yield from ((coin,) + x for x in change(coins[i:], amount - coin))\n",
    "\n",
    "\"\"\"generate all combinations of well-formed n pairs of parentheses\"\"\"\n",
    "# L22: generate all combinations of well-formed n pairs of parentheses.\n",
    "def generate_parenthesis(n: int) -> List[str]:\n",
    "    def generate(p, left, right):\n",
    "        if 0 <= left <= right:\n",
    "            if not right:\n",
    "                yield p\n",
    "            for q in generate(p + '(', left-1, right): yield q\n",
    "            for q in generate(p + ')', left, right-1): yield q\n",
    "    return list(generate('', n, n))\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Comprehension <a name=\"anchor3\"></a>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "\"\"\"list comprehension\"\"\"\n",
    "odds_list = [x for x in range(20) if x % 2]\n",
    "\n",
    "\"\"\"generator_expression\"\"\"\n",
    "odds_generator = (x for x in range(20) if x % 2)\n",
    "\n",
    "\"\"\"set comprehension\"\"\"\n",
    "odds_set = {x for x in range(20) if x % 2}\n",
    "\n",
    "\"\"\"dict comprehension\"\"\"\n",
    "square_dict = {x: x**2 for x in range(10)}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Inspirations:\n",
    "```python\n",
    "\"\"\"bfs in list comprehension way\"\"\"\n",
    "# L515: find the largest value in each row of a binary tree\n",
    "def find_largest_in_binary_tree_rows(root: TreeNode) -> List[int]:\n",
    "    maxes, row = [], [root]\n",
    "    while any(row):\n",
    "        maxes.append(max(node.val for node in row))\n",
    "        row = [kid for node in row for kid in (node.left, node.right) if kid]\n",
    "    return maxes\n",
    "\n",
    "\"\"\"rotate image by list comprehension\"\"\"\n",
    "# L48: rotate the image by 90 degrees (clockwise)\n",
    "def rotate_image_90_degrees(matrix: List[List[int]]) -> None:\n",
    "    matrix[:] = [[row[i] for row in matrix[::-1]] for i in range(len(A))]\n",
    "\n",
    "\"\"\"generate combinations by list comprehension recursively\"\"\"\n",
    "# L77: Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.\n",
    "def combine(n: int, k: int) -> List[List[int]]:\n",
    "    if k == 0:\n",
    "        return [[]]\n",
    "    # add last element\n",
    "    return [pre + [i] for i in range(k, n + 1) for pre in combine(i - 1, k - 1)]\n",
    "\n",
    "\"\"\"generate binary trees by list comprehension recursively\"\"\"\n",
    "# given an integer n, generate all structurally unique BST's (binary search trees) that store values 1 ... n.\n",
    "def generate_binary_search_trees(last: int, first: int=1) -> List[TreeNode]:\n",
    "    def node(val, left, right):\n",
    "        node = TreeNode(val)\n",
    "        node.left = left\n",
    "        node.right = right\n",
    "        return node\n",
    "    return [node(root, left, right) \n",
    "            for root in range(first, last+1)\n",
    "            for left in generate_binary_search_trees(root-1, first)\n",
    "            for right in generate_binary_search_trees(last, root+1)] or [None]\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## lambda <a name=\"anchor4\"></a>\n",
    "single expression with implicit return"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```python\n",
    "lambda arguments : expression\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "7"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\"\"\"lexical closure\"\"\"\n",
    "def make_adder(n):\n",
    "    return lambda x: x + n\n",
    "\n",
    "plus_3 = make_adder(3)\n",
    "plus_3(4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[('rotten tomato', 1), ('banana', 5), ('apple', 18), ('orange', 20)]"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\"\"\"lambda used in key\"\"\"\n",
    "# sort dict by value\n",
    "d = {'apple': 18, 'orange': 20, 'banana': 5, 'rotten tomato': 1}\n",
    "sorted(d.items(), key=lambda x: x[1])\n",
    "\n",
    "# alternative\n",
    "from operator import itemgetter\n",
    "sorted(d.items(), key=itemgetter(1))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Inspirations:\n",
    "```python\n",
    "for pos in range(len(S)):\n",
    "    \"\"\"lambda used in filter\"\"\"\n",
    "    matched_words = list(filter(lambda x: S[pos:].startswith(x), words))\n",
    "    if matched_words:\n",
    "        \"\"\"lambda used in max\"\"\"\n",
    "        add_interval([pos, pos + len(max(matched_words, key=lambda x: len(x)))])\n",
    "\n",
    "\"\"\"call lambda in nested\"\"\"\n",
    "# L422: given a sequence of words, check whether it forms a valid word square.\n",
    "def valid_word_square(words: List[str]) -> bool:\n",
    "    f = lambda x: map(None, *x)  # python 2\n",
    "    return f(f(words)) == f(words)\n",
    "\n",
    "\"\"\"use lambda to wrap parameter as callable\"\"\"\n",
    "def wrapped_callable(f):\n",
    "    if callable(f): return f\n",
    "    else: return lambda: f\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## map <a name=\"anchor5\"></a>\n",
    "`map` applies a function to all the items in a given iterable"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```python\n",
    "map(function, iterables) -> iterables\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Inspirations:\n",
    "```python\n",
    "\"\"\"map to node children recursively\"\"\"\n",
    "# get depth in binary tree\n",
    "def max_depth(root: TreeNode) -> int:\n",
    "    return 1 + max(map(maxDepth, (root.left, root.right))) if root else 0\n",
    "\n",
    "\"\"\"comparison map find with map index\"\"\"\n",
    "# given a pattern and a string words, find if words follows the same pattern. \n",
    "# i.e. pattern = 'abba', words = 'dog cat cat dog'\n",
    "def valid_word_pattern(pattern: str, words: str) -> bool:\n",
    "    s, t = pattern, words.split()\n",
    "    return list(map(s.find, s)) == list(map(t.index, t))\n",
    "\n",
    "\"\"\"map dict.get\"\"\"\n",
    "# given scores of N athletes, find their relative ranks and the people with the top three highest scores, who will be awarded medals: \"Gold Medal\", \"Silver Medal\" and \"Bronze Medal\"\n",
    "def find_relative_ranks(nums: List[int]) -> List[str]:\n",
    "    sorted_nums = sorted(nums, reverse=True)\n",
    "    rank = [\"Gold Medal\", \"Silver Medal\", \"Bronze Medal\"] + list(map(str, range(4, len(nums) + 1)))\n",
    "    return list(map(dict(zip(sorted_nums, rank)).get, nums))\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## reduce <a name=\"anchor6\"></a>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`reduce` returns a single value constructed by function on the first two items of the sequence, then on the result and the next item, and so on."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```python\n",
    "reduce(function, sequence[, initial]) -> value\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Inspirations:\n",
    "```python\n",
    "# every numbers appears twice except for one, find that single one\n",
    "def single_number(nums: List[int]) -> int:\n",
    "    return reduce(lambda x, y: x ^ y, nums)\n",
    "\n",
    "# generate all possible permutations\n",
    "def permute(nums: List[int]) -> List[List[int]]:\n",
    "    return reduce(lambda P, n: [p[:i] + [n] + p[i:] for p in P for i in range(len(p)+1)], \n",
    "                  nums, [[]])\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## zip <a name=\"anchor7\"></a>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`zip` takes iterator that aggregates elements based on the iterables passed, and returns an iterator of tuples."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```python\n",
    "zip(*iterables) -> iterator\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Notice iterator stops when shortest iterable is exhausted. If you prefer to match the longest iterable, you can try `zip_longest(*iterables, fillvalue=None)` in `itertools` module."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(1, 'one'), (2, 'two'), (3, 'three')]"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a = [1,2,3]\n",
    "b = ['one','two','three']\n",
    "zipped=zip(a,b)\n",
    "list(zipped)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Inspirations:\n",
    "```python\n",
    "\"\"\"construct dict\"\"\"\n",
    "keys = ['a', 'b', 'c']\n",
    "vals = [1, 2, 3]\n",
    "zipped_dict = dict(zip(keys, vals))\n",
    "\n",
    "\"\"\"difference of neighbor pairs\"\"\"\n",
    "arr, diffs = [1, 2, 3, 4, 5], []\n",
    "for pre, post in zip(arr[:-1], arr[1:]):  # zip(arr, arr[1:]) is ok too, zip matches the shortest\n",
    "    diffs.append(post - pre)\n",
    "\n",
    "\"\"\"transpose matrix\"\"\"\n",
    "# L867: The transpose of a matrix is the matrix flipped over it's main diagonal, switching the row and column indices of the matrix.\n",
    "def transpose(matrix: List[List[int]]) -> List[List[int]]:\n",
    "    return list(map(list, zip(*matrix)))\n",
    "\n",
    "\"\"\"zip into a set\"\"\"\n",
    "# L290: given a pattern and a string words, find if words follows the same pattern. \n",
    "# i.e. pattern = 'abba', words = 'dog cat cat dog'\n",
    "def valid_word_pattern(pattern: str, words: str) -> bool:\n",
    "    s, t = pattern, words.split()\n",
    "    return len(set(zip(s, t))) == len(set(s)) == len(set(t)) and len(s) == len(t)\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Unpacking <a name=\"anchor8\"></a>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "6"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def product(a, b):\n",
    "    return a * b\n",
    "\n",
    "\"\"\"use * to unpack tuple, list or other iterables\"\"\"\n",
    "param_tuple = (2, 3)\n",
    "product(*param_tuple)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "6"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\"\"\"use ** to unpack dict\"\"\"\n",
    "param_dict = {'a': 2, 'b': 3}\n",
    "product(**param_dict)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Inspirations:\n",
    "```python\n",
    "\"\"\"get rest of all\"\"\"\n",
    "a, *b, c = range(5)\n",
    "# b = [1, 2, 3]\n",
    "[(c, *d, [*e]), f, *g] = [[1, 2, 3, 4, [5, 5, 5]], 6, 7, 8]\n",
    "# d = [2, 3, 4], e = [5, 5, 5], g = [7, 8]\n",
    "\n",
    "\"\"\"merge dicts\"\"\"\n",
    "a = {'1': 1, '2': 2}\n",
    "b = {'2': 3, '4': 4}\n",
    "merged_dict = {**a, **b}   #{'1': 1, '2': 3, '4': 4}\n",
    "\n",
    "\"\"\"[*a] = list(a), [*zip(*matrix)]: transpose matrix\"\"\"\n",
    "# traverse matrix in spiral order.\n",
    "def traverse_spiral_order(matrix: List[List[int]]) -> List[int]:\n",
    "    return matrix and [*matrix.pop(0)] + traverse_spiral_order([*zip(*matrix)][::-1])\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## sum <a name=\"anchor9\"></a>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The `sum` function takes an iterable and returns the sum of items in it. Its syntax is as follows:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```python\n",
    "sum(iterable[, start]) -> number\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Inspirations:\n",
    "```python\n",
    "\"\"\"sum\"\"\"\n",
    "# L771: S is stones you have, J is types of stones which are jewels, and you want to know how many stones are also jewels.\n",
    "def num_jewels_in_stones(J: str, S: str) -> int:\n",
    "    return sum(map(J.count, S))\n",
    "\n",
    "# L389: string t is generated by random shuffling string s and then add one more letter at a random position, find the letter.\n",
    "def find_the_difference(s: str, t: str) -> str:\n",
    "    return chr(sum(map(ord, t)) - sum(map(ord, s)))\n",
    "\n",
    "# L266: determine if a permutation of the string could form a palindrome\n",
    "def can_permute_palindrome(s: str) -> bool:\n",
    "    \"\"\"at most one odd count character\"\"\"\n",
    "    return sum(v % 2 for v in Counter(s).values()) <= 1\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## max & min <a name=\"anchor10\"></a>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The `max` function returns the largest of the input values. Its syntax is as follows:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```python\n",
    "max(iterable[, default=obj, key=func]) -> value\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The `min` function is similar to this."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Inspirations:\n",
    "```python\n",
    "\"\"\"max\"\"\"\n",
    "# L169: find the majority element which appears more than ⌊ n/2 ⌋ times.\n",
    "def majority_element(nums: List[int]) -> int:\n",
    "    counts = Counter(nums)\n",
    "    return max(counts.keys(), key=counts.get)\n",
    "\n",
    "\"\"\"min\"\"\"\n",
    "# L14: find the longest common prefix string amongst an array of strings.\n",
    "def longest_common_prefix(strs: List[str]) -> str:\n",
    "    shortest = min(strs, key=len)\n",
    "    for i, ch in enumerate(shortest):\n",
    "        if any(s[i] != ch for s in strs):\n",
    "            return shortest[:i]\n",
    "    return shortest\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## any & all <a name=\"anchor11\"></a>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The `any` function tests whether any item in the iterable evaluates to `True` to not. Its syntax is as follows:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```python\n",
    "any(iterable) -> bool\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The `all` function is similar to this."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Inspirations:\n",
    "```python\n",
    "\"\"\"any\"\"\"\n",
    "# L36: determine if a 9x9 Sudoku board is valid, which means 1-9 in row, column, 3x3 sub-boxes\n",
    "def is_valid_sudoku(board: List[List[str]]) -> bool:\n",
    "    seen = set()\n",
    "    return not any(x in seen or seen.add(x)\n",
    "                   for i, row in enumerate(board)\n",
    "                   for j, c in enumerate(row)\n",
    "                   if c != '.'\n",
    "                   for x in ((c, i), (j, c), (i/3, j/3, c)))\n",
    "\n",
    "\"\"\"all\"\"\"\n",
    "# L766: a matrix is Toeplitz if every diagonal from top-left to bottom-right has the same element.\n",
    "def is_toeplitz_matrix(matrix: List[List[int]]) -> bool:\n",
    "    return all(r == 0 or c == 0 or matrix[r-1][c-1] == val\n",
    "               for r, row in enumerate(matrix)\n",
    "               for c, val in enumerate(row))\n",
    "\n",
    "# L246: verify the number is strobogrammatic, strobogrammatic number looks the same when rotated 180 degrees\n",
    "def is_strobogrammatic(num: str) -> bool:\n",
    "    return all(map('696 00 11 88'.count, map(operator.add, num, num[::-1])))\n",
    "\n",
    "# L261: given n nodes labeled from 0 to n-1 and a list of undirected edges, check whether these edges make up a valid tree.\n",
    "def valid_tree(n: int, edges: List[List[int]]) -> bool:\n",
    "    \"\"\"all check in union find\"\"\"\n",
    "    parent = range(n)\n",
    "    def find(x):\n",
    "        return x if parent[x] == x else find(parent[x])\n",
    "    def union(xy):\n",
    "        x, y = map(find, xy)\n",
    "        parent[x] = y\n",
    "        return x != y\n",
    "    return len(edges) == n-1 and all(map(union, edges))\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Customize iterable in bisect  <a name=\"anchor12\"></a>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`bisect` module provides support for maintaining a list in sorted order without having to sort the list after each insertion.\n",
    "The `bisect_left`/`bisect` function locates the insertion point for `x` in `a` to maintain sorted order."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```python\n",
    "bisect.bisect_left(a, x[, lo=0, hi=len(a)]) -> int\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Inspirations:\n",
    "In the following examples, bisect usage is generalized to customized iterables. The key point is the idea to construct an appropriate iterable. We need to use `__getitem__` for bisect to index.\n",
    "```python\n",
    "\"\"\"use binary search to find the first number that's less than or equal to the last.\"\"\"\n",
    "# L153: find the minimum element in rotated sorted array\n",
    "def find_min_in_rotated_sorted_arr(self, nums: List[int]) -> int:\n",
    "    \"\"\"construct iterable which distinguish the two parts of rotated array\"\"\"\n",
    "    self.__getitem__ = lambda i: nums[i] <= nums[-1]\n",
    "    return nums[bisect.bisect(self, False, 0, len(nums))]\n",
    "\n",
    "\"\"\"construct a boolean iterable and use binary search\"\"\"\n",
    "# L4: find the median of the two sorted arrays\n",
    "def find_median_in_two_sorted_arrays(nums1: List[int], nums2: List[int]) -> float:\n",
    "    a, b = sorted((nums1, nums2), key=len)\n",
    "    m, n = len(a), len(b)\n",
    "    after = (m + n - 1) // 2\n",
    "    class Range:\n",
    "        def __getitem__(self, i):\n",
    "            return after-i-1 < 0 or a[i] >= b[after-i-1]\n",
    "    i = bisect.bisect_left(Range(), True, 0, m)\n",
    "    nextfew = sorted(a[i:i+2] + b[after-i:after-i+2])\n",
    "    return (nextfew[0] + nextfew[1 - (m+n)%2]) / 2\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "***"
   ]
  }
 ],
 "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.5.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}