Dynamic Programming vs Memoized Recursion .ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "This notebook contains a few canonically dynamic programming problems and \n",
    "demonstrates that they can be solved recursively.  \n",
    "\n",
    "Most Computer Science programs teach dynamic programming.  You figure out your\n",
    "problem and you determine a recurrance relation for that problem which is usually\n",
    "a recursive formula.  Then you take that recursive formula and turn it into this \n",
    "disgusting collection of nested loops that iterative populate this data structure\n",
    "until eventually you've calculated the answer in a bottom-up fashion.\n",
    "\n",
    "Most Computer Science programs also teach recursion.  You figure out your\n",
    "problem and you determine a recurrance relation for that problem which is usually\n",
    "a recursive formula.  Then you take that recursive formula and write it in code.\n",
    "Then your teacher has you try to calculate the 100th fibinocci number and it takes\n",
    "forever.  Then the teacher goes on to tell you that recursion is\n",
    "evil and that you should always use dynamic programming instead.  \n",
    "\n",
    "What your Computer Science program probably didn't tell you is that if you just\n",
    "cache the result of that recursive formula then you wouldn't have to wait so long\n",
    "to figure out the 100th fibinocci number.  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Edit Distance"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "MISMATCH_COST = 2\n",
    "GAP_COST = 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "c  c\n",
      "o  o\n",
      "r  r\n",
      "-  r\n",
      "e  e\n",
      "c  c\n",
      "t  t\n"
     ]
    }
   ],
   "source": [
    "\"\"\"\n",
    "Edit distance using recursive approach\n",
    "\"\"\"\n",
    "\n",
    "import functools\n",
    "\n",
    "@functools.lru_cache(maxsize=None)\n",
    "def get_cost(a, b):\n",
    "    \"\"\"\n",
    "    get_cost is memoized - prior computations are cached\n",
    "    \"\"\"\n",
    "    if len(a) == 0:\n",
    "        return len(b) * GAP_COST\n",
    "    if len(b) == 0:\n",
    "        return len(a) * GAP_COST\n",
    "    \n",
    "    if a[0] == b[0]:\n",
    "        return get_cost(a[1:], b[1:])\n",
    "    else:\n",
    "        return min(\n",
    "            get_cost(a[1:], b[1:]) + MISMATCH_COST,\n",
    "            get_cost(a, b[1:]) + GAP_COST,\n",
    "            get_cost(a[1:], b) + GAP_COST\n",
    "        )\n",
    "    \n",
    "def print_edit_join(a, b):\n",
    "    if not a and not b:\n",
    "        pass\n",
    "    elif not a:\n",
    "        print(\"{}  {}\".format(\"-\", b[0]))\n",
    "        print_edit_join(a, b[1:])\n",
    "    elif not b:\n",
    "        print(\"{}  {}\".format(a[0], \"-\"))\n",
    "        print_edit_join(a[1:], b)\n",
    "    elif a[0] == b[0]:\n",
    "        print(\"{}  {}\".format(a[0], b[0]))\n",
    "        print_edit_join(a[1:], b[1:])\n",
    "    else:\n",
    "        mismatch_cost = get_cost(a[1:], b[1:]) + MISMATCH_COST\n",
    "        a_gap_cost = get_cost(a, b[1:]) + GAP_COST\n",
    "        b_gap_cost = get_cost(a[1:], b) + GAP_COST\n",
    "        \n",
    "        if mismatch_cost < a_gap_cost and mismatch_cost < b_gap_cost:\n",
    "            print(\"{}  {}\".format(a[0], b[0]))\n",
    "            print_edit_join(a[1:], b[1:])\n",
    "        elif a_gap_cost < b_gap_cost:\n",
    "            print(\"{}  {}\".format(\"-\", b[0]))\n",
    "            print_edit_join(a, b[1:])\n",
    "        else:\n",
    "            print(\"{}  {}\".format(a[0], \"-\"))\n",
    "            print_edit_join(a[1:], b)\n",
    "\n",
    "print_edit_join(\"corect\", \"correct\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "A  B\n",
      "----\n",
      "e  e\n",
      "l  l\n",
      "p  -\n",
      "p  p\n",
      "a  a\n"
     ]
    }
   ],
   "source": [
    "\"\"\"\n",
    "Classig Edit distance algorithm\n",
    "\"\"\"\n",
    "\n",
    "def dp_edit_distance(str_a, str_b):\n",
    "    subsol = [[None for _ in range(len(str_b) + 1)] for _ in range(len(str_a) + 1)]\n",
    "    \n",
    "    \"\"\"\n",
    "    Populate the first row and col (represents the case where there\n",
    "    is absolutely no commonality between the two strings)\n",
    "    \"\"\"\n",
    "    for i in range(len(str_b) + 1):\n",
    "        subsol[0][i] = i * GAP_COST\n",
    "    for i in range(len(str_a) + 1):\n",
    "        subsol[i][0] = i * GAP_COST\n",
    "    \n",
    "    for a_idx in range(len(str_a)):\n",
    "        for b_idx in range(len(str_b)):\n",
    "            if str_a[a_idx] == str_b[b_idx]:\n",
    "                match_cost = subsol[a_idx][b_idx]\n",
    "            else:\n",
    "                match_cost = subsol[a_idx][b_idx] + MISMATCH_COST\n",
    "                \n",
    "            a_gap_cost = subsol[a_idx][b_idx + 1] + GAP_COST\n",
    "            b_gap_cost = subsol[a_idx + 1][b_idx] + GAP_COST\n",
    "            \n",
    "            subsol[a_idx + 1][b_idx + 1] = min(match_cost, a_gap_cost, b_gap_cost)\n",
    "                \n",
    "    a_idx = len(str_a)\n",
    "    b_idx = len(str_b)\n",
    "    fmtstring = \"{a_char}  {b_char}\"\n",
    "    print(fmtstring.format(a_char=\"A\", b_char=\"B\"))\n",
    "    print(\"-\" * len(fmtstring.format(a_char=\"A\", b_char=\"B\")))\n",
    "    while a_idx > 0 or b_idx > 0:\n",
    "        if a_idx == 0:\n",
    "            b_idx -= 1\n",
    "            print(fmtstring.format(a_char=\"-\", b_char=str_b[b_idx]))\n",
    "        elif b_idx == 0:\n",
    "            a_idx -= 1\n",
    "            print(fmtstring.format(a_char=str_a[a_idx], b_char=\"-\"))\n",
    "        else:\n",
    "            match_cost = subsol[a_idx - 1][b_idx - 1] + (\n",
    "                MISMATCH_COST if str_a[a_idx - 1] != str_b[b_idx - 1] else 0)\n",
    "            a_gap_cost = subsol[a_idx - 1][b_idx] + GAP_COST\n",
    "            b_gap_cost = subsol[a_idx][b_idx - 1] + GAP_COST\n",
    "            \n",
    "            if match_cost < a_gap_cost and match_cost < b_gap_cost:\n",
    "                a_idx -= 1\n",
    "                b_idx -= 1\n",
    "                print(fmtstring.format(a_char=str_a[a_idx], b_char=str_b[b_idx]))\n",
    "            elif a_gap_cost < b_gap_cost:\n",
    "                a_idx -= 1\n",
    "                print(fmtstring.format(a_char=str_a[a_idx], b_char=\"-\"))\n",
    "            else:\n",
    "                b_idx -= 1\n",
    "                print(fmtstring.format(a_char=\"-\", b_char=str_b[b_idx]))\n",
    "                \n",
    "dp_edit_distance(\"apple\", \"aple\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Fibonocci"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "573147844013817084101\n"
     ]
    }
   ],
   "source": [
    "\"\"\"\n",
    "Recursive fibonocci number\n",
    "\"\"\"\n",
    "\n",
    "@functools.lru_cache(maxsize=None)\n",
    "def rec_fib(n):\n",
    "    if n < 2:\n",
    "        return 1\n",
    "    else:\n",
    "        return rec_fib(n - 2) + rec_fib(n - 1)\n",
    "    \n",
    "print(rec_fib(100))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "573147844013817084101\n"
     ]
    }
   ],
   "source": [
    "\"\"\"\n",
    "Dynamic Programming fibonocci number\n",
    "\"\"\"\n",
    "\n",
    "def dp_fib(n):\n",
    "    subsol = [None for _ in range(n + 1)]\n",
    "    subsol[0] = subsol[1] = 1\n",
    "    for i in range(2, n + 1):\n",
    "        subsol[i] = subsol[i - 1] + subsol[i - 2]\n",
    "    return subsol[n]\n",
    "    \n",
    "print(dp_fib(100))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Knapsack"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from collections import namedtuple\n",
    "Item = namedtuple(\"Item\", [\"name\", \"weight\", \"value\"])\n",
    "\n",
    "KNAPSACK_ITEMS = [\n",
    "    Item(name=\"...Baby One More Time\", weight=10, value=60),\n",
    "    Item(name=\"Oops!... I Did it Again\", weight=20, value=100),\n",
    "    Item(name=\"Britney\", weight=30, value=75),\n",
    "    Item(name=\"In the Zone\", weight=30, value=150),\n",
    "    Item(name=\"Blackout\", weight=40, value=200),\n",
    "    Item(name=\"Circus\", weight=35, value=190),\n",
    "    Item(name=\"Femme Fatale\", weight=30, value=180),\n",
    "    Item(name=\"Britney Jean\", weight=40, value=120),\n",
    "    Item(name=\"Glory\", weight=25, value=150),\n",
    "]\n",
    "\n",
    "MAX_CAPACITY=110\n",
    "NUM_ITEMS=len(KNAPSACK_ITEMS)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "620"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\"\"\"\n",
    "Recursive Knappsack problem\n",
    "\"\"\"\n",
    "\n",
    "@functools.lru_cache(maxsize=None)\n",
    "def rec_knapsack(capacity, num_items):\n",
    "    if capacity == 0:\n",
    "        return 0\n",
    "    elif num_items == 0:\n",
    "        return 0\n",
    "    elif KNAPSACK_ITEMS[num_items - 1].weight > capacity:\n",
    "        return rec_knapsack(capacity, num_items - 1)\n",
    "    else:\n",
    "        nth_item = KNAPSACK_ITEMS[num_items - 1]\n",
    "        return max(\n",
    "            rec_knapsack(capacity - nth_item.weight, num_items - 1) + nth_item.value,\n",
    "            rec_knapsack(capacity, num_items - 1)\n",
    "        )\n",
    "    \n",
    "rec_knapsack(MAX_CAPACITY, NUM_ITEMS)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "620"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\"\"\"\n",
    "Dynamic Programming Knappsack problem\n",
    "\"\"\"\n",
    "\n",
    "def dp_knapsack(capacity_max, num_items):\n",
    "    subsol = [[0 for _ in range(capacity_max + 1)] for _ in range(num_items + 1)]\n",
    "    \n",
    "    for item_idx in range(1, num_items + 1):\n",
    "        for capacity in range(1, capacity_max + 1):\n",
    "            nth_item = KNAPSACK_ITEMS[item_idx - 1]\n",
    "            if capacity < nth_item.weight:\n",
    "                subsol[item_idx][capacity] = subsol[item_idx - 1][capacity]\n",
    "            else:\n",
    "                subsol[item_idx][capacity] = max(\n",
    "                    subsol[item_idx - 1][capacity - nth_item.weight] + nth_item.value,\n",
    "                    subsol[item_idx - 1][capacity],\n",
    "                )\n",
    "    \n",
    "    return subsol[num_items][capacity_max]\n",
    "\n",
    "dp_knapsack(MAX_CAPACITY, NUM_ITEMS)"
   ]
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "kernelspec": {
   "display_name": "Python [conda env:anaconda3]",
   "language": "python",
   "name": "conda-env-anaconda3-py"
  },
  "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.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}