# Non-recursive edit_distance; confused by my output

 0 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. def edit_distance(s,t):  counter = {} for i in range(0,(len(s)+1)): counter[i,0] = i for j in range(0,(len(t)+1)): counter[0,j] = j for i in range(len(s)): for j in range(len(t)): if t[j] == s[i]: counter[i+1,j+1] = counter[i,j] else: counter[i+1,j+1] = 1 + min(counter[i,j],counter[i,j+1],counter[i+1,j]) return counter[len(s),len(t)]  asked 10 Apr '12, 12:13 Andrea1 41●5 accept rate: 0%

 1 You accidentally used tuple as your key, f.e. in this line: counter[i,0] = i  , 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. answered 10 Apr '12, 13:11 Stepas Tolia... 501●4●22
Question text:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "Title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported

×15,333
×57
×3