Lecture 19 - levenstein distance.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "## Exercise 9: Levinstein distance & dynamic programming"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def get_LD(s1, s2):\n",
    "    if len(s1) == 0:\n",
    "        return len(s2)\n",
    "    if len(s2) == 0:\n",
    "        return len(s1)\n",
    "    if s1[-1] == s2[-1]:\n",
    "        cost = 0\n",
    "    else:\n",
    "        cost = 1\n",
    "    d = min(get_LD(s1[:-1], s2)+1,\n",
    "            get_LD(s2[:-1], s1)+1,\n",
    "            get_LD(s1[:-1], s2[:-1])+cost)\n",
    "    return d\n",
    "\n",
    "get_LD(\"Apple\", \"@apple\")\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{('', 'p'): 1, ('', 'pi'): 2, ('', ''): 0, ('b', ''): 1}\n",
      "{('', 'p'): 1, ('', 'pi'): 2, ('b', 'p'): 1, ('', ''): 0, ('b', ''): 1}\n",
      "{('', 'p'): 1, ('', ''): 0, ('by', ''): 2, ('b', 'pi'): 2, ('', 'pi'): 2, ('b', 'p'): 1, ('b', ''): 1}\n",
      "{('by', 'p'): 2, ('', 'p'): 1, ('', ''): 0, ('by', ''): 2, ('b', 'pi'): 2, ('', 'pi'): 2, ('b', 'p'): 1, ('b', ''): 1}\n",
      "2\n"
     ]
    }
   ],
   "source": [
    "memo = {}\n",
    "def get_LD(s1, s2):\n",
    "    if len(s1) == 0:\n",
    "        return len(s2)\n",
    "    if len(s2) == 0:\n",
    "        return len(s1)\n",
    "    if s1[-1] == s2[-1]:\n",
    "        cost = 0\n",
    "    else:\n",
    "        cost = 1\n",
    "       \n",
    "    i1 = (s1[:-1], s2)\n",
    "    if not i1 in memo:\n",
    "        memo[i1] = get_LD(*i1)\n",
    "    i2 = (s1, s2[:-1])\n",
    "    if not i2 in memo:\n",
    "        memo[i2] = get_LD(*i2)\n",
    "    i3 = (s1[:-1], s2[:-1])\n",
    "    if not i3 in memo:\n",
    "        memo[i3] = get_LD(*i3)\n",
    "    d = min([memo[i1]+1, memo[i2]+1, memo[i3]+cost])\n",
    "    \n",
    "    print(memo)\n",
    "    return d\n",
    "print(get_LD(\"by\", \"pi\"))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0, 1, 2, 3, 4, 5, 6]\n",
      "[1, 0, 1, 2, 3, 4, 5]\n",
      "[2, 1, 1, 2, 3, 4, 5]\n",
      "[3, 2, 2, 2, 3, 4, 5]\n",
      "[4, 3, 3, 2, 3, 4, 5]\n",
      "[5, 4, 4, 3, 2, 3, 4]\n",
      "[6, 5, 5, 4, 3, 3, 4]\n",
      "[7, 6, 6, 5, 4, 4, 3]\n",
      "3\n"
     ]
    }
   ],
   "source": [
    "def get_iterative_LD(s1, s2):\n",
    "\n",
    "    rows = len(s1)+1\n",
    "    cols = len(s2)+1\n",
    "    dist = [[0 for x in range(cols)] for x in range(rows)]\n",
    "    #for r in range(rows):\n",
    "    #    print(dist[r])\n",
    "\n",
    "    for i in range(1, rows):\n",
    "        dist[i][0] = i\n",
    "\n",
    "    for i in range(1, cols):\n",
    "        dist[0][i] = i\n",
    "        \n",
    "    #for r in range(rows):\n",
    "    #    print(dist[r])\n",
    "        \n",
    "    for col in range(1, cols):\n",
    "        for row in range(1, rows):\n",
    "            if s1[row-1] == s2[col-1]:\n",
    "                cost = 0\n",
    "            else:\n",
    "                cost = 1\n",
    "            dist[row][col] = min(dist[row-1][col] + 1,      \n",
    "                                 dist[row][col-1] + 1,      \n",
    "                                 dist[row-1][col-1] + cost) \n",
    "    for r in range(rows):\n",
    "        print(dist[r])\n",
    "    \n",
    " \n",
    "    return dist[row][col]\n",
    "print(get_iterative_LD(\"peithen\", \"python\"))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "def get_multiples(n):\n",
    "    if n == 0:\n",
    "        return [(0,0)]\n",
    "    elif n == 1:\n",
    "        return get_moves((0,0))\n",
    "    else:\n",
    "        stack = []\n",
    "        for i in get_multiples(n-1):\n",
    "            stack.extend(get_moves(i))\n",
    "        return stack"
   ]
  }
 ],
 "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.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}