"""Triangle-grid maze helpers.

This module implements a simple triangular-grid maze generator (randomized
depth-first search), a BFS solver and a drawing helper that renders the
triangular tiling with walls and optional thin grey outlines for doors.

Maze representation:
    dict mapping (x,y) -> list of (dx,dy) neighbor offsets that are open.

Coordinates:
    x: column index, 0..w-1
    y: row index, 0..h-1

Triangle orientation alternates with parity: up when (x+y) % 2 == 0,
otherwise down.
"""
import random
from collections import deque
from .draw import draw_tri_maze as _draw_tri


def _neighbor_offsets(x, y, w, h):
    """Return valid neighbor offsets for triangle at (x,y) based on orientation."""
    up = ((x + y) % 2 == 0)
    if up:
        candidates = [(-1, 0), (1, 0), (0, 1)]
    else:
        candidates = [(-1, 0), (1, 0), (0, -1)]
    valid = []
    for dx, dy in candidates:
        nx, ny = x + dx, y + dy
        if 0 <= nx < w and 0 <= ny < h:
            valid.append((dx, dy))
    return valid


def generate_tri_maze(w, h=None, seed=0):
    """Generate a triangular maze using randomized DFS.

    Args:
        w (int): number of columns.
        h (int|None): number of rows (if None, equals w).

    Returns:
        dict: mapping (x,y) -> list of neighbor offsets (dx,dy) that are open.
    """
    if h is None:
        h = w
    # initialize empty adjacency
    maze = {(x, y): [] for x in range(w) for y in range(h)}
    rng = random.Random(seed) if seed else None
    visited = set()

    stack = [(0, 0)]
    visited.add((0, 0))

    while stack:
        x, y = stack[-1]
        offs = _neighbor_offsets(x, y, w, h)
        # filter to unvisited neighbours
        nbrs = [(dx, dy) for dx, dy in offs if (x + dx, y + dy) not in visited]
        if nbrs:
            dx, dy = (rng.choice(nbrs) if rng is not None else random.choice(nbrs))
            nx, ny = x + dx, y + dy
            # carve passage both ways (store offsets)
            maze[(x, y)].append((dx, dy))
            maze[(nx, ny)].append((-dx, -dy))
            visited.add((nx, ny))
            stack.append((nx, ny))
            # occasional extra random connection (10%) to introduce loops and increase difficulty
            if (rng.random() if rng is not None else random.random()) < 0.1:
                extra_offs = [o for o in offs if o != (dx, dy)]
                (rng.shuffle(extra_offs) if rng is not None else random.shuffle(extra_offs))
                for edx, edy in extra_offs:
                    enx, eny = x + edx, y + edy
                    # connect only to already visited neighbours to avoid isolating cells
                    if (enx, eny) in visited and (edx, edy) not in maze.get((x, y), []):
                        maze[(x, y)].append((edx, edy))
                        maze[(enx, eny)].append((-edx, -edy))
                        break
        else:
            stack.pop()
    # ensure the starting triangle (0,0) has one additional neighbour offset if possible
    start_offs = _neighbor_offsets(0, 0, w, h)
    candidates = [o for o in start_offs if o not in maze.get((0, 0), [])]
    if candidates:
        edx, edy = (rng.choice(candidates) if rng is not None else random.choice(candidates))
        nx, ny = 0 + edx, 0 + edy
        if (edx, edy) not in maze.get((0, 0), []):
            maze[(0, 0)].append((edx, edy))
            maze[(nx, ny)].append((-edx, -edy))

    return maze


def generate_tri_maze_iterative(w, h=None, seed=0):
    """Alias for generate_tri_maze; generation is already iterative.

    Kept for API symmetry with other generators.
    """
    return generate_tri_maze(w, h, seed=seed)


def solve_tri_maze(maze):
    """Solve a triangular maze returning a path from start to end.

    Start is assumed at (0,0). End is chosen as the cell with the maximum
    x+y (bottom-right-like) so it aligns with the drawing and CLI examples.

    Returns:
        list[(x,y)]: path from start to end (inclusive) or empty list if none.
    """
    if not maze:
        return []
    start = (0, 0)
    end = max(maze, key=lambda p: p[0] + p[1])

    q = deque([start])
    parent = {start: None}
    while q:
        cur = q.popleft()
        if cur == end:
            break
        x, y = cur
        for dx, dy in maze.get((x, y), []):
            nx, ny = x + dx, y + dy
            if (nx, ny) not in parent:
                parent[(nx, ny)] = (x, y)
                q.append((nx, ny))
    if end not in parent:
        return []
    # reconstruct path
    path = []
    at = end
    while at is not None:
        path.append(at)
        at = parent.get(at)
    return path[::-1]