I tried to write a recursive implementation for edit_distance, but kept getting errors, so I ended up submitting a non-recursive solution. At least, I think it's a solution, inasmuch as it was labeled "Correct" when I resubmitted it after the deadline. (I had a stupid typo in my recursive implementation that I finally caught -- but only after the submission deadline.)
Anyway, my code for the non-recursive is below. I used a dictionary to keep track of all the distances as I went through the strings.
What has me confused is that, at the end, if I print out my entire dictionary (as opposed to returning the one final result), all of my keys are two-value pairs enclosed in parentheses -- such as: (2,1) or (0,3). I expected the keys to be lists of two values. But a list would be enclosed in square brackets. We didn't see anything in this course that looked like those pairs in parentheses.
But, I submitted this since it worked -- and the function wasn't returning anything other than the dictionary value, so the keys didn't show up anyway.
My question is: What on earth did I do? Are these pairs the expected output of dictionary assignments that I did this way? Or is it the merest coincidence that this works at all? (I tested it with the long list of edit_distance test strings that was posted in another comment, and they all worked.)
Of course, if I'd caught that stupid typo earlier, none of this would be an issue for me!
Thanks in advance to anyone who can offer some insight.
You accidentally used tuple as your key, f.e. in this line:
, where key consists of number pair (i,0). Tuple is data type specific to Python, somewhat similar to an ordered list. See also Python docs. The code works because ordered list of two elements from 0 to n-1 maps exactly to the elements of two-dimensional n*n matrix.
You asked "Or is it the merest coincidence that this works at all? "
I ask "Is it the merest coincidence that this is a Pythonised version of the code at http://en.wikipedia.org/wiki/Levenshtein_distance?"
You are using a dictionary with tuples (i,j) as the index to store the matrix values.