main.rs
18.8 kB · rust · 604 lines
1use mrlycore::tensor::Tensor;2use mrlylab::atlas::run::heat_frame;3use mrlylab::atlas::{4 block_split, census, factors, fate_table, first_negative_lobe, mask_tensor, mini, pack, Census,5 Reading, Run,6};7use mrlymath::life::{animate, mask_offsets, moore, Boundary, Config, Fate};8use mrlymath::two::{carpet, create, Cell2d};9use std::collections::{BTreeMap, BTreeSet};1011const CAP: usize = 5000;12const SAMPLE_SEED: u64 = 1729;13const ROWS: usize = 40;1415#[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Debug)]16enum Kind {17 None,18 Confined,19 Tiled,20 Board,21 Proper,22}2324type Witness = (usize, usize, usize, usize, u128, usize);2526struct Scan {27 best: Kind,28 in_place: Kind,29 witness: Option<Witness>,30}3132struct Entry {33 label: String,34 index: usize,35 fill: usize,36 line: String,37 scan: Scan,38}3940struct Blocks {41 outer: Vec<u8>,42 inner: Vec<u8>,43 block: Vec<u8>,44}4546impl Blocks {47 fn new(n: usize) -> Blocks {48 Blocks {49 outer: vec![0u8; n * n],50 inner: vec![0u8; n * n],51 block: vec![0u8; n * n],52 }53 }54}5556fn split_into(bytes: &[u8], n: usize, shift: (usize, usize), d: usize, buf: &mut Blocks) -> bool {57 let m = n / d;58 let (dr, dc) = shift;59 let outer = &mut buf.outer[..d * d];60 let inner = &mut buf.inner[..m * m];61 let block = &mut buf.block[..m * m];62 outer.fill(0);63 let mut have = false;64 for i in 0..d {65 for j in 0..d {66 let mut live = false;67 for p in 0..m {68 let row = ((i * m + p + dr) % n) * n;69 for q in 0..m {70 let v = bytes[row + (j * m + q + dc) % n];71 block[p * m + q] = v;72 live |= v != 0;73 }74 }75 if !live {76 continue;77 }78 outer[i * d + j] = 1;79 if !have {80 inner.copy_from_slice(block);81 have = true;82 } else if *inner != *block {83 return false;84 }85 }86 }87 have88}8990fn one_run(live: &[bool]) -> bool {91 let d = live.len();92 if !live.iter().any(|&v| v) {93 return false;94 }95 (0..d).filter(|&i| live[i] && !live[(i + 1) % d]).count() <= 196}9798fn rect(outer: &[u8], d: usize) -> Option<(usize, usize)> {99 let rows: Vec<bool> = (0..d)100 .map(|i| (0..d).any(|j| outer[i * d + j] != 0))101 .collect();102 let cols: Vec<bool> = (0..d)103 .map(|j| (0..d).any(|i| outer[i * d + j] != 0))104 .collect();105 if !one_run(&rows) || !one_run(&cols) {106 return None;107 }108 let high = rows.iter().filter(|&&v| v).count();109 let wide = cols.iter().filter(|&&v| v).count();110 if outer.iter().filter(|&&v| v != 0).count() == high * wide {111 Some((high, wide))112 } else {113 None114 }115}116117fn classify(outer: &[u8], d: usize, foot: usize) -> Kind {118 let fill = outer.iter().filter(|&&v| v != 0).count();119 if fill == 1 {120 Kind::Confined121 } else if fill == d * d {122 Kind::Tiled123 } else if rect(outer, d) == Some((foot, foot)) {124 Kind::Board125 } else {126 Kind::Proper127 }128}129130fn footprint(canvas: usize, side: usize, d: usize) -> usize {131 let m = canvas / d;132 let pad = (canvas - side) / 2;133 (pad + side - 1) / m - pad / m + 1134}135136fn scan(frame: &Tensor, cuts: &[usize], side: usize) -> Scan {137 let n = frame.shape[0];138 let bytes = frame.bytes();139 let mut buf = Blocks::new(n);140 let mut best = Kind::None;141 let mut in_place = Kind::None;142 let mut witness = None;143 for dr in 0..n {144 for dc in 0..n {145 for &d in cuts {146 let m = n / d;147 if !split_into(bytes, n, (dr, dc), d, &mut buf) {148 continue;149 }150 let kind = classify(&buf.outer[..d * d], d, footprint(n, side, d));151 if dr == 0 && dc == 0 && kind > in_place {152 in_place = kind;153 }154 if kind > best {155 best = kind;156 }157 if kind == Kind::Proper && witness.is_none() {158 let fill = buf.outer[..d * d].iter().filter(|&&v| v != 0).count();159 let tile = Tensor::of(buf.inner[..m * m].to_vec(), vec![m, m]);160 let code = pack(&tile).unwrap_or(0);161 witness = Some((dr, dc, d, fill, code, tile.sum() as usize));162 }163 }164 }165 }166 Scan {167 best,168 in_place,169 witness,170 }171}172173fn witness_line(entry: &Entry) -> String {174 match entry.scan.witness {175 Some((dr, dc, d, outer, code, inner)) => format!(176 "{} fill {} shift ({dr},{dc}) d {d} outer fill {outer} inner tile {code} of {inner} cells",177 entry.label, entry.fill178 ),179 None => format!("{} fill {} none", entry.label, entry.fill),180 }181}182183fn report(title: &str, head: &str, entries: &[Entry]) {184 println!("\n{title}");185 println!(" {head}");186 println!(" a cut is confined when the nonzero blocks sit in one block of the cut, a tiling when every block is equal, the board when the outer is the board's own footprint block up to a torus shift, proper otherwise");187 let mut place = [0usize; 5];188 let mut after = [0usize; 5];189 let mut per: BTreeMap<usize, [usize; 3]> = BTreeMap::new();190 let mut first: BTreeMap<usize, String> = BTreeMap::new();191 for entry in entries {192 place[entry.scan.in_place as usize] += 1;193 after[entry.scan.best as usize] += 1;194 let row = per.entry(entry.index).or_default();195 row[0] += 1;196 row[1] += usize::from(entry.scan.in_place == Kind::Proper);197 row[2] += usize::from(entry.scan.best == Kind::Proper);198 if entry.scan.best == Kind::Proper {199 first200 .entry(entry.index)201 .or_insert_with(|| witness_line(entry));202 }203 }204 let show = |what: &str, counts: &[usize; 5]| {205 println!(206 " {what:<12} no cut {} confined {} tiling {} board {} proper {}",207 counts[0], counts[1], counts[2], counts[3], counts[4]208 );209 };210 show("in place", &place);211 show("after shifts", &after);212 for (index, counts) in &per {213 println!(214 " index {index}: frames {}, proper in place {}, proper after some shift {}",215 counts[0], counts[1], counts[2]216 );217 if let Some(line) = first.get(index) {218 println!(" first witness {line}");219 }220 }221 let mut rows = 0;222 for entry in entries.iter().filter(|e| e.scan.best == Kind::Proper) {223 rows += 1;224 if rows <= ROWS {225 println!(" proper {} | {}", witness_line(entry), entry.line);226 }227 }228 if rows > ROWS {229 println!(" and {} more rows", rows - ROWS);230 }231}232233fn reading_line(r: &Reading) -> String {234 format!(235 "fill {} comp {} holes {} euler {} box {:.2} sym {} ring {} share {:.2} cut {} ent {} churn {:.3}",236 r.fill,237 r.components,238 r.holes,239 r.euler,240 r.box_slope,241 r.symmetry.name,242 r.ring,243 r.share,244 r.ring_cut,245 r.entropy,246 r.churn247 )248}249250fn board_of(run: &Run) -> Cell2d {251 create(run.seed.code, run.seed.side, run.seed.level, 0, 2)252 .unwrap()253 .tile(run.tessellation, run.tessellation)254}255256fn rows_of(tile: &Tensor) -> String {257 let n = tile.shape[0];258 (0..n)259 .map(|r| {260 (0..n)261 .map(|c| if tile.get(&[r, c]) != 0 { '#' } else { '.' })262 .collect::<String>()263 })264 .collect::<Vec<String>>()265 .join("/")266}267268fn cuts_of(canvas: usize) -> Vec<usize> {269 (2..canvas).filter(|d| canvas.is_multiple_of(*d)).collect()270}271272fn rules(census: &Census) {273 println!("\nRULES birth = survive counts at budget 8 and 80");274 for rule in &census.preset.rules {275 let at = |budget: usize| rule.birth().values(budget).unwrap();276 println!(" {:<14} {:?} {:?}", rule.name(), at(8), at(80));277 }278}279280fn seeds(census: &Census) {281 println!("\nSEEDS the level-1 tile of every seed class, rows top to bottom");282 for seed in &census.preset.seeds {283 let tile = create(seed.code, seed.side, seed.level, 0, 2).unwrap();284 println!(285 " {}s{}l{} {}",286 seed.code,287 seed.side,288 seed.level,289 rows_of(tile.types())290 );291 }292}293294fn budgets(census: &Census) {295 println!("\nBUDGETS the largest neighbour count of every mask cell (seed, tessellation, mask)");296 let mut seen = BTreeSet::new();297 let mut cells = Vec::new();298 for run in &census.runs {299 let key = format!(300 "{}s{}l{} t{} {}",301 run.seed.code,302 run.seed.side,303 run.seed.level,304 run.tessellation,305 run.mask.name()306 );307 if !seen.insert(key.clone()) {308 continue;309 }310 let budget = mask_tensor(&run.mask, &board_of(run)).unwrap().sum() as usize;311 let copy = run.mask.name().starts_with("copy") && run.tessellation == 3;312 cells.push((key, budget, copy));313 }314 for (key, budget, _) in &cells {315 println!(" {key:<22} budget {budget}");316 }317 let small = cells.iter().filter(|(_, b, _)| *b <= 8).count();318 let big: Vec<&(String, usize, bool)> = cells.iter().filter(|(_, b, _)| *b > 8).collect();319 let low = big.iter().map(|(_, b, _)| *b).min().unwrap_or(0);320 let high = big.iter().map(|(_, b, _)| *b).max().unwrap_or(0);321 let copies = big.iter().filter(|(_, _, c)| *c).count();322 println!(323 "mask cells {}: {small} at budget 8 or less, {} above (budgets {low} to {high}), {copies} of those tessellation-3 copy masks",324 cells.len(),325 big.len()326 );327}328329fn fates(census: &Census) {330 println!("\nFATES per rule (dead alive loop timeout)");331 let mut family = "";332 let mut subtotal = [0usize; 4];333 let mut total = [0usize; 4];334 let flush = |family: &str, subtotal: &[usize; 4]| {335 if !family.is_empty() {336 println!(" {family:<8} total {subtotal:?}");337 }338 };339 for (fam, rule, counts) in fate_table(census) {340 if fam != family {341 flush(family, &subtotal);342 family = fam;343 subtotal = [0; 4];344 }345 println!(" {fam:<8} {rule:<14} {counts:?}");346 for i in 0..4 {347 subtotal[i] += counts[i];348 total[i] += counts[i];349 }350 }351 flush(family, &subtotal);352 println!(" all total {total:?}");353 let timeouts = census354 .runs355 .iter()356 .filter(|r| r.fate == Fate::Timeout)357 .count();358 let movers = census.runs.iter().filter(|r| r.mover.is_some()).count();359 println!(360 "timeouts {timeouts} of {} runs, movers among them {movers}",361 census.runs.len()362 );363 for run in census.runs.iter().filter(|r| r.mover.is_some()).take(ROWS) {364 let (dr, dc, lag) = run.mover.unwrap();365 println!(" mover {} shift ({dr},{dc}) lag {lag}", run.label());366 }367 budgets(census);368}369370fn closure(census: &Census) {371 let cuts = cuts_of(census.preset.canvas);372 let mut entries = Vec::new();373 for run in &census.runs {374 let Some(frame) = &run.settled else { continue };375 let reading = run.reading.as_ref().unwrap();376 entries.push(Entry {377 label: run.label(),378 index: run.mask_index,379 fill: reading.fill,380 line: reading_line(reading),381 scan: scan(frame.types(), &cuts, board_of(run).types().shape[0]),382 });383 }384 let head = format!(385 "{} settled frames, {} distinct up to the dihedral group and torus translation, every one of the {} torus shifts and both cuts {:?}",386 entries.len(),387 census.distinct,388 census.preset.canvas * census.preset.canvas,389 cuts390 );391 report(392 "CLOSURE the block test on every settled frame",393 &head,394 &entries,395 );396}397398fn config(run: &Run, mask: Tensor, canvas: usize, board_side: usize) -> Config {399 Config {400 mask: Cell2d::new(mask),401 birth: run.rule.birth(),402 survive: run.rule.survive(),403 boundary: run.boundary,404 max_generations: 64,405 grid_size: 1,406 padding: (canvas - board_side) / 2,407 }408}409410fn replay(run: &Run) -> Vec<Cell2d> {411 let board = board_of(run);412 let side = board.types().shape[0];413 let mask = mask_tensor(&run.mask, &board).unwrap();414 animate(&board, &config(run, mask, 27, side)).unwrap().grids415}416417fn heat(census: &Census) {418 let cuts = cuts_of(census.preset.canvas);419 let mut entries = Vec::new();420 for run in &census.runs {421 let frame = heat_frame(&replay(run));422 entries.push(Entry {423 label: run.label(),424 index: run.mask_index,425 fill: run.heat.fill,426 line: reading_line(&run.heat),427 scan: scan(frame.types(), &cuts, board_of(run).types().shape[0]),428 });429 }430 let head = format!(431 "{} heat frames, every one of the {} torus shifts and both cuts {:?}",432 entries.len(),433 census.preset.canvas * census.preset.canvas,434 cuts435 );436 report(437 "HEAT the block test on the median level set of every run's visit counts",438 &head,439 &entries,440 );441}442443fn lemma(census: &Census) {444 println!("\nLEMMA a mask on the sublattice 3Z^2 with 0 outside birth keeps every frame a Kronecker product A(t) (x) seed, A(t) the same rule on the 9-torus under mask/3");445 let mut checked = 0;446 let mut rules = BTreeSet::new();447 let mut masks = BTreeSet::new();448 for run in &census.runs {449 let board = board_of(run);450 let mask = mask_tensor(&run.mask, &board).unwrap();451 let offsets = mask_offsets(&mask);452 if offsets.is_empty() || offsets.iter().any(|o| o[0] % 3 != 0 || o[1] % 3 != 0) {453 continue;454 }455 let budget = mask.sum() as usize;456 if run.rule.birth().values(budget).unwrap().contains(&0) || run.tessellation != 3 {457 continue;458 }459 let mut small = Tensor::new(vec![3, 3]);460 for o in &offsets {461 small.set(&[(1 + o[0] / 3) as usize, (1 + o[1] / 3) as usize], 1);462 }463 let seed = create(run.seed.code, run.seed.side, run.seed.level, 0, 2).unwrap();464 let outer = Cell2d::new(Tensor::full(vec![3, 3], 1));465 let quotient = animate(&outer, &config(run, small, 9, 3)).unwrap();466 let full = animate(&board, &config(run, mask, 27, 9)).unwrap();467 assert_eq!(full.fate, quotient.fate, "{} fates differ", run.label());468 assert_eq!(469 full.grids.len(),470 quotient.grids.len(),471 "{} lengths differ",472 run.label()473 );474 for (a, x) in quotient.grids.iter().zip(&full.grids) {475 assert_eq!(476 a.types().kron(seed.types()).bytes(),477 x.types().bytes(),478 "{} frame differs",479 run.label()480 );481 }482 checked += 1;483 rules.insert(run.rule.name());484 masks.insert(format!(485 "{}s{} {} budget {budget}",486 run.seed.code,487 run.seed.side,488 run.mask.name()489 ));490 }491 println!(492 "verified frame by frame on {checked} runs, {} rules, masks {:?}",493 rules.len(),494 masks495 );496}497498fn stills(census: &Census) {499 println!("\nSTILLS tessellated seeds (t >= 3) reaching a still: peak ring against the seed comb and the mask lobe");500 let canvas = census.preset.canvas;501 let mut rows = 0;502 let mut comb_hits = 0;503 let mut lobe_hits = 0;504 let mut ring_stills = 0;505 for run in census506 .runs507 .iter()508 .filter(|r| r.tessellation >= 3 && r.fate == Fate::Alive)509 {510 let reading = run.reading.as_ref().unwrap();511 let comb = canvas / run.seed.side;512 let mask = mask_tensor(&run.mask, &board_of(run)).unwrap();513 let lobe = first_negative_lobe(&mask, canvas);514 let on_comb = reading.ring > 0 && reading.ring.is_multiple_of(comb);515 let in_lobe = lobe > 0 && reading.ring >= lobe;516 let ring_still = reading.share >= 0.5;517 comb_hits += usize::from(on_comb);518 lobe_hits += usize::from(in_lobe);519 ring_stills += usize::from(ring_still);520 rows += 1;521 if rows <= ROWS {522 println!(523 " {} at {} ring {} share {:.2} comb {comb} {} lobe {lobe} {} | fill {} sym {} factors {:?}",524 run.label(),525 run.settled_at,526 reading.ring,527 reading.share,528 if on_comb { "hit" } else { "miss" },529 if in_lobe { "in" } else { "out" },530 reading.fill,531 reading.symmetry.name,532 reading.factors533 );534 }535 }536 if rows > ROWS {537 println!(" and {} more rows", rows - ROWS);538 }539 println!("stills at t >= 3: {rows}, peak on a comb harmonic {comb_hits}, peak at or past the mask lobe {lobe_hits}, peak share at least one half {ring_stills}");540}541542fn self_check() {543 let mut t = Tensor::new(vec![5, 5]);544 t.set(&[1, 2], 1);545 t.set(&[2, 2], 1);546 t.set(&[3, 2], 1);547 let config = Config {548 boundary: Boundary::Constant,549 max_generations: 16,550 ..Config::new(moore(), vec![3], vec![2, 3])551 };552 let life = animate(&Cell2d::new(t), &config).unwrap();553 assert_eq!(554 (life.fate, life.loop_length),555 (Fate::Loop, 2),556 "the blinker must loop with period 2"557 );558 let frame = carpet(3, 2).unwrap();559 assert_eq!(560 factors(frame.types()),561 Some((3, 495, 495)),562 "the level-2 carpet must factor at 3"563 );564 let (outer, inner) = block_split(frame.types(), 3).unwrap();565 let mut buf = Blocks::new(9);566 assert!(567 split_into(frame.types().bytes(), 9, (0, 0), 3, &mut buf),568 "the shift split must find the carpet cut"569 );570 assert_eq!(571 (&buf.outer[..9], &buf.inner[..9]),572 (outer.bytes(), inner.bytes()),573 "the shift split must match block_split"574 );575 println!("\nSELF-CHECK blinker period 2 under b3s23, carpet level 2 factors as (3, 495, 495), the shift split agrees with block_split at shift (0,0)");576}577578fn main() {579 let preset = mini();580 for line in preset.describe() {581 println!("{line}");582 }583 let census = census(&preset, CAP, SAMPLE_SEED).unwrap();584 println!(585 "cut: canvas {} generations {} sweep {} after {} duplicate-mask runs dropped, ran {}{}",586 preset.canvas,587 preset.generations,588 census.universe,589 census.duplicates,590 census.runs.len(),591 match census.sample {592 Some(seed) => format!(", a sample drawn with seed {seed}"),593 None => String::new(),594 }595 );596 seeds(&census);597 rules(&census);598 fates(&census);599 closure(&census);600 heat(&census);601 lemma(&census);602 stills(&census);603 self_check();604}