# Notes from Wednesday, November 8

# A general purpose program for heuristic state-space search

#-----------------------------------------------------------------------------
# The Node class is used to represent nodes of the search tree.  Each node
# contains a state representation, a reference to the node's parent node, a
# string describing the action that generated the node's state from the parent
# state, the number of steps from the start node to this node, and the heuristic
# estimate of the distance remaining from this node to the nearest goal.

class Node:

    def __init__(self, state, parent, action):
        self.state = state
        self.parent = parent
        self.action = action
        self.steps = 0
        self.estimate = 0

    def cost(self):
        return self.steps + self.estimate

    def expand(self):
        successors = []
        for (action, newState) in self.state.applyOperators():
            newNode = Node(newState, self, action)
            successors.append(newNode)
        return successors

#-----------------------------------------------------------------------------
# search keeps track of all unexamined nodes in an ordered list called the
# fringe.  It repeatedly picks the next node with the lowest estimated cost
# (i.e., distance from start node + estimated distance remaining to the goal),
# and checks to see if it represents the goal.  If so, it prints the path from
# the start node to the goal node and stops.  Otherwise, it adds all of the
# successors of the node to the fringe, remembers the state just examined in
# order to avoid examining it again, and repeats the cycle.  The search fails
# if it runs out of nodes to examine before reaching a goal.

def search(initialState, goalState, heuristic):
    fringe = PriorityQueue()
    start = Node(initialState, None, None)
    start.estimate = heuristic(initialState, goalState)
    fringe.insert(start)
    oldStates = []
    while not fringe.empty():
        current = fringe.remove()
        if current.state == goalState:
            print 'Found a solution...'
            showSolution(current)
            return
        elif current.state not in oldStates:
            for successor in current.expand():
                successor.steps = current.steps + 1
                successor.estimate = heuristic(successor.state, goalState)
                fringe.insert(successor)
            oldStates.append(current.state)
    print 'Search failed'

# showSolution prints out the sequence of states and actions used to reach
# the goal, by following the chain of parent references backwards from the
# goal node to the start node.

def showSolution(node):
    numSteps = node.steps
    path = []
    # build up path in reverse
    while node is not None:
        path.insert(0, node)
        node = node.parent
    print path[0].state
    for n in path[1:]:
        print '%s\n%s' % (n.action, n.state)
    print 'Solution took %d steps' % numSteps

#-----------------------------------------------------------------------------
# A simple implementation of a priority queue as an ordered list.  Elements in
# a priority queue are stored in ascending order by their cost value.
#    q.empty() returns True if q is empty
#    q.insert(x) inserts x into q according to the cost of x
#    q.remove() removes and returns the lowest-cost element from q

class PriorityQueue:

    def __init__(self):
        self.contents = []

    def __str__(self):
        return '%s' % self.contents

    def empty(self):
        return len(self.contents) == 0

    def insert(self, new):
        for i in range(len(self.contents)):
            if new.cost() < self.contents[i].cost():
                # insert element at position i
                self.contents.insert(i, new)
                return
        # all elements are bigger, so add it to the end
        self.contents.append(new)

    def remove(self):
        if self.empty():
            return None
        else:
            # remove element at position 0
            return self.contents.pop(0)