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

##  The entries in the agenda are paths.
## A path is a list of (action, state) tuples, abbreviated as AS below.

def action(AS): return AS[0]
def state(AS): return AS[1]

## successors: s -> list((a, s))
## goalTest: s -> Boolean

def search(initialState, goalTest, successors,
           depthFirst = False, maxNodes = 10000):
    initialAS = (None, initialState)  # no action
    if goalTest(initialState): return [initialAS]
    agenda = [[initialAS]]              # a list of a single path
    count = 1
    while agenda != [] and (not maxNodes or maxNodes > count):
        if verbose: print "agenda: ", agenda
        path = agenda.pop(0)
        if somewhatVerbose or verbose: print "   expanding: ", path
        newPaths = []
        for newAS in successors(state(path[-1])):
            if goalTest(state(newAS)):
                print count+1, " states visited"
                return path + [newAS]
            elif state == None or stateInASList(state(newAS), path):
                pass
            else:
                count += 1
                newPaths.append(path + [newAS])
        if depthFirst:
            agenda = newPaths + agenda
        else:
            agenda = agenda + newPaths
    print "Search failed after visiting ", count, " states."
    return None

def depthFirst (initialState, goalTest, successors):
    return search(initialState, goalTest, successors, depthFirst=True)

def breadthFirst (initialState, goalTest, successors):
    return search(initialState, goalTest, successors, depthFirst=False)

##  The entries in the agenda are (action, state) tuples, abbreviated as AS
##  below.

def searchDP(initialState, goalTest, successors, depthFirst = False,
             maxNodes = 10000):
    initialAS = (None, initialState)  # no action
    if goalTest(initialState): return [initialAS]
    agenda = [initialAS]                # a list of a single AS
    pathTo = {initialState: [initialAS]}
    count = 1
    while agenda != [] and (not maxNodes or maxNodes > count):
        if verbose: print "agenda: ", agenda
        AS = agenda.pop(0)
        S = state(AS)
        if somewhatVerbose or verbose: print "   expanding: ", AS
        newASList = []
        for newAS in successors(state(AS)):
            newS = state(newAS)
            if newS != None and not pathTo.has_key(newS):
                count += 1
                pathTo[newS] = pathTo[S] + [newAS]
                if goalTest(newS):
                    print count, " states visited"
                    return pathTo[newS]
                else:
                    newASList.append(newAS)
        if depthFirst:
            agenda = newASList + agenda
        else:
            agenda = agenda + newASList
    print "Search failed after visiting ", count, " states."
    return None

def depthFirstDP (initialState, goalTest, successors):
    return searchDP(initialState, goalTest, successors, depthFirst=True)

def breadthFirstDP (initialState, goalTest, successors):
    return searchDP(initialState, goalTest, successors, depthFirst=False)

def stateInASList(state, ASList):
    for (a, s) in ASList:
        if s == state:
            return True
    return False

######################################################################
###
###  Number test domain
###
######################################################################

### init:  state
### goal:  state
### search: which search function to use (e.g., depthFirstDP)
###    a search function takes an initial state, a goal Test, and a
###    successor function and returns a plan or None

def numberTest(init, goal, search):
    # Generate possible successors:  returns a list of pairs, each of
    # which contains an action and a resulting state
    def s(state):
        return removeDuplicates([('x*2', state*2),
                                 ('x+1', state+1),
                                 ('x-1', state-1),
                                 ('x**2', state**2),
                                 ('-x', -state)])
    # Takes a state as input and returns True if it equals the goal
    def g(state):
        return state == goal
    return search(init, g, s)

# Given a list l of (a,s) pairs, return a new list with any duplicate
# states removed (even if they are associated with different actions)
def removeDuplicates(l):
    if len(l) == 0:
        return []
    elif stateInASList(l[0][1], l[1:]):
        return removeDuplicates(l[1:])
    else:
        return [l[0]] + removeDuplicates(l[1:])

# Same as numberTest, but only considers states whose absolute value
# is less than some maximum.  
def numberTestFinite(init, goal, search, maxVal):
    # Generate possible successors
    def s(state):
        return removeDuplicates([s for s in (('x*2', state*2),
                                             ('x+1', state+1),
                                             ('x-1', state-1),
                                             ('x**2', state**2),
                                             ('-x', -state)) \
                if abs(s[1]) < 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)