{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 116,
   "metadata": {},
   "outputs": [],
   "source": [
    "def min_edit_distance(source, target):\n",
    "    \n",
    "    n = len(source)\n",
    "    m = len(target)\n",
    "    \n",
    "    D = np.zeros((n+1, m+1))\n",
    "    \n",
    "    D[:, 0] = range(n+1)\n",
    "    D[0, :] = range(m+1)\n",
    "    \n",
    "    for i in range(1, n+1):\n",
    "        for j in range(1, m+1):\n",
    "            dc = D[i-1, j] + 1\n",
    "            ic = D[i, j-1] + 1\n",
    "            if source[i-1] == target[j-1]:\n",
    "                sc = D[i-1, j-1]\n",
    "            else:\n",
    "                sc = D[i-1, j-1] + 2\n",
    "            D[i, j] = min(dc, ic, sc)\n",
    "    print(D)\n",
    "    return D[n, m]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 117,
   "metadata": {},
   "outputs": [],
   "source": [
    "s = \"intention\"\n",
    "t = \"execution\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 118,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[ 0.  1.  2.  3.  4.  5.  6.  7.  8.  9.]\n",
      " [ 1.  2.  3.  4.  5.  6.  7.  6.  7.  8.]\n",
      " [ 2.  3.  4.  5.  6.  7.  8.  7.  8.  7.]\n",
      " [ 3.  4.  5.  6.  7.  8.  7.  8.  9.  8.]\n",
      " [ 4.  3.  4.  5.  6.  7.  8.  9. 10.  9.]\n",
      " [ 5.  4.  5.  6.  7.  8.  9. 10. 11. 10.]\n",
      " [ 6.  5.  6.  7.  8.  9.  8.  9. 10. 11.]\n",
      " [ 7.  6.  7.  8.  9. 10.  9.  8.  9. 10.]\n",
      " [ 8.  7.  8.  9. 10. 11. 10.  9.  8.  9.]\n",
      " [ 9.  8.  9. 10. 11. 12. 11. 10.  9.  8.]]\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "8.0"
      ]
     },
     "execution_count": 118,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "min_edit_distance(s, t)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "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.7.2"
  },
  "latex_envs": {
   "LaTeX_envs_menu_present": true,
   "autoclose": false,
   "autocomplete": true,
   "bibliofile": "biblio.bib",
   "cite_by": "apalike",
   "current_citInitial": 1,
   "eqLabelWithNumbers": true,
   "eqNumInitial": 1,
   "hotkeys": {
    "equation": "Ctrl-E",
    "itemize": "Ctrl-I"
   },
   "labels_anchors": false,
   "latex_user_defs": false,
   "report_style_numbering": false,
   "user_envs_cfg": false
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}