C2 - NLP with probabilistic models/Week_1/C2_W1_Assignment.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Assignment 1: Auto Correct\n",
    "\n",
    "Welcome to the first assignment of Course 2. This assignment will give you a chance to brush up on your python and probability skills. In doing so, you will implement an auto-correct system that is very effective and useful."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Outline\n",
    "- [0. Overview](#0)\n",
    "    - [0.1 Edit Distance](#0-1)\n",
    "- [1. Data Preprocessing](#1)\n",
    "    - [1.1 Exercise 1](#ex-1)\n",
    "    - [1.2 Exercise 2](#ex-2)\n",
    "    - [1.3 Exercise 3](#ex-3)\n",
    "- [2. String Manipulation](#2)\n",
    "    - [2.1 Exercise 4](#ex-4)\n",
    "    - [2.2 Exercise 5](#ex-5)\n",
    "    - [2.3 Exercise 6](#ex-6)\n",
    "    - [2.4 Exercise 7](#ex-7)\n",
    "- [3. Combining the edits](#3)\n",
    "    - [3.1 Exercise 8](#ex-8)\n",
    "    - [3.2 Exercise 9](#ex-9)\n",
    "    - [3.3 Exercise 10](#ex-10)\n",
    "- [4. Minimum Edit Distance](#4)\n",
    "    - [4.1 Exercise 11](#ex-11)\n",
    "- [5. Backtrace (Optional)](#5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<a name='0'></a>\n",
    "## 0. Overview\n",
    "\n",
    "You use autocorrect every day on your cell phone and computer. In this assignment, you will explore what really goes on behind the scenes. Of course, the model you are about to implement is not identical to the one used in your phone, but it is still quite good. \n",
    "\n",
    "By completing this assignment you will learn how to: \n",
    "\n",
    "- Get a word count given a corpus\n",
    "- Get a word probability in the corpus \n",
    "- Manipulate strings \n",
    "- Filter strings \n",
    "- Implement Minimum edit distance to compare strings and to help find the optimal path for the edits. \n",
    "- Understand how dynamic programming works\n",
    "\n",
    "\n",
    "Similar systems are used everywhere. \n",
    "- For example, if you type in the word **\"I am lerningg\"**, chances are very high that you meant to write **\"learning\"**, as shown in **Figure 1**. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div style=\"width:image width px; font-size:100%; text-align:center;\"><img src='auto-correct.png' alt=\"alternate text\" width=\"width\" height=\"height\" style=\"width:300px;height:250px;\" /> Figure 1 </div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<a name='0-1'></a>\n",
    "#### 0.1 Edit Distance\n",
    "\n",
    "In this assignment, you will implement models that correct words that are 1 and 2 edit distances away. \n",
    "- We say two words are n edit distance away from each other when we need n edits to change one word into another. \n",
    "\n",
    "An edit could consist of one of the following options: \n",
    "\n",
    "- Delete (remove a letter): ‘hat’ => ‘at, ha, ht’\n",
    "- Switch (swap 2 adjacent letters): ‘eta’ => ‘eat, tea,...’\n",
    "- Replace (change 1 letter to another): ‘jat’ => ‘hat, rat, cat, mat, ...’\n",
    "- Insert (add a letter): ‘te’ => ‘the, ten, ate, ...’\n",
    "\n",
    "You will be using the four methods above to implement an Auto-correct. \n",
    "- To do so, you will need to compute probabilities that a certain word is correct given an input. \n",
    "\n",
    "This auto-correct you are about to implement was first created by [Peter Norvig](https://en.wikipedia.org/wiki/Peter_Norvig) in 2007. \n",
    "- His [original article](https://norvig.com/spell-correct.html) may be a useful reference for this assignment.\n",
    "\n",
    "The goal of our spell check model is to compute the following probability:\n",
    "\n",
    "$$P(c|w) = \\frac{P(w|c)\\times P(c)}{P(w)} \\tag{Eqn-1}$$\n",
    "\n",
    "The equation above is [Bayes Rule](https://en.wikipedia.org/wiki/Bayes%27_theorem). \n",
    "- Equation 1 says that the probability of a word being correct $P(c|w) $is equal to the probability of having a certain word $w$, given that it is correct $P(w|c)$, multiplied by the probability of being correct in general $P(C)$ divided by the probability of that word $w$ appearing $P(w)$ in general.\n",
    "- To compute equation 1, you will first import a data set and then create all the probabilities that you need using that data set. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<a name='1'></a>\n",
    "# Part 1: Data Preprocessing "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import re\n",
    "from collections import Counter\n",
    "import numpy as np\n",
    "import pandas as pd"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As in any other machine learning task, the first thing you have to do is process your data set. \n",
    "- Many courses load in pre-processed data for you. \n",
    "- However, in the real world, when you build these NLP systems, you load the datasets and process them.\n",
    "- So let's get some real world practice in pre-processing the data!\n",
    "\n",
    "Your first task is to read in a file called **'shakespeare.txt'** which is found in your file directory. To look at this file you can go to `File ==> Open `. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<a name='ex-1'></a>\n",
    "### Exercise 1\n",
    "Implement the function `process_data` which \n",
    "\n",
    "1) Reads in a corpus (text file)\n",
    "\n",
    "2) Changes everything to lowercase\n",
    "\n",
    "3) Returns a list of words. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Options and Hints\n",
    "- If you would like more of a real-life practice, don't open the 'Hints' below (yet) and try searching the web to derive your answer.\n",
    "- If you want a little help, click on the green \"General Hints\" section by clicking on it with your mouse.\n",
    "- If you get stuck or are not getting the expected results, click on the green 'Detailed Hints' section to get hints for each step that you'll take to complete this function."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<details>    \n",
    "<summary>\n",
    "    <font size=\"3\" color=\"darkgreen\"><b>General Hints</b></font>\n",
    "</summary>\n",
    "<p>\n",
    "    \n",
    "General Hints to get started\n",
    "<ul>\n",
    "    <li>Python <a href=\"https://docs.python.org/3/tutorial/inputoutput.html\">input and output<a></li>\n",
    "    <li>Python <a href=\"https://docs.python.org/3/library/re.html\" >'re' documentation </a> </li>\n",
    "</ul>\n",
    "</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<details>    \n",
    "<summary>\n",
    "    <font size=\"3\" color=\"darkgreen\"><b>Detailed Hints</b></font>\n",
    "</summary>\n",
    "<p>     \n",
    "Detailed hints if you're stuck\n",
    "<ul>\n",
    "    <li>Use 'with' syntax to read a file</li>\n",
    "    <li>Decide whether to use 'read()' or 'readline().  What's the difference?</li>\n",
    "    <li>Choose whether to use either str.lower() or str.lowercase().  What is the difference?</li>\n",
    "    <li>Use re.findall(pattern, string)</li>\n",
    "    <li>Look for the \"Raw String Notation\" section in the Python 're' documentation to understand the difference between r'\\W', r'\\W' and '\\\\W'. </li>\n",
    "    <li>For the pattern, decide between using '\\s', '\\w', '\\s+' or '\\w+'.  What do you think are the differences?</li>\n",
    "</ul>\n",
    "</p>\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "# UNQ_C1 (UNIQUE CELL IDENTIFIER, DO NOT EDIT)\n",
    "# GRADED FUNCTION: process_data\n",
    "def process_data(file_name):\n",
    "    \"\"\"\n",
    "    Input: \n",
    "        A file_name which is found in your current directory. You just have to read it in. \n",
    "    Output: \n",
    "        words: a list containing all the words in the corpus (text file you read) in lower case. \n",
    "    \"\"\"\n",
    "    words = [] # return this variable correctly\n",
    "\n",
    "    ### START CODE HERE ### \n",
    "    with open(file_name, mode = 'r') as file:\n",
    "        for line in file:\n",
    "            line_words = re.findall(r'\\w+', line.lower())\n",
    "            for word in line_words:\n",
    "                words.append(word)\n",
    "            \n",
    "    ### END CODE HERE ###\n",
    "    \n",
    "    return words"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Note, in the following cell, 'words' is converted to a python `set`. This eliminates any duplicate entries."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The first ten words in the text are: \n",
      "['o', 'for', 'a', 'muse', 'of', 'fire', 'that', 'would', 'ascend', 'the']\n",
      "There are 6116 unique words in the vocabulary.\n"
     ]
    }
   ],
   "source": [
    "#DO NOT MODIFY THIS CELL\n",
    "word_l = process_data('shakespeare.txt')\n",
    "vocab = set(word_l)  # this will be your new vocabulary\n",
    "print(f\"The first ten words in the text are: \\n{word_l[0:10]}\")\n",
    "print(f\"There are {len(vocab)} unique words in the vocabulary.\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Expected Output\n",
    "```Python\n",
    "The first ten words in the text are: \n",
    "['o', 'for', 'a', 'muse', 'of', 'fire', 'that', 'would', 'ascend', 'the']\n",
    "There are 6116 unique words in the vocabulary.\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<a name='ex-2'></a>\n",
    "### Exercise 2\n",
    "\n",
    "Implement a `get_count` function that returns a dictionary\n",
    "- The dictionary's keys are words\n",
    "- The value for each word is the number of times that word appears in the corpus. \n",
    "\n",
    "For example, given the following sentence: **\"I am happy because I am learning\"**, your dictionary should return the following: \n",
    "<table style=\"width:20%\">\n",
    "\n",
    "  <tr>\n",
    "    <td> <b>Key </b>  </td>\n",
    "    <td> <b>Value </b> </td> \n",
    "\n",
    "\n",
    "  </tr>\n",
    "  <tr>\n",
    "    <td> I  </td>\n",
    "    <td> 2</td> \n",
    " \n",
    "  </tr>\n",
    "   \n",
    "  <tr>\n",
    "    <td>am</td>\n",
    "    <td>2</td> \n",
    "  </tr>\n",
    "\n",
    "  <tr>\n",
    "    <td>happy</td>\n",
    "    <td>1</td> \n",
    "  </tr>\n",
    "  \n",
    "   <tr>\n",
    "    <td>because</td>\n",
    "    <td>1</td> \n",
    "  </tr>\n",
    "  \n",
    "   <tr>\n",
    "    <td>learning</td>\n",
    "    <td>1</td> \n",
    "  </tr>\n",
    "</table>\n",
    "\n",
    "\n",
    "**Instructions**: \n",
    "Implement a `get_count` which returns a dictionary where the key is a word and the value is the number of times the word appears in the list.  \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<details>    \n",
    "<summary>\n",
    "    <font size=\"3\" color=\"darkgreen\"><b>Hints</b></font>\n",
    "</summary>\n",
    "<p>\n",
    "<ul>\n",
    "    <li>Try implementing this using a for loop and a regular dictionary. This may be good practice for similar coding interview questions</li>\n",
    "    <li>You can also use defaultdict instead of a regualr dictionary, along with the for loop</li>\n",
    "    <li>Otherwise, to skip using a for loop, you can use Python's <a href=\"https://docs.python.org/3.7/library/collections.html#collections.Counter\" > Counter class</a> </li>\n",
    "</ul>\n",
    "</p>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "# UNQ_C2 (UNIQUE CELL IDENTIFIER, DO NOT EDIT)\n",
    "# UNIT TEST COMMENT: Candidate for Table Driven Tests\n",
    "# GRADED FUNCTION: get_count\n",
    "def get_count(word_l):\n",
    "    '''\n",
    "    Input:\n",
    "        word_l: a set of words representing the corpus. \n",
    "    Output:\n",
    "        word_count_dict: The wordcount dictionary where key is the word and value is its frequency.\n",
    "    '''\n",
    "    \n",
    "    word_count_dict = {}  # fill this with word counts\n",
    "    ### START CODE HERE \n",
    "    word_count_dict = Counter(word_l)     \n",
    "    ### END CODE HERE ### \n",
    "    return word_count_dict"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "There are 6116 key values pairs\n",
      "The count for the word 'thee' is 240\n"
     ]
    }
   ],
   "source": [
    "#DO NOT MODIFY THIS CELL\n",
    "word_count_dict = get_count(word_l)\n",
    "print(f\"There are {len(word_count_dict)} key values pairs\")\n",
    "print(f\"The count for the word 'thee' is {word_count_dict.get('thee', 0)}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "#### Expected Output\n",
    "```Python\n",
    "There are 6116 key values pairs\n",
    "The count for the word 'thee' is 240\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<a name='ex-3'></a>\n",
    "### Exercise 3\n",
    "Given the dictionary of word counts, compute the probability that each word will appear if randomly selected from the corpus of words.\n",
    "\n",
    "$$P(w_i) = \\frac{C(w_i)}{M} \\tag{Eqn-2}$$\n",
    "where \n",
    "\n",
    "$C(w_i)$ is the total number of times $w_i$ appears in the corpus.\n",
    "\n",
    "$M$ is the total number of words in the corpus.\n",
    "\n",
    "For example, the probability of the word 'am' in the sentence **'I am happy because I am learning'** is:\n",
    "\n",
    "$$P(am) = \\frac{C(w_i)}{M} = \\frac {2}{7} \\tag{Eqn-3}.$$\n",
    "\n",
    "**Instructions:** Implement `get_probs` function which gives you the probability \n",
    "that a word occurs in a sample. This returns a dictionary where the keys are words, and the value for each word is its probability in the corpus of words."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<details>    \n",
    "<summary>\n",
    "    <font size=\"3\" color=\"darkgreen\"><b>Hints</b></font>\n",
    "</summary>\n",
    "<p>\n",
    "General advice\n",
    "<ul>\n",
    "    <li> Use dictionary.values() </li>\n",
    "    <li> Use sum() </li>\n",
    "    <li> The cardinality (number of words in the corpus should be equal to len(word_l).  You will calculate this same number, but using the word count dictionary.</li>\n",
    "</ul>\n",
    "    \n",
    "If you're using a for loop:\n",
    "<ul>\n",
    "    <li> Use dictionary.keys() </li>\n",
    "</ul>\n",
    "    \n",
    "If you're using a dictionary comprehension:\n",
    "<ul>\n",
    "    <li>Use dictionary.items() </li>\n",
    "</ul>\n",
    "</p>\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [],
   "source": [
    "# UNQ_C3 (UNIQUE CELL IDENTIFIER, DO NOT EDIT)\n",
    "# GRADED FUNCTION: get_probs\n",
    "def get_probs(word_count_dict):\n",
    "    '''\n",
    "    Input:\n",
    "        word_count_dict: The wordcount dictionary where key is the word and value is its frequency.\n",
    "    Output:\n",
    "        probs: A dictionary where keys are the words and the values are the probability that a word will occur. \n",
    "    '''\n",
    "    probs = {}  # return this variable correctly\n",
    "    M = len(word_l)\n",
    "    ### START CODE HERE ###\n",
    "    for key in word_count_dict.keys():\n",
    "        probs[key] = word_count_dict.get(key, 0) / M\n",
    "    ### END CODE HERE ###\n",
    "    return probs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Length of probs is 6116\n",
      "P('thee') is 0.0045\n"
     ]
    }
   ],
   "source": [
    "#DO NOT MODIFY THIS CELL\n",
    "probs = get_probs(word_count_dict)\n",
    "print(f\"Length of probs is {len(probs)}\")\n",
    "print(f\"P('thee') is {probs['thee']:.4f}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Expected Output\n",
    "\n",
    "```Python\n",
    "Length of probs is 6116\n",
    "P('thee') is 0.0045\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<a name='2'></a>\n",
    "# Part 2: String Manipulations\n",
    "\n",
    "Now, that you have computed $P(w_i)$ for all the words in the corpus, you will write a few functions to manipulate strings so that you can edit the erroneous strings and return the right spellings of the words. In this section, you will implement four functions: \n",
    "\n",
    "* `delete_letter`: given a word, it returns all the possible strings that have **one character removed**. \n",
    "* `switch_letter`: given a word, it returns all the possible strings that have **two adjacent letters switched**.\n",
    "* `replace_letter`: given a word, it returns all the possible strings that have **one character replaced by another different letter**.\n",
    "* `insert_letter`: given a word, it returns all the possible strings that have an **additional character inserted**. \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### List comprehensions\n",
    "\n",
    "String and list manipulation in python will often make use of a python feature called  [list comprehensions](https://docs.python.org/3/tutorial/datastructures.html#list-comprehensions). The routines below will be described as using list comprehensions, but if you would rather implement them in another way, you are free to do so as long as the result is the same. Further, the following section will provide detailed instructions on how to use list comprehensions and how to implement the desired functions. If you are a python expert, feel free to skip the python hints and move to implementing the routines directly."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Python List Comprehensions embed a looping structure inside of a list declaration, collapsing many lines of code into a single line. If you are not familiar with them, they seem slightly out of order relative to for loops. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div style=\"width:image width px; font-size:100%; text-align:center;\"><img src='GenericListComp3.PNG' alt=\"alternate text\" width=\"width\" height=\"height\"  style=\"width:800px;height:400px;\"/> Figure 2 </div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The diagram above shows that the components of a list comprehension are the same components you would find in a typical for loop that appends to a list, but in a different order. With that in mind, we'll continue the specifics of this assignment. We will be very descriptive for the first function, `deletes()`, and less so in later functions as you become familiar with list comprehensions."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<a name='ex-4'></a>\n",
    "### Exercise 4\n",
    "\n",
    "**Instructions for delete_letter():** Implement a `delete_letter()` function that, given a word, returns a list of strings with one character deleted. \n",
    "\n",
    "For example, given the word **nice**, it would return the set: {'ice', 'nce', 'nic', 'nie'}. \n",
    "\n",
    "**Step 1:** Create a list of 'splits'. This is all the ways you can split a word into Left and Right: For example,   \n",
    "'nice is split into : `[('', 'nice'), ('n', 'ice'), ('ni', 'ce'), ('nic', 'e'), ('nice', '')]`\n",
    "This is common to all four functions (delete, replace, switch, insert).\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div style=\"width:image width px; font-size:100%; text-align:center;\"><img src='Splits1.PNG' alt=\"alternate text\" width=\"width\" height=\"height\" style=\"width:650px;height:200px;\" /> Figure 3 </div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Step 2:** This is specific to `delete_letter`. Here, we are generating all words that result from deleting one character.  \n",
    "This can be done in a single line with a list comprehension. You can make use of this type of syntax:  \n",
    "`[f(a,b) for a, b in splits if condition]`  \n",
    "\n",
    "For our 'nice' example you get: \n",
    "['ice', 'nce', 'nie', 'nic']"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div style=\"width:image width px; font-size:100%; text-align:center;\"><img src='ListComp2.PNG' alt=\"alternate text\" width=\"width\" height=\"height\" style=\"width:550px;height:300px;\" /> Figure 4 </div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Levels of assistance\n",
    "\n",
    "Try this exercise with these levels of assistance.  \n",
    "- We hope that this will make it both a meaningful experience but also not a frustrating experience. \n",
    "- Start with level 1, then move onto level 2, and 3 as needed.\n",
    "\n",
    "    - Level 1. Try to think this through and implement this yourself.\n",
    "    - Level 2. Click on the \"Level 2 Hints\" section for some hints to get started.\n",
    "    - Level 3. If you would prefer more guidance, please click on the \"Level 3 Hints\" cell for step by step instructions.\n",
    "    \n",
    "- If you are still stuck, look at the images in the \"list comprehensions\" section above.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<details>    \n",
    "<summary>\n",
    "    <font size=\"3\" color=\"darkgreen\"><b>Level 2 Hints</b></font>\n",
    "</summary>\n",
    "<p>\n",
    "<ul>\n",
    "    <li><a href=\"\" > Use array slicing like my_string[0:2] </a> </li>\n",
    "    <li><a href=\"\" > Use list comprehensions or for loops </a> </li>\n",
    "</ul>\n",
    "</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<details>    \n",
    "<summary>\n",
    "    <font size=\"3\" color=\"darkgreen\"><b>Level 3 Hints</b></font>\n",
    "</summary>\n",
    "<p>\n",
    "<ul>\n",
    "    <li>splits: Use array slicing, like my_str[0:2], to separate a string into two pieces.</li>\n",
    "    <li>Do this in a loop or list comprehension, so that you have a list of tuples.\n",
    "    <li> For example, \"cake\" can get split into \"ca\" and \"ke\". They're stored in a tuple (\"ca\",\"ke\"), and the tuple is appended to a list.  We'll refer to these as L and R, so the tuple is (L,R)</li>\n",
    "    <li>When choosing the range for your loop, if you input the word \"cans\" and generate the tuple  ('cans',''), make sure to include an if statement to check the length of that right-side string (R) in the tuple (L,R) </li>\n",
    "    <li>deletes: Go through the list of tuples and combine the two strings together. You can use the + operator to combine two strings</li>\n",
    "    <li>When combining the tuples, make sure that you leave out a middle character.</li>\n",
    "    <li>Use array slicing to leave out the first character of the right substring.</li>\n",
    "</ul>\n",
    "</p>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [],
   "source": [
    "# UNQ_C4 (UNIQUE CELL IDENTIFIER, DO NOT EDIT)\n",
    "# UNIT TEST COMMENT: Candidate for Table Driven Tests\n",
    "# GRADED FUNCTION: deletes\n",
    "def delete_letter(word, verbose=False):\n",
    "    '''\n",
    "    Input:\n",
    "        word: the string/word for which you will generate all possible words \n",
    "                in the vocabulary which have 1 missing character\n",
    "    Output:\n",
    "        delete_l: a list of all possible strings obtained by deleting 1 character from word\n",
    "    '''\n",
    "    \n",
    "    delete_l = []\n",
    "    split_l = []\n",
    "    \n",
    "    ### START CODE HERE ###\n",
    "    split_l = [(word[:i], word[i:]) for i in range(len(word))]\n",
    "    delete_l = [left_string + right_string[1:] for left_string, right_string in split_l if right_string]\n",
    "    ### END CODE HERE ###\n",
    "\n",
    "    if verbose: print(f\"input word {word}, \\nsplit_l = {split_l}, \\ndelete_l = {delete_l}\")\n",
    "\n",
    "    return delete_l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "input word cans, \n",
      "split_l = [('', 'cans'), ('c', 'ans'), ('ca', 'ns'), ('can', 's')], \n",
      "delete_l = ['ans', 'cns', 'cas', 'can']\n"
     ]
    }
   ],
   "source": [
    "delete_word_l = delete_letter(word=\"cans\",\n",
    "                        verbose=True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Expected Output\n",
    "```CPP\n",
    "Note: You might get a slightly different result with split_l\n",
    "\n",
    "input word cans, \n",
    "split_l = [('', 'cans'), ('c', 'ans'), ('ca', 'ns'), ('can', 's')], \n",
    "delete_l = ['ans', 'cns', 'cas', 'can']\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Note 1\n",
    "- Notice how it has the extra tuple `('cans', '')`.\n",
    "- This will be fine as long as you have checked the size of the right-side substring in tuple (L,R).\n",
    "- Can you explain why this will give you the same result for the list of deletion strings (delete_l)?\n",
    "\n",
    "```CPP\n",
    "input word cans, \n",
    "split_l = [('', 'cans'), ('c', 'ans'), ('ca', 'ns'), ('can', 's'), ('cans', '')], \n",
    "delete_l = ['ans', 'cns', 'cas', 'can']\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Note 2\n",
    "If you end up getting the same word as your input word, like this:\n",
    "\n",
    "```Python\n",
    "input word cans, \n",
    "split_l = [('', 'cans'), ('c', 'ans'), ('ca', 'ns'), ('can', 's'), ('cans', '')], \n",
    "delete_l = ['ans', 'cns', 'cas', 'can', 'cans']\n",
    "```\n",
    "\n",
    "- Check how you set the `range`.\n",
    "- See if you check the length of the string on the right-side of the split."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Number of outputs of delete_letter('at') is 2\n"
     ]
    }
   ],
   "source": [
    "# test # 2\n",
    "print(f\"Number of outputs of delete_letter('at') is {len(delete_letter('at'))}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Expected output\n",
    "\n",
    "```CPP\n",
    "Number of outputs of delete_letter('at') is 2\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<a name='ex-5'></a>\n",
    "### Exercise 5\n",
    "\n",
    "**Instructions for switch_letter()**: Now implement a function that switches two letters in a word. It takes in a word and returns a list of all the possible switches of two letters **that are adjacent to each other**. \n",
    "- For example, given the word 'eta', it returns {'eat', 'tea'}, but does not return 'ate'.\n",
    "\n",
    "**Step 1:** is the same as in delete_letter()  \n",
    "**Step 2:** A list comprehension or for loop which forms strings by swapping adjacent letters. This is of the form:  \n",
    "`[f(L,R) for L, R in splits if condition]`  where 'condition' will test the length of R in a given iteration. See below."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div style=\"width:image width px; font-size:100%; text-align:center;\"><img src='Switches1.PNG' alt=\"alternate text\" width=\"width\" height=\"height\" style=\"width:600px;height:200px;\"/> Figure 5 </div>      "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Levels of difficulty\n",
    "\n",
    "Try this exercise with these levels of difficulty.  \n",
    "- Level 1. Try to think this through and implement this yourself.\n",
    "- Level 2. Click on the \"Level 2 Hints\" section for some hints to get started.\n",
    "- Level 3. If you would prefer more guidance, please click on the \"Level 3 Hints\" cell for step by step instructions."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<details>    \n",
    "<summary>\n",
    "    <font size=\"3\" color=\"darkgreen\"><b>Level 2 Hints</b></font>\n",
    "</summary>\n",
    "<p>\n",
    "<ul>\n",
    "    <li><a href=\"\" > Use array slicing like my_string[0:2] </a> </li>\n",
    "    <li><a href=\"\" > Use list comprehensions or for loops </a> </li>\n",
    "    <li>To do a switch, think of the whole word as divided into 4 distinct parts.  Write out 'cupcakes' on a piece of paper and see how you can split it into ('cupc', 'k', 'a', 'es')</li>\n",
    "</ul>\n",
    "</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<details>    \n",
    "<summary>\n",
    "    <font size=\"3\" color=\"darkgreen\"><b>Level 3 Hints</b></font>\n",
    "</summary>\n",
    "<p>\n",
    "<ul>\n",
    "    <li>splits: Use array slicing, like my_str[0:2], to separate a string into two pieces.</li>\n",
    "    <li>Splitting is the same as for delete_letter</li>\n",
    "    <li>To perform the switch, go through the list of tuples and combine four strings together. You can use the + operator to combine strings</li>\n",
    "    <li>The four strings will be the left substring from the split tuple, followed by the first (index 1) character of the right substring, then the zero-th character (index 0) of the right substring, and then the remaining part of the right substring.</li>\n",
    "    <li>Unlike delete_letter, you will want to check that your right substring is at least a minimum length.  To see why, review the previous hint bullet point (directly before this one).</li>\n",
    "</ul>\n",
    "</p>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [],
   "source": [
    "# UNQ_C5 (UNIQUE CELL IDENTIFIER, DO NOT EDIT)\n",
    "# UNIT TEST COMMENT: Candidate for Table Driven Tests\n",
    "# GRADED FUNCTION: switches\n",
    "def switch_letter(word, verbose=False):\n",
    "    '''\n",
    "    Input:\n",
    "        word: input string\n",
    "     Output:\n",
    "        switches: a list of all possible strings with one adjacent charater switched\n",
    "    ''' \n",
    "    \n",
    "    switch_l = []\n",
    "    split_l = []\n",
    "    \n",
    "    ### START CODE HERE ###\n",
    "    split_l = [(word[:i], word[i:]) for i in range(len(word))]\n",
    "    switch_l = [L + R[1] + R[0] + R[2:] for L, R in split_l if len(R) > 1]\n",
    "    ### END CODE HERE ###\n",
    "    \n",
    "    if verbose: print(f\"Input word = {word} \\nsplit_l = {split_l} \\nswitch_l = {switch_l}\") \n",
    "\n",
    "    return switch_l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Input word = eta \n",
      "split_l = [('', 'eta'), ('e', 'ta'), ('et', 'a')] \n",
      "switch_l = ['tea', 'eat']\n"
     ]
    }
   ],
   "source": [
    "switch_word_l = switch_letter(word=\"eta\",\n",
    "                         verbose=True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Expected output\n",
    "\n",
    "```Python\n",
    "Input word = eta \n",
    "split_l = [('', 'eta'), ('e', 'ta'), ('et', 'a')] \n",
    "switch_l = ['tea', 'eat']\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Note 1\n",
    "\n",
    "You may get this:\n",
    "```Python\n",
    "Input word = eta \n",
    "split_l = [('', 'eta'), ('e', 'ta'), ('et', 'a'), ('eta', '')] \n",
    "switch_l = ['tea', 'eat']\n",
    "```\n",
    "- Notice how it has the extra tuple `('eta', '')`.\n",
    "- This is also correct.\n",
    "- Can you think of why this is the case?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Note 2\n",
    "\n",
    "If you get an error\n",
    "```Python\n",
    "IndexError: string index out of range\n",
    "```\n",
    "- Please see if you have checked the length of the strings when switching characters."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Number of outputs of switch_letter('at') is 1\n"
     ]
    }
   ],
   "source": [
    "# test # 2\n",
    "print(f\"Number of outputs of switch_letter('at') is {len(switch_letter('at'))}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Expected output\n",
    "\n",
    "```CPP\n",
    "Number of outputs of switch_letter('at') is 1\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<a name='ex-6'></a>\n",
    "### Exercise 6\n",
    "**Instructions for replace_letter()**: Now implement a function that takes in a word and returns a list of strings with one **replaced letter** from the original word. \n",
    "\n",
    "**Step 1:** is the same as in `delete_letter()`\n",
    "\n",
    "**Step 2:** A list comprehension or for loop which form strings by replacing letters.  This can be of the form:  \n",
    "`[f(a,b,c) for a, b in splits if condition for c in string]`   Note the use of the second for loop.  \n",
    "It is expected in this routine that one or more of the replacements will include the original word. For example, replacing the first letter of 'ear' with 'e' will return 'ear'.\n",
    "\n",
    "**Step 3:** Remove the original input letter from the output."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<details>    \n",
    "<summary>\n",
    "    <font size=\"3\" color=\"darkgreen\"><b>Hints</b></font>\n",
    "</summary>\n",
    "<p>\n",
    "<ul>\n",
    "    <li>To remove a word from a list, first store its contents inside a set()</li>\n",
    "    <li>Use set.discard('the_word') to remove a word in a set (if the word does not exist in the set, then it will not throw a KeyError.  Using set.remove('the_word') throws a KeyError if the word does not exist in the set. </li>\n",
    "</ul>\n",
    "</p>\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {},
   "outputs": [],
   "source": [
    "# UNQ_C6 (UNIQUE CELL IDENTIFIER, DO NOT EDIT)\n",
    "# UNIT TEST COMMENT: Candidate for Table Driven Tests\n",
    "# GRADED FUNCTION: replaces\n",
    "def replace_letter(word, verbose=False):\n",
    "    '''\n",
    "    Input:\n",
    "        word: the input string/word \n",
    "    Output:\n",
    "        replaces: a list of all possible strings where we replaced one letter from the original word. \n",
    "    ''' \n",
    "    \n",
    "    letters = 'abcdefghijklmnopqrstuvwxyz'\n",
    "    replace_l = []\n",
    "    split_l = []\n",
    "    \n",
    "    ### START CODE HERE ###\n",
    "    split_l = [(word[:i], word[i:]) for i in range(len(word))]\n",
    "    replace_l = [L + C + R[1:] for L, R in split_l for C in letters if len(R) > 0 and C != R[0]]\n",
    "    ### END CODE HERE ###\n",
    "    \n",
    "    # turn the set back into a list and sort it, for easier viewing\n",
    "    replace_l = sorted(replace_l)\n",
    "    \n",
    "    if verbose: print(f\"Input word = {word} \\nsplit_l = {split_l} \\nreplace_l {replace_l}\")   \n",
    "    \n",
    "    return replace_l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Input word = can \n",
      "split_l = [('', 'can'), ('c', 'an'), ('ca', 'n')] \n",
      "replace_l ['aan', 'ban', 'caa', 'cab', 'cac', 'cad', 'cae', 'caf', 'cag', 'cah', 'cai', 'caj', 'cak', 'cal', 'cam', 'cao', 'cap', 'caq', 'car', 'cas', 'cat', 'cau', 'cav', 'caw', 'cax', 'cay', 'caz', 'cbn', 'ccn', 'cdn', 'cen', 'cfn', 'cgn', 'chn', 'cin', 'cjn', 'ckn', 'cln', 'cmn', 'cnn', 'con', 'cpn', 'cqn', 'crn', 'csn', 'ctn', 'cun', 'cvn', 'cwn', 'cxn', 'cyn', 'czn', 'dan', 'ean', 'fan', 'gan', 'han', 'ian', 'jan', 'kan', 'lan', 'man', 'nan', 'oan', 'pan', 'qan', 'ran', 'san', 'tan', 'uan', 'van', 'wan', 'xan', 'yan', 'zan']\n"
     ]
    }
   ],
   "source": [
    "replace_l = replace_letter(word='can',\n",
    "                              verbose=True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Expected Output**: \n",
    "```Python\n",
    "Input word = can \n",
    "split_l = [('', 'can'), ('c', 'an'), ('ca', 'n')] \n",
    "replace_l ['aan', 'ban', 'caa', 'cab', 'cac', 'cad', 'cae', 'caf', 'cag', 'cah', 'cai', 'caj', 'cak', 'cal', 'cam', 'cao', 'cap', 'caq', 'car', 'cas', 'cat', 'cau', 'cav', 'caw', 'cax', 'cay', 'caz', 'cbn', 'ccn', 'cdn', 'cen', 'cfn', 'cgn', 'chn', 'cin', 'cjn', 'ckn', 'cln', 'cmn', 'cnn', 'con', 'cpn', 'cqn', 'crn', 'csn', 'ctn', 'cun', 'cvn', 'cwn', 'cxn', 'cyn', 'czn', 'dan', 'ean', 'fan', 'gan', 'han', 'ian', 'jan', 'kan', 'lan', 'man', 'nan', 'oan', 'pan', 'qan', 'ran', 'san', 'tan', 'uan', 'van', 'wan', 'xan', 'yan', 'zan']\n",
    "```\n",
    "- Note how the input word 'can' should not be one of the output words."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Note 1\n",
    "If you get something like this:\n",
    "\n",
    "```Python\n",
    "Input word = can \n",
    "split_l = [('', 'can'), ('c', 'an'), ('ca', 'n'), ('can', '')] \n",
    "replace_l ['aan', 'ban', 'caa', 'cab', 'cac', 'cad', 'cae', 'caf', 'cag', 'cah', 'cai', 'caj', 'cak', 'cal', 'cam', 'cao', 'cap', 'caq', 'car', 'cas', 'cat', 'cau', 'cav', 'caw', 'cax', 'cay', 'caz', 'cbn', 'ccn', 'cdn', 'cen', 'cfn', 'cgn', 'chn', 'cin', 'cjn', 'ckn', 'cln', 'cmn', 'cnn', 'con', 'cpn', 'cqn', 'crn', 'csn', 'ctn', 'cun', 'cvn', 'cwn', 'cxn', 'cyn', 'czn', 'dan', 'ean', 'fan', 'gan', 'han', 'ian', 'jan', 'kan', 'lan', 'man', 'nan', 'oan', 'pan', 'qan', 'ran', 'san', 'tan', 'uan', 'van', 'wan', 'xan', 'yan', 'zan']\n",
    "```\n",
    "- Notice how split_l has an extra tuple `('can', '')`, but the output is still the same, so this is okay."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Note 2\n",
    "If you get something like this:\n",
    "```Python\n",
    "Input word = can \n",
    "split_l = [('', 'can'), ('c', 'an'), ('ca', 'n'), ('can', '')] \n",
    "replace_l ['aan', 'ban', 'caa', 'cab', 'cac', 'cad', 'cae', 'caf', 'cag', 'cah', 'cai', 'caj', 'cak', 'cal', 'cam', 'cana', 'canb', 'canc', 'cand', 'cane', 'canf', 'cang', 'canh', 'cani', 'canj', 'cank', 'canl', 'canm', 'cann', 'cano', 'canp', 'canq', 'canr', 'cans', 'cant', 'canu', 'canv', 'canw', 'canx', 'cany', 'canz', 'cao', 'cap', 'caq', 'car', 'cas', 'cat', 'cau', 'cav', 'caw', 'cax', 'cay', 'caz', 'cbn', 'ccn', 'cdn', 'cen', 'cfn', 'cgn', 'chn', 'cin', 'cjn', 'ckn', 'cln', 'cmn', 'cnn', 'con', 'cpn', 'cqn', 'crn', 'csn', 'ctn', 'cun', 'cvn', 'cwn', 'cxn', 'cyn', 'czn', 'dan', 'ean', 'fan', 'gan', 'han', 'ian', 'jan', 'kan', 'lan', 'man', 'nan', 'oan', 'pan', 'qan', 'ran', 'san', 'tan', 'uan', 'van', 'wan', 'xan', 'yan', 'zan']\n",
    "```\n",
    "- Notice how there are strings that are 1 letter longer than the original word, such as `cana`.\n",
    "- Please check for the case when there is an empty string `''`, and if so, do not use that empty string when setting replace_l."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Number of outputs of switch_letter('at') is 1\n"
     ]
    }
   ],
   "source": [
    "# test # 2\n",
    "print(f\"Number of outputs of switch_letter('at') is {len(switch_letter('at'))}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Expected output\n",
    "```CPP\n",
    "Number of outputs of switch_letter('at') is 1\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<a name='ex-7'></a>\n",
    "### Exercise 7\n",
    "\n",
    "**Instructions for insert_letter()**: Now implement a function that takes in a word and returns a list with a letter inserted at every offset.\n",
    "\n",
    "**Step 1:** is the same as in `delete_letter()`\n",
    "\n",
    "**Step 2:** This can be a list comprehension of the form:  \n",
    "`[f(a,b,c) for a, b in splits if condition for c in string]`   "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {},
   "outputs": [],
   "source": [
    "# UNQ_C7 (UNIQUE CELL IDENTIFIER, DO NOT EDIT)\n",
    "# UNIT TEST COMMENT: Candidate for Table Driven Tests\n",
    "# GRADED FUNCTION: inserts\n",
    "def insert_letter(word, verbose=False):\n",
    "    '''\n",
    "    Input:\n",
    "        word: the input string/word \n",
    "    Output:\n",
    "        inserts: a set of all possible strings with one new letter inserted at every offset\n",
    "    ''' \n",
    "    letters = 'abcdefghijklmnopqrstuvwxyz'\n",
    "    insert_l = []\n",
    "    split_l = []\n",
    "    \n",
    "    ### START CODE HERE ###\n",
    "    split_l = [(word[:i], word[i:]) for i in range(len(word) + 1)]\n",
    "    insert_l = [L + C + R for L, R in split_l for C in letters]\n",
    "    ### END CODE HERE ###\n",
    "\n",
    "    if verbose: print(f\"Input word {word} \\nsplit_l = {split_l} \\ninsert_l = {insert_l}\")\n",
    "    \n",
    "    return insert_l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Input word at \n",
      "split_l = [('', 'at'), ('a', 't'), ('at', '')] \n",
      "insert_l = ['aat', 'bat', 'cat', 'dat', 'eat', 'fat', 'gat', 'hat', 'iat', 'jat', 'kat', 'lat', 'mat', 'nat', 'oat', 'pat', 'qat', 'rat', 'sat', 'tat', 'uat', 'vat', 'wat', 'xat', 'yat', 'zat', 'aat', 'abt', 'act', 'adt', 'aet', 'aft', 'agt', 'aht', 'ait', 'ajt', 'akt', 'alt', 'amt', 'ant', 'aot', 'apt', 'aqt', 'art', 'ast', 'att', 'aut', 'avt', 'awt', 'axt', 'ayt', 'azt', 'ata', 'atb', 'atc', 'atd', 'ate', 'atf', 'atg', 'ath', 'ati', 'atj', 'atk', 'atl', 'atm', 'atn', 'ato', 'atp', 'atq', 'atr', 'ats', 'att', 'atu', 'atv', 'atw', 'atx', 'aty', 'atz']\n",
      "Number of strings output by insert_letter('at') is 78\n"
     ]
    }
   ],
   "source": [
    "insert_l = insert_letter('at', True)\n",
    "print(f\"Number of strings output by insert_letter('at') is {len(insert_l)}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Expected output\n",
    "\n",
    "```Python\n",
    "Input word at \n",
    "split_l = [('', 'at'), ('a', 't'), ('at', '')] \n",
    "insert_l = ['aat', 'bat', 'cat', 'dat', 'eat', 'fat', 'gat', 'hat', 'iat', 'jat', 'kat', 'lat', 'mat', 'nat', 'oat', 'pat', 'qat', 'rat', 'sat', 'tat', 'uat', 'vat', 'wat', 'xat', 'yat', 'zat', 'aat', 'abt', 'act', 'adt', 'aet', 'aft', 'agt', 'aht', 'ait', 'ajt', 'akt', 'alt', 'amt', 'ant', 'aot', 'apt', 'aqt', 'art', 'ast', 'att', 'aut', 'avt', 'awt', 'axt', 'ayt', 'azt', 'ata', 'atb', 'atc', 'atd', 'ate', 'atf', 'atg', 'ath', 'ati', 'atj', 'atk', 'atl', 'atm', 'atn', 'ato', 'atp', 'atq', 'atr', 'ats', 'att', 'atu', 'atv', 'atw', 'atx', 'aty', 'atz']\n",
    "Number of strings output by insert_letter('at') is 78\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Note 1\n",
    "\n",
    "If you get a split_l like this:\n",
    "```Python\n",
    "Input word at \n",
    "split_l = [('', 'at'), ('a', 't')] \n",
    "insert_l = ['aat', 'bat', 'cat', 'dat', 'eat', 'fat', 'gat', 'hat', 'iat', 'jat', 'kat', 'lat', 'mat', 'nat', 'oat', 'pat', 'qat', 'rat', 'sat', 'tat', 'uat', 'vat', 'wat', 'xat', 'yat', 'zat', 'aat', 'abt', 'act', 'adt', 'aet', 'aft', 'agt', 'aht', 'ait', 'ajt', 'akt', 'alt', 'amt', 'ant', 'aot', 'apt', 'aqt', 'art', 'ast', 'att', 'aut', 'avt', 'awt', 'axt', 'ayt', 'azt']\n",
    "Number of strings output by insert_letter('at') is 52\n",
    "```\n",
    "- Notice that split_l is missing the extra tuple ('at', '').  For insertion, we actually **WANT** this tuple.\n",
    "- The function is not creating all the desired output strings.\n",
    "- Check the range that you use for the for loop."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Note 2\n",
    "If you see this:\n",
    "```Python\n",
    "Input word at \n",
    "split_l = [('', 'at'), ('a', 't'), ('at', '')] \n",
    "insert_l = ['aat', 'bat', 'cat', 'dat', 'eat', 'fat', 'gat', 'hat', 'iat', 'jat', 'kat', 'lat', 'mat', 'nat', 'oat', 'pat', 'qat', 'rat', 'sat', 'tat', 'uat', 'vat', 'wat', 'xat', 'yat', 'zat', 'aat', 'abt', 'act', 'adt', 'aet', 'aft', 'agt', 'aht', 'ait', 'ajt', 'akt', 'alt', 'amt', 'ant', 'aot', 'apt', 'aqt', 'art', 'ast', 'att', 'aut', 'avt', 'awt', 'axt', 'ayt', 'azt']\n",
    "Number of strings output by insert_letter('at') is 52\n",
    "```\n",
    "\n",
    "- Even though you may have fixed the split_l so that it contains the tuple `('at', '')`, notice that you're still missing some output strings.\n",
    "    - Notice that it's missing strings such as 'ata', 'atb', 'atc' all the way to 'atz'.\n",
    "- To fix this, make sure that when you set insert_l, you allow the use of the empty string `''`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Number of outputs of insert_letter('at') is 78\n"
     ]
    }
   ],
   "source": [
    "# test # 2\n",
    "print(f\"Number of outputs of insert_letter('at') is {len(insert_letter('at'))}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Expected output\n",
    "\n",
    "```CPP\n",
    "Number of outputs of insert_letter('at') is 78\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<a name='3'></a>\n",
    "\n",
    "# Part 3: Combining the edits\n",
    "\n",
    "Now that you have implemented the string manipulations, you will create two functions that, given a string, will return all the possible single and double edits on that string. These will be `edit_one_letter()` and `edit_two_letters()`."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<a name='3-1'></a>\n",
    "## 3.1 Edit one letter\n",
    "\n",
    "<a name='ex-8'></a>\n",
    "### Exercise 8\n",
    "\n",
    "**Instructions**: Implement the `edit_one_letter` function to get all the possible edits that are one edit away from a word. The edits  consist of the replace, insert, delete, and optionally the switch operation. You should use the previous functions you have already implemented to complete this function. The 'switch' function  is a less common edit function, so its use will be selected by an \"allow_switches\" input argument.\n",
    "\n",
    "Note that those functions return *lists* while this function should return a *python set*. Utilizing a set eliminates any duplicate entries."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<details>    \n",
    "<summary>\n",
    "    <font size=\"3\" color=\"darkgreen\"><b>Hints</b></font>\n",
    "</summary>\n",
    "<p>\n",
    "<ul>\n",
    "    <li> Each of the functions returns a list.  You can combine lists using the `+` operator. </li>\n",
    "    <li> To get unique strings (avoid duplicates), you can use the set() function. </li>\n",
    "</ul>\n",
    "</p>\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 61,
   "metadata": {},
   "outputs": [],
   "source": [
    "# UNQ_C8 (UNIQUE CELL IDENTIFIER, DO NOT EDIT)\n",
    "# UNIT TEST COMMENT: Candidate for Table Driven Tests\n",
    "# GRADED FUNCTION: edit_one_letter\n",
    "def edit_one_letter(word, allow_switches = True):\n",
    "    \"\"\"\n",
    "    Input:\n",
    "        word: the string/word for which we will generate all possible wordsthat are one edit away.\n",
    "    Output:\n",
    "        edit_one_set: a set of words with one possible edit. Please return a set. and not a list.\n",
    "    \"\"\"\n",
    "    \n",
    "    edit_one_set = set()\n",
    "    \n",
    "    ### START CODE HERE ###\n",
    "    all_edits = delete_letter(word) + replace_letter(word) + insert_letter(word) \n",
    "    if allow_switches:\n",
    "        all_edits = all_edits + switch_letter(word)\n",
    "    for edit in all_edits:\n",
    "        edit_one_set.add(edit)\n",
    "    ### END CODE HERE ###\n",
    "\n",
    "    return edit_one_set"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 63,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "input word at \n",
      "edit_one_l \n",
      "['a', 'aa', 'aat', 'ab', 'abt', 'ac', 'act', 'ad', 'adt', 'ae', 'aet', 'af', 'aft', 'ag', 'agt', 'ah', 'aht', 'ai', 'ait', 'aj', 'ajt', 'ak', 'akt', 'al', 'alt', 'am', 'amt', 'an', 'ant', 'ao', 'aot', 'ap', 'apt', 'aq', 'aqt', 'ar', 'art', 'as', 'ast', 'ata', 'atb', 'atc', 'atd', 'ate', 'atf', 'atg', 'ath', 'ati', 'atj', 'atk', 'atl', 'atm', 'atn', 'ato', 'atp', 'atq', 'atr', 'ats', 'att', 'atu', 'atv', 'atw', 'atx', 'aty', 'atz', 'au', 'aut', 'av', 'avt', 'aw', 'awt', 'ax', 'axt', 'ay', 'ayt', 'az', 'azt', 'bat', 'bt', 'cat', 'ct', 'dat', 'dt', 'eat', 'et', 'fat', 'ft', 'gat', 'gt', 'hat', 'ht', 'iat', 'it', 'jat', 'jt', 'kat', 'kt', 'lat', 'lt', 'mat', 'mt', 'nat', 'nt', 'oat', 'ot', 'pat', 'pt', 'qat', 'qt', 'rat', 'rt', 'sat', 'st', 't', 'ta', 'tat', 'tt', 'uat', 'ut', 'vat', 'vt', 'wat', 'wt', 'xat', 'xt', 'yat', 'yt', 'zat', 'zt']\n",
      "\n",
      "The type of the returned object should be a set <class 'set'>\n",
      "Number of outputs from edit_one_letter('at') is 129\n"
     ]
    }
   ],
   "source": [
    "tmp_word = \"at\"\n",
    "tmp_edit_one_set = edit_one_letter(tmp_word)\n",
    "# turn this into a list to sort it, in order to view it\n",
    "tmp_edit_one_l = sorted(list(tmp_edit_one_set))\n",
    "\n",
    "print(f\"input word {tmp_word} \\nedit_one_l \\n{tmp_edit_one_l}\\n\")\n",
    "print(f\"The type of the returned object should be a set {type(tmp_edit_one_set)}\")\n",
    "print(f\"Number of outputs from edit_one_letter('at') is {len(edit_one_letter('at'))}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Expected Output\n",
    "```CPP\n",
    "input word at \n",
    "edit_one_l \n",
    "['a', 'aa', 'aat', 'ab', 'abt', 'ac', 'act', 'ad', 'adt', 'ae', 'aet', 'af', 'aft', 'ag', 'agt', 'ah', 'aht', 'ai', 'ait', 'aj', 'ajt', 'ak', 'akt', 'al', 'alt', 'am', 'amt', 'an', 'ant', 'ao', 'aot', 'ap', 'apt', 'aq', 'aqt', 'ar', 'art', 'as', 'ast', 'ata', 'atb', 'atc', 'atd', 'ate', 'atf', 'atg', 'ath', 'ati', 'atj', 'atk', 'atl', 'atm', 'atn', 'ato', 'atp', 'atq', 'atr', 'ats', 'att', 'atu', 'atv', 'atw', 'atx', 'aty', 'atz', 'au', 'aut', 'av', 'avt', 'aw', 'awt', 'ax', 'axt', 'ay', 'ayt', 'az', 'azt', 'bat', 'bt', 'cat', 'ct', 'dat', 'dt', 'eat', 'et', 'fat', 'ft', 'gat', 'gt', 'hat', 'ht', 'iat', 'it', 'jat', 'jt', 'kat', 'kt', 'lat', 'lt', 'mat', 'mt', 'nat', 'nt', 'oat', 'ot', 'pat', 'pt', 'qat', 'qt', 'rat', 'rt', 'sat', 'st', 't', 'ta', 'tat', 'tt', 'uat', 'ut', 'vat', 'vt', 'wat', 'wt', 'xat', 'xt', 'yat', 'yt', 'zat', 'zt']\n",
    "\n",
    "The type of the returned object should be a set <class 'set'>\n",
    "Number of outputs from edit_one_letter('at') is 129\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<a name='3-2'></a>\n",
    "## Part 3.2 Edit two letters\n",
    "\n",
    "<a name='ex-9'></a>\n",
    "### Exercise 9\n",
    "\n",
    "Now you can generalize this to implement to get two edits on a word. To do so, you would have to get all the possible edits on a single word and then for each modified word, you would have to modify it again. \n",
    "\n",
    "**Instructions**: Implement the `edit_two_letters` function that returns a set of words that are two edits away. Note that creating additional edits based on the `edit_one_letter` function may 'restore' some one_edits to zero or one edits. That is allowed here. This accounted for in get_corrections."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<details>    \n",
    "<summary>\n",
    "    <font size=\"3\" color=\"darkgreen\"><b>Hints</b></font>\n",
    "</summary>\n",
    "<p>\n",
    "<ul>\n",
    "    <li>You will likely want to take the union of two sets.</li>\n",
    "    <li>You can either use set.union() or use the '|' (or operator) to union two sets</li>\n",
    "    <li>See the documentation <a href=\"https://docs.python.org/2/library/sets.html\" > Python sets </a> for examples of using operators or functions of the Python set.</li>\n",
    "</ul>\n",
    "</p>\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 72,
   "metadata": {},
   "outputs": [],
   "source": [
    "# UNQ_C9 (UNIQUE CELL IDENTIFIER, DO NOT EDIT)\n",
    "# UNIT TEST COMMENT: Candidate for Table Driven Tests\n",
    "# GRADED FUNCTION: edit_two_letters\n",
    "def edit_two_letters(word, allow_switches = True):\n",
    "    '''\n",
    "    Input:\n",
    "        word: the input string/word \n",
    "    Output:\n",
    "        edit_two_set: a set of strings with all possible two edits\n",
    "    '''\n",
    "    \n",
    "    edit_two_set = set()\n",
    "    \n",
    "    ### START CODE HERE ###\n",
    "    one_edits = edit_one_letter(word, allow_switches)\n",
    "    for edit in one_edits:\n",
    "        edit_of_edit = edit_one_letter(edit, allow_switches)\n",
    "        if edit_of_edit is not None:\n",
    "            edit_two_set = edit_two_set.union(edit_of_edit)\n",
    "        \n",
    "    ### END CODE HERE ###\n",
    "    \n",
    "    return edit_two_set"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 73,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Number of strings with edit distance of two: 2654\n",
      "First 10 strings ['', 'a', 'aa', 'aaa', 'aab', 'aac', 'aad', 'aae', 'aaf', 'aag']\n",
      "Last 10 strings ['zv', 'zva', 'zw', 'zwa', 'zx', 'zxa', 'zy', 'zya', 'zz', 'zza']\n",
      "The data type of the returned object should be a set <class 'set'>\n",
      "Number of strings that are 2 edit distances from 'at' is 7154\n"
     ]
    }
   ],
   "source": [
    "tmp_edit_two_set = edit_two_letters(\"a\")\n",
    "tmp_edit_two_l = sorted(list(tmp_edit_two_set))\n",
    "print(f\"Number of strings with edit distance of two: {len(tmp_edit_two_l)}\")\n",
    "print(f\"First 10 strings {tmp_edit_two_l[:10]}\")\n",
    "print(f\"Last 10 strings {tmp_edit_two_l[-10:]}\")\n",
    "print(f\"The data type of the returned object should be a set {type(tmp_edit_two_set)}\")\n",
    "print(f\"Number of strings that are 2 edit distances from 'at' is {len(edit_two_letters('at'))}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Expected Output\n",
    "\n",
    "```CPP\n",
    "Number of strings with edit distance of two: 2654\n",
    "First 10 strings ['', 'a', 'aa', 'aaa', 'aab', 'aac', 'aad', 'aae', 'aaf', 'aag']\n",
    "Last 10 strings ['zv', 'zva', 'zw', 'zwa', 'zx', 'zxa', 'zy', 'zya', 'zz', 'zza']\n",
    "The data type of the returned object should be a set <class 'set'>\n",
    "Number of strings that are 2 edit distances from 'at' is 7154\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<a name='3-3'></a>\n",
    "## Part 3-3: suggest spelling suggestions\n",
    "\n",
    "Now you will use your `edit_two_letters` function to get a set of all the possible 2 edits on your word. You will then use those strings to get the most probable word you meant to type aka your typing suggestion.\n",
    "\n",
    "<a name='ex-10'></a>\n",
    "### Exercise 10\n",
    "**Instructions**: Implement `get_corrections`, which returns a list of zero to n possible suggestion tuples of the form (word, probability_of_word). \n",
    "\n",
    "**Step 1:** Generate suggestions for a supplied word: You'll use the edit functions you have developed. The 'suggestion algorithm' should follow this logic: \n",
    "* If the word is in the vocabulary, suggest the word. \n",
    "* Otherwise, if there are suggestions from `edit_one_letter` that are in the vocabulary, use those. \n",
    "* Otherwise, if there are suggestions from `edit_two_letters` that are in the vocabulary, use those. \n",
    "* Otherwise, suggest the input word.*  \n",
    "* The idea is that words generated from fewer edits are more likely than words with more edits.\n",
    "\n",
    "\n",
    "Note: \n",
    "- Edits of one or two letters may 'restore' strings to either zero or one edit. This algorithm accounts for this by preferentially selecting lower distance edits first."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Short circuit\n",
    "In Python, logical operations such as `and` and `or` have two useful properties. They can operate on lists and they have ['short-circuit' behavior](https://docs.python.org/3/library/stdtypes.html). Try these:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 74,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[]\n",
      "['a', 'b']\n",
      "['Most', 'Likely']\n",
      "['least', 'of', 'all']\n"
     ]
    }
   ],
   "source": [
    "# example of logical operation on lists or sets\n",
    "print( [] and [\"a\",\"b\"] )\n",
    "print( [] or [\"a\",\"b\"] )\n",
    "#example of Short circuit behavior\n",
    "val1 =  [\"Most\",\"Likely\"] or [\"Less\",\"so\"] or [\"least\",\"of\",\"all\"]  # selects first, does not evalute remainder\n",
    "print(val1)\n",
    "val2 =  [] or [] or [\"least\",\"of\",\"all\"] # continues evaluation until there is a non-empty list\n",
    "print(val2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The logical `or` could be used to implement the suggestion algorithm very compactly. Alternately, if/then constructs could be used.\n",
    " \n",
    "**Step 2**: Create a 'best_words' dictionary where the 'key' is a suggestion and the 'value' is the probability of that word in your vocabulary. If the word is not in the vocabulary, assign it a probability of 0.\n",
    "\n",
    "**Step 3**: Select the n best suggestions. There may be fewer than n."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<details>    \n",
    "<summary>\n",
    "    <font size=\"3\" color=\"darkgreen\"><b>Hints</b></font>\n",
    "</summary>\n",
    "<p>\n",
    "<ul>\n",
    "    <li>edit_one_letter and edit_two_letters return *python sets*. </li>\n",
    "    <li> Sets have a handy <a href=\"https://docs.python.org/2/library/sets.html\" > set.intersection </a> feature</li>\n",
    "    <li>To find the keys that have the highest values in a dictionary, you can use the Counter dictionary to create a Counter object from a regular dictionary.  Then you can use Counter.most_common(n) to get the n most common keys.\n",
    "    </li>\n",
    "    <li>To find the intersection of two sets, you can use set.intersection or the & operator.</li>\n",
    "    <li>If you are not as familiar with short circuit syntax (as shown above), feel free to use if else statements instead.</li>\n",
    "    <li>To use an if statement to check of a set is empty, use 'if not x:' syntax </li>\n",
    "</ul>\n",
    "</p>\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 93,
   "metadata": {},
   "outputs": [],
   "source": [
    "# UNQ_C10 (UNIQUE CELL IDENTIFIER, DO NOT EDIT)\n",
    "# UNIT TEST COMMENT: Candidate for Table Driven Tests\n",
    "# GRADED FUNCTION: get_corrections\n",
    "def get_corrections(word, probs, vocab, n=2, verbose = False):\n",
    "    '''\n",
    "    Input: \n",
    "        word: a user entered string to check for suggestions\n",
    "        probs: a dictionary that maps each word to its probability in the corpus\n",
    "        vocab: a set containing all the vocabulary\n",
    "        n: number of possible word corrections you want returned in the dictionary\n",
    "    Output: \n",
    "        n_best: a list of tuples with the most probable n corrected words and their probabilities.\n",
    "    '''\n",
    "    \n",
    "    suggestions = []\n",
    "    n_best = []\n",
    "    \n",
    "    ### START CODE HERE ###\n",
    "    if word in probs:\n",
    "        return (word, probs.get(word, 0))\n",
    "    \n",
    "    possible_edits = edit_one_letter(word) or edit_two_letters(word)\n",
    "    suggestions = vocab.intersection(possible_edits)\n",
    "    \n",
    "    for edit in suggestions:\n",
    "        n_best.append((edit, probs.get(edit, 0)))\n",
    "    \n",
    "    n_best = sorted(n_best, key = lambda x: x[1], reverse = True)\n",
    "    ### END CODE HERE ###\n",
    "    if verbose: print(\"entered word = \", word, \"\\nsuggestions = \", suggestions)\n",
    "\n",
    "    return n_best[:n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 94,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "entered word =  dys \n",
      "suggestions =  {'dye', 'days'}\n",
      "word 0: days, probability 0.000410\n",
      "word 1: dye, probability 0.000019\n",
      "data type of corrections <class 'list'>\n"
     ]
    }
   ],
   "source": [
    "# Test your implementation - feel free to try other words in my word\n",
    "my_word = 'dys' \n",
    "tmp_corrections = get_corrections(my_word, probs, vocab, 2, verbose=True) # keep verbose=True\n",
    "for i, word_prob in enumerate(tmp_corrections):\n",
    "    print(f\"word {i}: {word_prob[0]}, probability {word_prob[1]:.6f}\")\n",
    "\n",
    "# CODE REVIEW COMMENT: using \"tmp_corrections\" insteads of \"cors\". \"cors\" is not defined\n",
    "print(f\"data type of corrections {type(tmp_corrections)}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Expected Output\n",
    "- Note: This expected output is for `my_word = 'dys'`. Also, keep `verbose=True`\n",
    "```CPP\n",
    "entered word =  dys \n",
    "suggestions =  {'days', 'dye'}\n",
    "word 0: days, probability 0.000410\n",
    "word 1: dye, probability 0.000019\n",
    "data type of corrections <class 'list'>\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<a name='4'></a>\n",
    "# Part 4: Minimum Edit distance\n",
    "\n",
    "Now that you have implemented your auto-correct, how do you evaluate the similarity between two strings? For example: 'waht' and 'what'\n",
    "\n",
    "Also how do you efficiently find the shortest path to go from the word, 'waht' to the word 'what'?\n",
    "\n",
    "You will implement a dynamic programming system that will tell you the minimum number of edits required to convert a string into another string."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<a name='4-1'></a>\n",
    "### Part 4.1 Dynamic Programming\n",
    "\n",
    "Dynamic Programming breaks a problem down into subproblems which can be combined to form the final solution. Here, given a string source[0..i] and a string target[0..j], we will compute all the combinations of substrings[i, j] and calculate their edit distance. To do this efficiently, we will use a table to maintain the previously computed substrings and use those to calculate larger substrings.\n",
    "\n",
    "You have to create a matrix and update each element in the matrix as follows:  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\\text{Initialization}$$\n",
    "\n",
    "\\begin{align}\n",
    "D[0,0] &= 0 \\\\\n",
    "D[i,0] &= D[i-1,0] + del\\_cost(source[i]) \\tag{4}\\\\\n",
    "D[0,j] &= D[0,j-1] + ins\\_cost(target[j]) \\\\\n",
    "\\end{align}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "$$\\text{Per Cell Operations}$$\n",
    "\\begin{align}\n",
    " \\\\\n",
    "D[i,j] =min\n",
    "\\begin{cases}\n",
    "D[i-1,j] + del\\_cost\\\\\n",
    "D[i,j-1] + ins\\_cost\\\\\n",
    "D[i-1,j-1] + \\left\\{\\begin{matrix}\n",
    "rep\\_cost; & if src[i]\\neq tar[j]\\\\\n",
    "0 ; & if src[i]=tar[j]\n",
    "\\end{matrix}\\right.\n",
    "\\end{cases}\n",
    "\\tag{5}\n",
    "\\end{align}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "So converting the source word **play** to the target word **stay**, using an input cost of one, a delete cost of 1, and replace cost of 2 would give you the following table:\n",
    "<table style=\"width:20%\">\n",
    "\n",
    "  <tr>\n",
    "    <td> <b> </b>  </td>\n",
    "    <td> <b># </b>  </td>\n",
    "    <td> <b>s </b>  </td>\n",
    "    <td> <b>t </b> </td> \n",
    "    <td> <b>a </b> </td> \n",
    "    <td> <b>y </b> </td> \n",
    "  </tr>\n",
    "   <tr>\n",
    "    <td> <b>  #  </b></td>\n",
    "    <td> 0</td> \n",
    "    <td> 1</td> \n",
    "    <td> 2</td> \n",
    "    <td> 3</td> \n",
    "    <td> 4</td> \n",
    " \n",
    "  </tr>\n",
    "  <tr>\n",
    "    <td> <b>  p  </b></td>\n",
    "    <td> 1</td> \n",
    " <td> 2</td> \n",
    "    <td> 3</td> \n",
    "    <td> 4</td> \n",
    "   <td> 5</td>\n",
    "  </tr>\n",
    "   \n",
    "  <tr>\n",
    "    <td> <b> l </b></td>\n",
    "    <td>2</td> \n",
    "    <td>3</td> \n",
    "    <td>4</td> \n",
    "    <td>5</td> \n",
    "    <td>6</td>\n",
    "  </tr>\n",
    "\n",
    "  <tr>\n",
    "    <td> <b> a </b></td>\n",
    "    <td>3</td> \n",
    "     <td>4</td> \n",
    "     <td>5</td> \n",
    "     <td>4</td>\n",
    "     <td>5</td> \n",
    "  </tr>\n",
    "  \n",
    "   <tr>\n",
    "    <td> <b> y </b></td>\n",
    "    <td>4</td> \n",
    "      <td>5</td> \n",
    "     <td>6</td> \n",
    "     <td>5</td>\n",
    "     <td>4</td> \n",
    "  </tr>\n",
    "  \n",
    "\n",
    "</table>\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The operations used in this algorithm are 'insert', 'delete', and 'replace'. These correspond to the functions that you defined earlier: insert_letter(), delete_letter() and replace_letter(). switch_letter() is not used here."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The diagram below describes how to initialize the table. Each entry in D[i,j] represents the minimum cost of converting string source[0:i] to string target[0:j]. The first column is initialized to represent the cumulative cost of deleting the source characters to convert string \"EER\" to \"\". The first row is initialized to represent the cumulative cost of inserting the target characters to convert from \"\" to \"NEAR\"."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div style=\"width:image width px; font-size:100%; text-align:center;\"><img src='EditDistInit4.PNG' alt=\"alternate text\" width=\"width\" height=\"height\" style=\"width:1000px;height:400px;\"/> Figure 6 Initializing Distance Matrix</div>     "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Filling in the remainder of the table utilizes the 'Per Cell Operations' in the equation (5) above. Note, the diagram below includes in the table some of the 3 sub-calculations shown in light grey. Only 'min' of those operations is stored in the table in the `min_edit_distance()` function."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div style=\"width:image width px; font-size:100%; text-align:center;\"><img src='EditDistFill2.PNG' alt=\"alternate text\" width=\"width\" height=\"height\" style=\"width:800px;height:400px;\"/> Figure 7 Filling Distance Matrix</div>     "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Note that the formula for $D[i,j]$ shown in the image is equivalent to:\n",
    "\n",
    "\\begin{align}\n",
    " \\\\\n",
    "D[i,j] =min\n",
    "\\begin{cases}\n",
    "D[i-1,j] + del\\_cost\\\\\n",
    "D[i,j-1] + ins\\_cost\\\\\n",
    "D[i-1,j-1] + \\left\\{\\begin{matrix}\n",
    "rep\\_cost; & if src[i]\\neq tar[j]\\\\\n",
    "0 ; & if src[i]=tar[j]\n",
    "\\end{matrix}\\right.\n",
    "\\end{cases}\n",
    "\\tag{5}\n",
    "\\end{align}\n",
    "\n",
    "The variable `sub_cost` (for substitution cost) is the same as `rep_cost`; replacement cost.  We will stick with the term \"replace\" whenever possible."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Below are some examples of cells where replacement is used. This also shows the minimum path from the lower right final position where \"EER\" has been replaced by \"NEAR\" back to the start. This provides a starting point for the optional 'backtrace' algorithm below."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div style=\"width:image width px; font-size:100%; text-align:center;\"><img src='EditDistExample1.PNG' alt=\"alternate text\" width=\"width\" height=\"height\" style=\"width:1200px;height:400px;\"/> Figure 8 Examples Distance Matrix</div>    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<a name='ex-11'></a>\n",
    "### Exercise 11\n",
    "\n",
    "Again, the word \"substitution\" appears in the figure, but think of this as \"replacement\"."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Instructions**: Implement the function below to get the minimum amount of edits required given a source string and a target string. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<details>    \n",
    "<summary>\n",
    "    <font size=\"3\" color=\"darkgreen\"><b>Hints</b></font>\n",
    "</summary>\n",
    "<p>\n",
    "<ul>\n",
    "    <li>The range(start, stop, step) function excludes 'stop' from its output</li>\n",
    "    <li><a href=\"\" > words </a> </li>\n",
    "</ul>\n",
    "</p>\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 97,
   "metadata": {},
   "outputs": [],
   "source": [
    "# UNQ_C11 (UNIQUE CELL IDENTIFIER, DO NOT EDIT)\n",
    "# GRADED FUNCTION: min_edit_distance\n",
    "def min_edit_distance(source, target, ins_cost = 1, del_cost = 1, rep_cost = 2):\n",
    "    '''\n",
    "    Input: \n",
    "        source: a string corresponding to the string you are starting with\n",
    "        target: a string corresponding to the string you want to end with\n",
    "        ins_cost: an integer setting the insert cost\n",
    "        del_cost: an integer setting the delete cost\n",
    "        rep_cost: an integer setting the replace cost\n",
    "    Output:\n",
    "        D: a matrix of len(source) + 1 by len(target) + 1 containing minimum edit distances\n",
    "        med: the minimum edit distance (med) required to convert the source string to the target\n",
    "    '''\n",
    "    # use deletion and insert cost as  1\n",
    "    m = len(source) \n",
    "    n = len(target) \n",
    "    # initialize cost matrix with zeros and dimensions (m+1,n+1) \n",
    "    D = np.zeros((m + 1, n + 1), dtype = int) \n",
    "    \n",
    "    ### START CODE HERE (Replace instances of 'None' with your code) ###\n",
    "    \n",
    "    # Fill in column 0, from row 1 to row m, both inclusive\n",
    "    for row in range(1, m + 1): # Replace None with the proper range\n",
    "        D[row, 0] = D[row - 1, 0] + del_cost\n",
    "        \n",
    "    # Fill in row 0, for all columns from 1 to n, both inclusive\n",
    "    for col in range(1, n + 1): # Replace None with the proper range\n",
    "        D[0, col] = D[0, col - 1] + ins_cost\n",
    "        \n",
    "    # Loop through row 1 to row m, both inclusive\n",
    "    for row in range(1, m + 1): \n",
    "        \n",
    "        # Loop through column 1 to column n, both inclusive\n",
    "        for col in range(1, n + 1):\n",
    "            \n",
    "            # Intialize r_cost to the 'replace' cost that is passed into this function\n",
    "            r_cost = rep_cost\n",
    "            \n",
    "            # Check to see if source character at the previous row\n",
    "            # matches the target character at the previous column, \n",
    "            if source[row - 1] == target[col - 1]:\n",
    "                # Update the replacement cost to 0 if source and target are the same\n",
    "                r_cost = 0\n",
    "                \n",
    "            # Update the cost at row, col based on previous entries in the cost matrix\n",
    "            # Refer to the equation calculate for D[i,j] (the minimum of three calculated costs)\n",
    "            D[row, col] = min(D[row - 1, col] + del_cost, D[row, col - 1] + ins_cost, D[row - 1, col - 1] + r_cost)\n",
    "          \n",
    "    # Set the minimum edit distance with the cost found at row m, column n\n",
    "    med = D[m, n]\n",
    "    \n",
    "    ### END CODE HERE ###\n",
    "    return D, med"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 98,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "minimum edits:  4 \n",
      "\n",
      "   #  s  t  a  y\n",
      "#  0  1  2  3  4\n",
      "p  1  2  3  4  5\n",
      "l  2  3  4  5  6\n",
      "a  3  4  5  4  5\n",
      "y  4  5  6  5  4\n"
     ]
    }
   ],
   "source": [
    "#DO NOT MODIFY THIS CELL\n",
    "# testing your implementation \n",
    "source =  'play'\n",
    "target = 'stay'\n",
    "matrix, min_edits = min_edit_distance(source, target)\n",
    "print(\"minimum edits: \",min_edits, \"\\n\")\n",
    "idx = list('#' + source)\n",
    "cols = list('#' + target)\n",
    "df = pd.DataFrame(matrix, index=idx, columns= cols)\n",
    "print(df)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Expected Results:**  \n",
    "\n",
    "```CPP\n",
    "minimum edits:  4\n",
    "    \n",
    "   #  s  t  a  y\n",
    "#  0  1  2  3  4\n",
    "p  1  2  3  4  5\n",
    "l  2  3  4  5  6\n",
    "a  3  4  5  4  5\n",
    "y  4  5  6  5  4\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 99,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "minimum edits:  3 \n",
      "\n",
      "   #  n  e  a  r\n",
      "#  0  1  2  3  4\n",
      "e  1  2  1  2  3\n",
      "e  2  3  2  3  4\n",
      "r  3  4  3  4  3\n"
     ]
    }
   ],
   "source": [
    "#DO NOT MODIFY THIS CELL\n",
    "# testing your implementation \n",
    "source =  'eer'\n",
    "target = 'near'\n",
    "matrix, min_edits = min_edit_distance(source, target)\n",
    "print(\"minimum edits: \",min_edits, \"\\n\")\n",
    "idx = list(source)\n",
    "idx.insert(0, '#')\n",
    "cols = list(target)\n",
    "cols.insert(0, '#')\n",
    "df = pd.DataFrame(matrix, index=idx, columns= cols)\n",
    "print(df)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Expected Results**  \n",
    "```CPP\n",
    "minimum edits:  3 \n",
    "\n",
    "   #  n  e  a  r\n",
    "#  0  1  2  3  4\n",
    "e  1  2  1  2  3\n",
    "e  2  3  2  3  4\n",
    "r  3  4  3  4  3\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can now test several of our routines at once:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 100,
   "metadata": {},
   "outputs": [],
   "source": [
    "source = \"eer\"\n",
    "targets = edit_one_letter(source,allow_switches = False)  #disable switches since min_edit_distance does not include them\n",
    "for t in targets:\n",
    "    _, min_edits = min_edit_distance(source, t,1,1,1)  # set ins, del, sub costs all to one\n",
    "    if min_edits != 1: print(source, t, min_edits)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Expected Results**  \n",
    "```CPP\n",
    "(empty)\n",
    "```\n",
    "\n",
    "The 'replace()' routine utilizes all letters a-z one of which returns the original word."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 101,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "eer eer 0\n"
     ]
    }
   ],
   "source": [
    "source = \"eer\"\n",
    "targets = edit_two_letters(source,allow_switches = False) #disable switches since min_edit_distance does not include them\n",
    "for t in targets:\n",
    "    _, min_edits = min_edit_distance(source, t,1,1,1)  # set ins, del, sub costs all to one\n",
    "    if min_edits != 2 and min_edits != 1: print(source, t, min_edits)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Expected Results**  \n",
    "```CPP\n",
    "eer eer 0\n",
    "```\n",
    "\n",
    "We have to allow single edits here because some two_edits will restore a single edit."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Submission\n",
    "Make sure you submit your assignment before you modify anything below\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<a name='5'></a>\n",
    "\n",
    "# Part 5: Optional - Backtrace\n",
    "\n",
    "\n",
    "Once you have computed your matrix using minimum edit distance, how would find the shortest path from the top left corner to the bottom right corner? \n",
    "\n",
    "Note that you could use backtrace algorithm.  Try to find the shortest path given the matrix that your `min_edit_distance` function returned.\n",
    "\n",
    "You can use these [lecture slides on minimum edit distance](https://web.stanford.edu/class/cs124/lec/med.pdf) by Dan Jurafsky to learn about the algorithm for backtrace."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Experiment with back trace - insert your code here\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### References\n",
    "- Dan Jurafsky - Speech and Language Processing - Textbook\n",
    "- This auto-correct explanation was first done by Peter Norvig in 2007 "
   ]
  }
 ],
 "metadata": {
  "coursera": {
   "schema_names": [
    "NLPC2-1"
   ]
  },
  "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.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}