Problem 5 (200pts): autocorrect

Implement autocorrect, which takes a typed_word, a list of all word_list, a diff_function, and a limit.

If the typed_word is contained inside the word_list list, autocorrect returns that word.

Otherwise, autocorrect returns the word from word_list that has the lowest difference from the provided typed_word based on the diff_function. However, if the lowest difference between typed_word and any of the word_list is greater than limit, then typed_word is returned instead.

Important: If typed_word is not contained inside word_list, and multiple strings have the same lowest difference from typed_word according to diff_function, autocorrect should return the string that appears first in word_list.

A diff function takes in three arguments. The first is the typed_word, the second is the source word (in this case, a word from word_list), and the third argument is the limit. The output of the diff function, which is a number, represents the amount of difference between the two strings.

Note: Some diff functions may be asymmetric (meaning flipping the first two parameters may yield a different output), so make sure to pass in the arguments to diff_function in the correct order. We will see an example of an asymmetric diff function in problem 7.

Here is an example of a diff function that computes the minimum of 1 + limit and the difference in length between the two input strings:

>>> def length_diff(w1, w2, limit):
...     return min(limit + 1, abs(len(w2) - len(w1)))
>>> length_diff('mellow', 'cello', 10)
1
>>> length_diff('hippo', 'hippopotamus', 5)
6

Assume that typed_word and all elements of word_list are lowercase and have no punctuation.

Hint: Try using max or min with the optional key argument.

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

$ python ok -q 05 -u

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

$ python ok -q 05