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 start word into the goal word.

There are three kinds of edit operations:

  1. Add a letter to start.
    • Adding "k" to "itten" gives us "kitten".
  2. Remove a letter from start.
    • Removing "s" from "scat" gives up "cat".
  3. Substitute a letter in start for another.
    • Substituting "z" with "j" in "zaguar" gives us "jaguar".

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.

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:

$ python3 ok -q 07 -u

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

$ python3 ok -q 07

Try typing again. Are the corrections more accurate?

$ python3 cats_gui.py