Search algo

def performSearch(problem, fringe):
    print "Start:", problem.getStartState()
    """
    (state, direction, path, cost)
    """
    fringe.push((problem.getStartState(),None,[], 0))
    visited = []
    while fringe.isEmpty() == False:
        node = fringe.pop()
        path = node[2]
        if problem.isGoalState(node[0]):
            path.append(node[1])
            print "Found solution:", path
            return path
        elif node[0] not in visited:
            visited = visited + [node[0]]
            if node[1] is not None:
                path = path + [node[1]]
            for cNode in problem.getSuccessors(node[0]):
                if cNode[0] not in visited:
                    fringe.push((cNode[0], cNode[1], path, cNode[2]))

    print "Failed to find solution, fringe is emtpy"
    return []