{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "6a7dfd75",
   "metadata": {},
   "source": [
    "# Edit Distance"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "865cdb15",
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "from pylab import *"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "22593272",
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "a = \"the quick brown fox jumps over the lazy dogs\"\n",
    "b = \"the quack brine foxes jump over the lazy dog\""
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5b65a217",
   "metadata": {},
   "source": [
    "We start off by allocating an array of distances and sources.\n",
    "We keep track in these of the search."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "2ac046ba",
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "n,m = len(a),len(b)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "14060531",
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "sources = empty((m+1,n+1),object)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "id": "20d687c2",
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "dists = 99999*ones((m+1,n+1))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "479e8697",
   "metadata": {},
   "source": [
    "We start off by initializing the costs at time 0 to the number of\n",
    "initial characters that would be skipped."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "id": "6473bdfb",
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "dists[0,:] = arange(n+1)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "48feb802",
   "metadata": {},
   "source": [
    "The important step is forwarding from one column to the next."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "id": "43a7a88a",
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def step(previous,current):\n",
    "    for j in range(1,n+1):\n",
    "        if previous[j]+1<current[j]:\n",
    "            sources[i,j] = (i-1,j)\n",
    "            dists[i,j] = previous[j]+1\n",
    "        if current[j-1]+1<current[j]:\n",
    "            sources[i,j] = (i,j-1)\n",
    "            dists[i,j] = current[j-1]+1\n",
    "        delta = 1*(a[j-1]!=b[i-1])\n",
    "        if previous[j-1]+delta<current[j]:\n",
    "            sources[i,j] = (i-1,j-1)\n",
    "            dists[i,j] = previous[j-1]+delta"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "34b46542",
   "metadata": {},
   "source": [
    "We now repeat propagation of the values for each time step."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "id": "60a1910f",
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "for i in range(1,m+1):\n",
    "    previous = dists[i-1,:]\n",
    "    current = dists[i,:]\n",
    "    current[0] = i\n",
    "    step(previous,current)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5ea89cd9",
   "metadata": {},
   "source": [
    "The distance array now contains all the shortest paths from start to each point."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "id": "94a3b144",
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<matplotlib.image.AxesImage at 0x4731f50>"
      ]
     },
     "execution_count": 41,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAP0AAAD7CAYAAAChbJLhAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAIABJREFUeJztXV+MVUcZ/+61mKYRS33grnZBTOVPFxC2IVK1Wupm4aGW\nkpBQ+kA2Lb6Y+FAfqvioD2XRpA2NfTKYbDRB6YO6GiQBu2ytFU0KpLGFYBrAhSybUIpYU6Swxwed\n69lhvpnv+2bmzJzd80tudu/cmfm+Oef8Zr7vd+bc2yqKooAGDRrMGbRTO9CgQYNq0ZC+QYM5hob0\nDRrMMTSkb9BgjqEhfYMGcwwN6Rs0mGMQk/7QoUOwYsUKWLp0KezZsyekTw0aNIiJQoCbN28W9913\nX3H27Nnixo0bxZo1a4q33357Rh0AaF7Nq3kletlwBwjwl7/8BT772c/CkiVLAABg+/bt8Otf/xru\nv/9+tE2r1UJf7Xbb+p5TRulfUnbhwgVYvHhxpTapL1Xf1dexY8fgi1/8IrkP6Vhjn7+XX34Ztm/f\nLjomOZ2/559/Hp599llWO9u5Lr9sEJH+4sWLsGjRou773t5e+POf/2xtUxSF0xlJ3Qb5Iefzl7Nv\nUoyPj8P4+Dh5XCLSUztvtVrdg1xuo+/8Ne0E1sump6eh3W47y0ww9U/tr9y2KIpKbFJt6Lamp6e7\nq4Cpr6IojH7pfaj6qr/yKmOC67hhdUz+UvqnnAfTeDDfKDZ9y1x+UtuZxvWVr3wFHn744e55+t73\nvmftQ0T6e++9FyYmJrrvJyYmoLe397Z6iuimScI12JAHGKtD6U+9nz9/vvVCCmmTasPls/6+t7fX\nSXqbbRtZfCZpCvnLbfv6+rrEx9qZJi/sPcVmiDIdDz74IOm4UcdFRUvywM3Nmzdh+fLl8Pvf/x4+\n9alPwec//3nYv3//jJy+1WrBRz7ykdvals1VnR9idSj9pbDJyQ9N9Tn5LNVPlz8+xy308Qx1HmPn\n95LjYRvXHXfcYZ2gRSv9HXfcAT/60Y9g06ZNcOvWLdi5c6dRxGu1eCE9gHvV4pSZ+lYHiNtfCptU\nG1h9yhgUqOfDtUb4HDefCMrmf/n4U1JJis1UkWj5s/K4ONeJaKUnddxqwbx587rvVT5ZfsVYMagr\no7S/FDY5NvT6Ify1RQ+5nz/KMcnl/Pm2U38/+tGPhl/pOcSnfu6KBEKvjFKhLZWgGEvco/ah55Hl\nC84En4jN1i+3P9d4KO0kYwi14kvFPRuSkl5HncQ9CZFyFPdsoIh7rhDUJ9R3kZ87adRB3JNcW/q4\nXIhKet1xDNR8TJXlQHyT3zkSX7+wOReTaXwmYthCSd9IiXPBU8tdx0Q62cSMRF1+ca6Lylb6drt9\nG/Gp4l7MUL8R9+KLe757LiRCm6tduc1sE/dcqDS8txHftnEk9orv018KmxwbpvrUCKWcv9tWdwpB\npOeP0j+3P/1zShTnYzM08X2198pzehPxsTaNuMcvo9iS5o1YWFyeHBpxLz7xueddRxIhz0X8Muok\n7qXQFbg5vs1nSl+NuEe3mSvxkwl5LuLXUdyT2qTmzj42ynUbce/2cp9jwhlDaOJTJiUdSYU8W46v\n/6/DJ1SkHGAfcU8aOs8lcc+X+FWLe7kQn3qN2JBcyMuV+L79SS4aX5s+xK9a3DPZ4Ixprop7mB8c\ncS8LIc8V6jfiXjzipxb3fM5fI+7x2ilkI+S5iF9GI+7xy6i2JBe6j7hHnWw47Sm2be1Mkxf2nmsz\nB+JnJeS5iN+Ie/GIX3dxT5rjU8slk2Eq4ruQnZCXa46PXcixiG/LnavI8TkXeQ7ins/kLX0sN1fi\nu5ClkJcr8X36S2GTY8NUXyLu6ZMU9+ugfI7bXBX3uOc4WyHPFerXVdzzfcxVMgbuReH7WK4rYmh2\n7vmXUfrHUElOr1+woYhfRl3EPd3Xqmxyc3zffLbZuUe3GToFdaGSlb7VaolJ7iJ+DMErNgmlNuea\nuJfq6TzqZCKZDKtM1TDUQsiT5vjU8NR3Zq0qx7eFxrEuHFeoziWc3salz/jezpNO3nXeuedCbYQ8\nKfEB/HLEmPlaCpscG6b6HHGv3W5DURTW1b3ZuRemjINaCXmuUL+u4l7VNjk2dFvU1bdc1xYWl6OX\nRtyrhvhZ78iTEL+Muoh7KWxSbVB9pvTViHt0mzGJn+yLMWMSv645fh2+bDO1uOc7YVLDdk55anGP\n+3ht0m/DDU38uuf4Jr9jTzZUG1h9zkWew849Sf+UduU2VYt7Lt90JP8K7FTEl+b41INLffzR97ZU\nCJtYGdWWSz8B+P+Pmbr6c9XDbFCPm7R/rMxkT3rdVBXqJyc9QHxxT70aNAgFjMR1EPey+N57VTcG\n8ctkb4jfIASK4v+/cW+LOFKJey4k3ZyjIwbxG6I3iAWqYFy1uOdC8s05OhriN6gDKBpEanEPQxab\ncyh1QuX4mF8AM8M2DJQ6WL3QZbFtUm3pbbH+TaDUM/kV8hhR63HGpX8uFfdiCLHZbM6h1Amd41N2\ntIVW00PezqvCJtWWVLiykcLVF2UMtnvbPpt1FOoYRWb1dVmm9j7EDzWTSgnic7GaylLY5NiS+Ev9\nkg3OE4acUNrlo+1zFdpLiJ9yssjuKTsdIcN6Bf0es/5QiEll9SF+yI0zORI/x116nN2NEuL7ED41\nkgt5KYmvLqSiKLxCxarvv1Ju/YSebFzQb1VRCRdrl14oP2xtfQifcsLIQshLTXx1AmLn+CGJr/yv\n2ibVFpVw5fxaz7P10F99ZnpclzoGzA/psQSwk99G7tjiLIZshLwUxFf16irupbDJsRVD3FPni5Pj\nVyXuuaIIbtrBGRO1L4DMhLzQxKeIdKZ6MYkfOt+mhvp1yfEBwj+Cy/VDkuOrckpKFeocYmUuZCfk\nhSQ+5pOpnkvcAwhL/ND5tvTJsZxCfYUY4h7XDynxMb9ckyHWzmWTe14AMhXyYhMfq0cR90I+FRcy\n36auFnNd3OPczgs5kZo+i7lLz4ZshbzUxMfEPWpeloL4yv+qbVJtUYlfzq8p4p4tF6dMjpgfPuIe\nJQoJmSJyzou11tNPPw2dTgdWr17dLbty5QoMDg7CsmXLYOPGjXD16lW0vX7iyidHWhaqnautvqLo\nr+npaet7rIz6ovZH8SO2TR8b3L4ktqXHbXp6uvuS9E/x1VSP2g4r8yL9U089BYcOHZpRNjw8DIOD\ng3DmzBkYGBiA4eFhvPN2u/tKQXzTi2uzCuJjdWISP7RNzoUdi/i2fnyPm4T4prFTbftMNi5Yw/sv\nf/nLcO7cuRllo6OjMD4+DgAAQ0NDsGHDBpT4oYQ8aaiP+UTtvyjqK+5Jw0Qfmy5Ic3yAuSvu+djE\nwM7pp6amoNPpAABAp9OBqakptG5IIS8k8Tn9K7Kr/6UXDnaR6giZb1Nshp5sXJASHyOz3sZGesxG\nCD9cbamTiame1CYGLyFPD4F1XLhwofv//Pnz4eMf/3jtia/e66BeOK4TiLX1KUthk2qLetzU5BRD\n3OP4IT2WrrblNqaoxnZ8jx8/DidOnIi3I6/T6cClS5egp6cHJicnYeHChWjdxYsXd/8vE6duxDeV\nmU4g5WRRCUKZWKhlKWxybPn6GyJCMNW1RWyxd+5xjm9/fz888MAD3b5//OMfo34BCEi/efNmGBkZ\nge985zswMjICW7ZsQevqJ1L/LDbxKcTk2NTbUvJMnxw/ZL6dW47vymcpfdkmDko/lHQoRo5PKcd8\noUw2LlhJ/+STT8L4+DhcvnwZFi1aBN///vdh165dsG3bNti3bx8sWbIEDhw4gLaPKeRRV3OTTz79\nN+Iev4xqj+tvncU9Vxrjk+O7YCX9/v37jeVHjhwhdR5byJMS37f/Rtzjl9kgJX7dxT3qZCRNfzDU\nakdersRX73VQT1Yj7lUn7nFW7BTnD/ucK+7ZkPWjtTkT31QmJT71BIYW9yhRxmwT92zj9o3YYot7\nHL3BhlnzA5apiO8S9wDC5vih8+2Q9519ie/KZyl9UcQ9vR53DFXn+Dbb1Mm7jFn1A5YpQ/3y/yZx\nL9TtvND5dqrJhmqP628scY8TXscgfkhxL/lv2c0m4pfzfMqMLAn3XG1jhfqhJxsXpMSPJe5xw+uc\nxb3kpAeYXcS3vW+1bn9U13SSTfVMoPTvW+ay6esH1me5PNRxs/VH6SvF+cPa6HWpNgEq+rosijNV\nEJ9yUYey6dqi3KBBKlSy0qtZyLX6xiB++X667ltRmL9BNITN8tgb8jfICcm/LktHjLBeD4lshA9l\nU9lr0CA3ZLE5h1InBAn1HEiVxdhPULbRoEFOSCLkpVD1AXDRJZYfHDu6n5T6er1yRBOyTIfuW2g/\n9AnZVU/iL7UOx19bmQmU44a1kbRVSPK991R1PWaOX4ZLaOTatE12eo7P2SRCrRe6LLbNMnQVuopd\nerbPpLc8VZl0+6/PLj0Xkn3vvSJgqlBf9zOkH5QVh7L6cC9qV9uQxK9qe65+YUuIX8UuPVff0gmH\nsjeCuwciuZCXMseP5QcGLALQVzbXKqKDenH4llE+j0F8vT73oo+1S487Lm7/tnauydCGLIS8uUx8\n02aLXMJuCvHrsEuPOkGFeATXZi/kcw6mz6jHM5un7FKJexQbUj840IUYyW6tGDvyJLv0Qtssw0V8\n2xN0phxbD/3LdUJPaJRNapIJo9yGYiObH7D0IaVvvk25sDl++N6qMwl+cxWu8yUlF0Xcw/qSEr8q\ncc+FrH7AsgpxD/MzpB+cJ54wf0z/zzXot+wU6iTuUZ4FoPYvKTchSyEvdo7v0x+lnS/mMtEVMMKX\nUQdxz5VyhBJLy7ZcyFbIa4jfEJ/yVFwj7vGRjZCXQtzz6Y/SLlfE3qUXakeeXobZlm7gmc3ing3Z\nCHmmshjiHkXI852AfFZp3RdffSD2vecQfdn6p25ntfVHXRVnm7iHISshz1SmiOoS1kIKeTY/KCu+\nD1HViuZLdhNi76IL3b9pjznFpqk/CkFMKzxnhQ1xLKXiHof8tRLyXLN+FWF9lWF8SOJXseJjF58v\n8THoYb96j+X4qo6tP9OYQot7WJmtnPI59XqplZAXUtzzaVt1/h4qxC9HETFC8RB9cVctU74vFfeo\nK3gocY+iUVD7p7RTyFrIiy3uhfYtNDiPS1Lq29TwnHbp6e1d47f1q9ug2qT256qPlUn84PRvQ+2+\n956TW4cU8qQTkA8oD+iYgK0Es/E2oL6RSX/lCpdWERO1/t57ibiH+RlzApKiLGIqUGdzRXx1cVFE\nsbpCjakOZM8Byb8CO4W4F9qPKkN99b8pL9eh3z6cbWTQSd6QnoZKSO9aYVKIeyn88IUiO/V+MobZ\nSIp2uz2rJ7iQSL7SK6QQ91L44Qvp5p2QO+awsqptmo73XCA79RhhqPR7712oQtwLKeSZ/FAhNZaH\nu1YjinJrQsw94qlu3dn6x27TlSeDnCcAyU5DHdhxcyGblV4htriH+RkqrNcnFhPhfS7KEOJezLLY\nNl229GOaM/GpkOzSsyHZ3ntXu5jiXmibmB+me7susUnVpRwvqbg3m4mvkDvZKduLqREy9xgl23uf\nWtyr0qZpI4XrouRsyOGKe6mIr++0i018gPzJbwNnJybnGCXbex/7dp70ZIcmvm2F5056GCTiXgri\nm3wL2b8e6egRlm6fsgOOuhsvhEBp24Uo2aWHofLwXl3MmKhm6qPqjTMhiV/OwbHQHiM/lfizQdyT\nRgFlYOIex4YOqnZCfVhHOq6QSBLec8PvFOJejFDftMrrG0sodxJMvtZd3DP5HErcK9en2MB8Mk0c\nWL+2/jnjirGTstLw3pbjuzAbxD2beFd++Uxcjbhnt8Xtj7qCcxV2SlmsrdOV5/Tli3cuinvYhpJy\n2O87cTXintmWhPjUcpc/PsQPjeikd4Ws+v+usNSXcBzBI4RN22SD5ffY5MeZuLjinum4SMsowhTm\nG3Z+Qoh7PsQvT8yqjilVMNXjjsEW6tvG6aqjYD1iExMT8Mgjj8DKlSth1apV8OKLLwIAwJUrV2Bw\ncBCWLVsGGzduhKtXr5o7b7e7g9dD2HKZ6XPby9UfVlb2p/yKadNkD7NbPrkcP7ivOqAcrajX9PQ0\nqUyPdLD6kv6kdbk2sTL1svXvgpX08+bNgxdeeAHeeustOHbsGLz00ktw6tQpGB4ehsHBQThz5gwM\nDAzA8PCwsT2HIFURH+uLWi+UTYzspmMXYkx1gkmXCEXUGMT3sS/1w/aZC9bwvqenB3p6egAA4GMf\n+xjcf//9cPHiRRgdHYXx8XEAABgaGoINGzYYia9fbK7wlyNYUfqzlVH7i23TRkj1WavlJ+7VjfQK\n2AVcF3HP1kcI7YJCcBPIOf25c+fgxIkTsH79epiamoJOpwMAAJ1OB6ampoxt/vSnP3X/7+3thd7e\nXhJByhdpUcQT96j9xbRpGpupzEfcqyPpXRd0HcQ9gLhfoqn6Pn36NJw+fZp8nkmkf//992Hr1q2w\nd+9emD9//ozPbOHjl770pRkOKicpK34scc/Ul15GOXhc4kuJ12q1yMeN02fMPL98PFXftnPomuRN\nbcvHxVVG6UNva2qn++nqD6vn6p9btnz5clixYkX3XP7yl7802lRwkv7DDz+ErVu3wo4dO2DLli0A\n8N/V/dKlS9DT0wOTk5OwcOFC68BM4BCfglCE4LTznWwkCDHO0ETnrmauOmXi1zFKqRrca8t6Noqi\ngJ07d0JfXx8888wz3fLNmzfDyMgIAACMjIx0JwMdvsJYLHGP2i6kuBfyFUo8jEEoruhkq6P6i4WY\nfaewHUTI++Mf/wg/+9nP4HOf+xz09/cDAMDu3bth165dsG3bNti3bx8sWbIEDhw4YGwfIkyuasXH\n6oTM8aVotejP+1PEvfJ5yW3F16OQZqW3Q0VFnEnESvqHHnoIvYCOHDni7Jx6wrjEDyXuUdr5tA1J\nfE7/ruMea4XX3/sKbQ3haeBGDZU9ZVcO47C6VYh7LiHPRyUPJeRhPpr6cB03yioQi1zUW1uc9hRh\nyyS46WXlNi4BzlRm8gsTBU3+m3zzEfX0Pm1I8rNWGPmrCPUxP8v1Qt/y8xHyTBct1abJX1N/5Rxf\nz/upwPrT7QLIn73H2ur1XP3rpNRv3SmNhONvuT/bufa5x08ZFwXJviMP+ywV8fV6PjlzqLCecyvR\nNdnYVp5Qwh7Wj3TFp94PD33P3uSzqz99EtEnDqxfW/+ccamJjHIOKw3vsQ04pna5Ep/any/xXfeP\nqeKeqc9yX6HV/HJ/rgmHI+65Lv6Um3U49WP2keVKz1FlqxD3KPVSEh/AHt77pCEhb+FhtwTL/itN\nR0pMysVfJ+JjkYCE+NzzVumjtSYxrmpxj7Ijj0p8jrhHPTEmFdw0eUp26VV1X9omZNnENr0ca1uu\np5e5dulhdk31sbYcIc0kEtrqUsfp8sOGyn7sQoGbK4cO9TE/XcTxFfekhPO5U+FS9QHc20SlwNpL\nRMIGYVFJTu9aSRWqEvckNmx1KOIeFaYJiFKPQ3xTNFHuNzT0tK4hfVpEJT2AncgpxT2JDZudUIo9\npy/9eElDfc5dAi4wXachfjpEX+ldAltKcU9iA6tjK5dAKhRyiW/brx0jxG/Inh6VCHkA5m9AAUgv\n7klsYHXUmE2QCHk2EbAs5OnHK5S4JxWUbBuAyrDd3WkQD1lszslR3PPJ8UOt9gB0IkhDfaq4F+oe\nsm0nYINqkAXpARpxz+YDdmtJ90O64rvEPQXufWjlp8l3/W9D+uqQDekBGnEvhG8hxT3qZhrXBhhs\nlTeRv0F8ZEV602ehxT0TJLv5ciV+iBy/LO75hvUK+qpu2r3XoBok+336smhnu0ht9Uz1sT5sxLPt\nIKPasNmJoYK77q2HWvFN7wFkD4OYfJPcYWngh2S/T6/Dd+XMOdSX3kUI6Ze0LIS4R31irSF/NUj2\n+/Q+9X3EPcreext8VnwK1KrIbY+F9TmIe0rY08vK79W4G+LHR5Iv0cAu6CrEPcwuh2Sxie/TPpa4\nV/4rzfGxyQDzs0EcJBHyJLlvSHGP0iamuEeFlAQxxL3yXx9xzyb4NaSvBkmFvBDiHkYqTm5te/TX\nBkoko9777MiTIGdxz1RGEVPLY/DdLViuo+rpuwkpbW0+2/pzjYlqk+KHjqRCXghxz7SKUfsv+ykR\n/DDb2EorgbQt9VilEvdMob7tlp9CjN2CALcTzOUfxV9bfxS/JNoIBcmFvBTinqsed4WVjAsDVV+g\n1MMmJZ8tuzFXfMoFbLrwfWxybHH95dTHJnafuyEYshDyUoh7LlspiS+ZqDj1JKt7GSHFPdMFbCK1\njli6gssWl3DU8VEffMJscsZUyaO1pnLqBUYls0Tcw/zFVvwQ4h4VVRA/B3GPs3LriE388mTGHWf5\nM7XzsFwHmwxMdalhPZX4lT1aK11Z1MWJCXeqf1e9ch0dehkW6lPya1tkQgH30VrdR65vMcQ9XSDT\nIY0CTKiC+HpdaW6t98GJEExl2JhcyE7Ic13AlFCV0o/up80PTl9YHi0FdcKgRjLYpOob/ut76V0+\nh8rxMVshiJ9S3MPGNGuFPNcF7CvumWDqI3SOT4GPkCdJYcr9ufqyTRq2h2c4IpWESJwUwTcf1m1x\n/Q2R3kgnR4VshTzbBRxC3DPBFUVURXyffJ4aaYTM8W0bp8qElwp+GDF0xA71sfq+4p7EJ+kxAsjo\n23A5xPcR97j5sU4G/XOquMfdnOMah6leGRR7LgJjdaiTkk54FZ3EJGYVOb5+XUsIaxLtbCE9J5Jx\nobLvvZeS3LaahRD3THD5of/vyl+peTnFD4m/NsRKwWygrnQUMcuEKoiv1/XJt22Th6meq8yFysL7\nWKG+6XOsPod8HOLHBNVnKTGpKUIo4nN284Ugkq1/TlnZ/9zFPReSkh6genGPA1f4G4P4oYU8So6P\n1aFGAdItxlJiUsP8Oot7pvrcCQFDFl+iEYL4VHGPC1cUEYP4McJ6yapPXfE5CLWbj7rCxQ71sfqx\ndu7ZJoQshDzTSoHl177EtwlXvo9susigf24S96oU8iTHyNbWteJzxxZqNx9WpmOuiXsuJPtiTB+S\n28JM06RCSQ1cYh8nx/cJeV02Jb5x+8Mm6xgrPvYeYO7u3MP6s9XjIBnpsc9DXcDSMNwnDbG1pZ4c\njHAuhCQ+NVLwIb4pkomZ4/v077KRm7jnQnakB4gr7nH33lN8iy3umeB7G1Qi7tn6ksDUVno7Txrm\nY+WpxT3q+Li6A0Bi0vusqpQ+qLmmmqmpeSo3x48F32MkWfUpEwYG7M6ERNzDQmeXmMURyFKKe5ht\n6ROJZST7uqxyHdtTcbHEPRMotxipfkiJTxUBuUKezzFyRTccIQ/zI6S4l0uOn0rccyGLW3bq89Cq\nvi7uqZcOE4H0tpJJSUJ8PT+kwPcYhRL3fPwFCCfuUVe+2SruuWAl/fXr1+Hhhx+Gf//733Djxg14\n/PHHYffu3XDlyhV44okn4Pz587BkyRI4cOAALFiw4Lb2EuEnprhHAXdFjLXil2G6+ENunw0p7lHh\n8qMR9+y++hDfSvo777wTxsbG4K677oKbN2/CQw89BK+99hqMjo7C4OAgfPvb34Y9e/bA8PAwDA8P\n39aeSmBXG6xdlcTn6g96lENdvX1u9YWIiiTino+QRxEGm517/wV1A48LzvD+rrvuAgCAGzduwK1b\nt+Cee+6B0dFRGB8fBwCAoaEh2LBhA5n0AHwC2T6LSfyQ4h4V1G24VD84Zcq+xAYFnO8AaHbu0XyU\n2HeSfnp6Gh544AF455134Bvf+AasXLkSpqamoNPpAABAp9OBqakpY9uXX365+39fXx/09fV137vI\nHUvc4yKUuBdC7NLrxYiKqMfNFIq7gI2NSnwfIW82i3vnz5+Hv//97wBAOxdO0rfbbTh58iT84x//\ngE2bNsHY2NiMz22K4fbt22c4y7kfrj6PsWVXR3lHnu3etPJHIu6FEOdMPnPaxzhuEkiIj70HoN/O\no6yGdRT3Fi9eDJ/+9Keh3W5Dq9WCo0ePWtuQ1fu7774bHn30UXjjjTeg0+nApUuXoKenByYnJ2Hh\nwoXGNtKn7Gz92NqFWvGpAqTPmCR+cJFK3IvlWyPu2X2ljs9a4/Lly3D16lUAAPjggw/g8OHD0N/f\nD5s3b4aRkREAABgZGYEtW7YY2+thSPk99TPby9SOWha73xBjarfb6KuKsVBsSccp8U2/2PWXiiZt\nZaY6pjaUvjhlVFsSf13Rpw7rSj85OQlDQ0Ndx3bs2AEDAwPQ398P27Ztg3379sGS/92yw0hfhlTA\ns614sVZ8k01TH1zfKKBGP9S+qxD3KDD57JPjN+JehG24q1evhuPHj99W/olPfAKOHDni7BwjDjYr\nYSfblUtzLmqqyINd6Hq/LkJIhLyyr1hbkyiWStzjjM3XplTckxKzjuKeC9k9cCPNJX0FKWyC4Ih7\ntijG5162rW35GLrqxs7xdWC+UM+7i/g2O1Ti5KLq63V9xD0XsiM9QHxxT2KTkqqEEPA4YbvEZlXE\nL0cd6qKmRkWcMt1GGRSSz0Zxz4XKHrjhhPOuzwD8d+5xbcZcETl+KJQnh3IqIO2fmyJxyV++sENp\nNFXezsN0gBg5vm4rNPGz/IWbGJ+FIL5No+Dk+RRI0hzOhOM7iXHGiGkmajJoxD23LWmEYkLlj9aG\nEvck7bCcVy+TXOjlz0z1uEJe2Q9MyFN1yuPXfU8l7uljUfBJy6jEb8Q9Oyr/CmxJ2C5Z9ajtlE3O\npOGaZGz1uHCJcyb7OYt7MfwAaMQ9DpI8Ty8J26l5rqQdVi+XHN8E00RFnVh1hMjxQyDUBMQV96Q5\nc13FvWQ5vU0Qkqr6PncDsHqhiB+KGDZb1ONL6YtTZgL3LkQIP0zHOSbxMR0gRo6v2/IhfvJfrQ1B\nNN/PXPVsbaniXiy4jidn1Q9NfGmUEzrHp4p7JrFsNop7Sb4jTydFleKeVMjDbFLFPR/YhDyTb673\nocU9l9CYA/Gpqzt15dZRRY6vkx3ry4Wk35GXQtzD+vcNKbmTk80XiQhoIjqm6rvSjdm24vvm+Fhb\naV8+xNeSGxr8AAAOmklEQVTrUqORMioN7105PieEdrVxtaX0FSvHp4Lb1jax6v9L+vLRK6S6hm+O\nr0cjc0XcsyEp6QFo4pNPrh7rQucSn3rB6/W4KYIttOdqDT6TGFXIo9TzJf5cFfcwZPEDlhTxSUp8\n/TNufizxxyeX10kgWSG5OT6nL1MZ9SlAaj2pH1iZsqP/lZCQGk7HDvWx+pRrJZsfsNRXoVjiHnej\nC7cM89338VMuODm+slv18wzceqGJH5uYVeT4Otkpxzq7n7WKLe5hfYXIG8tlvjvyKON39e/y1xT6\nS/vyGQunXiji+z6dh5VR+gpNfGpdhaSkN9XBLkpq3z7Ep/QlST2oEQbFPtY/J/UJLe6FFPJiE79c\nxiG+KaynEi2VuIchOek5q5GrHeUzrq8hiO8DjCwcwc+W07smDVdfGHyEvCqIP5vFPReS/4Clquci\nfmhVn1M/NfFNMAl+nGPsem+DXjeGkJcix59N4p4NlT9lh8FEbL0spLhH9cHWV1XE9yGVzTfbez33\ndfVFtcmpl4L4sYlZVY5vQza/WmurV7W4x4ksQhOfItBhtiihuonopomVokXMNuLPlp17LiT/5hxu\nO1sfdRH3KODk2th+CE664vNYbmwhr4ocX5/06rxzz4UkT9mFvNXkakf5DEMO4h5VDDUd06rEPRNC\nC3lVEF8q7kmedsPqVLHiJxPyuMKTXsYJwcufce63cicRW5nk67JsPlN84h5jbnuFqoS8FDk+RdxT\n59dVpgOrE5v4SXN6ykUZWtzjwtaXzyoSCxSi2erb3rvEPUr/nHqpia9I6UPCHHP85Dm99CT6iHum\nOpQJooqwPsSDKqaIiJPj6xOr+rzcFwd1JX6r1aosx6+S+Mm/OQer5+qLkuNT+/bxA7PvQ3wOSTAy\nc+9kuM6L7diYCIGJiy7kQvxyWd3FPR1JduRJcscYOb7JhmvFj/FQCrU/Tl1sLCnFPRNCP/egw5f4\ns3HnXjZCXqgTSJ21y+BsaeWQplwmEfJsbak+x8zxuYgh5FWZ49dl554LWQl5lNXEVEcvc4l7Jj+p\nF3a5H464JxXyqG2pk5GEJFiOD4A/kmt7VJdi07csZP8AcnEvxdN5LmQp5FFOou2ZdclqxN3gYvPV\ndzWktMW+bIOSs5cnLk6Ob4qYsElJfwKMgjoQnyvumVZ3KlFjET8LIU9yEik5Pod42KoUUtyjgtqW\nu/kppLjHTZmwspALQxU5vj7mnMU9DFkIeZwyThuO+ITZovQRevsvtS2XsNhYfMW90HsQcid+ncQ9\nE7IR8rAyybfv2C5UG6QCHoU0sYQ829iqEvcw25RjjuX+ORNf+a3+qjFIiImRWgcn1HchKyHPVEY9\ngRJxD+vHlO/aVnxbu/LnElDaYseoKnGPospzhT3Mr9yIX450fHJw6qrvm88DZPYV2FiZz0odUtzD\nyiR1bG2pY3VNSq7UhJsKUcNd3U9bPZfglzvx1fhyeyzXhuTqPVZuW1kwUHN8HdjBlgp0Prk8pz01\nHbIduxCP5VJ9pAp+FJu5EN80vphP53H6x5CFeo+VS06ipA22997mq1Tco0JKfFcagq3UHC2Fm9P7\nToJYHzkRXyLumfJ5aphP1RBMSKbe+z61Fpr4mL+hxL2YO/KoK76tXO+DI+5RcnpbeK/73oh7fuKe\nC9l9731I4mM5rgnqAGKzuK+4F3tHHlUHiSnuueqEEPzqQPzU4p4LJNLfunUL1q1bB729vfCb3/wG\nrly5Ak888QScP38elixZAgcOHIAFCxbc1i72U2shRTWq4CcV90KD8qAKJ5w3taHqKJS7C66JTxf8\nZou4hwmVscU9G0g19+7dC319fd3BDA8Pw+DgIJw5cwYGBgZgeHjY2E4N2vZqt9vkcr0Ma8uto9ej\ntinX57YJ8fI5RhyfJeNLUd+nLFb/CnrUpyZTV5mpjuvlTfoLFy7AwYMH4etf/3q3w9HRURgaGgIA\ngKGhIfjVr34lJr3rwpRe1JILSid+CiJzX9RjxD3GIcbOPTezjfg6YhJ/enq6W88FZ3j/rW99C374\nwx/CtWvXumVTU1PQ6XQAAKDT6cDU1JSx7fPPP9/9/8EHH4QvfOELqB0fcY8ahkpEMb2+LTykhI4S\ncH3Gykz92Mpdx4LiHzenx87lXBP3TLfzsMnkvffeg6tXrwIALdW0kv63v/0tLFy4EPr7++Ho0aPG\nOmpmM+HZZ5/t/u8ipUIV4p5pDNgkElLco6DV+v/tQ90vG3wmR9uFwhX3qL656sx1cQ8juen6XbBg\nAdxzzz1dLr7zzjvW8VhJ//rrr8Po6CgcPHgQrl+/DteuXYMdO3ZAp9OBS5cuQU9PD0xOTsLChQuN\n7TmrpK0d1lZ6Eqk2VVkKcU8RlCKUldtIVvzQ4h7WB0XwM0UWjbjHfzrPBmvr5557DiYmJuDs2bPw\n85//HL761a/CT3/6U9i8eTOMjIwAAMDIyAhs2bLF2D5EnhcrX+P2I8k3U2gCPjoIx+dYef9szvHV\n/wqxcnwXWPfplcO7du2Cbdu2wb59+2DJ/27Z2errkM6sWDknf7XB1IYS3tpsSfzwBTXU52gTktRA\n6q9PSpHzim+KdlKs+K1CumvE1XGrBe+++273PWUGsymTIWdEEzh9Y/36zsC6H7a2oY6bZCz6saCO\ng3vcbe/L+X7Ia4Z6Xfr2VfY9dJQyNjZmvd6ye7TWBOns6iM86Re0S9wr17GRoUpUJe5RJzSuv7b3\nrVarSxhKX75lIfsHCLtzj3v8kz9lF1vckwpPmE1VJhH3qDapx8O0quioQtyz+cc97q5rpnz8XRFU\n7sRXY1ErtGksFJJzQ/3K995TyUutE/Ikcvu29emT60ojFJ9VDyO5LXopX7Q61IXJnXSxKGu25vjT\n0zP3jlCIr9pIc/xsfrW2KuJz8msAmrjHDY/Ln2O+uFYHUztqSG4r44iSnOPJnQQbcW8mQop7yZ6y\n8znA1EnDRRwFV4hoWumwsBPzEzsWNl9MK4ENrnq+OgiHuHqaIol8XMTnRhC5Eh8g7GO5LtTi0Vqf\ntpT+qHm0LSSmiHsScIQyCrF8iE+duABu314rTXc44p46To24Z0dS0gOkEfeoflBtUsU9CjhCni19\n8RX3XOkRdZy68KZQ/p+7OGBRFmWCzZ34UnEvm5y+7ITtQkkl7oWy6ZNvmkBdFalRDLWtLZIxtaeQ\n32RHha/lvzZfMd9ma44vEfewMhOS37JT5VWJe6YDaMqjbZCKe1To/bvUcZudqsU9zI5pY4qkn7lC\nfMptOazMhUpWeiqpfA6wdNIAMD9lZ2uHhblY2MlFiAuY6oPviu9za7K8wlNWe8w322Rr6zdn4pd9\nL19rvvk8QEUrPUfJ9cnxQ7b1aecS9ygwrY4cPxRC6irUfRcuSMhu88022YYSk1MRf3p6esY1UCsh\njxOK+ZBXqg+Y6vnYDCnuUeES32KKezpsO/IoKYkrPbKljqbVv67iXrmMK+5hSPYLN668twpxj2I3\nxEnFiGGC7z52qSaBtZVOhK761N18tlSw2bk3E1Ti+z2N70Cr1YLx8XH2U0OqnFOf06f+crVtt9tw\n/Phxp12Jr9I2tnrYZ6dPnxb16zpG0mMqPZcXLlwg+cY9/tTrLdR1ee3aNVb/OsqhP+dWanTSv/rq\nq86Tzb2AqQdYSiBTuxMnTojsqTJswjGRRTJZUI4RhfTUY845vpTjZps09FeZ9K7zZ+qvfH1Kr7cQ\nxP/nP//J7kuhTHKd+C5UJuTp0MMYUx2sLlZGbUupp4eP6kRI7iRwwnuO36pfbJY3HWP94uHYN5VR\n+uLUM9kytdXLXGmITnaq7RBltv6VL5y+KOKe1T65ZgRwL4QcENvnKo6JbQWR9JUrOESvGin9ifrN\nOQ0aNEgDG62jhfeR5pIGDRp4Iml436BBg+rRkL5BgzmGqKQ/dOgQrFixApYuXQp79uyJaSoonn76\naeh0OrB69epu2ZUrV2BwcBCWLVsGGzdu7P6MUK6YmJiARx55BFauXAmrVq2CF198EQDqN47r16/D\n+vXrYe3atdDX1wff/e53AaB+4wD4768/9/f3w2OPPQYA6cYQjfS3bt2Cb37zm3Do0CF4++23Yf/+\n/XDq1KlY5oLiqaeegkOHDs0oo/5Sby6YN28evPDCC/DWW2/BsWPH4KWXXoJTp07Vbhx33nknjI2N\nwcmTJ+HNN9+EsbExeO2112o3DgD5rz8HRxEJr7/+erFp06bu+927dxe7d++OZS44zp49W6xatar7\nfvny5cWlS5eKoiiKycnJYvny5alcE+Hxxx8vDh8+XOtx/Otf/yrWrVtX/PWvf63dOCYmJoqBgYHi\nlVdeKb72ta8VRZHumoq20l+8eBEWLVrUfd/b2wsXL16MZS46qL/UmyPOnTsHJ06cgPXr19dyHNPT\n07B27VrodDrdlKVu41C//lzeRJNqDNFIP5vv0/tuaKkS77//PmzduhX27t0L8+fPn/FZXcbRbrfh\n5MmTcOHCBXj11VdhbGxsxue5j6P8688Fciu7yjFEI/29994LExMT3fcTExPQ29sby1x0qF/qBQDr\nL/XmhA8//BC2bt0KO3bs6P7IaB3HoXD33XfDo48+Cm+88UatxqF+/fkzn/kMPPnkk/DKK6/M+PVn\ngGrHEI3069atg7/97W9w7tw5uHHjBvziF7+AzZs3xzIXHdRf6s0FRVHAzp07oa+vD5555plued3G\ncfny5a6q/cEHH8Dhw4ehv7+/VuPw/fXn4IgpGBw8eLBYtmxZcd999xXPPfdcTFNBsX379uKTn/xk\nMW/evKK3t7f4yU9+Urz77rvFwMBAsXTp0mJwcLB47733UrtpxR/+8Iei1WoVa9asKdauXVusXbu2\n+N3vfle7cbz55ptFf39/sWbNmmL16tXFD37wg6IoitqNQ+Ho0aPFY489VhRFujFE23vfoEGDPNHs\nyGvQYI6hIX2DBnMMDekbNJhjaEjfoMEcQ0P6Bg3mGBrSN2gwx9CQvkGDOYb/AK6S3aTdrHIPAAAA\nAElFTkSuQmCC\n"
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "imshow(dists,cmap=cm.gray)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f88d4c46",
   "metadata": {},
   "source": [
    "# Tracing Back the Path"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "id": "8bfe113d",
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "l = sources[i,n]\n",
    "path = []\n",
    "while l is not None:\n",
    "    path.append(l)\n",
    "    i,j = l\n",
    "    l = sources[i,j]\n",
    "path = [(n+2,m+2)]+path"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "id": "24ab9fc8",
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(46, 46), (44, 43), (43, 42), (42, 41), (41, 40)]"
      ]
     },
     "execution_count": 36,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "path[:5]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e3e5e486",
   "metadata": {},
   "source": [
    "# Summarizing the Edits"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "id": "ceba971b",
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "the quick brown_ fox__ jumps over the lazy dogs\n",
      "the quack bri_ne foxes jump_ over the lazy dog_\n",
      "      ^     ^^ ^    ^^     ^                  ^\n"
     ]
    }
   ],
   "source": [
    "al,bl = [],[]\n",
    "for k in range(len(path)-1):\n",
    "    i,j = path[k]\n",
    "    i0,j0 = path[k+1]\n",
    "    u = \"_\"\n",
    "    v = \"_\"\n",
    "    if j!=j0 and j0<n: u = a[j0]\n",
    "    if i!=i0 and i0<m: v = b[i0]\n",
    "    al.append(u)\n",
    "    bl.append(v)\n",
    "al = \"\".join(al[::-1])\n",
    "bl = \"\".join(bl[::-1])\n",
    "print al\n",
    "print bl\n",
    "print \"\".join([\"^\" if al[i]!=bl[i] else \" \" for i in range(len(al))])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "07ea7ab2",
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 5
}