@@ -0,0 +1,1901 @@
+# Starting in top left corner, only being able to to move to the right and down,%0A# how many routes are in a 20x20 grid?%0A%0Afrom nose.tools import *%0A%0Adef test_2x2_grid_has_6_routes():%0A    x = 0%0A    y = 0%0A    path = %5B(x,y)%5D%0A    while True:%0A        path.append%0A        %0A%0Adef find_next_path(x, y):%0A    if x + 1 %3E 2:%0A        return (x,y)%0A    else:%0A        return %5B(x,y)%5D.append(find_next_path(x+1, y))%0A%0A    if y + 1 %3E 2:%0A        return (x,y)%0A    else:%0A        return %5B(x,y)%5D.append(find_next_path(x, y+1))%0A%0A%0Adef generate_grid(xmax,ymax):%0A    return %5BNode(x,y) for x in range(xmax) for y in range(ymax)%5D%0A%0Adef can_connect(curr, neighbor):%0A    if neighbor.x - curr.x == 1 and neighbor.y - curr.y == 0:%0A        return True%0A    if neighbor.x - curr.x == 0 and neighbor.y - curr.y == 1:%0A        return True%0A    return False%0A%0A%0Aclass Node(object):%0A    def __init__(self, x, y):%0A        self.x = x%0A        self.y = y%0A        self.connected_to = %5B%5D%0A%0A    def connect(self, other):%0A        self.connected_to.append(other)%0A%0A    def __str__(self):%0A        return %22(%7B0%7D, %7B1%7D)%22.format(self.x, self.y)%0A%0A    def __repr__(self):%0A        return %22Node(%7B0%7D, %7B1%7D)%22.format(self.x, self.y)%0A%0Adef solve_p015():%0A    grid = generate_grid(21,21)%0A    for node in grid:%0A        for pot_neighbor in grid:%0A            if can_connect(node, pot_neighbor):%0A                node.connect(pot_neighbor)%0A%0A    return find_paths(grid%5B0%5D)%0A%0Adef memoize(func):%0A    memoized_results = %7B%7D%0A    def wrapper(*args):%0A        if args not in memoized_results:%0A            memoized_results%5Bargs%5D = func(*args)%0A        return memoized_results%5Bargs%5D%0A    return wrapper%0A%0A@memoize%0Adef find_paths(node):%0A    if node.x == 20 and node.y == 20:%0A        return 1%0A    if not node.connected_to:%0A        return 0%0A%0A    total = 0%0A    for neighbor in node.connected_to:%0A         total += find_paths(neighbor)%0A%0A    return total%0A%0Aif __name__ == '__main__':%0A    print solve_p015()%0A

Solving p015