A = 5 B = 3 abs(A - B) import math from Graphics import Point A = Point(1, 3) B = Point(2, 5) math.sqrt( (A.x - B.x) ** 2 + (A.y - B.y) ** 2 ) def distance(s1, s2): # s1 is string1, s2 is string2 if len(s1) == 0: # base case, nothing left to do return len(s2) # except return length of other elif len(s2) == 0: # base case, nothing left to do return len(s1) # except return length of other if s1[0] == s2[0]: # same return distance(s1[1:], s2[1:]) + 0 # return 0 + rest else: # difference! Take minimum of: return min( distance(s1[1:], s2[1:]) + 1, # edit, return 1 + rest distance(s1, s2[1:]) + 1, # insert, return 1 + rest distance(s1[1:], s2) + 1) # delete, return 1 + rest distance("apple", "apple") distance("apple", "aple") distance("abcdefghijklmnopqrstuvwxyz", "abcdefghijklmnopqrstuvwxyzA") distance("abcdefghijklmnopqrstuvwxyz", "Aabcdefghijklmnopqrstuvwxyz") def distance1(s1, s2): if len(s1) == 0 or len(s2) == 0: return len(s2) + len(s1) cost = 0 if (s1[0] == s2[0]) else 1 return min( distance1(s1[1:], s2[1:]) + cost, distance1(s1, s2[1:]) + 1, distance1(s1[1:], s2) + 1) def memoize(f): cache = {} def m(*args): if args not in cache: cache[args] = f(*args) return cache[args] return m @memoize def distance(s1, s2): if len(s1) == 0 or len(s2) == 0: return len(s2) + len(s1) cost = 0 if (s1[0] == s2[0]) else 1 return min( distance(s1[1:], s2[1:]) + cost, distance(s1, s2[1:]) + 1, distance(s1[1:], s2) + 1) distance("abcdefghijklmnopqrstuvwxyz", "Aabcdefghijklmnopqrstuvwxyz") def distance(s1, s2): if len(s1) == 0: return 0 cost = 0 if s1[0] == s2[0] else 1 return cost + distance(s1[1:], s2[1:]) def distance(s1, s2): cost = 0 for i in range(len(s1)): cost += 0 if s1[i] == s2[i] else 1 return cost