"""Grid sizes, the location rule, and nested stage maps.

The location rule (both page sets use it)
-----------------------------------------
Every item lives at one point (v, u) of the unit square: v down, u across.
On any grid R x C it is drawn in the cell that contains that point:

    row = floor(v * R), col = floor(u * C)

So an item's place on every size is a function of its point alone: it never
moves from where it lives, and on any grid it is at most half a cell from its
point. Every button an item has, on every size, contains that one point.

Points are not free: an item lives in an *atom*, one rectangle of the common
refinement of the cell boundaries of every size in the ladder (all the
fractions k/R and k/C). An atom never straddles a cell boundary of any size,
so its centre is a safe point. (The cell centres of the largest grid alone are
not enough: going from 6x8 to 7x9 merges cells of 8x10 that 6x8 keeps apart,
so no layout on 8x10 centres can keep every size full.)

Stage maps
----------
An item's *stage* is the first ladder size at which it appears. A stage map is
valid when, at every size, no cell holds two items whose stages are at or
before that size: nothing that appeared at a smaller size is ever pushed out
at a larger one. When the number of items per stage equals the growth in
capacity between sizes, valid also means every cell of every size is filled.
"""

from __future__ import annotations

from dataclasses import dataclass
from fractions import Fraction
from functools import lru_cache


@dataclass(frozen=True, order=True)
class Size:
    rows: int
    cols: int

    @property
    def cells(self) -> int:
        return self.rows * self.cols

    @property
    def name(self) -> str:
        return f"{self.rows}x{self.cols}"

    @staticmethod
    def parse(text: str) -> "Size":
        r, c = text.lower().split("x")
        return Size(int(r), int(c))

    def __str__(self) -> str:
        return self.name


def place(point: tuple[float, float], size: Size) -> tuple[int, int]:
    """The cell (row, col) of `size` that contains `point` (v, u)."""
    v, u = point
    return min(int(v * size.rows), size.rows - 1), min(int(u * size.cols), size.cols - 1)


def centre(cell: tuple[int, int], size: Size) -> tuple[float, float]:
    """Normalised centre (v, u) of `cell` on `size`."""
    return (cell[0] + 0.5) / size.rows, (cell[1] + 0.5) / size.cols


def rect(cell: tuple[int, int], size: Size) -> tuple[float, float, float, float]:
    """The cell's area as (v0, v1, u0, u1)."""
    r, c = cell
    return r / size.rows, (r + 1) / size.rows, c / size.cols, (c + 1) / size.cols


def _breaks(ns: set[int]) -> list[Fraction]:
    pts = {Fraction(k, n) for n in ns for k in range(n + 1)}
    return sorted(pts)


class Ladder:
    """A ladder of grid sizes, and the atoms items may live in."""

    def __init__(self, sizes: list[Size]):
        self.sizes = sizes
        for a, b in zip(sizes, sizes[1:]):
            if not (a.rows <= b.rows and a.cols <= b.cols and a.cells < b.cells):
                raise ValueError(f"ladder must grow: {a} then {b}")
        vb = _breaks({s.rows for s in sizes})
        ub = _breaks({s.cols for s in sizes})
        self.v_intervals = list(zip(vb, vb[1:]))
        self.u_intervals = list(zip(ub, ub[1:]))
        # atom = (i, j): v interval i, u interval j; its point is the centre
        self.atoms = [(i, j) for i in range(len(self.v_intervals)) for j in range(len(self.u_intervals))]
        self.points = [
            (float((self.v_intervals[i][0] + self.v_intervals[i][1]) / 2), float((self.u_intervals[j][0] + self.u_intervals[j][1]) / 2))
            for i, j in self.atoms
        ]
        self.block = [[place(p, s) for p in self.points] for s in sizes]
        n = len(self.atoms)
        # last_same[a][b]: the last ladder index at which atoms a and b fall
        # in the same cell (-1 if never). Stored per pair in a flat list.
        self._last = [-1] * (n * n)
        for k in range(len(sizes)):
            groups: dict[tuple[int, int], list[int]] = {}
            for a, cell in enumerate(self.block[k]):
                groups.setdefault(cell, []).append(a)
            for members in groups.values():
                for x in members:
                    base = x * n
                    for y in members:
                        self._last[base + y] = k
        self.n = n

    def last_same(self, a: int, b: int) -> int:
        return self._last[a * self.n + b]

    def capacity_steps(self) -> list[int]:
        caps = [s.cells for s in self.sizes]
        return [caps[0]] + [b - a for a, b in zip(caps, caps[1:])]

    def compatible(self, a: int, sa: int, b: int, sb: int) -> bool:
        """Can atoms a (stage sa) and b (stage sb) both hold an item?"""
        return a != b and self._last[a * self.n + b] < max(sa, sb)

    def atom_of(self, point: tuple[float, float]) -> int:
        v, u = Fraction(point[0]).limit_denominator(10_000), Fraction(point[1]).limit_denominator(10_000)
        i = next(i for i, (lo, hi) in enumerate(self.v_intervals) if lo < v < hi)
        j = next(j for j, (lo, hi) in enumerate(self.u_intervals) if lo < u < hi)
        return i * len(self.u_intervals) + j


def check_stages(sizes: list[Size], items: dict[str, tuple[tuple[float, float], int]], full: bool) -> list[str]:
    """Problems with items {key: (point, stage index)}; empty when valid."""
    problems = []
    for k, size in enumerate(sizes):
        seen: dict[tuple[int, int], str] = {}
        for key, (point, stage) in items.items():
            if stage <= k:
                cell = place(point, size)
                if cell in seen:
                    problems.append(f"{size}: {seen[cell]!r} and {key!r} both fall in cell {cell}")
                seen[cell] = key
        if full and len(seen) != size.cells:
            problems.append(f"{size}: {size.cells - len(seen)} cell(s) empty")
    return problems


@lru_cache(maxsize=None)
def ladder_for(names: tuple[str, ...]) -> Ladder:
    return Ladder([Size.parse(n) for n in names])


def fmt_point(p: tuple[float, float]) -> list[float]:
    return [round(p[0], 5), round(p[1], 5)]