breadth first search optimisation in python

Question

I was solving a problem related to breadth first search. I solved the problem but my solution took the longest time to solve (0.12 as compared to 0.01 and 0.02 done by others). The question is a simple BFS on a graph.

Here is how I have implemented BFS:

def bfs1(g, s):
    parent = {s: None}
    level = {s: 0}
    frontier = [s]
    ctr = 1
    while frontier:
            next = []
            for i in frontier:
                for j in g[i]:
                    if j not in parent:
                        parent[j] = i
                        level[j] = ctr
                        next.append(j)
            frontier = next
            ctr += 1
    return level

Here g and s are adjacency list (dict in case of python) and starting Node respectively.

I learned this approach from MIT algorithms course.

Here is the problem which I was solving.

Below is the complete solution which I submitted

Here d is the graph which I pre-generated 


d={'f1': ['d2', 'e3', 'h2', 'g3'], 'f2': ['d1', 'd3', 'e4', 'h1', 'h3', 'g4'], 'f3': ['d2', 'd4', 'e1', 'e5', 'h2', 'h4', 'g1', 'g5'], 'f4': ['d3', 'd5', 'e2', 'e6', 'h3', 'h5', 'g2', 'g6'], 'd8': ['b7', 'c6', 'f7', 'e6'], 'f6': ['d5', 'd7', 'e4', 'e8', 'h5', 'h7', 'g4', 'g8'], 'f7': ['d6', 'd8', 'e5', 'h6', 'h8', 'g5'], 'f8': ['d7', 'e6', 'h7', 'g6'], 'h3': ['f2', 'f4', 'g1', 'g5'], 'h1': ['f2', 'g3'], 'h6': ['f5', 'f7', 'g4', 'g8'], 'h7': ['f6', 'f8', 'g5'], 'h4': ['f3', 'f5', 'g2', 'g6'], 'h5': ['f4', 'f6', 'g3', 'g7'], 'b4': ['a2', 'a6', 'd3', 'd5', 'c2', 'c6'], 'b5': ['a3', 'a7', 'd4', 'd6', 'c3', 'c7'], 'b6': ['a4', 'a8', 'd5', 'd7', 'c4', 'c8'], 'b7': ['a5', 'd6', 'd8', 'c5'], 'b1': ['a3', 'd2', 'c3'], 'b2': ['a4', 'd1', 'd3', 'c4'], 'b3': ['a1', 'a5', 'd2', 'd4', 'c1', 'c5'], 'd6': ['b5', 'b7', 'c4', 'c8', 'f5', 'f7', 'e4', 'e8'], 'd7': ['b6', 'b8', 'c5', 'f6', 'f8', 'e5'], 'd4': ['b3', 'b5', 'c2', 'c6', 'f3', 'f5', 'e2', 'e6'], 'd5': ['b4', 'b6', 'c3', 'c7', 'f4', 'f6', 'e3', 'e7'], 'b8': ['a6', 'd7', 'c6'], 'd3': ['b2', 'b4', 'c1', 'c5', 'f2', 'f4', 'e1', 'e5'], 'd1': ['b2', 'c3', 'f2', 'e3'], 'e1': ['c2', 'd3', 'g2', 'f3'], 'f5': ['d4', 'd6', 'e3', 'e7', 'h4', 'h6', 'g3', 'g7'], 'd2': ['b1', 'b3', 'c4', 'f1', 'f3', 'e4'], 'e5': ['c4', 'c6', 'd3', 'd7', 'g4', 'g6', 'f3', 'f7'], 'h2': ['f1', 'f3', 'g4'], 'e3': ['c2', 'c4', 'd1', 'd5', 'g2', 'g4', 'f1', 'f5'], 'h8': ['f7', 'g6'], 'e2': ['c1', 'c3', 'd4', 'g1', 'g3', 'f4'], 'g7': ['e6', 'e8', 'f5', 'h5'], 'g6': ['e5', 'e7', 'f4', 'f8', 'h4', 'h8'], 'g5': ['e4', 'e6', 'f3', 'f7', 'h3', 'h7'], 'g4': ['e3', 'e5', 'f2', 'f6', 'h2', 'h6'], 'g3': ['e2', 'e4', 'f1', 'f5', 'h1', 'h5'], 'g2': ['e1', 'e3', 'f4', 'h4'], 'g1': ['e2', 'f3', 'h3'], 'e4': ['c3', 'c5', 'd2', 'd6', 'g3', 'g5', 'f2', 'f6'], 'g8': ['e7', 'f6', 'h6'], 'a1': ['c2', 'b3'], 'a3': ['c2', 'c4', 'b1', 'b5'], 'a2': ['c1', 'c3', 'b4'], 'a5': ['c4', 'c6', 'b3', 'b7'], 'a4': ['c3', 'c5', 'b2', 'b6'], 'a7': ['c6', 'c8', 'b5'], 'a6': ['c5', 'c7', 'b4', 'b8'], 'c3': ['a2', 'a4', 'b1', 'b5', 'e2', 'e4', 'd1', 'd5'], 'c2': ['a1', 'a3', 'b4', 'e1', 'e3', 'd4'], 'c1': ['a2', 'b3', 'e2', 'd3'], 'e6': ['c5', 'c7', 'd4', 'd8', 'g5', 'g7', 'f4', 'f8'], 'c7': ['a6', 'a8', 'b5', 'e6', 'e8', 'd5'], 'c6': ['a5', 'a7', 'b4', 'b8', 'e5', 'e7', 'd4', 'd8'], 'c5': ['a4', 'a6', 'b3', 'b7', 'e4', 'e6', 'd3', 'd7'], 'c4': ['a3', 'a5', 'b2', 'b6', 'e3', 'e5', 'd2', 'd6'], 'e7': ['c6', 'c8', 'd5', 'g6', 'g8', 'f5'], 'a8': ['c7', 'b6'], 'c8': ['a7', 'b6', 'e7', 'd6'], 'e8': ['c7', 'd6', 'g7', 'f6']}


def bfs1(g, s):
        # parent = {s: None}
        level = {s: 0}
        frontier = [s]
        ctr = 1
        while frontier:
                next = []
                for i in frontier:
                    for j in g[i]:
                        if j not in level:
                            # parent[j] = i
                            level[j] = ctr
                            next.append(j)
                frontier = next
                ctr += 1
        return level



    for i in range(int(raw_input())):
        x, y =  raw_input().split()
        print bfs1(d, x).get(y)

Answer 1

There has been some advice to implement a nice bfs. In two dimensional problems you can save half the time by searching from both ends simultanously.

But when it comes to brute optimisation for timing you always go for lookup tables. In your case you have quite nice constraints: 64 positions to start and 64 positions to finish. that is a pretty small lookup table of 4096 integers. So use whatever inefficient algorithm in a helper program to fill that lookup table and print it out. paste that table into the source code of your competition code.

Answer 2

The main problem performance-wise seem to be the fact that this is performing a full graph search and returning the distances of all nodes compared to the root node.

That is much more than is needed for the problem at hand.

In the specific chess problem you are trying to solve (find out how many jumps a knight has to make from A to B), this function will find out how many jumps a knigth needs to make from A to every other square.

So, it if input asks for the simplest A1-B3 (answer: 1), this function will also calculate A1-C8, A1-H7...

There are several options for solving that problem. I would get rid of the level variable entirely and replace writing to it with a yield. So instead of:

level[j] = ctr

do this:

yield j, ctr

Then the caller of this function can stop further execution as soon as the wanted result is reached.

Furthermore

I would also rename all the variables, so that it is clear what they are. There is no way you can make meaningful code analysis if it is all cryptic.

Then, replace parent = {} with seen = set(), because you only use it to skip nodes which were already seen.

With those little changes, you get:

def bfs1(adjacency, root):
    seen = {root}
    frontier = [root]
    yield root, 0
    next_distance = 1
    while frontier:
        next_frontier = []
        for node in frontier:
            for next_node in adjacency[node]:
                if next_node in seen:
                    continue
                seen.add(next_node)
                yield next_node, next_distance
                next_frontier.append(next_node)
        frontier = next_frontier
        next_distance += 1

And then you need:

def get_distance_from_a_to_b(a, b, adjacency):
    for node, distance in bfs1(adjacency, a):
        if node == b:
            return distance