def depthFirstSearch(problem):
    stack, visited = [(problem.getStartState(), [])], []
    while stack:
        vertex, path = stack.pop()
        visited.append(vertex)

        if problem.isGoalState(vertex):
            return path
        else:
            successors = problem.getSuccessors(vertex)
            for successor in successors:
                nextVertex, action, cost = successor
                if nextVertex not in visited:
                    stack.append((nextVertex, path + [action]))
    return []

def breadthFirstSearch(problem):
    queue = util.Queue()
    queue.push( (problem.getStartState(),[]))
    visited = []

    while not queue.isEmpty() :
        node, actions = queue.pop()
        if (problem.isGoalState(node)):
            return actions
        if not node in visited:
            visited.append(node)
            for child, derection, cost  in problem.getSuccessors(node):
                queue.push((child,actions+[derection]))
    return []

def uniformCostSearch(problem):
    queue = util.PriorityQueue()
    queue.push((problem.getStartState(), [], 0), 0)
    visited = []

    while not queue.isEmpty():
        node, actions, cur_cost = queue.pop()

        if (problem.isGoalState(node)):
                return actions
        if not node in visited :
            visited.append(node)
            for child, direction, cost in problem.getSuccessors(node):
                queue.push((child, actions+[direction], cur_cost+cost), cur_cost+cost)
    return []


def aStarSearch(problem, heuristic=nullHeuristic):
    queue = util.PriorityQueue()
    queue.push((problem.getStartState(), [], 0),heuristic(problem.getStartState(),problem) )
    visited = []

    while not queue.isEmpty():
        node, actions, cur_cost = queue.pop()
        if (problem.isGoalState(node)):
                return actions
        if not node in visited:
            visited.append(node)
            for child, direction, cost in problem.getSuccessors(node):
                g= cur_cost + cost
                queue.push((child, actions+[direction], g),g+heuristic(child,problem) )
    return []