tilezz 0.2.0

//! Rep-tile screen: does a tile tile a *scaled-up copy of itself*?
//!
//! A tile `T` is a **rep-tile** of order `m` when `m` copies of `T` assemble
//! into one big tile similar to `T`. If the big copy is scaled by a linear
//! factor `k` (every side `k` times longer), its area is `k^2` times larger, so
//! the number of unit copies is forced: `m = k^2`. So "rep-tile at scale `k`"
//! means: exactly `k^2` copies of `T` (rotated and translated -- single
//! chirality, matching the rest of this crate) exactly tile the `k`-scaled `T`.
//!
//! # The k-scaled region
//!
//! In the turn-sequence encoding a straight step is a `0` turn, so scaling every
//! unit edge to length `k` is just interspersing `k-1` zeros after each turn:
//! a hexagon `[2,2,2,2,2,2]` at `k=2` becomes `[2,0,2,0,2,0,2,0,2,0,2,0]`. The
//! angle sum is unchanged (zeros contribute nothing), so it still closes into a
//! simple polygon -- the target region `R` with `area(R) = k^2 * area(T)`.
//!
//! # The fill (sound AND complete)
//!
//! Unlike surroundability / periodicity (finite windows can't decide those),
//! this is a *fixed* region filled by a *fixed* count, so exhaustive
//! backtracking terminates: a "yes" is a witnessed tiling and a "no" is a
//! **proof** that no scale-`k` rep-tiling exists (within the orientation-
//! preserving model). The search grows the covered region by edge-gluing:
//!
//! - Maintain the boundary of the uncovered region as a set of directed unit
//!   edges (uncovered on the left). Placing a copy adds its edges reversed,
//!   cancelling the shared ones; the region is exactly filled iff the boundary
//!   set empties.
//! - Each step covers the *canonical* (lowest-leftmost) uncovered edge -- this
//!   both guarantees completeness (that edge must be covered by someone) and
//!   kills permutation blow-up (each tiling is reached in one order).
//! - A candidate placement is one of the `<= n` copies whose edge lands on the
//!   canonical edge; it is kept only if it stays inside `R` (containment) and
//!   overlaps no placed copy. Both tests are exact ring arithmetic.
//!
//! The lattice does the heavy lifting on soundness: every vertex is a ring
//! point and every edge is a unit vector, so two unit edges on a line are
//! identical or disjoint -- never partially overlapping. Hence the fill is
//! edge-to-edge at unit granularity and stays exact even for rep-tilings with
//! polygon-level T-junctions.

use std::collections::{HashMap, HashSet};

use serde::{Deserialize, Serialize};

use crate::classify::grow::{capture_placement, replay_placements};
use crate::cyclotomic::IsRing;
use crate::cyclotomic::geometry::{
    PointLocation, cmp_xy, intersect_unit_segments, point_in_polygon,
};
use crate::geom::iso::{Iso, dir_of_unit};
use crate::geom::matches::PatchMatch;
use crate::geom::patch::{BasicPatch, boundary_vertices};
use crate::geom::rat::Rat;
use crate::geom::tileset::TileSet;
use crate::stringmatch::canonical_rotation;

/// The `k`-scaled turn word: intersperse `k-1` zeros after each turn, so every
/// unit edge becomes `k` collinear unit steps.
fn scaled_seq(seq: &[i8], k: usize) -> Vec<i8> {
    let mut out = Vec::with_capacity(seq.len() * k);
    for &t in seq {
        out.push(t);
        out.extend(std::iter::repeat_n(0, k - 1)); // straight run: k-1 collinear steps
    }
    out
}

/// The placement whose base edge `f` runs *parallel* onto the directed edge
/// `p -> q` (`base[f] -> p`, `base[f+1] -> q`). A CCW copy placed this way sits
/// on the left of `p -> q` -- the uncovered side of a frontier edge.
fn mate<T: IsRing>(base: &[T], f: usize, p: T, q: T) -> Option<Iso<T>> {
    let n = base.len();
    let src = dir_of_unit::<T>(base[(f + 1) % n] - base[f])?;
    let dst = dir_of_unit::<T>(q - p)?;
    Some(Iso::carrying(base[f], src, p, dst))
}

/// Exact test: do the interiors of two placed copies (given by their vertex
/// polygons) overlap? Adjacent copies sharing a full edge are disjoint; overlap
/// shows up either as a proper edge crossing or as a vertex strictly inside the
/// other (the lattice rules out partial collinear overlap).
fn interiors_disjoint<T: IsRing>(a: &[T], b: &[T]) -> bool {
    let (na, nb) = (a.len(), b.len());
    for i in 0..na {
        let ea = (a[i], a[(i + 1) % na]);
        for j in 0..nb {
            let eb = (b[j], b[(j + 1) % nb]);
            if intersect_unit_segments(&ea, &eb) {
                return false;
            }
        }
    }
    !a.iter()
        .any(|v| point_in_polygon(v, b) == PointLocation::Inside)
        && !b
            .iter()
            .any(|v| point_in_polygon(v, a) == PointLocation::Inside)
}

/// Add directed edge `x -> y` to a frontier edge-set, cancelling an opposing
/// `y -> x` (a now-interior shared edge). The frontier empties exactly when the
/// placed copies tile the region with no gap or overlap.
fn add_edge<T: IsRing>(f: &mut HashMap<(T, T), i32>, x: T, y: T) {
    if let Some(c) = f.get_mut(&(y, x)) {
        *c -= 1;
        if *c == 0 {
            f.remove(&(y, x));
        }
    } else {
        *f.entry((x, y)).or_insert(0) += 1;
    }
}

/// Is a placed copy fully inside the region? Every vertex in the closure of the
/// region, and no edge crossing the region boundary.
///
/// This is a search PRUNE, not the soundness gate: the fill's real guarantee is
/// `frontier` cancelling to empty at exactly `k*k` disjoint copies (a leaked
/// copy would leave uncancelled outer edges, so it can never reach that). So the
/// one theoretical gap here -- a reflex region vertex strictly inside a copy
/// whose edges only endpoint-touch the boundary, which the unit lattice makes
/// unreachable anyway -- cannot produce a false accept.
fn contained_in<T: IsRing>(poly: &[T], region: &[T], redges: &[(T, T)]) -> bool {
    if poly
        .iter()
        .any(|v| point_in_polygon(v, region) == PointLocation::Outside)
    {
        return false;
    }
    let m = poly.len();
    (0..m).all(|i| {
        let e = (poly[i], poly[(i + 1) % m]);
        !redges.iter().any(|re| intersect_unit_segments(&e, re))
    })
}

/// The turn sequence of the OUTER boundary of a union of CCW copies, if they
/// leave a single simple loop of exactly `expected` unit edges (no gap, each
/// boundary edge covered once). `None` otherwise -- a gap leaves extra inner
/// loops, an overlap leaves doubled edges. Frame-independent (works from the
/// placements alone), so it verifies a rep-tiling wherever the patch sits.
fn union_boundary_seq<T: IsRing>(polys: &[Vec<T>], expected: usize) -> Option<Vec<i8>> {
    let mut boundary: HashMap<(T, T), i32> = HashMap::new();
    for poly in polys {
        let m = poly.len();
        for i in 0..m {
            add_edge(&mut boundary, poly[i], poly[(i + 1) % m]);
        }
    }
    if boundary.len() != expected {
        return None;
    }
    // Each uncancelled edge exactly once, one successor per vertex (a simple loop).
    let mut next: HashMap<T, T> = HashMap::with_capacity(expected);
    for (&(a, b), &c) in &boundary {
        if c != 1 || next.insert(a, b).is_some() {
            return None;
        }
    }
    let &start = next.keys().next()?;
    let mut verts = Vec::with_capacity(expected);
    let mut cur = start;
    loop {
        verts.push(cur);
        cur = *next.get(&cur)?;
        if cur == start {
            break;
        }
        if verts.len() > expected {
            return None;
        }
    }
    if verts.len() != expected {
        return None; // a single loop didn't cover every edge -- a gap split the boundary
    }
    let h = T::turn() / 2;
    let mut seq = Vec::with_capacity(expected);
    for i in 0..expected {
        let prev = dir_of_unit::<T>(verts[i] - verts[(i + expected - 1) % expected])?;
        let cur = dir_of_unit::<T>(verts[(i + 1) % expected] - verts[i])?;
        let raw = (cur - prev).rem_euclid(T::turn());
        seq.push(if raw > h { raw - T::turn() } else { raw });
    }
    Some(seq)
}

/// Do two turn words describe the same cyclic sequence (equal up to a rotation
/// of the starting vertex)? Compares lex-min canonical rotations (Booth O(n)).
fn cyclic_eq(a: &[i8], b: &[i8]) -> bool {
    a.len() == b.len() && canonical_rotation(a) == canonical_rotation(b)
}

/// Backtracking state for filling one region with copies of one base tile.
struct Filler<'a, T: IsRing> {
    base: &'a [T],
    n: usize,
    region: &'a [T],
    redges: &'a [(T, T)],
    target: usize,
    placed: Vec<Iso<T>>,
    polys: Vec<Vec<T>>,
    frontier: HashMap<(T, T), i32>,
    /// Node budget: `search` bails once `nodes` exceeds it. An unbudgeted proof
    /// (`reptile_at`) uses `usize::MAX`; the screen caps it.
    budget: usize,
    nodes: usize,
}

impl<T: IsRing> Filler<'_, T> {
    fn search(&mut self) -> bool {
        self.nodes += 1;
        if self.nodes > self.budget {
            return false; // budget exhausted -- caller treats a None here as inconclusive
        }
        if self.frontier.is_empty() {
            return self.placed.len() == self.target;
        }
        if self.placed.len() >= self.target {
            return false; // budget spent but region not closed -- dead
        }
        // Canonical uncovered edge: lowest-leftmost. Forces a single fill order.
        let &(p, q) = self
            .frontier
            .keys()
            .min_by(|a, b| cmp_xy(&a.0, &b.0).then_with(|| cmp_xy(&a.1, &b.1)))
            .unwrap();
        for f in 0..self.n {
            let Some(g) = mate(self.base, f, p, q) else {
                continue;
            };
            if self
                .placed
                .iter()
                .any(|h| h.rot == g.rot && h.shift == g.shift)
            {
                continue; // duplicate placement
            }
            let poly = g.tile(self.base);
            if !contained_in(&poly, self.region, self.redges) {
                continue;
            }
            if self.polys.iter().any(|pp| !interiors_disjoint(&poly, pp)) {
                continue;
            }
            let saved = self.frontier.clone();
            let m = poly.len();
            for i in 0..m {
                add_edge(&mut self.frontier, poly[(i + 1) % m], poly[i]);
            }
            self.placed.push(g);
            self.polys.push(poly);
            if self.search() {
                return true;
            }
            self.polys.pop();
            self.placed.pop();
            self.frontier = saved;
        }
        false
    }
}

/// The shared fill: tile the `k`-scaled region with `k*k` copies within a node
/// `budget`. Returns the witness (if found) and whether the budget was exhausted
/// -- a `None` with `aborted == true` is inconclusive, not a proof.
fn fill<T: IsRing>(base: &Rat<T>, k: usize, budget: usize) -> (Option<Vec<Iso<T>>>, bool) {
    if k < 2 {
        return (None, false);
    }
    let bverts = boundary_vertices::<T>(base.seq());
    let region = boundary_vertices::<T>(&scaled_seq(base.seq(), k));
    let redges: Vec<(T, T)> = (0..region.len())
        .map(|i| (region[i], region[(i + 1) % region.len()]))
        .collect();
    let mut frontier: HashMap<(T, T), i32> = HashMap::new();
    for &(a, b) in &redges {
        *frontier.entry((a, b)).or_insert(0) += 1;
    }
    let mut filler = Filler {
        base: &bverts,
        n: bverts.len(),
        region: &region,
        redges: &redges,
        target: k * k,
        placed: Vec::new(),
        polys: Vec::new(),
        frontier,
        budget,
        nodes: 0,
    };
    let found = filler.search();
    let aborted = filler.nodes > budget;
    (found.then_some(filler.placed), aborted)
}

/// Try to tile the `k`-scaled copy of `base` with exactly `k*k` rotated /
/// translated copies. Returns the `k*k` placements (a witness) if `base` is a
/// rep-tile at scale `k`, or `None` -- and since the region and the count are
/// fixed and the backtracking is exhaustive, `None` is a PROOF that no scale-`k`
/// rep-tiling exists in the orientation-preserving (single-chirality) model.
/// Unbudgeted (exact); use [`reptile_screen_one`] to bound the cost.
pub fn reptile_at<T: IsRing>(base: &Rat<T>, k: usize) -> Option<Vec<Iso<T>>> {
    fill(base, k, usize::MAX).0
}

/// Smallest scale `k` in `2..=kmax` at which `base` is a rep-tile, with its
/// witness placements; `None` if it is not a rep-tile at any of those scales.
pub fn reptile<T: IsRing>(base: &Rat<T>, kmax: usize) -> Option<(usize, Vec<Iso<T>>)> {
    (2..=kmax).find_map(|k| reptile_at(base, k).map(|w| (k, w)))
}

/// Reconstruct a replayable `build` recipe -- a `PatchMatch` sequence with
/// tile 0 = identity, exactly like `PeriodicCert.build` -- from a connected set
/// of `placements` (e.g. a rep-tile witness). It grows the junction-free
/// [`BasicPatch`] core (this replay only reads the boundary and glues, so each
/// probe-clone skips the interior junction fan), at each step gluing on the copy
/// that lands on one of the root-normalized targets, so the result replays via
/// [`replay_placements`](crate::classify::grow::replay_placements) and
/// draws via [`witness_svg`](crate::classify::render::witness_svg) with
/// the rest of the crate's machinery -- no bespoke serialization or renderer.
/// `None` if the placements are not a connected edge-to-edge patch.
pub(crate) fn build_from_placements<T: IsRing>(
    base: &Rat<T>,
    placements: &[Iso<T>],
) -> Option<Vec<PatchMatch>> {
    if placements.len() <= 1 {
        return Some(Vec::new());
    }
    let v = boundary_vertices::<T>(base.seq());
    // Targets in the frame where the root copy (placements[0]) is the identity.
    let root_inv = placements[0].inv();
    let targets: HashSet<Iso<T>> = placements.iter().map(|g| root_inv.after(g)).collect();
    let seed = BasicPatch::single_tile(TileSet::single(base.clone()), 0);
    // First glue: the candidate whose second copy lands on a target. The patch
    // grows in its own frame (tile 0 at `q0`), so normalize captures by
    // `q0.inv()` before comparing; `q0` is stable (tile 0 never moves) and is
    // captured once here, while tile 0 still has exposed edges.
    let mut chosen = None;
    for first in seed.get_all_matches() {
        let Some(g) = seed.with_tile(&first) else {
            continue;
        };
        let (Some(q0), Some(i1)) = (capture_placement(&g, &v, 0), capture_placement(&g, &v, 1))
        else {
            continue;
        };
        let q0inv = q0.inv();
        let t1 = q0inv.after(&i1);
        if targets.contains(&t1) {
            chosen = Some((g, q0inv, t1, vec![first]));
            break;
        }
    }
    let (mut gp, q0inv, t1, mut build) = chosen?;
    let mut placed: HashSet<Iso<T>> = HashSet::from([Iso::id(), t1]);
    while placed.len() < placements.len() {
        let mut advanced = false;
        'scan: for edge in 0..gp.len() {
            for pm in gp.get_matches_in_edge_range(edge, edge) {
                let new_id = gp.next_tile_id();
                let mut trial = gp.clone();
                if trial.add_tile(&pm).is_none() {
                    continue;
                }
                let Some(iso) = capture_placement(&trial, &v, new_id) else {
                    continue;
                };
                let norm = q0inv.after(&iso);
                if targets.contains(&norm) && placed.insert(norm) {
                    build.push(pm);
                    gp = trial;
                    advanced = true;
                    break 'scan;
                }
            }
        }
        if !advanced {
            return None;
        }
    }
    Some(build)
}

/// A verified rep-tile certificate: `k*k` copies of the base tile, described by
/// the replayable glue `build` (tile 0 = base at identity), exactly tile the
/// `k`-scaled copy of the base. Mirrors `PeriodicCert` / `HeeschCert`: a compact,
/// ring-independent `PatchMatch` recipe that replays
/// ([`replay_placements`]),
/// renders ([`witness_svg`](crate::classify::render::witness_svg)), and
/// re-verifies ([`RepTileCert::verify`]) with the shared machinery.
#[derive(Debug, Clone, Serialize, Deserialize)]
pub struct RepTileCert {
    /// Linear scale: the cluster is a `k`x-scaled copy of the tile (order `k*k`).
    pub k: usize,
    /// Glue recipe for the `k*k` copies; `replay_placements(base, &build)` yields
    /// them (tile 0 = base at the identity).
    pub build: Vec<PatchMatch>,
}

impl RepTileCert {
    /// Re-verify from scratch against `base`: replay the recipe, then check the
    /// `k*k` copies are all inside the `k`-scaled region, pairwise non-
    /// overlapping, and leave no gap (their boundary cancels exactly to the
    /// region boundary). All exact ring arithmetic -- a corrupt or wrong cert
    /// fails. This is the trust gate, like `PeriodicCert::verify`.
    pub fn verify<T: IsRing>(&self, base: &Rat<T>) -> bool {
        let Some(placements) = replay_placements(base, &self.build) else {
            return false;
        };
        if self.k < 2 || placements.len() != self.k * self.k {
            return false;
        }
        let bverts = boundary_vertices::<T>(base.seq());
        let polys: Vec<Vec<T>> = placements.iter().map(|g| g.tile(&bverts)).collect();
        for i in 0..polys.len() {
            for j in (i + 1)..polys.len() {
                if !interiors_disjoint(&polys[i], &polys[j]) {
                    return false;
                }
            }
        }
        // The copies' union must be gap-free and its outer boundary a k-scaled
        // copy of the tile (same shape up to rotation). Frame-independent, so it
        // does not care where `replay_placements` re-rooted the patch.
        let Some(loop_seq) = union_boundary_seq(&polys, base.seq().len() * self.k) else {
            return false;
        };
        cyclic_eq(&loop_seq, &scaled_seq(base.seq(), self.k))
    }
}

/// Turn a fill witness into a cert and VERIFY it before trusting it -- the mint
/// gate, matching every other cert minter in the crate. `None` if the witness
/// can't be reconstructed into a replayable `build`, or the rebuilt cert fails
/// re-verification (which, since the fill already found a valid tiling, is a bug
/// signal, not a normal negative -- see [`RepScreen::Anomaly`]).
fn mint_cert<T: IsRing>(base: &Rat<T>, k: usize, placements: &[Iso<T>]) -> Option<RepTileCert> {
    let cert = RepTileCert {
        k,
        build: build_from_placements(base, placements)?,
    };
    cert.verify(base).then_some(cert)
}

/// Smallest-scale rep-tile certificate for `base` (scales `2..=kmax`), or `None`
/// if it is not a rep-tile at any of those scales -- a proof, in the
/// orientation-preserving model. The returned cert is verify-gated.
pub fn reptile_cert<T: IsRing>(base: &Rat<T>, kmax: usize) -> Option<RepTileCert> {
    let (k, placements) = reptile(base, kmax)?;
    mint_cert(base, k, &placements)
}

/// One tile's rep-tile screen outcome under a per-scale node budget.
pub enum RepScreen {
    /// Confirmed rep-tile at the smallest working scale, with its verified cert.
    RepTile(RepTileCert),
    /// Every scale `2..=kmax` was fully searched with no tiling -- a proof it is
    /// not a rep-tile (in the orientation-preserving model, up to `kmax`).
    No,
    /// A scale's fill hit the node budget before finishing: no tiling found, but
    /// not proven absent -- a candidate for a deeper, unbudgeted re-run.
    Inconclusive,
    /// The fill FOUND a scale-`k` tiling but it could not be reconstructed into a
    /// verified cert -- a bug signal (surfaced, never silently dropped as a "no").
    Anomaly(usize),
}

/// Screen ONE tile with a per-scale node `budget` -- the screening entry point.
/// An unbudgeted [`reptile_cert`] can blow up *proving* that a near-miss is NOT
/// a rep-tile at a large scale (exhausting a `k*k`-tile region); a real rep-tile
/// is found fast (first success), so the budget only caps those "no" proofs,
/// turning the worst of them into [`RepScreen::Inconclusive`] instead of a hang.
pub fn reptile_screen_one<T: IsRing>(base: &Rat<T>, kmax: usize, budget: usize) -> RepScreen {
    let mut any_abort = false;
    for k in 2..=kmax {
        let (res, aborted) = fill(base, k, budget);
        if let Some(placements) = res {
            // The fill found a scale-k tiling; certify it (verify-gated).
            return match mint_cert(base, k, &placements) {
                Some(cert) => RepScreen::RepTile(cert),
                None => RepScreen::Anomaly(k),
            };
        }
        any_abort |= aborted;
    }
    if any_abort {
        RepScreen::Inconclusive
    } else {
        RepScreen::No
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::cyclotomic::ZZ12;

    fn rat(seq: &[i8]) -> Rat<ZZ12> {
        Rat::from_slice_trusted(seq)
    }

    /// The equilateral triangle `[4,4,4]` (120-degree turns) is the archetypal
    /// rep-tile: rep-4 at k=2 (3 corners + 1 half-turned centre) and rep-9 at k=3.
    #[test]
    fn triangle_is_rep4_and_rep9() {
        let t = rat(&[4, 4, 4]);
        assert_eq!(reptile_at(&t, 2).expect("triangle rep-4").len(), 4);
        assert_eq!(reptile_at(&t, 3).expect("triangle rep-9").len(), 9);
    }

    /// The unit square `[3,3,3,3]` (90-degree turns) is rep-4 (a 2x2 block) and
    /// rep-9 (a 3x3 block), all copies in the same orientation.
    #[test]
    fn square_is_rep4_and_rep9() {
        let s = rat(&[3, 3, 3, 3]);
        assert_eq!(reptile_at(&s, 2).expect("square rep-4").len(), 4);
        assert_eq!(reptile_at(&s, 3).expect("square rep-9").len(), 9);
    }

    /// The regular hexagon tiles the plane but is NOT a rep-tile at any scale --
    /// the exhaustive fill must return a (proven) `None`.
    #[test]
    fn hexagon_is_not_a_reptile() {
        let h = rat(&[2, 2, 2, 2, 2, 2]);
        for k in 2..=4 {
            assert!(
                reptile_at(&h, k).is_none(),
                "regular hexagon must not rep-tile at k={k}"
            );
        }
    }

    /// `reptile` reports the smallest working scale.
    #[test]
    fn reptile_reports_smallest_scale() {
        let (k, w) = reptile(&rat(&[4, 4, 4]), 6).expect("triangle is a rep-tile");
        assert_eq!(k, 2);
        assert_eq!(w.len(), 4);
    }

    /// The L-tromino `[3,0,3,3,-3,3,3,0]` -- concave, with straight (0-turn)
    /// runs and a reflex corner -- is the classic rep-4, tiled by rotations
    /// alone. A non-trivial exercise of containment + overlap on a concave tile.
    #[test]
    fn l_tromino_is_rep4() {
        let (k, w) = reptile(&rat(&[3, 0, 3, 3, -3, 3, 3, 0]), 4).expect("L-tromino rep-tile");
        assert_eq!(k, 2);
        assert_eq!(w.len(), 4);
    }

    /// The L-tetromino (4 cells, non-convex) is rep-4, rotations only.
    #[test]
    fn l_tetromino_is_rep4() {
        let t = rat(&[3, 0, 3, 3, -3, 0, 3, 3, 0, 0]);
        let cert = reptile_cert(&t, 6).expect("L-tetromino rep-tile");
        assert_eq!(cert.k, 2);
        assert!(cert.verify(&t), "rep-4 tiling verifies exactly");
    }

    /// The T-tetromino is rep-**16** (k=4), rotations only: sixteen copies tile
    /// the 4x-scaled T as four 4x4-square pinwheels (each square = 4 T's). A
    /// higher-order, non-convex check -- and it must EXACTLY verify (guards
    /// against a false-positive fill on a 16-tile region).
    #[test]
    fn t_tetromino_is_rep16() {
        let t = rat(&[3, 0, 0, 3, 3, -3, 3, 3, -3, 3]);
        let cert = reptile_cert(&t, 6).expect("T-tetromino rep-tile");
        assert_eq!(cert.k, 4);
        assert_eq!(cert.build.len(), 15); // 16 copies -> 15 glues
        assert!(
            cert.verify(&t),
            "the rep-16 tiling verifies exactly (no gap/overlap)"
        );
    }

    /// A rep-tile witness reconstructs into a replayable `build` recipe that
    /// reproduces the same placements -- so the witness serializes and renders
    /// through the standard cert machinery.
    #[test]
    fn build_recipe_round_trips_the_witness() {
        use crate::classify::grow::replay_placements;
        for seq in [
            &[4, 4, 4][..],
            &[3, 3, 3, 3][..],
            &[3, 0, 3, 3, -3, 3, 3, 0][..],
        ] {
            let base = rat(seq);
            let (_k, placements) = reptile(&base, 3).expect("rep-tile");
            let build = build_from_placements(&base, &placements).expect("build recipe");
            assert_eq!(
                build.len(),
                placements.len() - 1,
                "one glue per non-root copy"
            );
            let root_inv = placements[0].inv();
            let want: HashSet<Iso<ZZ12>> = placements.iter().map(|g| root_inv.after(g)).collect();
            let got: HashSet<Iso<ZZ12>> = replay_placements(&base, &build)
                .expect("replay")
                .into_iter()
                .collect();
            assert_eq!(
                got, want,
                "replayed build == the witness placements (seq {seq:?})"
            );
        }
    }

    /// ZZ10 has rep-tiles too -- but only C1/C2 (oblique/rhombic), because its
    /// only crystallographic rotations are 0 and 180 (no 90/60/120 -- those
    /// aren't multiples of 36). The Penrose thin (36/144) and thick (72/108)
    /// rhombi are parallelograms, hence rep-4 by pure translation. Confirms the
    /// checker is genuinely ring-generic.
    #[test]
    fn zz10_penrose_rhombi_are_rep4() {
        use crate::cyclotomic::ZZ10;
        for seq in [&[4, 1, 4, 1][..], &[3, 2, 3, 2][..]] {
            let base = Rat::<ZZ10>::from_slice_trusted(seq);
            let cert = reptile_cert(&base, 4).expect("rhombus is a rep-tile");
            assert_eq!(cert.k, 2, "a parallelogram is rep-4");
            assert!(cert.verify(&base), "verifies exactly");
        }
    }

    /// End-to-end: mint a cert from a rep-tile, it self-verifies, survives a
    /// JSON round-trip (stores like the other certs), and a corrupt/absent cert
    /// is rejected.
    #[test]
    fn reptile_cert_mints_verifies_and_serdes() {
        let base = rat(&[4, 4, 4]);
        let cert = reptile_cert(&base, 6).expect("triangle rep-tile cert");
        assert_eq!(cert.k, 2);
        assert_eq!(cert.build.len(), 3); // 4 copies -> 3 glues
        assert!(cert.verify(&base), "cert self-verifies");
        let json = serde_json::to_string(&cert).unwrap();
        let back: RepTileCert = serde_json::from_str(&json).unwrap();
        assert!(back.verify(&base), "cert survives serde round-trip");
        assert!(
            reptile_cert(&rat(&[2, 2, 2, 2, 2, 2]), 4).is_none(),
            "hexagon has no cert"
        );
        let bad = RepTileCert {
            k: 3,
            build: cert.build.clone(),
        };
        assert!(!bad.verify(&base), "wrong-k cert rejected");
    }

    /// `verify` rejects a malformed cert whose `build` replays to the wrong copy
    /// count (one glue dropped -> 3 copies, but the k=2 region needs 4) -- the
    /// re-verification gate that `reptile_cert` / the screen now rely on.
    #[test]
    fn verify_rejects_wrong_tile_count() {
        let tri = rat(&[4, 4, 4]);
        let cert = reptile_cert(&tri, 6).expect("triangle cert"); // k=2, 3 glues -> 4 copies
        let short = RepTileCert {
            k: cert.k,
            build: cert.build[..cert.build.len() - 1].to_vec(), // 2 glues -> 3 copies
        };
        assert!(
            !short.verify(&tri),
            "3 copies cannot fill the k=2 region (needs 4)"
        );
    }
}