Problem 7 (300pts): minimum_mewtations

Implement minimum_mewtations, which is a diff function that returns the minimum number of edit operations needed to transform the typed word into the source word.

There are three kinds of edit operations:

  1. Add a letter to typed.
    • Adding "t" to "kiten" gives us "kitten".
  2. Remove a letter from typed.
    • Removing "t" from "catts" gives us "cats".
  3. Substitute a letter in typed for another.
    • Substituting "a" with "o" in "baok" gives us "book".

Each edit operation contributes 1 to the difference between two words.

>>> big_limit = 10
>>> minimum_mewtations("cats", "scat", big_limit)       # cats -> scats -> scat
2
>>> minimum_mewtations("purng", "purring", big_limit)   # purng -> purrng -> purring
2
>>> minimum_mewtations("ckiteus", "kittens", big_limit) # ckiteus -> kiteus -> kitteus -> kittens
3

We have provided a template of an implementation in cats.py.

Hint: This is a recursive function with three recursive calls. One of these recursive calls will be similar to the recursive call in sphinx_fixes if you implemented sphinx_fixes with recursion.

You may modify the template however you want or delete it entirely.

Important: If the number of edits required is greater than limit, then minimum_mewtations should return any number larger than limit and should minimize the amount of computation needed to do so.

These two calls to minimum_mewtations should take about the same amount of time to evaluate:

>>> limit = 2
>>> minimum_mewtations("ckiteus", "kittens", limit) > limit
True
>>> minimum_mewtations("ckiteusabcdefghijklm", "kittensnopqrstuvwxyz", limit) > limit
True

Before writing any code, unlock the tests to verify your understanding of the question:

$ python ok -q 07 -u

Once you are done unlocking, begin implementing your solution. You can check your correctness with:

$ python ok -q 07

Try typing again. Are the corrections more accurate?

$ python cats_gui.py