# Set to True to get a more detailed explanation of what's happening.
verbose = False

def depthFirst(initialState, goalTest, successors):
    if goalTest(initialState): return [initialState]
    agenda = [[initialState]]
    count = 1
    while agenda != []:
        if verbose: print "agenda: ", agenda
        path = agenda.pop(0)
        if verbose: print "   expanding: ", path
        newPaths = []
        for newState in successors(path[-1]):
            if goalTest(newState):
                print count+1, " states visited"
                return path + [newState]
            elif newState in path:
                pass
            else:
                count += 1
                newPaths.append(path + [newState])
        agenda = newPaths + agenda
    print "Search failed after visiting ", count, " states."
    return None

def breadthFirst(initialState, goalTest, successors):
    if goalTest(initialState): return [initialState]
    agenda = [[initialState]]
    count = 1
    while agenda != []:
        if verbose: print "agenda: ", agenda
        path = agenda.pop(0)
        if verbose: print "   expanding: ", path
        newPaths = []
        for newState in successors(path[-1]):
            if goalTest(newState):
                print count+1, " states visited"
                return path + [newState]
            elif newState in path:
                pass
            else:
                count += 1
                newPaths.append(path + [newState])
        agenda = agenda + newPaths
    print "Search failed after visiting ", count, " states."
    return None

def breadthFirstDP(initialState, goalTest, successors):
    if goalTest(initialState): return [initialState]
    agenda = [initialState]
    pathTo = {initialState: [initialState]}
    count = 1
    while agenda != []:
        if verbose: print "agenda: ", agenda
        state = agenda.pop(0)
        if verbose: print "   expanding: ", state
        newStates = []
        for newState in successors(state):
            if not pathTo.has_key(newState):
                count += 1
                pathTo[newState] = pathTo[state] + [newState]
                if goalTest(newState):
                    print count, " states visited"
                    return pathTo[newState]
                else:
                    newStates.append(newState)
        agenda = agenda + newStates
    print "Search failed after visiting ", count, " states."
    return None

def depthFirstDP(initialState, goalTest, successors):
    if goalTest(initialState): return [initialState]
    agenda = [initialState]
    pathTo = {initialState: [initialState]}
    count = 1
    while agenda != []:
        if verbose: print "agenda: ", agenda
        state = agenda.pop(0)
        if verbose: print "   expanding: ", state
        newStates = []
        for newState in successors(state):
            if not pathTo.has_key(newState):
                count += 1
                pathTo[newState] = pathTo[state] + [newState]
                if goalTest(newState):
                    print count, " states visited"
                    return pathTo[newState]
                else:
                    newStates.append(newState)
        agenda = newStates + agenda
    print "Search failed after visiting ", count, " states."
    return None



######################################################################
##
##    Testing stuff
##
######################################################################

def numberTest(init, goal, search):
    # Generate possible successors
    def s(state):
        return removeDuplicates((state*2, state+1, state-1, state**2, -state))
    # Just see if we've reached our goal.
    def g(state):
        return state == goal
    return search(init, g, s)

def removeDuplicates(l):
    if len(l) == 0:
        return []
    elif l[0] in l[1:]:
        return removeDuplicates(l[1:])
    else:
        return [l[0]] + removeDuplicates(l[1:])

def numberTestFinite(init, goal, search, maxVal):
    # Generate possible successors
    def s(state):
        return removeDuplicates([s for s in (state*2, state+1, \
                                             state-1, state**2, -state) \
                if abs(s) < maxVal])
    # Just see if we've reached our goal.
    def g(state):
        return state == goal
    return search(init, g, s)

def searchTest(goal):
    print "BreadthFirst: ", numberTestFinite(1, goal, breadthFirst, goal+1)
    print "BreadthFirstDP: ", numberTestFinite(1, goal, breadthFirstDP, goal+1)
    print "DepthFirst: ", numberTestFinite(1, goal, depthFirst, goal+1)
    print "DepthFirstDP: ", numberTestFinite(1, goal, depthFirstDP, goal+1)

def successorsCity1(s):
    succ1 = {'S' : ['A','B'], 'A': ['C', 'D', 'S'], 'B': ['D', 'E', 'S'], 'C' : ['A', 'F'], 'D': ['A', 'B', 'F', 'H'], 'E' : ['B', 'H'], 'F' : ['C', 'D', 'G'], 'H' : ['D', 'E', 'G'], 'G' : ['F', 'H']}
    return succ1[s]

def successorsCity2(s):
    succ2 = {'S' : ['A', 'B'], 'A': ['C', 'D', 'S'], 'B':['E', 'F', 'S'], 'C': ['A', 'D'], 'D': ['A', 'C'], 'E': ['B'], 'F': ['B', 'G'], 'G':['F']}
    return succ2[s]

def p1(s):
    succ = {'a':('b', 'c'), 'b':('a','e'),'c':('a','f'),'e':('b','h'),'f':('c','i'),'h':('e','j'),'i':('f','j'),'j':('h','i')}
    return succ[s]

def p2(s):
    succ = {'a':('b', 'c'),'b':('a', 'd', 'e'), 'c':('a', 'e', 'f'), 'd':('b', 'g'), 'e':('b', 'c', 'g', 'h'), 'f':('g', 'h'), 'g':('d', 'e', 'i', 'j'), 'h':('e', 'f', 'j', 'k'), 'i':('g', 'l'), 'j':('g','h', 'l', 'm'),'k':('h','m'), 'l':('i','j','n'),'m':('j','k','n'),'n':('l','m')}
    return succ[s]

def p3(s):
    succ = {'a':('b','c'), 'b':('a','d'),'c':('a','d'),'d':('b','c','e','f'), 'e':('e','g'),'f':('d','g'),'g':('e','f')}
    return succ[s]

def p4(s):
    succ = {'a':('b','c'),'b':('a','c','d','e'),'c':('a','b','d','f'),'d':('b','c','e','f'),'e':('b','d','f','g'),'f':('c','d','e','g'),'g':('e','f')}
    return succ[s]

def bfsTest(max):
    global verbose
    verbose = False
    return [len(numberTest(1, goal, breadthFirst)) for goal in range(1, max+1, 10)]

def bfsTestDP(max):
    global verbose
    verbose = False
    return [len(numberTest(1, goal, breadthFirstDP)) for goal in range(1, max+1, 10)]
