'''
CMSI 2130 - Classwork 2
Author: SOLUTION

Modify only this file as part of your submission, as it will contain all of the logic
necessary for implementing the breadth-first tree search that solves the basic maze
pathfinding problem.
'''

from queue import Queue
from maze_problem import *
from dataclasses import *

@dataclass
class SearchTreeNode:
    """
    SearchTreeNodes contain the following attributes to be used in generation of
    the Search tree:

    Attributes:
        player_loc (tuple[int, int]):
            The player's location in this node.
        action (str):
            The action taken to reach this node from its parent (or empty if the root).
        parent (Optional[SearchTreeNode]):
            The parent node from which this node was generated (or None if the root).
    """
    player_loc: tuple[int, int]
    action: str
    parent: Optional["SearchTreeNode"]
    
    def __str__(self) -> str:
        return "@: " + str(self.player_loc)

def _get_solution(node: "SearchTreeNode") -> list[str]:
    """
    Returns a solution (a sequence of str actions) from the given
    SearchTreeNode node, presumed to be a goal state

    Parameters:
        node (SearchTreeNode):
            A goal SearchTreeNode in the search tree

    Returns:
        list[str]:
            A solution to the problem: a sequence of actions leading from the initial
            state to the goal.
    """
    soln = []
    while node.parent is not None:
        soln.append(node.action)
        node = node.parent
    soln.reverse()
    return soln

def pathfind(problem: MazeProblem) -> Optional[list[str]]:
    """
    The main workhorse method of the package that performs breadth-first tree search to find the optimal
    sequence of actions that takes the agent from its initial state to the goal state in
    the given MazeProblem's maze, or determines that the problem is unsolvable.

    Parameters:
        problem (MazeProblem):
            The MazeProblem object constructed on the maze that is to be solved or determined
            unsolvable by this method.

    Returns:
        Optional[list[str]]:
            A solution to the problem: a sequence of actions leading from the 
            initial state to the goal. If no such solution is possible, returns None.
    """
    # Setup
    frontier: Queue["SearchTreeNode"] = Queue()
    
    # Search!
    frontier.put(SearchTreeNode(problem.get_initial_loc(), "", None))
    while not frontier.empty():
        # Get front node of priority queue
        expanding = frontier.get()
        
        # Generate new nodes on frontier
        transitions = problem.get_transitions(expanding.player_loc)
        for action, next_state in transitions.items():
            child_node = SearchTreeNode(next_state, action, expanding)
            
            # Test for goal state
            if child_node.player_loc == problem.get_goal_loc():
                return _get_solution(child_node)
            
            frontier.put(child_node)
        
    # No solution
    return None