# search.py
# ---------
# Licensing Information:  You are free to use or extend these projects for
# educational purposes provided that (1) you do not distribute or publish
# solutions, (2) you retain this notice, and (3) you provide clear
# attribution to UC Berkeley, including a link to http://ai.berkeley.edu.
# 
# Attribution Information: The Pacman AI projects were developed at UC Berkeley.
# The core projects and autograders were primarily created by John DeNero
# (denero@cs.berkeley.edu) and Dan Klein (klein@cs.berkeley.edu).
# Student side autograding was added by Brad Miller, Nick Hay, and
# Pieter Abbeel (pabbeel@cs.berkeley.edu).


"""
In search.py, you will implement generic search algorithms which are called by
Pacman agents (in searchAgents.py).
"""

import util
import sys
import copy

class SearchProblem:
    """
    This class outlines the structure of a search problem, but doesn't implement
    any of the methods (in object-oriented terminology: an abstract class).

    You do not need to change anything in this class, ever.
    """

    def getStartState(self):
        """
        Returns the start state for the search problem.
        """
        util.raiseNotDefined()

    def goalTest(self, state):
        """
          state: Search state

        Returns True if and only if the state is a valid goal state.
        """
        util.raiseNotDefined()

    def getActions(self, state):
        """
        Given a state, returns available actions.
        Returns a list of actions
        """        
        util.raiseNotDefined()

    def getResult(self, state, action):
        """
        Given a state and an action, returns resulting state.
        """
        util.raiseNotDefined()

    def getCost(self, state, action):
        """
        Given a state and an action, returns step cost, which is the incremental cost 
        of moving to that successor.
        """
        util.raiseNotDefined()

    def getCostOfActions(self, actions):
        """
         actions: A list of actions to take

        This method returns the total cost of a particular sequence of actions.
        The sequence must be composed of legal moves.
        """
        util.raiseNotDefined()

class Node:
    """
    Search node object for your convenience.

    This object uses the state of the node to compare equality and for its hash function,
    so you can use it in things like sets and priority queues if you want those structures
    to use the state for comparison.

    Example usage:
    >>> S = Node("Start", None, None, 0)
    >>> A1 = Node("A", S, "Up", 4)
    >>> B1 = Node("B", S, "Down", 3)
    >>> B2 = Node("B", A1, "Left", 6)
    >>> B1 == B2
    True
    >>> A1 == B2
    False
    >>> node_list1 = [B1, B2]
    >>> B1 in node_list1
    True
    >>> A1 in node_list1
    False
    """
    def __init__(self, state, parent, action, path_cost):
        self.state = state
        self.parent = parent
        self.action = action
        self.path_cost = path_cost

    def __hash__(self):
        return hash(self.state)

    def __eq__(self, other):
        return self.state == other.state

    def __ne__(self, other):
        return self.state != other.state


def tinyMazeSearch(problem):
    """
    Returns a sequence of moves that solves tinyMaze.  For any other maze, the
    sequence of moves will be incorrect, so only use this for tinyMaze.
    """
    from game import Directions
    s = Directions.SOUTH
    w = Directions.WEST
    return  [s, s, w, s, w, w, s, w]

def breadthFirstSearch(problem):
    """
    Search the shallowest nodes in the search tree first.

    You are not required to implement this, but you may find it useful for Q5.
    """
    "*** YOUR CODE HERE ***"
    util.raiseNotDefined()

def nullHeuristic(state, problem=None):
    """
    A heuristic function estimates the cost from the current state to the nearest
    goal in the provided SearchProblem for a in actions:
    This heuristic is trivial.
    """

def iterativeDeepeningSearch(problem: SearchProblem):

    """
    index = 1
    queue = list()
    visited_Nodes = list()
    goal_Actions = list()

    def depthFirstSearchHelper(current_Node, current_depth, max_depth):
        total_Nodes = 0
        if (problem.goalTest(current_Node.state)):
            if (not(current_Node.state == problem.getStartState())):
                goal_Actions.insert(0, current_Node.action)
            return True

        if current_depth > max_depth:
            return False
        
        current_Node_Actions = problem.getActions(current_Node.state)

        for action in current_Node_actions:
            result = problem.getResult(current_Node.state, action)

            if result not in visited_Nodes:
                new_Node = Node(result, current_Node, a, problem.getCost(current_Node.state, 1))
                visited_Nodes.append(current_Node)
                queue.insert(0, new_Node)
                total_Nodes += 1

        for node in range(total_Nodes):
            if (depthFirstSearchHelper(queue.pop(0), current_depth + 1, max_depth)):
                if (current_Node.state != problem.getStartState()):
                    goal_Actions.insert(0, current_Node.action)
                return True

        return False

    while (~depthFirstSearchHelper(problem.getStartState(), 1, index)):
        index += 1
        visited_Nodes.clear()
        depthFirstSearchHelper(problem.getStartState(), 1, index)

    print(goal_Actions)
    return goal_Actions

    Perform DFS with increasingly larger depth. Begin with a depth of 1 and increment depth by 1 at every step.

    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.goalTest(problem.getStartState()))
    print("Actions from start state:", problem.getActions(problem.getStartState()))

    Then try to print the resulting state for one of those actions
    by calling problem.getResult(problem.getStartState(), one_of_the_actions)
    or the resulting cost for one of these actions
    by calling problem.getCost(problem.getStartState(), one_of_the_actions)
    """

    def depthFirstSearch(problem, max_depth):
        global visited_Nodes #variables that span through all iterations of nodes
        global node_queue
        global node_Actions
        visited_Nodes = list()
        node_queue = list()
        node_Actions = list()
        return depthFirstSearchHelper(Node(problem.getStartState(), None, None, 0), 1, max_depth)

    def depthFirstSearchHelper(current_Node, current_depth, max_depth):
        if problem.goalTest(current_Node.state):
            if current_Node.state != problem.getStartState():
                node_Actions.append(current_Node.action)
            return True
        if current_depth > max_depth:
            return False
            
        node_Counter = 0
        allActions = problem.getActions(current_Node.state)
        for action in allActions:
            child_Node = problem.getResult(current_Node.state, action)
            if child_Node not in visited_Nodes:
                node_Counter += 1
                new_Node = Node(child_Node, current_Node, action, problem.getCost(current_Node.state, action))
                node_queue.insert(0, new_Node)
                visited_Nodes.append(child_Node)

        for every_node in range(0, node_Counter):
            front_Node = node_queue.pop(0)
            if depthFirstSearchHelper(front_Node, current_depth + 1, max_depth):
                if current_Node.state != problem.getStartState():
                    node_Actions.insert(0, current_Node.action)
                return True
        return False

    max_depth_index = 1
    while not depthFirstSearch(problem, max_depth_index):
        visited_Nodes.clear() #clear lists
        node_queue.clear()
        node_Actions.clear()
        max_depth_index += 1
    return node_Actions


def aStarSearch(problem, heuristic=nullHeuristic):
    node_queue = list()
    visited_Nodes = list()
    node_Actions = list()

    def actions_to_goal(current_Node):
        if current_Node.state != problem.getStartState():
            goal_Actions.insert(0, current_Node.action)
            actions_to_goal(current_Node.parent)
        return True

    def aStarHelper(current_Node, heuristic):
        if problem.goalTest(current_Node.state):
            if current_Node.state != problem.getStartState():
                node_Actions.insert(0, current_Node.action)
                actions_to_goal(current_Node)
            return True

        allActions = problem.getActions(current_Node.state)
        for action in allActions:
            child_Node = problem.getResult(current_Node.state, action)
            if child_Node not in visited_Nodes:
                new_Node = Node(child_Node, current_Node, action, problem.getCost(current_Node.state,
                action)+current_Node.path_cost)
                node_queue.append(new_Node)
                visited_Nodes.append(child_Node)

            for i in range (len(node_queue)):
                if node_queue[i].state == child_Node:
                    if problem.getCost(current_Node.state, action) + current_Node.path_cost < node_queue[i].path_cost:
                        node_queue[i].path_cost = current_Node.path_cost + problem.getCost(current_Node.state, action)
                        node_queue[i].action = action
                        node_queue[i].parent = current_Node

        min_path = heuristic(node_queue[0].state, problem) + node_queue[0].path_cost
        min_node_index = 0
        for index in (len(node_queue)):
            if heuristic(node_queue[index].state, problem) + node_queue[index].path_cost < min_path:
                min_path = heuristic(node_queue[index].state, problem) + node_queue[index].path_cost
                min_node_index = index

        front = node_queue.pop(min_node_index)
        return aStarHelper(front, heuristic)

    aStarHelper(Node(problem.getStartState(), None, None, 0), heuristic)
"""
    
    src = Node(problem.getStartState(), None, None, 0)

    possible = list()
    visisted = list()
    instructions = list()

    visited.append(src.state)
"""

# Abbreviations
bfs = breadthFirstSearch
astar = aStarSearch
ids = iterativeDeepeningSearch
