tilezz 0.2.0

//! Anisohedral periodicity: the monotile tiles by a multi-tile cluster.
//!
//! A k-anisohedral tiling uses k symmetry-inequivalent copies of the SAME tile
//! per fundamental domain. Equivalently: glue k copies into a connected cluster
//! (still the one shape, rotations only) and that cluster tiles the plane as a
//! composite. So we enumerate k-tile clusters by edge-gluing (reusing
//! `BasicPatch`), dedup by lex-min-rotation boundary (rotation-only, no
//! reflection -- single chirality), and test each cluster's boundary with the
//! Conway check, then verify by minting a certificate. Acceptance is sound only
//! through that cert: `mint` gates it on `PeriodicCert::verify`, which re-checks
//! exact surroundedness at one tile PER TRANSLATION CLASS
//! (`all_exactly_surrounded`) plus exact multiplicity gates -- necessary because
//! a k-cluster tiling has k>1 translation classes, so the center-only
//! `verify_tiling` pre-filter is not sufficient here. A verified cert proves the
//! monotile tiles periodically.

use crate::classify::conway::build_tiling;
use crate::classify::tiling::{CLUSTER_ORBIT_CAP, ORBIT_RADIUS_FACTOR, Tiling, verify_tiling};
use crate::cyclotomic::IsRing;
use crate::geom::matches::PatchMatch;
use crate::geom::patch::BasicPatch;
use crate::geom::rat::Rat;
use crate::geom::tileset::TileSet;
use crate::stringmatch::canonical_rotation;

/// A found anisohedral witness: `k` copies of the base tile glue into a
/// connected cluster -- `build` is the assembly recipe (for the cert's
/// meta-tile) and `tiling` the cluster's own verified periodic tiling (in the
/// canonical-rotation frame of the cluster boundary, which is `tiling.seq`),
/// proving the base tiles anisohedrally.
pub struct ClusterWitness<T> {
    pub k: usize,
    pub build: Vec<PatchMatch>,
    pub tiling: Tiling<T>,
}

/// The cluster boundary `seq`'s own periodic tiling, if it has one
/// (Conway-positive and constructively verified). A hit means the monotile
/// that composes the cluster tiles anisohedrally; the returned [`Tiling`] is
/// handed to the cert minter so the glue is read off THIS tiling instead of
/// rebuilding it.
fn cluster_tiling<T: IsRing>(seq: &[i8]) -> Option<Tiling<T>> {
    // build_tiling itself runs the Conway criterion and returns None on a miss.
    let r = ORBIT_RADIUS_FACTOR * seq.len() as f64;
    build_tiling::<T>(seq, r, CLUSTER_ORBIT_CAP).filter(|t| verify_tiling(t).ok())
}

/// xorshift64 step -- a tiny deterministic PRNG for the seeded exploration order
/// (the restart seed); seeded so a shuffled run is still reproducible.
#[inline]
fn xorshift64(s: &mut u64) -> u64 {
    let mut x = *s;
    x ^= x << 13;
    x ^= x >> 7;
    x ^= x << 17;
    *s = x;
    x
}

/// Fisher-Yates shuffle in place. A zero state means "no shuffle" (the default
/// deterministic order), so unseeded runs are byte-identical to before.
fn seeded_shuffle<X>(v: &mut [X], state: &mut u64) {
    if *state == 0 || v.len() < 2 {
        return;
    }
    for i in (1..v.len()).rev() {
        let j = (xorshift64(state) % (i as u64 + 1)) as usize;
        v.swap(i, j);
    }
}

/// Seeded **restarts** over the anisohedral search: try seeds `1..=restarts`,
/// each a fresh search bounded by `per_budget` clusters, returning the first
/// witness. The search is strongly HEAVY-TAILED -- a tiling cluster's position
/// in the exploration order varies wildly with the seed (measured 2k..26k for
/// one n=11 tile), so a good cluster almost always surfaces early under SOME
/// seed. A handful of small-budget restarts therefore certifies a hard tile far
/// faster, and bounded (`restarts * per_budget`), than one large deterministic
/// pass -- and it is reproducible (fixed seed sequence). `restarts <= 1` is the
/// plain deterministic search (seed 0), so it changes nothing unless opted in.
pub fn tiles_anisohedral_restart<T: IsRing>(
    tile_seq: &[i8],
    kmax: usize,
    cluster_cap: usize,
    per_budget: usize,
    restarts: usize,
) -> Option<ClusterWitness<T>> {
    if restarts <= 1 {
        return tiles_anisohedral_seeded::<T>(tile_seq, kmax, cluster_cap, per_budget, 0);
    }
    for seed in 1..=restarts as u64 {
        if let Some(hit) =
            tiles_anisohedral_seeded::<T>(tile_seq, kmax, cluster_cap, per_budget, seed)
        {
            return Some(hit);
        }
    }
    None
}

/// The anisohedral search with an explicit exploration-order `seed` (0 = the
/// original deterministic order). A nonzero seed shuffles which frontier
/// clusters are extended first, in which match order, and thus which survive the
/// per-level `cluster_cap` truncation -- see [`tiles_anisohedral_restart`].
/// `cluster_cap` bounds the breadth kept per cluster size; `budget` is a
/// DETERMINISTIC ceiling on distinct clusters tested (0 = unlimited) -- the
/// same budget gives the same verdict every run, and exhausting any bound
/// returns `None` (undecided), never a false accept.
pub fn tiles_anisohedral_seeded<T: IsRing>(
    tile_seq: &[i8],
    kmax: usize,
    cluster_cap: usize,
    budget: usize,
    seed: u64,
) -> Option<ClusterWitness<T>> {
    use std::collections::HashSet;
    let ts = TileSet::single(Rat::<T>::from_slice_trusted(tile_seq));
    let pseed = BasicPatch::single_tile(ts, 0);
    let mut seen: HashSet<Vec<i8>> = HashSet::new();
    // Distinct clusters examined so far; the deterministic work ceiling.
    let mut examined = 0usize;
    let over = |examined: usize| budget != 0 && examined >= budget;
    // Exploration-order shuffle state (0 = deterministic order, unshuffled).
    let mut rng: u64 = seed;

    // k = 2: glue a second copy every way. Each frontier entry carries the
    // recipe ([grow, add...]) that built it, for cert minting.
    let mut frontier: Vec<(BasicPatch<T>, Vec<PatchMatch>)> = Vec::new();
    let mut k2: Vec<PatchMatch> = pseed.get_all_matches();
    seeded_shuffle(&mut k2, &mut rng);
    for pm in &k2 {
        let Some(gp) = pseed.with_tile(pm) else {
            continue;
        };
        // `to_rat().seq()` maps back through `cyc` to exactly `angles()`, so
        // canonicalize the raw boundary directly: one lex_min_rot, no Rat.
        let key = canonical_rotation(gp.angles());
        if !seen.insert(key.clone()) {
            continue;
        }
        examined += 1;
        let recipe = vec![*pm];
        if let Some(tiling) = cluster_tiling::<T>(&key) {
            return Some(ClusterWitness {
                k: 2,
                build: recipe,
                tiling,
            });
        }
        if over(examined) {
            return None;
        }
        frontier.push((gp, recipe));
    }

    // k = 3..=kmax: extend each cluster by one more copy at any boundary edge.
    for k in 3..=kmax {
        let mut next: Vec<(BasicPatch<T>, Vec<PatchMatch>)> = Vec::new();
        seeded_shuffle(&mut frontier, &mut rng);
        for (gp, recipe) in &frontier {
            let mut matches = gp.get_all_matches();
            seeded_shuffle(&mut matches, &mut rng);
            for pm in &matches {
                let mut g2 = gp.clone();
                if g2.add_tile(pm).is_none() {
                    continue;
                }
                // Same as above: canonicalize `angles()` directly, no Rat.
                let key = canonical_rotation(g2.angles());
                if !seen.insert(key.clone()) {
                    continue;
                }
                examined += 1;
                let mut r2 = recipe.clone();
                r2.push(*pm);
                // Test BEFORE the budget bail, so `budget = B` really tests B
                // clusters (it used to count the B-th and drop it untested).
                if let Some(tiling) = cluster_tiling::<T>(&key) {
                    if crate::classify::trace::aniso() {
                        eprintln!(
                            "ANISO_TRACE: found k={k} cluster after examining {examined} clusters"
                        );
                    }
                    return Some(ClusterWitness {
                        k,
                        build: r2,
                        tiling,
                    });
                }
                if over(examined) {
                    return None;
                }
                next.push((g2, r2));
            }
        }
        next.truncate(cluster_cap);
        frontier = next;
        if frontier.is_empty() {
            break;
        }
    }
    None
}

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

    /// The anisohedral search is HEAVY-TAILED: n=11 tile 104492's tiling k=4
    /// cluster sits ~22.5k deep in the deterministic (seed 0) order but ~2k deep
    /// under a lucky seed. So a plain search at a small per-budget MISSES it while
    /// seeded RESTARTS at the same per-budget FIND it -- the property that makes
    /// `tiles_anisohedral_restart` beat one large deterministic pass. Slow (~30s),
    /// so opt-in.
    #[test]
    #[ignore = "aniso restart rescues the heavy-tail cluster (104492), ~30s"]
    fn aniso_restart_rescues_heavy_tail() {
        let seq = [-1i8, 0, -1, 0, 5, 1, 0, 1, 1, 1, 5]; // n=11 idx 104492, k=4
        let (kmax, cap, per) = (6, 4_000, 5_000);
        // Deterministic (seed 0) at this per-budget does not reach the cluster.
        assert!(
            tiles_anisohedral_seeded::<ZZ12>(&seq, kmax, cap, per, 0).is_none(),
            "seed 0 should miss the deep cluster at per_budget {per}",
        );
        // Restarts over seeds 1..=12 surface it (a lucky seed finds it early).
        let hit = tiles_anisohedral_restart::<ZZ12>(&seq, kmax, cap, per, 12);
        assert_eq!(
            hit.map(|w| w.k),
            Some(4),
            "restarts must find the k=4 cluster"
        );
    }
}