tilezz 0.2.0

//! The Conway criterion -- the cheapest sound "tiles periodically" detector.
//!
//! A tile that admits *any* periodic tiling is disqualified as an aperiodic
//! monotile (the spectre family tiles only aperiodically). So a sound
//! "tiles periodically" certificate moves a candidate out of the
//! aperiodic-candidate pool. Like the Heesch reject, this can only ever
//! fire *positively* and soundly; a tile we cannot certify stays a
//! candidate (it might still tile periodically by a structure we do not
//! test, or only aperiodically, or not at all).
//!
//! The certificate here is the **Conway criterion** on the boundary edge
//! sequence: a closed topological disk tiles the plane (isohedrally) if its
//! boundary splits into six consecutive arcs `A B C D E F` (cyclic order)
//! such that
//!
//! - `A` is the translate of `D` -- their edge-vector sequences satisfy
//!   `D = reverse(negate(A))` (a translation maps arc `A` onto arc `D`,
//!   reversing the traversal sense), and
//! - each of `B`, `C`, `E`, `F` is **centrally symmetric** about its own
//!   midpoint -- its edge-vector sequence is a palindrome.
//!
//! Arcs may be degenerate (a single vertex / zero edges). The criterion
//! uses only translations and half-turns, so it is exactly within our
//! single-chirality scope (rotations only, no reflections). It is
//! *sufficient*, not necessary -- in TWO directions: it misses tilings that
//! need 3-, 4-, or 6-fold rotation centres (the
//! [`isohedral`](crate::classify::isohedral) and
//! [`aniso`](crate::classify::aniso) searches take over there), and
//! it also misses PURE-TRANSLATION tilings whose translate-pair arcs are not
//! palindromic -- offset brick walls with bumpy sides. Those are exactly
//! characterized by the Beauquier-Nivat factorization ([`bn_criterion`]),
//! which runs as its own stage.
//!
//! Derivation of the edge-vector conditions (so they can be trusted rather
//! than recalled):
//!
//! - **Central symmetry.** A half-turn `R(x) = 2M - x` about the arc
//!   midpoint maps the arc onto itself with reversed vertex order:
//!   `R(q_i) = q_{j-i}`, so `q_i + q_{j-i} = 2M`. The edge vectors
//!   `b_i = q_{i+1} - q_i` then satisfy `b_{j-1-i} = b_i` -- a palindrome.
//!   (A single edge is trivially a palindrome -- it is centrally symmetric
//!   about its midpoint, as it should be.)
//! - **Translate pair.** A translation `T(x) = x + t` mapping arc `A` onto
//!   arc `D` with reversed order has `T(a_i) = d_{L-i}`, so
//!   `D_{L-1-i} = -A_i`: `D` is `A` reversed and negated.
//!
//! The criterion is not just a yes/no: [`build_tiling`] applies the isometries
//! a certificate names to build the actual tiling, which the exact
//! [`verify_tiling`](crate::classify::tiling::verify_tiling) then
//! checks -- a wrong certificate or generator is caught, never rendered.

use crate::classify::lattice::independent_pair;
use crate::classify::tiling::Tiling;
use crate::cyclotomic::IsRing;
use crate::geom::iso::{Iso, build_orbit};
use crate::geom::patch::{boundary_vertices, trace_boundary_positions};

/// A Conway-criterion decomposition: the six arc-start edge indices
/// `[a, b, c, d, e, f]` (cyclic), where `A = edges[a..b)`, `B = edges[b..c)`,
/// ... `F = edges[f..a)`. `A` and `D` are the translate pair; `B C E F` are
/// the centrally-symmetric arcs.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct ConwayCert {
    pub cuts: [usize; 6],
}

/// Edge-vector sequence of a closed boundary turn-word. Position `i+1` minus
/// position `i` is the (exact) unit edge vector for edge `i`. The polyline
/// closes (`positions[n] == positions[0]`), so we take the first `n` diffs.
fn edge_vectors<T: IsRing>(seq: &[i8]) -> Vec<T> {
    let pos = trace_boundary_positions::<T>(seq);
    let n = seq.len();
    (0..n).map(|i| pos[i + 1] - pos[i]).collect()
}

/// Whether the cyclic edge run of length `len` starting at `s` is a
/// palindrome (`edges[s+k] == edges[s+len-1-k]`). Length 0 and 1 are
/// vacuously palindromic.
fn is_palindrome<T: IsRing>(edges: &[T], s: usize, len: usize) -> bool {
    let n = edges.len();
    (0..len / 2).all(|k| edges[(s + k) % n] == edges[(s + len - 1 - k) % n])
}

/// Whether arc `A` (start `sa`, length `len`) is the translate of arc `D`
/// (start `sd`, length `len`): `A[k] == -D[len-1-k]`. Vacuously true for
/// `len == 0` (degenerate point pair).
fn is_translate_pair<T: IsRing>(edges: &[T], sa: usize, sd: usize, len: usize) -> bool {
    let n = edges.len();
    (0..len).all(|k| edges[(sa + k) % n] == -edges[(sd + len - 1 - k) % n])
}

/// Search for a Conway decomposition of the boundary turn-word `seq`.
/// Returns the first one found, or `None`. Boundary lengths here are small
/// (matchstick perimeters), so the brute-force scan over the start vertex
/// and the four free arc lengths is cheap.
pub fn conway_criterion<T: IsRing>(seq: &[i8]) -> Option<ConwayCert> {
    let edges = edge_vectors::<T>(seq);
    let n = edges.len();
    if n == 0 {
        return None;
    }
    for sa in 0..n {
        // |A| = |D| = la (the translate pair has equal length); 2*la <= n.
        for la in 0..=(n / 2) {
            let rem = n - 2 * la; // edges shared among B, C, E, F
            for lb in 0..=rem {
                for lc in 0..=(rem - lb) {
                    for le in 0..=(rem - lb - lc) {
                        let lf = rem - lb - lc - le;
                        let a0 = sa;
                        let b0 = (a0 + la) % n;
                        let c0 = (b0 + lb) % n;
                        let d0 = (c0 + lc) % n;
                        let e0 = (d0 + la) % n;
                        let f0 = (e0 + le) % n;
                        if is_translate_pair(&edges, a0, d0, la)
                            && is_palindrome(&edges, b0, lb)
                            && is_palindrome(&edges, c0, lc)
                            && is_palindrome(&edges, e0, le)
                            && is_palindrome(&edges, f0, lf)
                        {
                            return Some(ConwayCert {
                                cuts: [a0, b0, c0, d0, e0, f0],
                            });
                        }
                    }
                }
            }
        }
    }
    None
}

/// Beauquier-Nivat p1 factorizations: the boundary factors cyclically as
/// `A B C A' B' C'` with each primed arc its partner reversed and negated
/// (a translate pair; `C` may be empty). By the Beauquier-Nivat theorem this
/// EXACTLY characterizes tiling by pure translation: the brick-wall detector
/// (same tile, same orientation, offset rows). The [`conway_criterion`]
/// misses this class whenever the paired arcs are not palindromic -- its
/// four symmetric arcs demand central symmetry, which bumpy brick sides do
/// not have (learned on the n=14 residue: 27 of 31 fast-pass survivors were
/// plain brick walls invisible to Conway and to the rosette-prone torus
/// grower).
///
/// Returns the candidate lattice-generator pairs `(dA+dB, dB+dC)` of every
/// factorization found (deduped); the minter verify-gates each, so a wrong
/// or degenerate proposal costs a miss, never a wrong accept.
pub fn bn_criterion<T: IsRing>(seq: &[i8]) -> Vec<(T, T)> {
    let edges = edge_vectors::<T>(seq);
    let n = edges.len();
    if n == 0 || !n.is_multiple_of(2) {
        return Vec::new();
    }
    let h = n / 2;
    // Primed arc at offset `off` past the half is its partner (at `lo`,
    // length `len`) reversed and negated.
    let pair_ok = |s: usize, off: usize, lo: usize, len: usize| {
        (0..len).all(|i| edges[(s + h + off + i) % n] == -edges[(s + lo + len - 1 - i) % n])
    };
    let disp = |s: usize, lo: usize, len: usize| {
        (0..len).fold(T::zero(), |acc, i| acc + edges[(s + lo + i) % n])
    };
    let mut out: Vec<(T, T)> = Vec::new();
    for s in 0..n {
        for a in 0..=h {
            for b in 0..=(h - a) {
                let c = h - a - b;
                if pair_ok(s, 0, 0, a) && pair_ok(s, a, a, b) && pair_ok(s, a + b, a + b, c) {
                    let (da, db, dc) = (disp(s, 0, a), disp(s, a, b), disp(s, a + b, c));
                    let cand = (da + db, db + dc);
                    if !out.contains(&cand) {
                        out.push(cand);
                    }
                }
            }
        }
    }
    out
}

/// Cyclic arc length from cut `i` to cut `i+1`.
fn arc_len(cuts: &[usize; 6], i: usize, n: usize) -> usize {
    (cuts[(i + 1) % 6] + n - cuts[i]) % n
}

/// Generators of the tiling promised by a Conway certificate: the translation
/// `A -> D` (when `A` is non-degenerate) and a half-turn about the midpoint of
/// each non-degenerate centrally-symmetric arc `B, C, E, F`. Returns the
/// generator list (with translation inverse) and two lattice vectors.
fn conway_isometries<T: IsRing>(verts: &[T], cert: &ConwayCert) -> (Vec<Iso<T>>, (T, T)) {
    let n = verts.len();
    let c = cert.cuts;
    let mut gens: Vec<Iso<T>> = Vec::new();
    let mut lat: Vec<T> = Vec::new();

    let half = T::turn() / 2; // half-turn rotation (180 degrees)

    // Translation A -> D: maps p_a to p_e (see is_translate_pair derivation).
    if arc_len(&c, 0, n) > 0 {
        let t = verts[c[4]] - verts[c[0]];
        gens.push(Iso { rot: 0, shift: t });
        gens.push(Iso { rot: 0, shift: -t });
        lat.push(t);
    }
    // Half-turns about the midpoints of the four centrally-symmetric arcs.
    // Doubled centre S = sum of arc endpoints; H(x) = S - x = x*unit(half) + S.
    let arcs = [(1usize, 2usize), (2, 3), (4, 5), (5, 0)]; // (B,C,E,F) as cut pairs
    let mut centers: Vec<T> = Vec::new();
    for (idx, &(s, _e)) in arcs.iter().enumerate() {
        let arc_index = [1, 2, 4, 5][idx]; // arc start cut for B,C,E,F
        if arc_len(&c, arc_index, n) == 0 {
            continue; // degenerate (point) arc -> no half-turn
        }
        let start = c[s];
        let end = c[(s + 1) % 6];
        let center2 = verts[start] + verts[end];
        gens.push(Iso {
            rot: half,
            shift: center2,
        });
        centers.push(center2);
    }
    // Lattice: translations are t and differences of doubled half-turn centres
    // (H_i after H_j is translation by S_i - S_j). Collect candidates, pick two
    // independent ones.
    for i in 0..centers.len() {
        for j in (i + 1)..centers.len() {
            lat.push(centers[i] - centers[j]);
        }
    }
    // Degenerate (no independent pair) yields zeros; verification fails loudly.
    let lattice = independent_pair(lat).unwrap_or((T::zero(), T::zero()));
    (gens, lattice)
}

/// Build the tiling promised by the tile's Conway certificate: apply the
/// generators breadth-first to fill a disk of the given `radius` (centroid
/// distance), capped at `cap` tiles. The central tile is the identity
/// placement. `None` if the criterion does not hold.
pub fn build_tiling<T: IsRing>(seq: &[i8], radius: f64, cap: usize) -> Option<Tiling<T>> {
    let cert = conway_criterion::<T>(seq)?;
    let verts = boundary_vertices::<T>(seq);
    let (gens, lattice) = conway_isometries::<T>(&verts, &cert);
    let placements = build_orbit(&verts, &gens, radius, cap);
    Some(Tiling {
        verts,
        seq: seq.to_vec(),
        lattice,
        placements,
    })
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::classify::tiling::verify_tiling;
    use crate::cyclotomic::ZZ12;
    use crate::geom::rat::Rat;
    use crate::geom::tiles;

    fn rat_of(snake: crate::geom::snake::Snake<ZZ12>) -> Rat<ZZ12> {
        Rat::from_snake_trusted(&snake)
    }

    /// Known periodic tilers satisfy Conway; the regular dodecagon (a known
    /// non-tiler) does not. The dodecagon case is the soundness guard -- a
    /// false positive there would mean the certificate is unsound.
    #[test]
    fn conway_separates_tilers_from_dodecagon() {
        let square = rat_of(tiles::square::<ZZ12>());
        let triangle = rat_of(tiles::triangle::<ZZ12>());
        let hexagon = rat_of(tiles::hexagon::<ZZ12>());
        for (name, rat) in [
            ("square", &square),
            ("triangle", &triangle),
            ("hexagon", &hexagon),
        ] {
            let cert = conway_criterion::<ZZ12>(rat.seq());
            eprintln!("{name}: {cert:?}");
            assert!(cert.is_some(), "{name} must satisfy Conway (it tiles)");
        }

        let dodecagon = Rat::<ZZ12>::from_snake_trusted(&tiles::dodecagon());
        let cert = conway_criterion::<ZZ12>(dodecagon.seq());
        eprintln!("dodecagon: {cert:?}");
        assert!(
            cert.is_none(),
            "regular dodecagon must fail Conway (it does not tile)"
        );
    }

    /// Rectangles tile by pure translation -- a degenerate Conway case
    /// (opposite edges are the translate pair, the short edges palindromic).
    #[test]
    fn rectangles_pass() {
        for (name, snake) in [
            ("tetromino_O", tiles::tetromino_O::<ZZ12>()),
            ("tetromino_I", tiles::tetromino_I::<ZZ12>()),
        ] {
            let rat = rat_of(snake);
            let cert = conway_criterion::<ZZ12>(rat.seq());
            eprintln!("{name}: {cert:?}");
            assert!(cert.is_some(), "{name} (a rectangle) must satisfy Conway");
        }
    }

    /// The constructive proof: for tiles the criterion accepts, actually
    /// build the promised tiling and verify the central tile is exactly
    /// surrounded (angles sum to a full turn, every edge shared once) and the
    /// patch is translationally periodic. This catches a wrong certificate or
    /// wrong generator -- a false "periodic" would fail to tile here.
    #[test]
    fn constructed_tilings_actually_tile() {
        let square = rat_of(tiles::square::<ZZ12>());
        let triangle = rat_of(tiles::triangle::<ZZ12>());
        let hexagon = rat_of(tiles::hexagon::<ZZ12>());
        for (name, rat) in [
            ("square", &square),
            ("triangle", &triangle),
            ("hexagon", &hexagon),
        ] {
            let perim = rat.seq().len() as f64;
            let tiling =
                build_tiling::<ZZ12>(rat.seq(), 3.0 * perim, 4000).expect("conway-positive");
            let chk = verify_tiling(&tiling);
            eprintln!("{name}: {} tiles, check={chk:?}", tiling.placements.len());
            assert!(chk.ok(), "{name} constructed tiling must verify: {chk:?}");
        }
    }

    /// A Conway decomposition really is a valid decomposition: the six arcs
    /// partition the boundary (lengths sum to n) AND the certified relations
    /// hold on the edge vectors -- A/D a translate pair, B/C/E/F palindromes.
    #[test]
    fn cert_is_well_formed() {
        let square = rat_of(tiles::square::<ZZ12>());
        let edges = edge_vectors::<ZZ12>(square.seq());
        let n = edges.len();
        let ConwayCert { cuts } = conway_criterion::<ZZ12>(square.seq()).unwrap();
        // Arc lengths (cyclic gaps between consecutive cuts) sum to n.
        let len = |i: usize| (cuts[(i + 1) % 6] + n - cuts[i]) % n;
        let total: usize = (0..6).map(len).sum();
        assert_eq!(total, n, "the six arcs must partition the boundary");
        // The certified relations themselves.
        assert_eq!(len(0), len(3), "translate pair arcs have equal length");
        assert!(
            is_translate_pair(&edges, cuts[0], cuts[3], len(0)),
            "A/D translate pair"
        );
        for i in [1usize, 2, 4, 5] {
            assert!(
                is_palindrome(&edges, cuts[i], len(i)),
                "arc {i} centrally symmetric"
            );
        }
    }

    /// bn_criterion catches the brick-wall class Conway misses: an n=14
    /// pure-translation tile (offset rows, bumpy non-palindromic sides) is
    /// Conway-NEGATIVE but BN-positive with a nondegenerate lattice proposal.
    /// Negatives stay negative: the dodecagon (cannot tile) and the spectre
    /// (tiles, but never by pure translation) yield no factorization.
    #[test]
    fn bn_catches_bricks_conway_misses() {
        use crate::cyclotomic::geometry::float::cross_f;
        // n=14 brick (dataset idx 20729692): 27 of the 31 n=14 fast-pass
        // survivors are in this class.
        let brick: [i8; 14] = [-4, 0, 4, 0, 2, 2, -2, 0, 4, 2, -2, 0, 4, 2];
        assert!(
            conway_criterion::<ZZ12>(&brick).is_none(),
            "Conway misses the brick"
        );
        let cands = bn_criterion::<ZZ12>(&brick);
        assert!(!cands.is_empty(), "BN factorizes the brick");
        assert!(
            cands.iter().any(|(v1, v2)| cross_f(v1, v2).abs() > 1e-9),
            "a nondegenerate lattice proposal exists"
        );
        // Negatives.
        let dodec = rat_of(tiles::dodecagon::<ZZ12>());
        assert!(
            bn_criterion::<ZZ12>(dodec.seq()).is_empty(),
            "dodecagon: no BN hexagon"
        );
        let spectre = rat_of(tiles::spectre::<ZZ12>());
        assert!(
            bn_criterion::<ZZ12>(spectre.seq()).is_empty(),
            "spectre: no BN hexagon"
        );
    }
}