use std::fs::File;
use std::io::BufWriter;
use std::sync::Mutex;
use std::time::Instant;
use clap::{Parser, ValueEnum};
use tilezz::rat_enum::dfs::STREAM_RAT_LINES;
use tilezz::rat_enum::output::{print_stats, run_rat_enum_polylines};
use tilezz::rat_enum::prune::{
install_closure_table_prune, install_modular_prune, install_shadow_prune,
};
use tilezz::rat_enum::run_rat_enum_seqs;
use tilezz::rat_enum::seed::{dispatch_collect_seed_prefixes, dispatch_enumerate_from_seed};
use tilezz::stringmatch::{DEFAULT_TARGET_BLOCK_BYTES, RatDafsa};
#[cfg(test)]
use std::collections::HashSet;
#[cfg(test)]
use tilezz::cyclotomic::IsRing;
#[cfg(test)]
use tilezz::rat_enum::canonical::{free_canonical, make_ops};
#[cfg(test)]
use tilezz::rat_enum::dfs::rat_enum_with;
#[cfg(test)]
use tilezz::rat_enum::prune::Prunes;
#[cfg(test)]
use tilezz::rat_enum::stats::DfsStats;
use tilezz::vis::animation::render_gif;
use tilezz::vis::draw::{MarkerStyle, TileStyle};
use tilezz::vis::plotutils::P64;
use tilezz::vis::scene::{Color, Fill, Scene, Stroke, TextStyle, Viewport};
static VERBOSE: Mutex<bool> = Mutex::new(false);
#[cfg(test)]
fn rat_enum<ZZ: IsRing>(max_steps: usize, step: i8) -> (Vec<Vec<i8>>, DfsStats) {
rat_enum_with::<ZZ>(
max_steps,
step,
make_ops(false),
"enumeration",
"",
false,
&Prunes::default(),
)
}
#[cfg(test)]
fn rat_enum_free<ZZ: IsRing>(max_steps: usize, step: i8) -> (Vec<Vec<i8>>, DfsStats) {
rat_enum_with::<ZZ>(
max_steps,
step,
make_ops(true),
"free enumeration",
"free ",
false,
&Prunes::default(),
)
}
#[derive(Copy, Clone, Debug, ValueEnum)]
enum Mode {
Render,
Bench,
ListSeeds,
Dafsa,
DafsaBlocks,
Stream,
Merge,
Build,
Rehost,
}
#[derive(Parser, Debug)]
#[command(
version = tilezz::VERSION,
about = "Enumerate simple cyclotomic matchstick polygons (rats) up to a given perimeter",
long_about = "\
Enumerate every simple polygon (closed self-avoiding boundary) of\n\
unit-length edges on a cyclotomic ring `ZZn`, with perimeter up to `-n`.\n\
\n\
Output is selected via `--mode` (default: render):\n\
* render enumerate and render the polygons as a GIF (`-o file.gif`)\n\
* bench enumerate, time, report counts (no -o needed)\n\
* dafsa enumerate and write a gzipped DAFSA (`-o file.bin.gz`)\n\
* dafsa-blocks same, but as a directory of lazy-loadable blocks\n\
* stream stage 1 of the streaming pipeline: write per-thread runs\n\
to `<-o dir>/runs/run_tNN_rMM.bin` (bounded memory)\n\
* merge stage 2 of the streaming pipeline: k-way merge runs into\n\
`<-o dir>/unique.bin` + `certificate.json`\n\
* build stage 3 of the streaming pipeline: stream `unique.bin`\n\
through a DAFSA builder and write blocks to `<-o dir>/dafsa/`\n\
* list-seeds walk DFS to `--split-depth` and print SEED + RAT lines\n\
(for multi-host orchestration; see `--seed`)\n\
* rehost patch an existing dataset's RO-Crate host fields to a\n\
new `--base-url` / `--doi` (no recompute; see -o)\n\
\n\
Performance opts (combine for maximum speedup):\n\
--reachability-prune reachability prune, finite + archimedean places; up to 376x\n\
--closure-table-prune exact lattice closure-table prune; another 2-5x on top\n\
--threads N parallel DFS; near-linear in streaming modes,\n\
sub-linear in HashSet modes (set-merge overhead)\n\
--free free (= full dihedral reduction) output:\n\
one rep per chiral pair (lex-min over rotations and\n\
reflections); also accelerates DFS via\n\
complement-reflection prune\n\
\n\
For memory at large n: prefer the streaming pipeline (`--mode stream`\n\
then `--mode merge`) over `--mode bench --threads N`. See the file-level\n\
docstring in src/bin/rat_enum.rs for the full memory accounting.\n"
)]
struct Cli {
#[arg(short = 'r', long)]
ring: Option<u8>,
#[arg(short = 'n', long)]
max_steps: Option<usize>,
#[arg(long, value_enum, default_value_t = Mode::Render)]
mode: Mode,
#[arg(short = 'o', long)]
filename: Option<String>,
#[arg(short, long)]
verbose: bool,
#[arg(long)]
profile: Option<String>,
#[arg(long)]
stats: bool,
#[arg(long, default_value_t = 1)]
threads: usize,
#[arg(long, default_value_t = 1)]
step: i8,
#[arg(long)]
free: bool,
#[arg(long)]
paranoid: bool,
#[arg(long)]
reachability_prune: bool,
#[arg(long, value_delimiter = ',', num_args = 1..)]
reachability_moduli: Option<Vec<i64>>,
#[arg(long)]
closure_table_prune: bool,
#[arg(long, default_value_t = 4)]
closure_table_depth: usize,
#[arg(long, default_value_t = DEFAULT_TARGET_BLOCK_BYTES)]
target_block_bytes: u32,
#[arg(long)]
no_rocrate: bool,
#[arg(long)]
oeis_a_number: Option<String>,
#[arg(long)]
base_url: Option<String>,
#[arg(long)]
doi: Option<String>,
#[arg(long, value_delimiter = ',', allow_hyphen_values = true, num_args = 1)]
seed: Option<Vec<i8>>,
#[arg(long)]
split_depth: Option<usize>,
}
fn resolve_n_threads(requested: usize) -> usize {
let max = num_cpus::get().max(1);
if requested == 0 {
max
} else {
requested.min(max)
}
}
fn main() {
let cli = Cli::parse();
if cli.verbose {
let mut verbose = VERBOSE.lock().unwrap();
*verbose = true;
}
let n_threads = resolve_n_threads(cli.threads);
if matches!(cli.mode, Mode::Rehost) {
let Some(dir) = cli.filename.as_deref() else {
eprintln!("--mode rehost requires -o <existing dataset directory>");
std::process::exit(2);
};
let dir = std::path::Path::new(dir);
match tilezz::stringmatch::dafsa::rehost_ro_crate(
dir,
cli.base_url.as_deref(),
cli.doi.as_deref(),
) {
Ok(()) => {
let where_to = match (cli.base_url.as_deref(), cli.doi.as_deref()) {
(Some(b), Some(d)) => format!("base_url={b} doi={d}"),
(Some(b), None) => format!("base_url={b}"),
(None, Some(d)) => format!("doi={d}"),
(None, None) => "location-independent (relative) form".to_string(),
};
eprintln!(
"rehost: patched {}/ro-crate-metadata.json to {where_to}",
dir.display()
);
}
Err(e) => {
eprintln!("--mode rehost failed: {e}");
std::process::exit(2);
}
}
return;
}
let Some(ring) = cli.ring else {
eprintln!("--ring is required for every mode except --mode rehost");
std::process::exit(2);
};
let Some(max_steps) = cli.max_steps else {
eprintln!("-n / --max-steps is required for every mode except --mode rehost");
std::process::exit(2);
};
if cli.reachability_prune {
install_modular_prune(ring, max_steps, cli.reachability_moduli.as_deref());
install_shadow_prune(ring);
}
if cli.closure_table_prune {
install_closure_table_prune(ring, cli.closure_table_depth);
}
if matches!(cli.mode, Mode::ListSeeds) {
let split_depth = cli.split_depth.unwrap_or(3);
let (closed, seeds) =
dispatch_collect_seed_prefixes(ring, max_steps, cli.step, split_depth, cli.free);
for prefix in &seeds {
let s = prefix
.iter()
.map(|a| a.to_string())
.collect::<Vec<_>>()
.join(",");
println!("SEED {s}");
}
for seq in &closed {
println!("RAT {seq:?}");
}
eprintln!(
"list-seeds: {} alive prefixes at depth {}, {} polygons closed before split",
seeds.len(),
split_depth,
closed.len(),
);
return;
}
if let Some(seed) = cli.seed.as_deref() {
let t0 = Instant::now();
let rats = dispatch_enumerate_from_seed(
ring,
max_steps,
cli.step,
seed,
n_threads,
cli.free,
cli.paranoid,
);
let dt = t0.elapsed();
for seq in &rats {
println!("RAT {seq:?}");
}
eprintln!("seed {:?}: {} unique rats in {dt:?}", seed, rats.len());
return;
}
match cli.mode {
Mode::ListSeeds => unreachable!("handled above"),
Mode::Rehost => unreachable!("handled above"),
Mode::Build => {
let Some(out_dir) = cli.filename.as_deref() else {
eprintln!("--mode build requires -o <output directory>");
std::process::exit(2);
};
let out_dir = std::path::Path::new(out_dir);
let unique_path = out_dir.join(tilezz::rat_enum::stream::UNIQUE_FILENAME);
if !unique_path.exists() {
eprintln!(
"--mode build: {} not found; run `--mode merge` first",
unique_path.display()
);
std::process::exit(2);
}
let t0 = Instant::now();
let records = tilezz::rat_enum::stream::read_unique_records(&unique_path)
.expect("open unique.bin")
.map(|r| r.expect("read unique record"));
let dafsa = RatDafsa::from_sorted_unique_rats(records);
let t_build = t0.elapsed();
eprintln!(
"build: streamed {} rats into RatDafsa in {:?}",
dafsa.len(),
t_build
);
let blocks_dir = out_dir.join("dafsa");
std::fs::create_dir_all(&blocks_dir).expect("create dafsa/");
let t1 = Instant::now();
dafsa
.write_blocks(&blocks_dir, cli.target_block_bytes)
.expect("write_blocks");
if !cli.no_rocrate {
use tilezz::stringmatch::dafsa::{
AssetParams, ProducedVia, SequenceCounts, write_archival_extras, write_ro_crate,
};
let params = AssetParams {
ring,
max_steps,
step: cli.step,
free: cli.free,
target_block_bytes: cli.target_block_bytes,
n_sequences: dafsa.len() as u64,
oeis_a_number: cli.oeis_a_number.as_deref(),
produced_via: ProducedVia::StreamingPipeline,
};
let counts = SequenceCounts::from_rats(dafsa.iter());
write_archival_extras(&blocks_dir, ¶ms).expect("write archival extras");
write_ro_crate(
&blocks_dir,
¶ms,
&counts,
cli.base_url.as_deref(),
cli.doi.as_deref(),
)
.expect("write ro-crate-metadata.json");
}
fn dir_size_recursive(p: &std::path::Path) -> u64 {
let mut total = 0u64;
if let Ok(rd) = std::fs::read_dir(p) {
for entry in rd.flatten() {
let path = entry.path();
if path.is_dir() {
total += dir_size_recursive(&path);
} else if let Ok(m) = entry.metadata() {
total += m.len();
}
}
}
total
}
let total_bytes = dir_size_recursive(&blocks_dir);
eprintln!(
"build: wrote {} ({} bytes) in {:?}",
blocks_dir.display(),
total_bytes,
t1.elapsed()
);
}
Mode::Merge => {
let Some(out_dir) = cli.filename.as_deref() else {
eprintln!("--mode merge requires -o <output directory>");
std::process::exit(2);
};
let t0 = Instant::now();
let cert = tilezz::rat_enum::stream::merge_runs(
std::path::Path::new(out_dir),
ring,
max_steps,
cli.step,
cli.free,
)
.expect("merge_runs");
let dt = t0.elapsed();
println!(
"merge: ring={} step={} max_steps={} -> {} unique rats in {:?}",
ring, cli.step, max_steps, cert.unique_records, dt
);
}
Mode::Stream => {
let Some(out_dir) = cli.filename.as_deref() else {
eprintln!("--mode stream requires -o <output directory>");
std::process::exit(2);
};
STREAM_RAT_LINES.store(false, std::sync::atomic::Ordering::Relaxed);
let t0 = Instant::now();
let stats = tilezz::rat_enum::stream::stream_enum_dispatch(
ring,
max_steps,
cli.step,
n_threads,
cli.free,
cli.paranoid,
std::path::Path::new(out_dir),
)
.expect("stream_enum_dispatch");
let dt = t0.elapsed();
println!(
"stream: ring={} step={} max_steps={} -> wrote runs to {} in {:?}",
ring, cli.step, max_steps, out_dir, dt
);
println!("{stats}");
}
Mode::Dafsa => {
let Some(filename) = cli.filename.as_deref() else {
eprintln!("--mode dafsa requires -o <output path>");
std::process::exit(2);
};
STREAM_RAT_LINES.store(false, std::sync::atomic::Ordering::Relaxed);
let t0 = Instant::now();
let (rats, _stats) =
run_rat_enum_seqs(ring, max_steps, cli.step, n_threads, cli.free, cli.paranoid);
eprintln!("enumerated {} rats in {:?}", rats.len(), t0.elapsed());
let t1 = Instant::now();
let dafsa = RatDafsa::from_rats(rats.iter().map(|r| r.as_slice()));
eprintln!(
"built RatDafsa ({} entries) in {:?}",
dafsa.len(),
t1.elapsed()
);
let t2 = Instant::now();
let file = File::create(filename).expect("create output file");
dafsa
.write_json_gz(BufWriter::new(file))
.expect("write gzipped RatDafsa");
let bytes = std::fs::metadata(filename).map(|m| m.len()).unwrap_or(0);
eprintln!("wrote {filename} ({bytes} bytes) in {:?}", t2.elapsed());
if cli.stats {
print_stats(&rats);
}
}
Mode::DafsaBlocks => {
let Some(dir) = cli.filename.as_deref() else {
eprintln!("--mode dafsa-blocks requires -o <output directory>");
std::process::exit(2);
};
STREAM_RAT_LINES.store(false, std::sync::atomic::Ordering::Relaxed);
let t0 = Instant::now();
let (rats, _stats) =
run_rat_enum_seqs(ring, max_steps, cli.step, n_threads, cli.free, cli.paranoid);
eprintln!("enumerated {} rats in {:?}", rats.len(), t0.elapsed());
let t1 = Instant::now();
let dafsa = RatDafsa::from_rats(rats.iter().map(|r| r.as_slice()));
eprintln!(
"built RatDafsa ({} entries) in {:?}",
dafsa.len(),
t1.elapsed()
);
let t2 = Instant::now();
let path = std::path::Path::new(dir);
std::fs::create_dir_all(path).expect("create output dir");
dafsa
.write_blocks(path, cli.target_block_bytes)
.expect("write blocked RatDafsa");
if !cli.no_rocrate {
use tilezz::stringmatch::dafsa::{
AssetParams, ProducedVia, SequenceCounts, write_archival_extras, write_ro_crate,
};
let params = AssetParams {
ring,
max_steps,
step: cli.step,
free: cli.free,
target_block_bytes: cli.target_block_bytes,
n_sequences: dafsa.len() as u64,
oeis_a_number: cli.oeis_a_number.as_deref(),
produced_via: ProducedVia::InMemory,
};
let counts = SequenceCounts::from_rats(dafsa.iter());
write_archival_extras(path, ¶ms).expect("write archival extras");
write_ro_crate(
path,
¶ms,
&counts,
cli.base_url.as_deref(),
cli.doi.as_deref(),
)
.expect("write ro-crate-metadata.json");
}
fn dir_size(p: &std::path::Path) -> u64 {
let mut total = 0u64;
if let Ok(rd) = std::fs::read_dir(p) {
for entry in rd.flatten() {
let path = entry.path();
if path.is_dir() {
total += dir_size(&path);
} else if let Ok(m) = entry.metadata() {
total += m.len();
}
}
}
total
}
let total_bytes = dir_size(path);
let extras = if cli.no_rocrate {
""
} else {
" + schemas + ro-crate-metadata"
};
eprintln!(
"wrote {dir}/ ({total_bytes} bytes across manifest + blocks{extras}) in {:?}",
t2.elapsed()
);
if cli.stats {
print_stats(&rats);
}
}
Mode::Bench => {
STREAM_RAT_LINES.store(false, std::sync::atomic::Ordering::Relaxed);
let profile = tilezz::util::profile::ProfileGuard::start(cli.profile.as_deref());
let t0 = Instant::now();
let (rats, stats) =
run_rat_enum_seqs(ring, max_steps, cli.step, n_threads, cli.free, cli.paranoid);
let dt = t0.elapsed();
let total_boundary_len: usize = rats.iter().map(|s| s.len()).sum();
println!(
"benchmark: ring={} step={} max_steps={} -> {} unique rats (total boundary len={}) in {:?}",
ring,
cli.step,
max_steps,
rats.len(),
total_boundary_len,
dt
);
println!("{stats}");
profile.finish();
if cli.stats {
print_stats(&rats);
}
}
Mode::Render => {
let rats: Vec<Vec<P64>> = run_rat_enum_polylines(
ring,
max_steps,
cli.step,
n_threads,
cli.free,
cli.paranoid,
);
let Some(filename) = cli.filename else {
return;
};
let mut max_abs: f64 = 1.0;
for poly in &rats {
for (x, y) in poly {
max_abs = max_abs.max(x.abs()).max(y.abs());
}
}
let pad = 0.15 * max_abs;
let r = max_abs + pad;
let bounds = ((-r, -r), (r, r));
let style = TileStyle::filled(
Fill::solid(Color::YELLOW.with_alpha(80)),
Stroke::solid(Color::BLACK, 0.01 * r),
)
.with_vertex_marker(MarkerStyle::filled_circle(0.06 * r, Color::RED))
.with_vertex_labels(TextStyle::new(0.04 * r, Color::WHITE).bold());
let frames: Vec<Scene> = rats
.iter()
.enumerate()
.map(|(ix, tile)| {
println!("rendering frame {}/{}", ix + 1, rats.len());
let mut scene = Scene::new().with_background(Color::WHITE);
scene.draw_tile(tile, &style);
scene
})
.collect();
let w = 500u32;
let vp = Viewport::square_for(w, bounds, 8);
let gif_bytes = render_gif(&frames, &vp, 500).expect("render GIF");
std::fs::write(&filename, gif_bytes).expect("write GIF");
println!("wrote {filename}");
}
}
}
#[cfg(test)]
mod free_tests {
use super::*;
use std::collections::HashMap;
use tilezz::cyclotomic::geometry::intersect;
use tilezz::cyclotomic::{IsRing, Units, ZZ4, ZZ8, ZZ12};
fn validate_simple_polygon<ZZ: IsRing>(angles: &[i8]) -> Result<(), String> {
let n = angles.len();
if n < 3 {
return Err(format!("perimeter {n} < 3"));
}
let mut pts: Vec<ZZ> = Vec::with_capacity(n + 1);
pts.push(ZZ::zero());
let mut dir: i64 = 0;
for &a in angles {
dir = (dir + a as i64).rem_euclid(ZZ::turn() as i64);
let next = *pts.last().unwrap() + <ZZ as Units>::unit(dir as i8);
pts.push(next);
}
if !pts.last().unwrap().is_zero() {
return Err(format!("does not close: last={:?}", pts.last().unwrap()));
}
pts.pop();
let mut seen: HashMap<ZZ, usize> = HashMap::new();
for (i, &p) in pts.iter().enumerate() {
if let Some(&j) = seen.get(&p) {
return Err(format!("duplicate vertex: pts[{j}] == pts[{i}]"));
}
seen.insert(p, i);
}
for i in 0..n {
let a1 = pts[i];
let a2 = pts[(i + 1) % n];
for j in (i + 2)..n {
if i == 0 && j == n - 1 {
continue;
}
let b1 = pts[j];
let b2 = pts[(j + 1) % n];
if intersect(&(a1, a2), &(b1, b2)) {
return Err(format!(
"edges {i} ({a1:?}->{a2:?}) and {j} ({b1:?}->{b2:?}) intersect/touch"
));
}
}
}
Ok(())
}
#[test]
#[cfg_attr(
debug_assertions,
ignore = "release-only: full A316192 pin to n>=10 takes ~12 min debug / ~30 s release"
)]
fn test_oeis_a316192_zz12() {
const OEIS: &[(usize, usize)] = &[
(3, 1),
(4, 3),
(5, 4),
(6, 22),
(7, 69),
(8, 418),
(9, 2210),
(10, 14024),
];
let max_n = OEIS.iter().map(|&(n, _)| n).max().unwrap();
let (rats, _) = super::rat_enum_free::<ZZ12>(max_n, 1);
let mut by_len: std::collections::BTreeMap<usize, usize> =
std::collections::BTreeMap::new();
for seq in &rats {
*by_len.entry(seq.len()).or_insert(0) += 1;
}
let mut mismatches: Vec<(usize, usize, usize)> = Vec::new();
for &(n, expected) in OEIS {
let got = by_len.get(&n).copied().unwrap_or(0);
if got != expected {
mismatches.push((n, got, expected));
}
}
if !mismatches.is_empty() {
for (n, got, expected) in &mismatches {
eprintln!(
"n={n}: got {got}, expected (OEIS A316192) {expected}, diff {:+}",
*got as i64 - *expected as i64
);
}
panic!(
"free ZZ12 enumeration differs from OEIS A316192 at {} perimeter length(s)",
mismatches.len()
);
}
}
#[test]
fn test_free_output_polygons_are_simple_and_unique() {
let (free_rats, _) = super::rat_enum_free::<ZZ12>(9, 1);
let unique: std::collections::HashSet<Vec<i8>> = free_rats.iter().cloned().collect();
assert_eq!(
unique.len(),
free_rats.len(),
"duplicate sequences in free output"
);
let mut failures: Vec<(Vec<i8>, String)> = Vec::new();
for seq in &free_rats {
if let Err(why) = validate_simple_polygon::<ZZ12>(seq) {
failures.push((seq.clone(), why));
}
}
if !failures.is_empty() {
eprintln!("{} polygons failed independent validation:", failures.len());
for (seq, why) in failures.iter().take(20) {
eprintln!(" {seq:?} -- {why}");
}
panic!("non-simple polygons in free enumeration output");
}
}
fn check_quotient_match<ZZ: IsRing>(ring_label: &str, max_steps: usize) {
let (all_rats, _) = super::rat_enum::<ZZ>(max_steps, 1);
let mut expected: HashSet<Vec<i8>> = HashSet::new();
for seq in &all_rats {
expected.insert(super::free_canonical(seq));
}
let (free_rats, _) = super::rat_enum_free::<ZZ>(max_steps, 1);
let actual: HashSet<Vec<i8>> = free_rats.into_iter().collect();
if expected != actual {
for s in expected.difference(&actual) {
eprintln!("[{ring_label} n={max_steps}] MISSING: {s:?}");
}
for s in actual.difference(&expected) {
eprintln!("[{ring_label} n={max_steps}] EXTRA: {s:?}");
}
}
assert_eq!(
expected, actual,
"{ring_label} n={max_steps}: free DFS != rotation DFS / free",
);
eprintln!(
"[{ring_label} n={max_steps}] OK -- {} free classes from {} rotation-canonical rats",
actual.len(),
all_rats.len(),
);
}
#[test]
#[cfg_attr(
debug_assertions,
ignore = "release-only: ZZ12 n<=9 + ZZ8 n<=12 dihedral cross-check is ~9 min debug / ~25 s release"
)]
fn test_free_enum_matches_dfs_quotient() {
for n in [4, 5, 6, 7, 8, 9] {
check_quotient_match::<ZZ12>("ZZ12", n);
}
for n in [4, 6, 8, 10, 12] {
check_quotient_match::<ZZ8>("ZZ8", n);
}
for n in [4, 6, 8, 10, 12, 14] {
check_quotient_match::<ZZ4>("ZZ4", n);
}
}
#[test]
fn test_seed_partitioning_matches_one_shot() {
for &n in &[5usize, 6, 7] {
for &free in &[false, true] {
for &split_depth in &[1usize, 2, 3] {
if split_depth >= n {
continue;
}
let (one_shot_seqs, _) = if free {
super::rat_enum_free::<ZZ12>(n, 1)
} else {
super::rat_enum::<ZZ12>(n, 1)
};
let one_shot: HashSet<Vec<i8>> = one_shot_seqs.into_iter().collect();
let (mut seeded, prefixes) = tilezz::rat_enum::seed::collect_seed_prefixes::<
ZZ12,
>(n, 1, split_depth, free);
for prefix in &prefixes {
for nthreads in &[1usize, 4] {
seeded.extend(tilezz::rat_enum::seed::enumerate_from_seed::<ZZ12>(
n, 1, prefix, *nthreads, free, false,
));
}
}
assert_eq!(
one_shot,
seeded,
"n={n} free={free} split_depth={split_depth}: \
seed-partitioned != one-shot \
({} prefixes + {} pre-closed)",
prefixes.len(),
seeded.len() - prefixes.iter().map(|_| 0).sum::<usize>(),
);
}
}
}
}
}
#[cfg(test)]
mod opt_correctness_tests {
use super::*;
use std::sync::Arc;
use tilezz::cyclotomic::{ZZ4, ZZ6, ZZ8, ZZ10, ZZ12, ZZ14, ZZ16, ZZ18, ZZ20, ZZ24, ZZ32, ZZ60};
use tilezz::rat_enum::prune::closure_table::{ClosureTablePrune, collect_closure_keys};
use tilezz::rat_enum::prune::modular::ModularPrune;
use tilezz::rat_enum::prune::shadow::ShadowPrune;
use tilezz::rat_enum::prune::units::unit_vectors_for_ring;
use tilezz::rat_enum::seed::rat_enum_parallel;
fn closure_tables_for(ring: u8, max_l: usize) -> rustc_hash::FxHashSet<(Vec<i64>, i8)> {
tilezz::dispatch_ring!(ring, collect_closure_keys::<ZZ>(max_l))
}
fn build_prunes(
ring: u8,
max_steps: usize,
with_mod: bool,
with_ck: bool,
with_shadow: bool,
) -> Prunes {
let (units, phi) = unit_vectors_for_ring(ring);
let mut prunes = Prunes::default();
if with_mod {
let mp = ModularPrune::build(&units, phi, max_steps, None);
prunes.modular_prune = Some(Arc::new(mp));
}
if with_ck {
let max_l = 4;
let keys = closure_tables_for(ring, max_l);
prunes.closure_table_prune = Some(Arc::new(ClosureTablePrune { max_l, keys }));
}
if with_shadow {
prunes.shadow_prune = Some(Arc::new(ShadowPrune::for_ring(ring)));
}
prunes
}
fn run<ZZ: IsRing>(
max_steps: usize,
free: bool,
n_threads: usize,
prunes: &Prunes,
) -> std::collections::HashSet<Vec<i8>> {
let ops = make_ops(free);
let (rats, _) = if n_threads <= 1 {
rat_enum_with::<ZZ>(max_steps, 1, ops, "test", "", false, prunes)
} else {
rat_enum_parallel::<ZZ>(max_steps, 1, n_threads, ops, "test", "", false, prunes)
};
rats.into_iter().collect()
}
fn opt_subsets() -> impl Iterator<Item = (bool, bool, bool)> {
(0..8).map(|mask| (mask & 1 != 0, mask & 2 != 0, mask & 4 != 0))
}
fn check_ring<ZZ: IsRing>(ring: u8, max_steps: usize) {
for &free in &[false, true] {
let baseline = run::<ZZ>(max_steps, free, 1, &Prunes::default());
for (with_mod, with_ck, with_shadow) in opt_subsets() {
let prunes = build_prunes(ring, max_steps, with_mod, with_ck, with_shadow);
for &n_threads in &[1usize, 4] {
let got = run::<ZZ>(max_steps, free, n_threads, &prunes);
assert_eq!(
got,
baseline,
"ZZ{ring} n={max_steps} free={free} \
mod={with_mod} ck={with_ck} shadow={with_shadow} threads={n_threads}: \
result set differs from baseline ({} vs {} rats)",
got.len(),
baseline.len(),
);
}
}
}
}
#[test]
fn cross_validate_zz4() {
check_ring::<ZZ4>(4, 10);
}
#[test]
fn cross_validate_zz8() {
check_ring::<ZZ8>(8, 10);
}
#[test]
fn cross_validate_zz12() {
check_ring::<ZZ12>(12, 8);
}
#[test]
#[cfg_attr(
debug_assertions,
ignore = "release-only: ZZ14 n=7 32-prune-combo cross-check is ~5 min debug / ~15 s release"
)]
fn cross_validate_zz14() {
check_ring::<ZZ14>(14, 7);
}
#[test]
#[cfg_attr(
debug_assertions,
ignore = "release-only: ZZ18 n=7 32-prune-combo cross-check is ~13 min debug / ~40 s release"
)]
fn cross_validate_zz18() {
check_ring::<ZZ18>(18, 7);
}
#[test]
fn cross_validate_zz18_step3_matches_zz6() {
let ops_zz6 = make_ops(true);
let (zz6_rats, _) =
rat_enum_with::<ZZ6>(8, 1, ops_zz6, "zz6_ref", "", false, &Prunes::default());
let mut zz6_by_len: std::collections::BTreeMap<usize, usize> =
std::collections::BTreeMap::new();
for r in &zz6_rats {
*zz6_by_len.entry(r.len()).or_insert(0) += 1;
}
let ops_zz18 = make_ops(true);
let (zz18_rats, _) =
rat_enum_with::<ZZ18>(8, 3, ops_zz18, "zz18_step3", "", false, &Prunes::default());
let mut zz18_by_len: std::collections::BTreeMap<usize, usize> =
std::collections::BTreeMap::new();
for r in &zz18_rats {
*zz18_by_len.entry(r.len()).or_insert(0) += 1;
}
let mut all_lens: std::collections::BTreeSet<usize> = zz6_by_len.keys().copied().collect();
all_lens.extend(zz18_by_len.keys().copied());
let mut mismatches: Vec<(usize, usize, usize)> = Vec::new();
for &n in &all_lens {
let z6 = zz6_by_len.get(&n).copied().unwrap_or(0);
let z18 = zz18_by_len.get(&n).copied().unwrap_or(0);
if z6 != z18 {
mismatches.push((n, z6, z18));
}
}
if !mismatches.is_empty() {
for (n, z6, z18) in &mismatches {
eprintln!(
"perim={n}: ZZ6={z6}, ZZ18-step-3={z18}, diff={:+}",
*z18 as i64 - *z6 as i64
);
}
panic!(
"ZZ18-step-3 disagrees with ZZ6 at {} perimeter(s) -- sign helper or \
cell_floor regression in ZZ18",
mismatches.len()
);
}
}
fn assert_step_subset<Big: IsRing, Small: IsRing>(max_steps: usize, step: i8, label: &str) {
let count_by_len = |rats: &[Vec<i8>]| {
let mut m = std::collections::BTreeMap::<usize, usize>::new();
for r in rats {
*m.entry(r.len()).or_insert(0) += 1;
}
m
};
let (big, _) = rat_enum_with::<Big>(
max_steps,
step,
make_ops(true),
label,
"",
false,
&Prunes::default(),
);
let (small, _) = rat_enum_with::<Small>(
max_steps,
1,
make_ops(true),
"ref",
"",
false,
&Prunes::default(),
);
assert_eq!(
count_by_len(&big),
count_by_len(&small),
"{label}: step-{step} subset counts disagree with the reference ring \
-- a sign-helper or cell_floor bug in the bigger ring",
);
}
#[test]
fn zz16_step2_matches_zz8() {
assert_step_subset::<ZZ16, ZZ8>(8, 2, "zz16_step2");
}
#[test]
fn zz20_step2_matches_zz10() {
assert_step_subset::<ZZ20, ZZ10>(7, 2, "zz20_step2");
}
#[test]
fn zz24_step2_matches_zz12() {
assert_step_subset::<ZZ24, ZZ12>(7, 2, "zz24_step2");
}
#[test]
fn zz32_step4_matches_zz8() {
assert_step_subset::<ZZ32, ZZ8>(6, 4, "zz32_step4");
}
#[test]
fn zz60_step5_matches_zz12() {
assert_step_subset::<ZZ60, ZZ12>(6, 5, "zz60_step5");
}
#[test]
#[cfg_attr(
debug_assertions,
ignore = "release-only: A316192 pin x 32 prune combos is ~17 min debug / ~60-90 s release"
)]
fn oeis_a316192_each_opt_combo() {
const OEIS: &[(usize, usize)] = &[
(3, 1),
(4, 3),
(5, 4),
(6, 22),
(7, 69),
(8, 418),
(9, 2210), (10, 14024), ];
let max_n = OEIS.iter().map(|&(n, _)| n).max().unwrap();
for (with_mod, with_ck, with_shadow) in opt_subsets() {
let prunes = build_prunes(12, max_n, with_mod, with_ck, with_shadow);
for &n_threads in &[1usize, 4] {
let rats = run::<ZZ12>(max_n, true, n_threads, &prunes);
let mut by_len: std::collections::BTreeMap<usize, usize> =
std::collections::BTreeMap::new();
for seq in &rats {
*by_len.entry(seq.len()).or_insert(0) += 1;
}
let mut mismatches: Vec<(usize, usize, usize)> = Vec::new();
for &(n, expected) in OEIS {
let got = by_len.get(&n).copied().unwrap_or(0);
if got != expected {
mismatches.push((n, got, expected));
}
}
if !mismatches.is_empty() {
for (n, got, expected) in &mismatches {
eprintln!(
"n={n}: got {got}, expected (OEIS A316192) {expected}, diff {:+}",
*got as i64 - *expected as i64
);
}
panic!(
"OEIS mismatch with mod={with_mod} ck={with_ck} shadow={with_shadow} \
threads={n_threads}: {} length(s) differ",
mismatches.len()
);
}
}
}
}
#[test]
#[ignore = "opt-in (cargo test -- --include-ignored): ~4 min; pre-submission / thorough CI \
guard, not part of the default debug or release suite"]
fn zz12_extension_frontier_guard() {
let none = build_prunes(12, 11, false, false, false);
let all11 = build_prunes(12, 11, true, true, true);
let base = by_length(&run::<ZZ12>(11, true, 0, &none));
let pruned = by_length(&run::<ZZ12>(11, true, 0, &all11));
assert_eq!(
base, pruned,
"ZZ12 free n=11: prunes changed the count -- over-pruning at the frontier",
);
let all12 = build_prunes(12, 12, true, true, true);
let c12 = by_length(&run::<ZZ12>(12, true, 0, &all12));
assert_eq!(c12.get(&11).copied(), Some(89075), "ZZ12 a(11) regression");
assert_eq!(c12.get(&12).copied(), Some(597581), "ZZ12 a(12) regression");
}
fn by_length(
rats: &std::collections::HashSet<Vec<i8>>,
) -> std::collections::BTreeMap<usize, usize> {
let mut by_len = std::collections::BTreeMap::new();
for seq in rats {
*by_len.entry(seq.len()).or_insert(0) += 1;
}
by_len
}
fn assert_oeis_pins<ZZ: IsRing>(ring: u8, oeis_name: &str, oeis: &[(usize, usize)]) {
let max_n = oeis.iter().map(|&(n, _)| n).max().unwrap();
let prunes = build_prunes(ring, max_n, true, true, true);
let rats = run::<ZZ>(max_n, true, 1, &prunes);
let by_len = by_length(&rats);
let mut mismatches: Vec<(usize, usize, usize)> = Vec::new();
for &(n, expected) in oeis {
let got = by_len.get(&n).copied().unwrap_or(0);
if got != expected {
mismatches.push((n, got, expected));
}
}
if !mismatches.is_empty() {
for (n, got, expected) in &mismatches {
eprintln!(
"{oeis_name} ZZ{ring} perim={n}: got {got}, OEIS says {expected}, diff {:+}",
*got as i64 - *expected as i64
);
}
panic!("{oeis_name} ZZ{ring}: {} term(s) differ", mismatches.len());
}
}
#[test]
fn oeis_a266549_zz4_pin() {
const OEIS: &[(usize, usize)] = &[
(4, 1), (6, 1), (8, 3), (10, 6), (12, 25), (14, 86), ];
assert_oeis_pins::<ZZ4>(4, "A266549", OEIS);
}
#[test]
fn oeis_a316198_zz8_pin() {
const OEIS: &[(usize, usize)] = &[
(4, 2), (6, 6), (8, 59), (10, 695), (12, 12198), ];
assert_oeis_pins::<ZZ8>(8, "A316198", OEIS);
}
#[test]
fn oeis_a316200_zz10_pin() {
const OEIS: &[(usize, usize)] = &[
(4, 2), (5, 2), (6, 10), (7, 15), (8, 124), (9, 352), (10, 2378), ];
assert_oeis_pins::<ZZ10>(10, "A316200", OEIS);
}
#[test]
fn oeis_a284869_zz6_pin() {
const OEIS: &[(usize, usize)] = &[
(3, 1), (4, 1), (5, 1), (6, 4), (7, 5), (8, 16), (9, 37), (10, 120), (11, 344), (12, 1175), (13, 3807), (14, 13224), ];
assert_oeis_pins::<ZZ6>(6, "A284869", OEIS);
}
}