from __future__ import annotations

from typing import Iterable


def split_lines(board: str) -> list[str]:
    return board.replace("\r", "").split("\n")


def pad_lines(lines: Iterable[str], width: int) -> list[str]:
    return [line.ljust(width) for line in lines]


def join_grid(grid: list[list[str]]) -> str:
    return "\n".join("".join(row) for row in grid)


def _parse_loopy(problem_ascii: str) -> tuple[list[str], list[tuple[int, int]], list[tuple[int, int]]]:
    lines = split_lines(problem_ascii)
    rows = max(0, (len(lines) - 3) // 2)
    cols = max(0, ((len(lines[0]) if lines else 0) - 3) // 2)
    horizontal_edges: list[tuple[int, int]] = []
    vertical_edges: list[tuple[int, int]] = []

    for row in range(rows + 1):
        for col in range(cols):
            horizontal_edges.append((1 + 2 * row, 2 + 2 * col))

    for row in range(rows):
        for col in range(cols + 1):
            vertical_edges.append((2 + 2 * row, 1 + 2 * col))

    return lines, horizontal_edges, vertical_edges


def _decorated_loopy_dimensions(problem_ascii: str) -> tuple[int, int]:
    puzzle_lines, _, _ = _parse_loopy(problem_ascii)
    width = len(puzzle_lines[0]) if puzzle_lines else 0
    height = len(puzzle_lines)
    return width, height


def _is_compact_loopy_board(problem_ascii: str, board_ascii: str) -> bool:
    lines = split_lines(board_ascii)
    decorated_width, decorated_height = _decorated_loopy_dimensions(problem_ascii)
    compact_width = max(0, decorated_width - 2)
    compact_height = max(0, decorated_height - 2)
    return (
        len(lines) == compact_height
        and all(len(line) <= compact_width for line in lines)
        and compact_width > 0
        and compact_height > 0
    )


def _expand_compact_loopy_board(problem_ascii: str, board_ascii: str) -> str:
    puzzle_lines, _, _ = _parse_loopy(problem_ascii)
    decorated_width, _ = _decorated_loopy_dimensions(problem_ascii)
    compact_lines = pad_lines(split_lines(board_ascii), max(0, decorated_width - 2))
    grid = [list(line) for line in pad_lines(puzzle_lines, decorated_width)]

    for row_idx, line in enumerate(compact_lines, start=1):
        if row_idx >= len(grid) - 1:
            break
        for col_idx, char in enumerate(line, start=1):
            if col_idx >= len(grid[row_idx]) - 1:
                break
            grid[row_idx][col_idx] = char

    return join_grid(grid)


def normalize_loopy_board(problem_ascii: str, board_ascii: str) -> str:
    puzzle_lines, horizontal_edges, vertical_edges = _parse_loopy(problem_ascii)
    width = len(puzzle_lines[0]) if puzzle_lines else 0
    if _is_compact_loopy_board(problem_ascii, board_ascii):
        board_ascii = _expand_compact_loopy_board(problem_ascii, board_ascii)
    grid = [list(line) for line in pad_lines(split_lines(board_ascii), width)]
    if not grid:
        grid = [list(line) for line in pad_lines(puzzle_lines, width)]

    # A submitted board with the wrong number of rows/columns must not cause an
    # IndexError below; pad to the decorated puzzle's dimensions so edge lookups
    # always land inside the grid (a too-small/misshapen board simply stays blank
    # in the missing cells and verifies as not solved).
    height = len(puzzle_lines)
    while len(grid) < height:
        grid.append([])
    for grid_row in grid:
        if len(grid_row) < width:
            grid_row.extend(" " * (width - len(grid_row)))

    for row, col in horizontal_edges:
        current = grid[row][col]
        if current != "-":
            grid[row][col] = "x"

    for row, col in vertical_edges:
        current = grid[row][col]
        if current != "|":
            grid[row][col] = "x"

    return join_grid(grid)


def compact_loopy_board(problem_ascii: str, board_ascii: str) -> str:
    normalized = normalize_loopy_board(problem_ascii, board_ascii)
    lines = split_lines(normalized)
    if len(lines) <= 2:
        return normalized
    return "\n".join(line[1:-1] for line in lines[1:-1])


def _parse_pattern_rows(board_ascii: str) -> tuple[list[str], list[str], list[str]]:
    lines = split_lines(board_ascii)
    clue_lines: list[str] = []
    content_lines: list[str] = []
    border_lines: list[str] = []

    grid_started = False
    for line in lines:
        if "|" in line:
            grid_started = True
            content_lines.append(line)
        elif "+" in line and "-" in line:
            if grid_started:
                border_lines.append(line)
            else:
                clue_lines.append(line)
        else:
            clue_lines.append(line)

    return clue_lines, content_lines, border_lines


def normalize_pattern_board(board_ascii: str) -> str:
    clue_lines, content_lines, border_lines = _parse_pattern_rows(board_ascii)
    if not content_lines:
        return board_ascii

    normalized: list[str] = [*clue_lines]
    border_iter = iter(border_lines)

    for content in content_lines:
        pieces = content.split("|")
        if len(pieces) < 3:
            normalized.append(content)
            continue
        next_pieces = [pieces[0]]
        for cell in pieces[1:-1]:
            next_pieces.append(".." if cell == "  " else cell)
        next_pieces.append(pieces[-1])
        normalized.append("|".join(next_pieces))
        try:
            normalized.append(next(border_iter))
        except StopIteration:
            pass

    return "\n".join(normalized)


def normalize_board_for_display(*, puzzle_type: str, problem_ascii: str, board_ascii: str) -> str:
    if puzzle_type == "loopy":
        return normalize_loopy_board(problem_ascii, board_ascii)
    if puzzle_type == "pattern":
        return normalize_pattern_board(board_ascii)
    return board_ascii


def normalize_board_for_submission(*, puzzle_type: str, problem_ascii: str, board_ascii: str) -> str:
    if puzzle_type == "loopy":
        return compact_loopy_board(problem_ascii, board_ascii)
    if puzzle_type == "pattern":
        return normalize_pattern_board(board_ascii)
    return board_ascii