Problem 6 (200pts): sphinx_swap
Implement sphinx_swap
, which is a diff function that takes two strings. It returns the minimum number of characters that must be changed in the start
word in order to transform it into the goal
word. If the strings are not of equal length, the difference in lengths is added to the total.
Here are some examples:
>>> big_limit = 10
>>> sphinx_swap("nice", "rice", big_limit) # Substitute: n -> r
1
>>> sphinx_swap("range", "rungs", big_limit) # Substitute: a -> u, e -> s
2
>>> sphinx_swap("pill", "pillage", big_limit) # Don't substitute anything, length difference of 3.
3
>>> sphinx_swap("roses", "arose", big_limit) # Substitute: r -> a, o -> r, s -> o, e -> s, s -> e
5
>>> sphinx_swap("rose", "hello", big_limit) # Substitue: r->h, o->e, s->l, e->l, length difference of 1.
5
If the number of characters that must change is greater than limit
, then sphinx_swap
should return any number larger than limit
and should minimize the amount of computation needed to do so.
These two calls to sphinx_swap
should take about the same amount of time to evaluate:
>>> limit = 4
>>> sphinx_swap("roses", "arose", limit) > limit
True
>>> sphinx_swap("rosesabcdefghijklm", "arosenopqrstuvwxyz", limit) > limit
True
Important: You may not use
while
orfor
statements in your implementation. Use recursion.
Try turning on autocorrect in the GUI. Does it help you type faster? Are the corrections accurate? You should notice that inserting a letter or leaving one out near the beginning of a word is not handled well by this diff function. Let's fix that!
# Test your implementation
python ok -q 06