import random
from collections import deque


def generate_hex_maze(radius, seed=0):
    """Backwards-compatible wrapper that uses the iterative implementation."""
    return generate_hex_maze_iterative(radius, seed=seed)


def generate_hex_maze_iterative(radius, seed=0):
    """
    Generate a hexagonal maze using an explicit stack (iterative DFS) on axial coords.

    Args:
        radius (int): maximum radius (in hex steps) from the origin to include.

    Returns:
        dict: mapping (q, r) -> list of (dq, dr) neighbor offsets for open edges.
    """
    maze = {}
    visited = set()
    stack = [(0, 0)]
    visited.add((0, 0))
    dirs = [(1,0),(0,1),(-1,1),(-1,0),(0,-1),(1,-1)]
    rng = random.Random(seed) if seed else None
    while stack:
        q,r = stack[-1]
        directions = dirs[:]                    # ← fixed: copy before shuffle
        (rng.shuffle(directions) if rng is not None else random.shuffle(directions))
        moved = False
        for dq,dr in directions:
            nq,nr = q+dq,r+dr
            if (nq,nr) not in visited and max(abs(nq),abs(nr),abs(nq+nr)) <= radius:
                visited.add((nq,nr))
                stack.append((nq,nr))
                maze.setdefault((q,r),[]).append((dq,dr))
                maze.setdefault((nq,nr),[]).append((-dq,-dr))
                # occasional extra random connection (10%) to introduce loops and increase difficulty
                if (rng.random() if rng is not None else random.random()) < 0.1:
                    # prefer connecting to an already visited neighbor so we create a loop
                    extra_dirs = [d for d in dirs if d != (dq,dr)]
                    (rng.shuffle(extra_dirs) if rng is not None else random.shuffle(extra_dirs))
                    for edq,edr in extra_dirs:
                        enq,enr = q+edq, r+edr
                        # only connect to already visited neighbours to avoid creating isolated cells
                        if (enq,enr) in visited and (edq,edr) not in maze.get((q,r), []):
                            maze.setdefault((q,r),[]).append((edq,edr))
                            maze.setdefault((enq,enr),[]).append((-edq,-edr))
                            break
                moved = True
                break
        if not moved:
            stack.pop()
    # Ensure the starting hex has two additional neighbor offsets if possible.
    # This makes the maze entry/exit from the center more open and increases difficulty.
    # (If there are not enough valid neighbours within the radius, add as many as possible.)
    if (0, 0) not in maze:
        maze.setdefault((0, 0), [])
    # choose up to two directions not already open from the start
    available = [d for d in dirs if d not in maze.get((0, 0), []) and max(abs(d[0]), abs(d[1]), abs(d[0] + d[1])) <= radius]
    (rng.shuffle(available) if rng is not None else random.shuffle(available))
    for dq, dr in available[:2]:
        nq, nr = dq, dr
        # add reciprocal entries even if the neighbour wasn't previously in the maze
        if (dq, dr) not in maze.get((0, 0), []):
            maze.setdefault((0, 0), []).append((dq, dr))
            maze.setdefault((nq, nr), []).append((-dq, -dr))

    return maze


def solve_hex_maze(maze):
    """
    Solve a hex maze (produced by generate_hex_maze) using breadth-first search.

    Args:
        maze (dict): mapping (q, r) -> list of (dq, dr) neighbor offsets.

    Returns:
        list[tuple[int,int]]: sequence of axial coordinates from the origin to the
        farthest cell (heuristic goal) in the generated maze. Returns empty list
        for an empty maze.
    """
    if not maze:
        return []
    start = (0,0)
    end = max(maze, key=lambda p: abs(p[0])+abs(p[1])+abs(p[0]+p[1]))
    queue = deque([start])
    parent = {start: None}
    while queue:
        curr = queue.popleft()
        if curr == end:
            break
        for dq,dr in maze.get(curr,[]):
            neigh = (curr[0]+dq, curr[1]+dr)
            if neigh not in parent:
                parent[neigh] = curr
                queue.append(neigh)
    path = []
    at = end
    while at:
        path.append(at)
        at = parent.get(at)
    return path[::-1]