solver.py

from typing import List, Tuple, Optional
from collections import deque
from typing import Deque, Set


class MazeSolver:
    """solve mazes and find shortest paths"""

    def __init__(
        self, grid: List[List[int]],
        entry: Tuple[int, int],
        exit: Tuple[int, int]
    ) -> None:
        """Initialize the solver"""
        self.grid = grid
        self.height = len(grid)
        self.width = len(grid[0]) if grid else 0
        self.entry = entry
        self.exit = exit

    def solve(self) -> Optional[List[str]]:
        """
        Find shortest path from entry to exit
        Returns:
            List of directions ('N', 'E', 'S', 'W') or None if no path exists
        """

        if not self.grid:
            return None

        queue: Deque[Tuple[Tuple[int, int], List[str]]] = deque(
                [(self.entry, [])]
            )
        visited: Set[Tuple[int, int]] = {self.entry}

        while queue:
            (x, y), path = queue.popleft()

            if (x, y) == self.exit:
                return path

            cell = self.grid[y][x]

            if not (cell & 1) and y > 0 and (x, y - 1) not in visited:
                visited.add((x, y - 1))
                queue.append(((x, y - 1), path + ["N"]))

            if (not (cell & 2)
                    and x < self.width - 1
                    and (x + 1, y) not in visited):

                visited.add((x + 1, y))
                queue.append(((x + 1, y), path + ["E"]))

            if (not (cell & 4)
                    and y < self.height - 1
                    and (x, y + 1) not in visited):

                visited.add((x, y + 1))
                queue.append(((x, y + 1), path + ["S"]))

            if not (cell & 8) and x > 0 and (x - 1, y) not in visited:
                visited.add((x - 1, y))
                queue.append(((x - 1, y), path + ["W"]))

        return None

    def get_path_cells(
            self, path: Optional[List[str]]
            ) -> List[Tuple[int, int]]:
        """
        Convert path directions to cell coordinates.

        Args:
            path: List of directions

        Returns:
            List of (x, y) coordinates along the path
        """

        if not path:
            return [self.entry]

        cells = [self.entry]
        x, y = self.entry

        for direction in path:
            if direction == "N":
                y -= 1
            elif direction == "E":
                x += 1
            elif direction == "S":
                y += 1
            elif direction == "W":
                x -= 1
            cells.append((x, y))

        return cells