def getind(seq, i, default):
    """Convience function"""
    try: return seq[i]
    except LookupError: return default


fuzzycache = dict()  #cached results of fuzzydistance()

def clearcache():
    """Clear the fuzzydistance() cache"""
    fuzzycache.clear()

def fuzzydistance(a, b):
    """
    Calculates the number of edit operations it takes to transform string a and string b.

    The possible operations are each weighted with different values

        delete     - 3 points
        insert     - 3 points
        swap       - 2 points
        substitute - 2 points
        strip      - 1 point

    The weights are intended to detect abbreviations and typos as closely as possible.

    The lower the return value, the more similst the strings are.
    """
    try:
        return fuzzycache[a,b]
    except KeyError:
        dist = _fuzzydist(a, b)
        fuzzycache[a,b] = dist
        return dist

def _fuzzydist(x, y, dist=0):
    xchar = getind(x, 0, None)
    ychar = getind(y, 0, None)
    nextxchar = getind(x, 1, None)
    nextychar = getind(y, 1, None)
    
    if xchar == None:
        return dist + len(y)
    elif ychar == None:
        return dist + (len(x) * 3)
    else:
        options = []
        if xchar == ychar:
            options.append((0, 1, 1))
        else:
            options.append((2, 1, 1))
            
        if (xchar, nextxchar) == (nextychar, ychar):
            options.append((2, 2, 2))
        elif xchar == nextychar:
            options.append((3, 0, 1))
        elif ychar == nextxchar:
            options.append((3, 1, 0))

        return min(_fuzzydist(x[xi:], y[yi:], dist+d) for d,xi,yi in options)


def test(seq):
    import profile
    for a,b in seq:
        profile.runctx("fuzzydistance(a,b)", globals(), locals())
        print "fuzzydistance(%r, %r) == %r" % (a,b, fuzzydistance(a,b))
        print "------------------------------"
        #fuzzydistance(a,b)
        



if __name__ == "__main__":
    test(
        [("Goffredo", "Geoffrey"),
         ("Goffredo", "Gofredo"),
         ("Lea", "Leanna"),
         ("Brit", "Britanny"),
         ("Britanny", "Brit"),
         ("Kurt", "Krut"),
         ("Hippo", "Haiku"),
         ("bicker", "bcisjfeflge")]
        )