fun with manhattan memoizers

manhattan

# generic 'catch-all' memoization decorator
def memoize(function):
    # some data types don't take kindly to being map keys. serialize 'em
    def serialize(x):
        if type(x) == list:
            return tuple(x)
        elif type(x) == dict:
            return tuple(x.items())
        else:
            return x

    class memo_func(dict):
        # we're turning the function call into a map, where the set of the arguments are the key
        # and the return value of the function call is the value of the cell of the map
        def __init__(self, function):
            # called on creation. wraps the function call internally
            self.f = function
            # and lets do some efficiency metric calculation while we're here
            self.hits = 0
            self.misses = 0

        def __call__(self, *args):
            # if the map has this key, return the value
            self.hits += 1
            return self[tuple(map(serialize, args))]

        def __missing__(self, call):
            # this method is called when a map gets an unknown key requested
            self.misses += 1
            # so we calculate the value, and store it in the map for next time
            ret = self[tuple(map(serialize, call))] = self.f(*call)
            return ret

    return memo_func(function)

# This problem is fairly straight-forward.
# "Given two letters in this two dimensional array, calulate all shortest paths between them."

cell = ["abcde","fghij","klmno","pqrst","uvwxy"]
# abcde
# fghij
# klmno
# pqrst
# uvwxy

@memoize
def findchar(let):
    for (i,row) in enumerate(cell):
        for (j, col) in enumerate(row):
            if (col == let):
                return (i,j)

    print let, "not found"
    return None

@memoize
def pathcalc((x1,y1),(x2,y2)):
    if (x1,y1) == (x2,y2):
        # shortest path to self is self
        return [cell[x1][y1]]

    # calculate the paths to our target from one-nearer
    candidates = []
    if (x1 > x2):
        candidates += pathcalc((x1-1,y1),(x2,y2))
    elif (x1 < x2):
        candidates += pathcalc((x1+1,y1),(x2,y2))

    if (y1 > y2):
        candidates += pathcalc((x1,y1-1),(x2,y2))
    elif (y1 < y2):
        candidates += pathcalc((x1,y1+1),(x2,y2))

    # prepend our current location to those paths
    results = []
    for path in candidates:
        results += [cell[x1][y1] + path]

    return results

# test char lookups
print findchar('a')
print findchar('o')
print findchar('x')
print findchar('z')

# some sample paths
print pathcalc(findchar('a'), findchar('a'))
print pathcalc(findchar('o'), findchar('q'))
print pathcalc(findchar('a'), findchar('y'))

# function meta-logging statistics
print pathcalc.hits, pathcalc.misses
print pathcalc