BFS - 2 way search code

bfs2way.py

import rubik
import unittest
def shortest_path(start, end):
    """
    Using 2-way BFS, finds the shortest path from start_position to
    end_position. Returns a list of moves. 

    You can use the rubik.quarter_twists move set.
    Each move can be applied using rubik.perm_apply
    """

    
    global levelA
    levelA = {start : 0}
    global levelB
    levelB = {end : 0}
    
    global parent
    parent = { start:None, end:None }

    global final_list
    final_list = []


    iA = iB = 1
    continued = resultA = resultB = True
    
    
    frontierA = [start]
    frontierB = [end]

    

    while (frontierA or frontierB) :
       
        
        resultA,iA,frontierA,leveA,levelB = traversal( frontierA, levelA, levelB, iA, final_list )
        
        if resultA is True:
            resultB, iB,frontierB,levelB,levelA = traversal( frontierB, levelB, levelA, iB, final_list )
        if resultA is False or resultB is False:
            frontierA = frontierB = []

        
    if start in final_list:
        final_list.remove(start)
    return final_list
    raise NotImplementedError



def traversal( frontier,l1, l2, i, final_list  ):
    next = []
    if frontier:
        for u in frontier:
            if u not in l2:

                for v in rubik.quarter_twists:
                #for v in u.adj:
                    #print rubik.quarter_twists_names[v]
                    cube = rubik.perm_apply(v, u)
                    if cube not in l1 and cube not in l2:
                        l1[cube] = i
                        parent[cube]= u
                        next.append(cube)
                    elif cube in l2 and cube not in l1:
                        buildPath(u,cube, l1, final_list)
                        return False, i,frontier,l1,l2
                        
                frontier.remove(u)
            else:
                return False, i,frontier,l1,l2
        for element in next:
            frontier.append(element)

        #print i
        #printList(next)
        #print "====================================="
        
        
        i = i+1
    
    return True,i,frontier,l1,l2


def buildPath(founder, node, level, final_list):
    
    # if the last node is already discovered in level B
    if level is levelA:
        u = founder
        v = node
    else:
        u = node
        v = founder

    # get from start
    while u :
        final_list.append(u)
        u = parent[u]

    
    
    final_list.reverse() # ugly error solved, just because python does stuff in-place and doesn't allow list = list.reverse() and shows crytic errors

    # get upto end
    while v :
        final_list.append(v)
        v = parent[v]
    
class BitchClass:
    def __init__(self, name):
        self.name = name
        self.adj = ()    

def printList( list ):
    for element in list:
            print element,
            print "-->",
    print ""


if __name__ == '__main__2' :
        a = BitchClass('a')
        b = BitchClass('b')
        c = BitchClass('c')
        d = BitchClass('d')
        e = BitchClass('e')
        f = BitchClass('f')
        g = BitchClass('g')
        j = BitchClass('j')

        a.adj = (b,c,j)
        b.adj = (a,e,d)
        c.adj = (a,f)
        d.adj = (b,e)
        e.adj = (b,f,g)
        f.adj = (c,e,g)
        g.adj = (e,f,j)
        #rubik.perm_to_string(ans)  
        shortest_path( a, g )
        printList( final_list )        

if __name__ == '__main__' :
        start = (6, 7, 8, 20, 18, 19, 3, 4, 5, 16, 17, 15, 0, 1, 2, 14, 12, 13, 10, 11, 9, 21, 22, 23)
        end = rubik.I
        ans = shortest_path(start, end)
        printList(ans)
        print "------------------"
        print len(ans)
        
        

Change rubik moves to adj for normal graph. Also python pass by reference is shit. It is pass by symbol