12-Recursion.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 12.0 Recursion"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 12.1 Towers of Hanoi\n",
    "\n",
    "### Problem Statement\n",
    "Imagine 3 rods with $n$ discs of increasing diameter stacked on the first rod.  Write a function that moves all $n$ discs from the first rod to a goal rod according to the following rules:\n",
    "* A disc moves from the top of one rod to the top of another rod.\n",
    "* A smaller disc can only be placed on top of a wider disc.\n",
    "* Only 1 disc can be moved at a time.\n",
    "\n",
    "The solution should be returned as a list of tuples of $(d, r_s, r_d)$ where:\n",
    "* $d$ is the diameter of the disc to move\n",
    "* $r_s$ and $r_d$ are the source and destination rods respectively"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "test_towers_of_hanoi (__main__.TowersOfHanoiTest) ... ok\n",
      "\n",
      "----------------------------------------------------------------------\n",
      "Ran 1 test in 0.005s\n",
      "\n",
      "OK\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "<unittest.main.TestProgram at 0x7f3e7cb9d3c8>"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from collections import deque, namedtuple\n",
    "import unittest\n",
    "\n",
    "\n",
    "def make_rods(n):\n",
    "    \"\"\"Return rods initialized with n discs.\"\"\"\n",
    "    rods = [deque(), deque(), deque()]\n",
    "    for d in range(n,0,-1):\n",
    "        rods[0].appendleft(d)\n",
    "    return rods\n",
    "\n",
    "\n",
    "def rod_index(rods, d):\n",
    "    \"\"\"Return rod index containing d as topmost disc or None.\"\"\"\n",
    "    for ind, rod in enumerate(rods):\n",
    "        if len(rod) > 0 and rod[0] == d:\n",
    "            return ind\n",
    "    return None\n",
    "\n",
    "\n",
    "def move(rods, rs, rd):\n",
    "    \"\"\"Move topmost disc from rs to rd.\"\"\"\n",
    "    rods[rd].appendleft(rods[rs].popleft())\n",
    "\n",
    "\n",
    "def towers_of_hanoi(rods, n, right=True):\n",
    "    \"\"\"Return the solution tuple for the towers of hanoi with n discs.\"\"\"\n",
    "\n",
    "    moves = []\n",
    "    if n < 1:\n",
    "        return moves\n",
    "\n",
    "    # Move all smaller discs (<n) to some other rod.\n",
    "    moves.extend(towers_of_hanoi(rods, n-1, not(right)))\n",
    "\n",
    "    # Move the nth disc to the goal rod.\n",
    "    # Goal rod rotates left or rotate at each level of recursion.\n",
    "    rs = rod_index(rods, n)\n",
    "    rd = (rs+1)%len(rods) if right else (rs-1)%len(rods)\n",
    "    move(rods, rs, rd)\n",
    "    moves.append((n, rs, rd))\n",
    "\n",
    "    # Move all smaller discs back to the goal rod.\n",
    "    moves.extend(towers_of_hanoi(rods, n-1, not(right)))\n",
    "\n",
    "    return moves\n",
    "\n",
    "\n",
    "class TowersOfHanoiTest(unittest.TestCase):\n",
    "\n",
    "    def test_towers_of_hanoi(self):\n",
    "        case = namedtuple('case', ['n','expected'])\n",
    "        cases = [\n",
    "            # Edge cases.\n",
    "            case(0, []),\n",
    "            case(1, [(1,0,1)]),\n",
    "            case(2, [(1,0,2),(2,0,1),(1,2,1)]),\n",
    "            # Standard case: 3 discs.\n",
    "            case(3, [(1,0,1),(2,0,2),\n",
    "                     (1,1,2),(3,0,1),\n",
    "                     (1,2,0),(2,2,1),\n",
    "                     (1,0,1)]),\n",
    "            # 4 discs = f(3 discs) + 4 + f(3 discs).\n",
    "            case(4, [(1,0,2),(2,0,1),\n",
    "                     (1,2,1),(3,0,2),\n",
    "                     (1,1,0),(2,1,2),\n",
    "                     (1,0,2),\n",
    "                     (4,0,1),(1,2,1),\n",
    "                     (2,2,0),(1,1,0),\n",
    "                     (3,2,1),(1,0,2),\n",
    "                     (2,0,1),(1,2,1)]),\n",
    "        ]\n",
    "        for c in cases:\n",
    "            rods = make_rods(c.n)\n",
    "            rcv = towers_of_hanoi(rods, c.n)\n",
    "            self.assertEqual(rcv, c.expected)\n",
    "\n",
    "\n",
    "unittest.main(TowersOfHanoiTest(), argv=[''], verbosity=2, exit=False)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 12.2 Implement regular expression\n",
    "\n",
    "### Problem Statement\n",
    "Implement a regular expression matcher with the following rules:\n",
    "1. `.` matches any single character\n",
    "1. `*` matches 0 or more copies of the previous character\n",
    "\n",
    "#### Examples\n",
    "\n",
    "| Pattern | Match | No Match |\n",
    "| ------- | ----- | -------- |\n",
    "| ra. | ray | raymond |\n",
    "| fo\\*d | foood | fooods |\n",
    "| .\\*at | chat | chats |"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "test_match (__main__.MatchTest) ... ok\n",
      "\n",
      "----------------------------------------------------------------------\n",
      "Ran 1 test in 0.010s\n",
      "\n",
      "OK\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "<unittest.main.TestProgram at 0x7f3e7cb17358>"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from collections import namedtuple\n",
    "import unittest\n",
    "\n",
    "\n",
    "def match(pattern, string):\n",
    "    \"\"\"Return True when string matches pattern.\"\"\"\n",
    "    #print(pattern, string)\n",
    "    \n",
    "    # Matching is over when either of the pattern or string ends.\n",
    "    if len(pattern) == 0 or len(string) == 0:\n",
    "        return True if pattern == string or pattern == '*' else False\n",
    "\n",
    "    # Wildcard match.\n",
    "    if len(pattern) > 2 and pattern[1] == '*':\n",
    "        ind = 0\n",
    "        if pattern[:2] == '.*':\n",
    "            # Advance string to first character after wildcard.\n",
    "            while ind < len(string) and string[ind] != pattern[2]:\n",
    "                ind += 1\n",
    "        else:\n",
    "            # Advance string to the first non-repeating character.\n",
    "            while ind < len(string) and string[ind] == pattern[0]:\n",
    "                ind += 1\n",
    "        return match(pattern[2:], string[ind:])\n",
    "    # Exact match or single character wildcard.\n",
    "    elif pattern[0] == string[0] or pattern[0] == '.':\n",
    "        return match(pattern[1:], string[1:])\n",
    "\n",
    "    return False\n",
    "\n",
    "\n",
    "class MatchTest(unittest.TestCase):\n",
    "    \n",
    "    def test_match(self):\n",
    "        case = namedtuple('case', ['pattern','string','expected'])\n",
    "        cases = [\n",
    "            # Simple exact string matches.\n",
    "            case('rat', 'rat', True),\n",
    "            case('rat', 'rad', False),\n",
    "            case('rat', 'bat', False),\n",
    "            # Match contains '.'.\n",
    "            case('ra.', 'ray', True),\n",
    "            case('ra.', 'raymond', False),\n",
    "            case('r.t', 'rot', True),\n",
    "            case('r.t', 'rat', True),\n",
    "            case('.at', 'hat', True),\n",
    "            case('.at', 'hats', False),\n",
    "            # Match contains '*'.\n",
    "            case('fo*d', 'fod', True),  # 1 occurrence.\n",
    "            case('fo*d', 'foood', True),  # 3 occurrences.\n",
    "            case('fo*d', 'fd', True),  # 0 occurrences.\n",
    "            case('fo*d', 'fooods', False),\n",
    "            case('tail*', 'tail', True),\n",
    "            # Match contains mix of '.' and '*'.\n",
    "            case('.*at', 'chat', True),\n",
    "            case('.*at', 'helloat', True),\n",
    "            case('.*at', 'hellot', False),\n",
    "            case('.*at', 'chats', False),\n",
    "        ]\n",
    "        for c in cases:\n",
    "            rcv = match(c.pattern, c.string)\n",
    "            self.assertEqual(rcv, c.expected)\n",
    "\n",
    "\n",
    "unittest.main(MatchTest(), argv=[''], verbosity=2, exit=False)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 12.3 Find minimum and maximum efficiently\n",
    "\n",
    "### Problem Statement\n",
    "Given an array of $n$ numbers, find the minimum and maximum using less than $2(n-2)$ comparisons."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "test_minmax (__main__.MinmaxTest) ... ok\n",
      "\n",
      "----------------------------------------------------------------------\n",
      "Ran 1 test in 0.013s\n",
      "\n",
      "OK\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "<unittest.main.TestProgram at 0x7f3e7cb93f28>"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from collections import namedtuple\n",
    "import unittest\n",
    "\n",
    "\n",
    "def minmax(elems):\n",
    "    \"\"\"Return a tuple of the minimum and maximum elements.\"\"\"\n",
    "    \n",
    "    # Use divide and conquer to find minimum and maximum\n",
    "    # of left and right subarrays.  During the merge, only\n",
    "    # the extreme values are compared, thus avoiding an\n",
    "    # additional comparison per recursive step resulting in\n",
    "    # (3n/2)-2 comparisons instead of 2n-2.\n",
    "    if len(elems) == 1:\n",
    "        return (elems[0], elems[0])\n",
    "    elif len(elems) == 2:\n",
    "        return ((elems[0], elems[1]) if elems[0] < elems[1] else\n",
    "                (elems[1], elems[0]))\n",
    "    \n",
    "    mid = len(elems)//2\n",
    "    min1, max1 = minmax(elems[:mid])\n",
    "    min2, max2 = minmax(elems[mid:])\n",
    "    return (min(min1, min2), max(max1, max2))\n",
    "\n",
    "\n",
    "class MinmaxTest(unittest.TestCase):\n",
    "    \n",
    "    def test_minmax(self):\n",
    "        case = namedtuple('case', ['input', 'expected'])\n",
    "        cases = [\n",
    "            case([1],(1,1)),\n",
    "            # Permutations of [1,2].\n",
    "            case([1,2],(1,2)),\n",
    "            case([2,1],(1,2)),\n",
    "            # Permutations of [1,2,3].\n",
    "            case([1,2,3],(1,3)),\n",
    "            case([1,3,2],(1,3)),\n",
    "            case([2,1,3],(1,3)),\n",
    "            case([2,3,1],(1,3)),\n",
    "            case([3,1,2],(1,3)),\n",
    "            case([3,2,1],(1,3)),\n",
    "            # Random.\n",
    "            case([18,44,29,50,49,43,2,67,3,81], (2,81)),\n",
    "            case([3,2,44,18,29,50,43,49,81,67], (2,81)),\n",
    "            case([29,18,2,43,50,81,3,67,49,44], (2,81)),\n",
    "        ]\n",
    "        for c in cases:\n",
    "            rcv = minmax(c.input)\n",
    "            self.assertEqual(rcv, c.expected)\n",
    "\n",
    "\n",
    "unittest.main(MinmaxTest(), argv=[''], verbosity=2, exit=False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "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.6.9"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}