Problem 7 (300pts): feline_fixes

Implement feline_fixes, 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,
  2. Remove a letter from start,
  3. Substitute a letter in start for another.

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

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

We have provided a template of an implementation in cats.py. This is a recursive function with three recursive calls. One of these recursive calls will be similar to the recursive call in sphinx_swap.

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

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

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

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

You can test your implementation with this. 

# Test your implementation
python ok -q 07

Try typing again. Are the corrections more accurate?

python gui.py

Extensions: You may optionally design your own diff function called final_diff. Here are some ideas for making even more accurate corrections:

  • Take into account which additions and deletions are more likely than others. For example, it's much more likely that you'll accidentally leave out a letter if it appears twice in a row.
  • Treat two adjacent letters that have swapped positions as one change, not two.
  • Try to incorporate common misspellings