Today is a two-for-one deal since I forgot to post anything yesterday.
Write a Python decorator to add http://en.wikipedia.org/wiki/Memoization to any function.
Python decorators are very nice. Django uses them for users to specify which views require login and things of that nature. Decorators give the ability to modify how a function will behave. Now memoization is a technique that can be used to speed up a recursive solution to a dynamic programming problem. Today my example isn't really a dynamic programming problem (because I am a bit lazy) but will illustrate how much of a speed up you can get by using memoization.
import time def mem(fn): mem = {} def mod(*args,**kwargs): key = hash((args,tuple([(k,kwargs[k]) for k in kwargs]))) if mem.has_key(key): return mem[key] else: val = fn(*args,**kwargs) mem[key] = val return val return mod @mem def fib(n): if n == 1 or n == 2: return 1 else: return fib(n-1) + fib(n-2) t1 = time.time() fib(35) t2 = time.time() print t2-t1
With the @mem decorating the function it takes: 0.0002 seconds to compute fib(35). Without @mem it takes about 10 seconds. (Results may vary depending on your computer).
Now for the second part:
You are on an alien world preparing for a potential invasion. The planet has some sort of dampening field covering it so you cannot use any sort of wireless communication. Your mission is to connect all the bases under your command with the least amount of wire. Every base must be able to communicate to every other base. A base will be able to communicate with any other base if a path exists between the two.
This can be solved by creating a minimum spanning tree.
bases = [ #distance, #start base, #end base (5,0,1), (5,0,2), (2,0,5), (10,1,5), (30,1,2), (3,1,3), (6,1,4), (4,2,5), (6,2,3), (6,2,4), (7,3,5), (3,4,3) ] def wire(num_bases,data): base_to_set = {} connections = [] data.sort() for i in range(num_bases): base_to_set[i] = set([i]) cost = 0 for entry in data: base1_set = base_to_set[entry[1]] base2_set = base_to_set[entry[2]] if len(base1_set.intersection(base2_set)) > 0: continue merge = base1_set.union(base2_set) for item_id in merge: base_to_set[item_id] = merge cost += entry[0] connections.append((entry[1],entry[2])) return (connections,cost)
The function takes in the number of bases and a list of tuples that contain the cost and two base ids indicating they are connected.
The problem today is to find "dead" nodes in a graph. This sort of algorithm could be applied to all sorts of things such as eliminating the unreachable states in a DFA or unreachable code in a compiler.
class State: def __init__(self, id): self.id = id self.outs = [] self.visited = False def __repr__(self): return str(self.id) def dead(begins, all): def search(state): if state.visited: return state.visited = True for s in state.outs: search(s) for s in begins: search(s) removable = [] for s in all: if not s.visited: removable.append(s); return removable if __name__ == "__main__": ss = [] for i in range(6): ss.append(State(i)) ss[0].outs = [ss[5]] ss[1].outs = [ss[3],ss[2]] ss[2].outs = [ss[1]] ss[3].outs = [ss[2],ss[4]] ss[4].outs = [] ss[5].outs = [] print dead([ss[1]], ss) for s in ss: s.visited = False print dead([ss[0]], ss) for s in ss: s.visited = False print dead([ss[0],ss[1]], ss)
I have been asked to do basic string problems before. The problem for today:
Given a string, print out each character that appears, the number of times that it appears and it must be done in the order the characters appear in the original string. And it must be done in O(n) time.
def do(s): seenMap = {} orderList = [] for c in s: if not seenMap.has_key(c): orderList.append(c) seenMap[c] = 0 seenMap[c] += 1 for c in orderList: print c, str(seenMap[c])
The important thing here is to do it in O(n) time. It is easy to get trapped and do this in polynomial time. The trick here is to use a list to store the order that characters appear and to use a dictionary to keep track of if a character has been seen and how many times it has been seen. Provided that the has_key function has O(1) running time my algorithm is O(n).