def postorder_traverse_4(root):
    """postorder_traverse_4

    algorithm:
      improve postorder_traverse_3 based on the fact that if last visited
    node is current node's right child, then current node should be popped up
    """
    stack = Stack([], debug=True)
    node = root
    last_visited = None

    while True:
        # push
        while node:
            stack.append(node)
            node = node.left

        if not stack: break

        # top/pop
        node = stack[-1]
        if not node.right or node.right == last_visited:
            node = stack.pop()
            yield node
            last_visited = node

            # prepare next
            node = None

        else:
            # prepare next
            node = node.right

def find_immediate_common_ancestor_2(root, value1, value2):
    """find_immediate_common_ancestor_2

    algorithm:
      in post-order, the stack holds all the parent node
    when find the first value, the parent list only shrink on the
    road to find the 2nd value.
    """
    p, last_visited, immediate_ancestor = root, None, None
    #stack = Stack([], debug=True)
    stack = Stack([])
    while p or stack:
        while p:
            stack.append(p)
            p = p.left

        p = stack[-1]
        if not p.right or p.right == last_visited:
            stack.pop()
            #^#
            if p.value in (value1, value2):
                if not immediate_ancestor:
                    immediate_ancestor = stack[-1]
                else:
                    return immediate_ancestor.value
            if p == immediate_ancestor:
                if stack:
                    immediate_ancestor = stack[-1]
            #$#
            last_visited = p
            p = None
        else:
            p = p.right

def postorder_traverse_3(root):
    """postorder_traverse_3

    algorithm:
      push/pop node to stack according to current node's state
    """
    ns = [root, VISIT_LEFT] #(node, state)
    stack = Stack([], debug=True)
    while ns or stack:
        while ns:
            stack.append(ns)
            node, state = ns
            #ns[1] == VISIT_LEFT
            ns[1] = VISIT_RIGHT
            if node.left:
                ns = [node.left, VISIT_LEFT]
            else:
                ns = None

        ns = stack[-1]
        if ns[1] == VISIT_RIGHT:
            ns[1] = VISIT_SELF
            if ns[0].right:
                ns = [ns[0].right, VISIT_LEFT]
            else:
                ns = None
        elif ns[1] == VISIT_SELF:
            yield ns[0]
            stack.pop()
            ns = None

def depthFirstSearch(problem):
    """
    Search the deepest nodes in the search tree first

    Your search algorithm needs to return a list of actions that reaches
    the goal.  Make sure to implement a graph search algorithm

    To get started, you might want to try some of these simple commands to
    understand the search problem that is being passed in:

    print "Start:", problem.getStartState()
    print "Is the start a goal?", problem.isGoalState(problem.getStartState())
    print "Start's successors:", problem.getSuccessors(problem.getStartState())
    """
    "*** YOUR CODE HERE ***"
    path = Stack()
    explored = []
    def depthSearch(state):        
        
        explored.append(state)#record that this node is explored
        
        if problem.isGoalState(state): #check if goal
            return True  #return to the higher level of the "depthSearch" 
        
        suc = problem.getSuccessors(state)  #get a list of triples(successor, action, stepCost)   
                                            #the successor is the next state
                                            #e.g. [((5, 4), 'South', 1), ((4, 5), 'West', 1)] 
#         suc = [triple for triple in suc if not triple[0] in explored]
#         for triple in suc:
#             explored.append(triple[0])
                
        for triple in suc: # for every triple(successor, action, stepCost)  
            if explored.__contains__(triple[0]):#check if the state is searched
                continue           
            if depthSearch(triple[0]): #the recursive
                path.push(triple[1])    # if the lower level return true, record the action
                return True            # which means this level also has found goal state
         
        return False   

    depthSearch(problem.getStartState()) #The first call
    
    route = []
    while (not path.isEmpty()):
        action = path.pop()
        #print action
        route.append(action) #return a list of action
    return route

def depthFirstSearch(problem):
    """
    Search the deepest nodes in the search tree first.

    Your search algorithm needs to return a list of actions that reaches the
    goal. Make sure to implement a graph search algorithm.

    To get started, you might want to try some of these simple commands to
    understand the search problem that is being passed in:

    print "Start:", problem.getStartState()
    print "Is the start a goal?", problem.isGoalState(problem.getStartState())
    print "Start's successors:", problem.getSuccessors(problem.getStartState())
    """
    from util import Stack
    start = problem.getStartState()
    checkStack = Stack()
    checkStack.push((start,[]))
    visitedStates = []
    while not checkStack.isEmpty():
            popState, popDirection = checkStack.pop()
            for successors in problem.getSuccessors(popState):
                state, direction, cost  = successors
                if not state in visitedStates:
                    if problem.isGoalState(state):
                        print state
                        return popDirection + [direction]
                    checkStack.push((state,popDirection+[direction]))
                    visitedStates = visitedStates+[popState]

def depthFirstSearch(problem):
    from collections import defaultdict
    from util import Stack
    initial_node=problem.getStartState()
    
    current_node=defaultdict(list)
    current_node[initial_node].append("No parent")
    current_node[initial_node].append("No direction")
    stack=Stack()
    stack.push(current_node)
    current_node=stack.pop()
    direction_list={}
    Child=current_node.keys()
    Parent=current_node.values()[0]
    visited_list={}
    while (problem.isGoalState(Child[0]) is not True):
            
        if(Child[0] in visited_list.keys()):
            
            current_node=stack.pop()
            Child=current_node.keys()
            Parent=current_node.values()[0]
            
        else:
            visited_list[Child[0]]=Parent[0]
            direction_list[Child[0]]=Parent[1]
            Successor_node=problem.getSuccessors(Child[0])
            for index in range(len(Successor_node)):
                temp_dict=defaultdict(list)
                temp_dict[Successor_node[index][0]].append(Child[0])
                temp_dict[Successor_node[index][0]].append(Successor_node[index][1])
                #print"The temp dict values are",temp_dict
                
                stack.push(temp_dict)
                
            #print " The heap of queue is",priority_queue.heap
            current_node=stack.pop()
            #print "The current node is",current_node
            Child=current_node.keys()
            Parent=current_node.values()[0]
    
    visited_list[Child[0]]= Parent[0]
    direction_list[Child[0]]=Parent[1]
    backtracking =[]
    path = Child[0]
    backtracking.append(direction_list[path])
    path = visited_list[path]
    print "The path is",path
    while (path!= problem.getStartState()):
        backtracking.append(direction_list[path])
        path = visited_list[path]
    backtracking.reverse()

    return backtracking
    util.raiseNotDefined()

def depthFirstSearch(problem):
    """
    Search the deepest nodes in the search tree first.

    Your search algorithm needs to return a list of actions that reaches the
    goal. Make sure to implement a graph search algorithm.

    To get started, you might want to try some of these simple commands to
    understand the search problem that is being passed in:

    print "Start:", problem.getStartState()
    print "Is the start a goal?", problem.isGoalState(problem.getStartState())
    print "Start's successors:", problem.getSuccessors(problem.getStartState())
    """
    "*** YOUR CODE HERE ***"
    from util import Stack
    frontier=Stack()
    start_node = Node(problem.getStartState(), step_cost=0)
    explored = []
    frontier.push(start_node)
    while not frontier.isEmpty():
        node = frontier.pop()
        explored.append(node.state)
        if problem.isGoalState(node.state):
            return node.getPath()
        for child in node.getChildren(problem):
            if not child.state in explored:
                frontier.push(child)

def depthFirstSearch(problem):

    successor_idx = {'dir': 1, 'state': 0, 'cost': -1}

    MAX_ITER = int(20000)
    stateStack = Stack()
    visitedSet = set()
    actionList = [] # add actions to get to the state, use pop to remove last one
    successorDict = {}

    curState = problem.getStartState()
    stateStack.push(curState)
   
    for it in range(MAX_ITER):

        if problem.isGoalState(curState):
            return actionList

        if curState not in visitedSet:
            successors = problem.getSuccessors(curState)
            successorDict[curState] = successors

        visitedSet.add(curState)
        nStateTuple = filter(lambda x: x[0] not in visitedSet, successorDict[curState]) # get next state

        if len(nStateTuple) == 0:
            stateStack.pop()
            actionList.pop()
            curState = stateStack.list[-1]
        else:
            curState = nStateTuple[0][successor_idx['state']]
            stateStack.push(curState)
            actionList.append(nStateTuple[0][successor_idx['dir']])

    return []

def depthFirstSearch(problem):
  
    stack = Stack(); parentNode = []; successors = []; visitedNodes = []
    parentChildMapList = {}
    stack.push(problem.getStartState())
    currentState = problem.getStartState() #need to remove
    while problem.isGoalState(currentState) is False and problem.isGoalState(currentState[0]) is False:
        if(currentState == problem.getStartState()):
            successors = problem.getSuccessors(currentState)
            visitedNodes.append(currentState)
        else:
            successors = problem.getSuccessors(currentState[0])
            visitedNodes.append(currentState[0])
        if successors != None and len(successors) > 0 :
            parentNode.append(currentState)
        for node in successors:
            if(visitedNodes.__contains__(node) == False and visitedNodes.__contains__(node[0]) == False):
                stack.push(node)
                parentChildMapList[node] = currentState
        
        tempCurrentNode = stack.pop()
        if(visitedNodes.__contains__(tempCurrentNode) == False and visitedNodes.__contains__(tempCurrentNode[0]) == False):
            currentState = tempCurrentNode
        else:
            currentState = stack.pop()
            
    validDirections = []
    firstState = currentState
    while firstState != problem.getStartState():
        validDirections.append(firstState[1])
        firstState = parentChildMapList[firstState]

    validDirections.reverse()
    return validDirections
    util.raiseNotDefined()

def depthFirstSearch(problem):
    "Search the shallowest nodes in the search tree first. [p 81]"
    from util import Stack
    BFS1 = Stack()
    Moves = []
    Visited = []
    Final = []
    NewState = (0, (problem.getStartState(), 'Start', 0))
    #print CurrentState
    BFS1.push([NewState])
    while not BFS1.isEmpty():
        NewState = BFS1.pop()
        if problem.isGoalState(NewState[0][1][0]):
            Final = NewState
            break
        if Visited.count(NewState[0][1][0]) == 0:
            #print NewState
            for item in enumerate(problem.getSuccessors(NewState[0][1][0])):
                #print item
                BFS1.push([item] + NewState)
        Visited.append(NewState[0][1][0])
    for nodes in Final:
        Moves.append(nodes[1][1])
    Moves.reverse()
    Moves.remove('Start')
    #print Moves
    return Moves

def depthFirstSearch(problem):
  """
  Search the deepest nodes in the search tree first [p 85].
        
  Your search algorithm needs to return a list of actions that reaches
  the goal.  Make sure to implement a graph search algorithm [Fig. 3.7].
        
  To get started, you might want to try some of these simple commands to
  understand the search problem that is being passed in:
        
  print "Start:", problem.getStartState()
  print "Is the start a goal?", problem.isGoalState(problem.getStartState())
  print "Start's successors:", problem.getSuccessors(problem.getStartState())
  """
  frontier = Stack()  # A helper stack of (state,route_to_state)
  explored_set = set()  # A set of state recording the explored nodes
  
  start = problem.getStartState()
  frontier.push((start,list()))
  
  while not frontier.isEmpty():
   current_node = frontier.pop()
   if problem.isGoalState(current_node[0]): return current_node[1]
   successors = problem.getSuccessors(current_node[0])
   explored_set.add(current_node[0])
   for s in successors:
       if s[0] not in explored_set:
           current_route = list(current_node[1])
           current_route.append(s[1])
           frontier.push((s[0],current_route))
           
  print "No route found!"
  return list()

def depthFirstSearch(problem):
    """
    Search the deepest nodes in the search tree first

    Your search algorithm needs to return a list of actions that reaches
    the goal.  Make sure to implement a graph search algorithm

    To get started, you might want to try some of these simple commands to
    understand the search problem that is being passed in:

    print "Start:", problem.getStartState()
    print "Is the start a goal?", problem.isGoalState(problem.getStartState())
    print "Start's successors:", problem.getSuccessors(problem.getStartState())
    """
    "*** YOUR CODE HERE ***"
    '''util.raiseNotDefined()'''
    from util import Stack
    path=[]
    closedList=[]
    cost=0
    fringe  = Stack()
    node=[path, cost ,problem.getStartState()]
    fringe.push(node)
    while (1):
        if fringe.isEmpty():
            raise Exception, 'no solutiion'
        newState=fringe.pop()
        if problem.isGoalState(newState[2]):
            return newState[0]
        if newState[2] not in closedList:
            closedList.append(newState[2])
            for x in problem.getSuccessors(newState[2]):
                fringe.push([newState[0]+[str(x[1])],newState[1]+x[2],x[0]])

def getNodes(dsType, problem):
        if dsType == DataStructureType.STACK:
            from util import Stack
            nodes = Stack()
            nodes.push(Node([problem.getStartState()], [], 0, 0))
            return nodes
        elif dsType == DataStructureType.QUEUE:
            from util import Queue
            nodes = Queue()
            nodes.push(Node([problem.getStartState()], [], 0, 0))
            return nodes
        elif dsType == DataStructureType.PRIORITY_QUEUE:
            from util import PriorityQueue
            nodes =  PriorityQueue()
            nodes.push(Node([problem.getStartState()], [], 0,0),0)
            return nodes

def depthFirstSearch(problem):
    """
    Search the deepest nodes in the search tree first

    Your search algorithm needs to return a list of actions that reaches
    the goal.  Make sure to implement a graph search algorithm

    To get started, you might want to try some of these simple commands to
    understand the search problem that is being passed in:


    print "Start:", problem.getStartState()

    print "Is the start a goal?", problem.isGoalState(problem.getStartState())
    print "Start's successors:", problem.getSuccessors(problem.getStartState())
    """
    "*** YOUR CODE HERE ***"

    from util import Stack
    #: lista de nodos visitados
    closed = []
    #: pila que hace la funcion de frontera
    frontier = Stack()
    # Recogemos el primer estado, creamos un nodo y lo 
    # insertamos en la pila
    frontier.push(Node(problem.getStartState()))
    # iteramos hasta que no hayan nodos en la pila
    # o hayamos encontrado el objetivo
    while not frontier.isEmpty():
        #: siguiente nodo a expandir
        node = frontier.pop()
        # comprobamos si el estado actual nos cumple el objetivo
        if problem.isGoalState(node.state):
            # si lo cumple, salimos del bucle
            break

        if node.state not in closed:
            # insertamos el estado en la lista de visitados
            closed.append(node.state)
            # recuperamos los estados sucesores
            for successor in problem.getSuccessors(node.state):
                frontier.push(Node(
                                successor[0],
                                node,
                                successor[1],
                                    successor[2]))

    #: acciones para llegar al objetivo
    actions = []
    # recorremos mientras haya un action en el nodo previo
    while node.action:
        actions.append(node.action)
        node = node.previous
    #mostramos el resultado antes de devolverlo
    #print  actions[::-1]
    return actions[::-1]

def find_immediate_common_ancestor(root, value1, value2):
    """find_immediate_common_ancestor

    algorithm:
      in post-order, the stack holds all the ancestor node.
    record the 2 ancestor lists and compare them.
    """
    p = root
    #stack = Stack([], debug=True)
    stack = Stack([])
    last_visited = None
    count_found = 0
    while p or stack:
        while p:
            stack.append(p)
            p = p.left

        p = stack[-1]
        if not p.right or p.right == last_visited:
            stack.pop()
            #^#
            if p.value in (value1, value2):
                count_found += 1
                if count_found == 1:
                    parent_stack1 = stack[:]
                elif count_found == 2:
                    common_idx = -1
                    min_len = len(stack) < len(parent_stack1) and len(stack) or len(parent_stack1)
                    idx = 0
                    while idx < min_len:
                        if stack[idx] == parent_stack1[idx]:
                            common_idx = idx
                            idx += 1
                        else:
                            break
                    return stack[common_idx].value
            #$#
            last_visited = p
            p = None
        else:
            p = p.right

def inorder_traverse(root):
    """inorder traversal
    """
    stack = Stack([], debug=True)
    node = root

    while True:
        # push
        while node:
            stack.append(node)
            node = node.left

        if len(stack) == 0: break

        # pop
        node = stack.pop()

        yield node

        # next
        node = node.right

def depthFirstSearch(problem):
    """
    Search the deepest nodes in the search tree first.

    Your search algorithm needs to return a list of actions that reaches the
    goal. Make sure to implement a graph search algorithm.

    To get started, you might want to try some of these simple commands to
    understand the search problem that is being passed in:

    print "Start:", problem.getStartState()
    print "Is the start a goal?", problem.isGoalState(problem.getStartState())
    print "Start's successors:", problem.getSuccessors(problem.getStartState())
    """
    "*** YOUR CODE HERE ***"
    stateStack = Stack()

    state = problem.getStartState()
    state = [(state, "Stop", 0)]
    stateStack.push(state)

    while not problem.isGoalState(state[len(state) - 1][0]):
        state = stateStack.pop()
        successors = problem.getSuccessors(state[len(state) - 1][0])
        for successor in successors:
            if successor[0] not in [position[0] for position in state]:
                stateStack.push(state + [successor])
    return [direction[1] for direction in state]

def find_immediate_common_ancestor_5(root, value1, value2):
    """find_immediate_common_ancestor_5

    algorithm:
      pre-order traversal with value for each level
    """
    if not root:
        return

    ancestor, immediate_ancestor_level = {}, -1
    stack = Stack([(root, 0)])
    while stack:
        p, level = stack.pop()
        #^#
        ancestor[level] = p

        if p.value in (value1, value2):
            if immediate_ancestor_level == -1:
                immediate_ancestor_level = level - 1
            else:
                return ancestor[immediate_ancestor_level].value

        if immediate_ancestor_level > level - 1:
            immediate_ancestor_level = level - 1
        #$#
        if p.right:
            stack.append((p.right, level+1))
        if p.left:
            stack.append((p.left, level+1))

def depthFirstSearch(problem):
    """
    Search the deepest nodes in the search tree first
    [2nd Edition: p 75, 3rd Edition: p 87]

    Your search algorithm needs to return a list of actions that reaches
    the goal.  Make sure to implement a graph search algorithm
    [2nd Edition: Fig. 3.18, 3rd Edition: Fig 3.7].

    To get started, you might want to try some of these simple commands to
    understand the search problem that is being passed in:

    print "Start:", problem.getStartState()
    print "Is the start a goal?", problem.isGoalState(problem.getStartState())
    print "Start's successors:", problem.getSuccessors(problem.getStartState())
    """
    "*** YOUR CODE HERE ***"
    from util import Stack
    fringe = Stack()
    visited = set()
    path = Stack()
    start = problem.getStartState()
    visited.add(start)
    path.push(start)
    children = problem.getSuccessors(start)

    for child in children:
        fringe.push(child)
        ds = DFSRec(problem,fringe,visited,path)
        if ds != None:
            break

    pathToGoal = directions(ds)
    return pathToGoal

def depthFirstSearch(problem):
  """
  Search the deepest nodes in the search tree first
  [2nd Edition: p 75, 3rd Edition: p 87]
  
  Your search algorithm needs to return a list of actions that reaches
  the goal.  Make sure to implement a graph search algorithm 
  [2nd Edition: Fig. 3.18, 3rd Edition: Fig 3.7].
  
  To get started, you might want to try some of these simple commands to
  understand the search problem that is being passed in:
  
  print "Start:", problem.getStartState()
  print "Is the start a goal?", problem.isGoalState(problem.getStartState())
  print "Start's successors:", problem.getSuccessors(problem.getStartState())
  """
  "*** YOUR CODE HERE ***"
  print "the problem is ", problem
  from game import Directions
  s = Directions.SOUTH
  w = Directions.WEST
  n = Directions.NORTH
  e = Directions.EAST
  start = problem.getStartState()
  if problem.isGoalState(start):
    return []
  from util import Stack
  statesStack = Stack()
  exploredSet = set([start])
  tup = (start,[])
  statesStack.push(tup)
  while not statesStack.isEmpty():
    tup1 = statesStack.pop()
    state = tup1[0]
    path = tup1[1]
    if problem.isGoalState(state):
      return path
    successors = problem.getSuccessors(state)
    for succ in successors:
      coor = succ[0]
      move = succ[1]
      #cost = succ[2]
      tempPath = list(path)
      if not coor in exploredSet:
        exploredSet.add(coor)
        if move == 'North':
          tempPath.append(n)
        elif move == 'East':
          tempPath.append(e)
        elif move == 'South':
          tempPath.append(s)
        elif move == 'West':
          tempPath.append(w)
        statesStack.push((coor,tempPath))        
  return []