main.rs
40.0 kB · rust · 1249 lines
1use mrlycore::state::{choice, randint, seed};2use mrlycore::tensor::Tensor;3use mrlygame::frames::secondaries;4use mrlygame::music::score;5use mrlygame::sequence::rulebook;6use mrlygame::variations::{board, mask, Board};7use mrlygame::{pivot_options, quest, Config, Path, Way};8use mrlymath::life::crop;9use mrlymath::life::metrics::{churn, entropy};10use mrlymath::life::{moore, next_grid, Boundary, Counts, Fate};11use mrlymath::two::Cell2d;12use mrlynum::fft::{convolve_with, embed_kernel, peak_ring, radial_profile, transform};13use std::collections::HashMap;14use std::time::Instant;1516// ENGINE1718#[derive(Clone)]19struct Grid {20 side: usize,21 data: Vec<u8>,22}2324impl Grid {25 fn of(cell: &Cell2d) -> Grid {26 let side = cell.width();27 Grid {28 side,29 data: cell.types().bytes().to_vec(),30 }31 }32 fn cell(&self) -> Cell2d {33 Cell2d::new(Tensor::of(self.data.clone(), vec![self.side, self.side]))34 }35 fn tile(&self, reps: usize) -> Grid {36 let side = self.side * reps;37 let mut data = vec![0u8; side * side];38 for r in 0..side {39 for c in 0..side {40 data[r * side + c] = self.data[(r % self.side) * self.side + c % self.side];41 }42 }43 Grid { side, data }44 }45 fn pad(&self, count: usize) -> Grid {46 let side = self.side + 2 * count;47 let mut data = vec![0u8; side * side];48 for r in 0..self.side {49 let src = &self.data[r * self.side..(r + 1) * self.side];50 data[(r + count) * side + count..(r + count) * side + count + self.side]51 .copy_from_slice(src);52 }53 Grid { side, data }54 }55}5657struct Plan {58 n: usize,59 rho: usize,60 shift: bool,61 kre: Vec<f64>,62 kim: Vec<f64>,63}6465struct Stepper {66 side: usize,67 wrap: bool,68 offsets: Vec<(isize, isize)>,69 plan: Plan,70}7172impl Stepper {73 fn new(side: usize, mask: &Grid, wrap: bool) -> Stepper {74 let m = mask.side;75 let rho = m / 2;76 let mut offsets = Vec::new();77 for r in 0..m {78 for c in 0..m {79 if mask.data[r * m + c] == 1 {80 offsets.push((r as isize - rho as isize, c as isize - rho as isize));81 }82 }83 }84 let need = if wrap && side.is_power_of_two() && m <= side {85 side86 } else if wrap {87 side + 2 * rho88 } else {89 side + rho90 };91 let n = need.max(m).next_power_of_two();92 let shift_cost = side * side * offsets.len();93 let fft_cost = 16 * n * n * (n.trailing_zeros() as usize + 1);94 let shift = shift_cost <= fft_cost;95 let (kre, kim) = if shift {96 (Vec::new(), Vec::new())97 } else {98 transform(&embed_kernel(&mask.data, m, n), n)99 };100 Stepper {101 side,102 wrap,103 offsets,104 plan: Plan {105 n,106 rho,107 shift,108 kre,109 kim,110 },111 }112 }113 fn cost(&self) -> u64 {114 if self.plan.shift {115 (self.side * self.side * self.offsets.len()) as u64116 } else {117 (16 * self.plan.n * self.plan.n * (self.plan.n.trailing_zeros() as usize + 1)) as u64118 }119 }120 fn counts(&self, grid: &[u8]) -> Vec<u32> {121 if self.plan.shift {122 self.counts_shift(grid)123 } else {124 self.counts_fft(grid)125 }126 }127 fn counts_shift(&self, grid: &[u8]) -> Vec<u32> {128 let s = self.side;129 let si = s as isize;130 let mut out = vec![0u32; s * s];131 for &(dr, dc) in &self.offsets {132 for r in 0..s {133 let sr = r as isize + dr;134 let sr = if self.wrap {135 sr.rem_euclid(si)136 } else if sr < 0 || sr >= si {137 continue;138 } else {139 sr140 } as usize;141 let row = &grid[sr * s..(sr + 1) * s];142 let dst = &mut out[r * s..(r + 1) * s];143 if self.wrap {144 let shift = dc.rem_euclid(si) as usize;145 for (c, slot) in dst.iter_mut().enumerate() {146 let mut sc = c + shift;147 if sc >= s {148 sc -= s;149 }150 *slot += row[sc] as u32;151 }152 } else {153 let lo = (-dc).max(0) as usize;154 let hi = (si - dc).min(si) as usize;155 for c in lo..hi {156 dst[c] += row[(c as isize + dc) as usize] as u32;157 }158 }159 }160 }161 out162 }163 fn counts_fft(&self, grid: &[u8]) -> Vec<u32> {164 let s = self.side;165 let n = self.plan.n;166 let rho = self.plan.rho;167 let mut field = vec![0.0; n * n];168 let periodic = self.wrap && n != s;169 let (span, off) = if periodic { (s + 2 * rho, rho) } else { (s, 0) };170 for r in 0..span {171 let sr = (r + s - off % s) % s;172 for c in 0..span {173 let sc = (c + s - off % s) % s;174 field[r * n + c] = grid[sr * s + sc] as f64;175 }176 }177 let conv = convolve_with(&field, &self.plan.kre, &self.plan.kim, n);178 let mut out = vec![0u32; s * s];179 for r in 0..s {180 for c in 0..s {181 out[r * s + c] = conv[(r + off) * n + c + off].round() as u32;182 }183 }184 out185 }186 fn next(&self, grid: &[u8], birth: &[bool], survive: &[bool]) -> Vec<u8> {187 let counts = self.counts(grid);188 grid.iter()189 .zip(&counts)190 .map(|(&v, &k)| {191 let table = if v == 1 { survive } else { birth };192 u8::from(table.get(k as usize).copied().unwrap_or(false))193 })194 .collect()195 }196}197198fn table(values: &[usize], budget: usize) -> Vec<bool> {199 let mut out = vec![false; budget + 1];200 for &v in values {201 if v <= budget {202 out[v] = true;203 }204 }205 out206}207208struct Chapter {209 way: Way,210 path: Path,211 mask: Grid,212 rule: String,213 frames: Vec<Vec<u8>>,214 fate: Fate,215}216217struct Replay {218 outer: u64,219 tile: Grid,220 inner: u64,221 boundary: Boundary,222 canvas: usize,223 unit: usize,224 t: usize,225 climb: usize,226 chapters: Vec<Chapter>,227 attempts: usize,228 cost: u64,229}230231fn hex_key() {232 for _ in 0..8 {233 randint(0, 15);234 }235}236237fn run_chapter(238 start: Grid,239 mask: &Grid,240 rule: (&[usize], &[usize]),241 boundary: Boundary,242 cap: usize,243 cost: &mut u64,244 deadline: Option<Instant>,245) -> Option<(Vec<Vec<u8>>, Fate)> {246 let (birth, survive) = rule;247 let budget = mask.data.iter().filter(|&&v| v == 1).count();248 let birth = table(birth, budget);249 let survive = table(survive, budget);250 let stepper = Stepper::new(start.side, mask, boundary.wrap());251 let mut current = start.data;252 let mut frames = vec![current.clone()];253 let mut history: HashMap<Vec<u8>, usize> = HashMap::new();254 history.insert(current.clone(), 0);255 let mut fate = Fate::Timeout;256 for i in 1..cap {257 if let Some(d) = deadline {258 if Instant::now() > d {259 return None;260 }261 }262 let next = stepper.next(¤t, &birth, &survive);263 *cost += stepper.cost();264 if next == current {265 fate = if next.iter().all(|&v| v == 0) {266 Fate::Dead267 } else {268 Fate::Alive269 };270 break;271 }272 if history.contains_key(&next) {273 fate = Fate::Loop;274 break;275 }276 history.insert(next.clone(), i);277 current = next;278 frames.push(current.clone());279 }280 Some((frames, fate))281}282283fn replay(outer: u64, config: &Config, deadline: Option<Instant>) -> Option<Replay> {284 seed(outer);285 let mut cost = 0u64;286 for attempt in 0..config.attempts.max(1) {287 let inner = randint(0, i64::MAX) as u64;288 seed(inner);289 hex_key();290 let boundary = choice(&[Boundary::Constant, Boundary::Wrap]);291 let mut chapters: Vec<Chapter> = Vec::new();292 let mut prev: Option<Grid> = None;293 let mut climb = (0, 0, 0, 0);294 let mut tile = Grid {295 side: 0,296 data: Vec::new(),297 };298 for index in 0..config.max_segments {299 hex_key();300 choice(&secondaries());301 let (way, stage) = match (&prev, chapters.last()) {302 (Some(grid), Some(last)) => (last.way.flip(), Board::of(grid.cell())),303 _ => {304 let way = choice(&[Way::Conway, Way::Mrly]);305 (way, board(config).unwrap())306 }307 };308 let (path, mask_cell, rule) = match way {309 Way::Conway => (Path::Simple, moore(), None),310 Way::Mrly => {311 let (path, cell) = mask(&stage, config).unwrap();312 let rule = rulebook(path == Path::Simple);313 (path, cell, Some(rule))314 }315 };316 let _ = score(way);317 if index == 0 {318 climb = (stage.canvas_unit(), stage.unit, stage.grid, stage.canvas);319 tile = Grid::of(&stage.cell);320 }321 let (birth, survive, name) = match &rule {322 Some(r) => (323 r.birth(),324 r.survive(),325 format!(326 "B{}/S{}{}{}",327 r.birth_sequence.name(),328 r.survive_sequence.name(),329 if r.zeros { "+0" } else { "" },330 if r.ones { "+1" } else { "" }331 ),332 ),333 None => (334 Counts::from(vec![3]),335 Counts::from(vec![2, 3]),336 "B3/S23".to_string(),337 ),338 };339 let mask_grid = Grid::of(&mask_cell);340 let budget = mask_cell.types().sum() as usize;341 let birth = birth.values(budget).unwrap();342 let survive = survive.values(budget).unwrap();343 let mut start = Grid::of(&stage.cell);344 if stage.grid > 1 {345 start = start.tile(stage.grid);346 }347 if stage.padding() > 0 {348 start = start.pad(stage.padding());349 }350 let (frames, fate) = run_chapter(351 start,352 &mask_grid,353 (&birth, &survive),354 boundary,355 config.max_generations,356 &mut cost,357 deadline,358 )?;359 chapters.push(Chapter {360 way,361 path,362 mask: mask_grid,363 rule: name,364 frames,365 fate,366 });367 if fate == Fate::Alive {368 return Some(Replay {369 outer,370 tile: tile.clone(),371 inner,372 boundary,373 canvas: climb.0,374 unit: climb.1,375 t: climb.2,376 climb: climb.3,377 chapters,378 attempts: attempt + 1,379 cost,380 });381 }382 let last = chapters.last_mut().unwrap();383 let count = last.frames.len();384 let options = pivot_options(count);385 let length = if options.is_empty() {386 count387 } else {388 choice(&options)389 };390 if length > 0 && length < last.frames.len() {391 last.frames.truncate(length);392 }393 prev = Some(Grid {394 side: climb.0,395 data: last.frames.last().unwrap().clone(),396 });397 }398 }399 None400}401402fn stepper_check() -> usize {403 let mut failures = 0;404 let mut state = 88172645463325252u64;405 let mut next = || {406 state ^= state << 13;407 state ^= state >> 7;408 state ^= state << 17;409 state410 };411 for trial in 0..24 {412 let side = [16, 17, 32, 45][trial % 4];413 let m = [3, 5, 9, 15][(trial / 4) % 4];414 let wrap = trial % 2 == 0;415 let mut mask = Grid {416 side: m,417 data: (0..m * m).map(|_| (next() % 2) as u8).collect(),418 };419 mask.data[(m / 2) * m + m / 2] = 0;420 let grid: Vec<u8> = (0..side * side).map(|_| (next() % 3 == 0) as u8).collect();421 let budget = mask.data.iter().filter(|&&v| v == 1).count();422 let birth: Vec<usize> = (0..=budget).filter(|_| next() % 3 == 0).collect();423 let survive: Vec<usize> = (0..=budget).filter(|_| next() % 2 == 0).collect();424 let boundary = if wrap {425 Boundary::Wrap426 } else {427 Boundary::Constant428 };429 let cell = Cell2d::new(Tensor::of(grid.clone(), vec![side, side]));430 let want = next_grid(&cell, &birth, &survive, mask.cell().types(), boundary).unwrap();431 for force in [true, false] {432 let mut stepper = Stepper::new(side, &mask, wrap);433 if stepper.plan.shift != force {434 stepper.plan.shift = force;435 if !force {436 let (kre, kim) =437 transform(&embed_kernel(&mask.data, m, stepper.plan.n), stepper.plan.n);438 stepper.plan.kre = kre;439 stepper.plan.kim = kim;440 }441 }442 let got = stepper.next(&grid, &table(&birth, budget), &table(&survive, budget));443 if got != want.types().bytes() {444 failures += 1;445 }446 }447 }448 failures449}450451// READINGS452453struct Rings {454 n: usize,455 index: Vec<usize>,456 count: Vec<usize>,457}458459impl Rings {460 fn new(n: usize) -> Rings {461 let mut index = vec![0; n * n];462 let mut count = Vec::new();463 for r in 0..n {464 for c in 0..n {465 let k = (r.min(n - r) as f64).hypot(c.min(n - c) as f64).round() as usize;466 index[r * n + c] = k;467 if k >= count.len() {468 count.resize(k + 1, 0);469 }470 count[k] += 1;471 }472 }473 Rings { n, index, count }474 }475 fn sums(&self, values: &[f64]) -> Vec<f64> {476 let mut sums = vec![0.0; self.count.len()];477 for (i, &v) in values.iter().enumerate() {478 sums[self.index[i]] += v;479 }480 sums481 }482 fn means(&self, values: &[f64]) -> Vec<f64> {483 self.sums(values)484 .iter()485 .zip(&self.count)486 .map(|(&s, &c)| if c == 0 { 0.0 } else { s / c as f64 })487 .collect()488 }489}490491fn argmax(values: &[f64], count: &[usize], cap: usize) -> usize {492 let mut best = 0;493 let mut top = f64::NEG_INFINITY;494 for (k, &v) in values.iter().enumerate().skip(1).take(cap) {495 if count[k] >= MIN_BINS && v > top {496 top = v;497 best = k;498 }499 }500 best501}502503fn argmin(values: &[f64]) -> usize {504 let mut best = 0;505 let mut low = f64::INFINITY;506 for (k, &v) in values.iter().enumerate().skip(1) {507 if v < low {508 low = v;509 best = k;510 }511 }512 best513}514515struct Spectrum {516 k: usize,517 full_k: usize,518 shares: Vec<f64>,519 cut_k: usize,520}521522fn spectrum(frame: &[u8], s: usize, rings: &Rings) -> Spectrum {523 let n = rings.n;524 let ones = frame.iter().filter(|&&v| v == 1).count() as f64;525 let mean = ones / (s * s) as f64;526 let mut field = vec![0.0; n * n];527 for r in 0..s {528 for c in 0..s {529 field[r * n + c] = frame[r * s + c] as f64 - mean;530 }531 }532 let (re, im) = transform(&field, n);533 let power: Vec<f64> = re.iter().zip(&im).map(|(a, b)| a * a + b * b).collect();534 let sums = rings.sums(&power);535 let total: f64 = sums.iter().skip(1).sum();536 let shares: Vec<f64> = sums537 .iter()538 .map(|&v| if total > 0.0 { v / total } else { 0.0 })539 .collect();540 let means: Vec<f64> = sums541 .iter()542 .zip(&rings.count)543 .map(|(&s, &c)| if c == 0 { 0.0 } else { s / c as f64 })544 .collect();545 let half = n / 2;546 let k = argmax(&means, &rings.count, half);547 let full_k = argmax(&means, &rings.count, means.len());548 let mut centred = vec![0.0; n * n];549 for r in 0..n {550 for c in 0..n {551 centred[((r + half) % n) * n + (c + half) % n] = power[r * n + c];552 }553 }554 let cut_k = peak_ring(&radial_profile(¢red, n));555 Spectrum {556 k,557 full_k,558 shares,559 cut_k,560 }561}562563struct Xor(u64);564565impl Xor {566 fn unit(&mut self) -> f64 {567 self.0 ^= self.0 << 13;568 self.0 ^= self.0 >> 7;569 self.0 ^= self.0 << 17;570 (self.0 >> 11) as f64 / (1u64 << 53) as f64571 }572}573574const BASELINE_SEED: u64 = 1729;575const BASELINE_SAMPLES: usize = 4;576const BUCKETS: usize = 20;577578struct Baseline {579 cache: HashMap<(usize, usize, usize), Vec<f64>>,580}581582impl Baseline {583 fn shares(&mut self, s: usize, rings: &Rings, fill: f64) -> &Vec<f64> {584 let bucket = (fill * BUCKETS as f64).round() as usize;585 let key = (s, rings.n, bucket);586 self.cache.entry(key).or_insert_with(|| {587 let p = (bucket as f64 / BUCKETS as f64)588 .clamp(0.5 / BUCKETS as f64, 1.0 - 0.5 / BUCKETS as f64);589 let mut rng = Xor(BASELINE_SEED ^ ((s as u64) << 20) ^ ((bucket as u64) << 40));590 let mut total = vec![0.0; rings.count.len()];591 for _ in 0..BASELINE_SAMPLES {592 let frame: Vec<u8> = (0..s * s).map(|_| u8::from(rng.unit() < p)).collect();593 for (slot, v) in total.iter_mut().zip(spectrum(&frame, s, rings).shares) {594 *slot += v / BASELINE_SAMPLES as f64;595 }596 }597 total598 })599 }600}601602struct Lobe {603 first: Option<(usize, usize)>,604 neg: usize,605 band: Option<(usize, usize)>,606}607608fn lobes(mask: &Grid, rings: &Rings) -> Lobe {609 let (re, _) = transform(&embed_kernel(&mask.data, mask.side, rings.n), rings.n);610 let g = rings.means(&re);611 let mut first = None;612 let mut k = 1;613 while k < g.len() {614 if g[k] < 0.0 {615 let lo = k;616 while k < g.len() && g[k] < 0.0 {617 k += 1;618 }619 first = Some((lo, k - 1));620 break;621 }622 k += 1;623 }624 let neg = argmin(&g);625 let band = if g[neg] < 0.0 {626 let mut lo = neg;627 while lo > 1 && g[lo - 1] < 0.0 {628 lo -= 1;629 }630 let mut hi = neg;631 while hi + 1 < g.len() && g[hi + 1] < 0.0 {632 hi += 1;633 }634 Some((lo, hi))635 } else {636 None637 };638 Lobe { first, neg, band }639}640641fn period(tile: &Grid) -> usize {642 let u = tile.side;643 for d in 1..=u {644 if !u.is_multiple_of(d) {645 continue;646 }647 let ok = (0..u).all(|r| {648 (0..u).all(|c| {649 let v = tile.data[r * u + c];650 v == tile.data[((r + d) % u) * u + c] && v == tile.data[r * u + (c + d) % u]651 })652 });653 if ok {654 return d;655 }656 }657 u658}659660// HUNT661662#[derive(Clone)]663struct Row {664 seed: u64,665 chapter: usize,666 way: Way,667 path: Path,668 mask: usize,669 crop: usize,670 t: usize,671 generation: usize,672 still: bool,673 fill: f64,674 k: usize,675 wavelength: f64,676 share: f64,677 ratio: f64,678 churn: f64,679 entropy: i64,680 lobe: Option<(usize, usize)>,681 band: Option<(usize, usize)>,682 comb: f64,683 field: usize,684}685686impl Row {687 fn in_lobe(&self) -> bool {688 self.lobe689 .is_some_and(|(lo, hi)| self.k >= lo && self.k <= hi)690 }691 fn in_band(&self) -> bool {692 self.band693 .is_some_and(|(lo, hi)| self.k >= lo && self.k <= hi)694 }695 fn comb_distance(&self) -> f64 {696 let j = (self.k as f64 / self.comb).round().max(1.0);697 (self.k as f64 - j * self.comb).abs()698 }699 fn comb_chance(&self) -> f64 {700 (1.0 / self.comb).min(1.0)701 }702 fn drawn(&self) -> bool {703 self.path != Path::Simple704 }705 fn resolved(&self) -> bool {706 self.crop >= 4 * self.mask707 }708 fn text(&self) -> String {709 format!(710 "seed {} chapter {} gen {} {} {} m{} crop {} t {} k {} wavelength {:.2} ratio {:.1} share {:.4} fill {:.3} churn {:.4} entropy {} lobe {:?} comb {:.2} field {}{}",711 self.seed, self.chapter, self.generation, self.way.name(), self.path.name(), self.mask, self.crop, self.t, self.k, self.wavelength, self.ratio, self.share, self.fill, self.churn, self.entropy, self.lobe, self.comb, self.field, if self.still { " still" } else { "" }712 )713 }714}715716struct Tally {717 quests: usize,718 frames: usize,719 skipped: usize,720 cut_disagree: usize,721 corner: usize,722 rows: Vec<Row>,723 per_path: HashMap<&'static str, (usize, usize)>,724 verified: Vec<(u64, usize, usize, bool)>,725 mismatches: usize,726}727728impl Tally {729 fn new() -> Tally {730 Tally {731 quests: 0,732 frames: 0,733 skipped: 0,734 cut_disagree: 0,735 corner: 0,736 rows: Vec::new(),737 per_path: HashMap::new(),738 verified: Vec::new(),739 mismatches: 0,740 }741 }742}743744const CHLADNI_GAIN: f64 = 3.0;745const LOW_RING: usize = 2;746const MIN_BINS: usize = 8;747const MIN_LIVE: usize = 8;748const PRINT_CAP: usize = 3;749const VERIFY_COST: u64 = 100_000_000;750const VERIFY_CAP: usize = 4;751752fn verify(r: &Replay, config: &Config) -> usize {753 seed(r.outer);754 let q = quest(config).unwrap();755 let mut bad = 0;756 bad += usize::from(q.seed != r.inner || q.canvas != r.canvas);757 let lengths: Vec<usize> = r.chapters.iter().map(|c| c.frames.len()).collect();758 bad += usize::from(q.story.chapter_lengths() != lengths);759 for (a, b) in q.segments.iter().zip(&r.chapters) {760 bad += usize::from(761 a.way != b.way || a.path != b.path || a.mask.types().bytes() != b.mask.data.as_slice(),762 );763 }764 let mine: Vec<&Vec<u8>> = r.chapters.iter().flat_map(|c| c.frames.iter()).collect();765 for (a, b) in q.story.grids().iter().zip(&mine) {766 bad += usize::from(a.types().bytes() != b.as_slice());767 }768 bad769}770771fn hunt(r: &Replay, baseline: &mut Baseline, tally: &mut Tally, label: &str) {772 let cells: Vec<Cell2d> = r773 .chapters774 .iter()775 .flat_map(|c| {776 c.frames777 .iter()778 .map(|f| Cell2d::new(Tensor::of(f.clone(), vec![r.canvas, r.canvas])))779 })780 .collect();781 let cropped = crop(&cells);782 let s = cropped[0].width();783 let widest = r.chapters.iter().map(|c| c.mask.side).max().unwrap_or(3);784 let n = s.max(widest).next_power_of_two();785 let rings = Rings::new(n);786 let p = period(&r.tile);787 let comb = n as f64 / p as f64;788 let summary: Vec<String> = r789 .chapters790 .iter()791 .map(|c| {792 format!(793 "{}:{}:{}:m{}:{}:{}",794 c.way.name(),795 c.path.name(),796 c.rule,797 c.mask.side,798 c.frames.len(),799 c.fate.name()800 )801 })802 .collect();803 println!(804 "{label} seed {} inner {} {:?} canvas {} crop {} field {} unit {} period {} t {} climb {} attempts {} comb {:.2} chapters {}",805 r.outer, r.inner, r.boundary, r.canvas, s, n, r.unit, p, r.t, r.climb, r.attempts, comb, summary.join(" ")806 );807 tally.quests += 1;808 let mut peaks: Vec<usize> = Vec::new();809 let mut index = 0;810 for (ci, chapter) in r.chapters.iter().enumerate() {811 let lobe = lobes(&chapter.mask, &rings);812 let mut found: Vec<Row> = Vec::new();813 let mut shown = 0;814 let last = chapter.frames.len() - 1;815 for gen in 0..chapter.frames.len() {816 let frame = cropped[index].types().bytes();817 let live = frame.iter().filter(|&&v| v == 1).count();818 let fill = live as f64 / (s * s) as f64;819 let churned = if index == 0 {820 0.0821 } else {822 churn(&cropped[index - 1..=index])823 };824 let ent = entropy(&cropped[index]);825 index += 1;826 tally.frames += 1;827 let entry = tally.per_path.entry(chapter.path.name()).or_insert((0, 0));828 entry.0 += 1;829 if live < MIN_LIVE || live + MIN_LIVE > s * s {830 tally.skipped += 1;831 continue;832 }833 let spec = spectrum(frame, s, &rings);834 if spec.cut_k != spec.k {835 tally.cut_disagree += 1;836 }837 if spec.full_k != spec.k {838 tally.corner += 1;839 }840 let base = baseline.shares(s, &rings, fill)[spec.k];841 let share = spec.shares[spec.k];842 let ratio = if base > 0.0 { share / base } else { 0.0 };843 let wavelength = n as f64 / spec.k.max(1) as f64;844 if ratio >= CHLADNI_GAIN && wavelength <= 2.0 * chapter.mask.side as f64 {845 entry.1 += 1;846 let row = Row {847 seed: r.outer,848 chapter: ci,849 way: chapter.way,850 path: chapter.path,851 mask: chapter.mask.side,852 crop: s,853 t: r.t,854 generation: gen,855 still: chapter.fate == Fate::Alive && gen == last,856 fill,857 k: spec.k,858 wavelength,859 share,860 ratio,861 churn: churned,862 entropy: ent,863 lobe: lobe.first,864 band: lobe.band,865 comb,866 field: n,867 };868 if gen > 0 && shown < PRINT_CAP {869 println!(870 " gen {gen} fill {:.3} k {} wavelength {:.2} ratio {:.1} share {:.4} churn {:.4} entropy {}{}",871 fill, spec.k, wavelength, ratio, share, churned, ent, if row.still { " still" } else { "" }872 );873 shown += 1;874 }875 found.push(row);876 }877 }878 if !found.is_empty() {879 println!(880 " chapter {ci} {} {} m{} lobe {:?} neg {} band {:?} chladni {} of {} frames, {} at gen 0",881 chapter.way.name(),882 chapter.path.name(),883 chapter.mask.side,884 lobe.first,885 lobe.neg,886 lobe.band,887 found.len(),888 chapter.frames.len(),889 found.iter().filter(|r| r.generation == 0).count()890 );891 }892 peaks.extend(found.iter().filter(|r| r.generation > 0).map(|r| r.k));893 tally.rows.extend(found);894 }895 if !peaks.is_empty() {896 let mut hist: HashMap<usize, usize> = HashMap::new();897 for k in &peaks {898 *hist.entry(*k).or_default() += 1;899 }900 let mut bins: Vec<(usize, usize)> = hist.into_iter().collect();901 bins.sort();902 let top = bins903 .iter()904 .max_by_key(|(k, c)| (*c, usize::MAX - *k))905 .unwrap();906 let cells: Vec<String> = bins.iter().map(|(k, c)| format!("{k}:{c}")).collect();907 println!(908 " peak rings past gen 0 {} plurality ring {} in {} of {}",909 cells.join(" "),910 top.0,911 top.1,912 peaks.len()913 );914 }915}916917fn tag(pass: usize, total: usize, witness: Option<&Row>) -> String {918 if total == 0 {919 "Empty".to_string()920 } else if pass == total {921 "Verified on the printed domain".to_string()922 } else {923 format!(924 "Refuted, witness {}",925 witness.map(|r| r.text()).unwrap_or_default()926 )927 }928}929930type Domain = (&'static str, Box<dyn Fn(&Row) -> bool>);931932fn law_table(name: &str, rows: &[&Row]) {933 let n = rows.len();934 let mut quests: Vec<u64> = rows.iter().map(|r| r.seed).collect();935 quests.sort_unstable();936 quests.dedup();937 let mut chapters: Vec<(u64, usize)> = rows.iter().map(|r| (r.seed, r.chapter)).collect();938 chapters.sort_unstable();939 chapters.dedup();940 let mut combs: Vec<f64> = rows.iter().map(|r| r.comb).collect();941 combs.sort_by(|a, b| a.partial_cmp(b).unwrap());942 let flat = rows.iter().filter(|r| r.t == 1).count();943 let lobe = rows.iter().filter(|r| r.in_lobe()).count();944 let band = rows.iter().filter(|r| r.in_band()).count();945 let half = rows.iter().filter(|r| r.comb_distance() <= 0.5).count();946 let one = rows.iter().filter(|r| r.comb_distance() <= 1.0).count();947 let chance: f64 = rows.iter().map(|r| r.comb_chance()).sum::<f64>();948 let product = rows949 .iter()950 .filter(|r| r.in_lobe() && r.comb_distance() <= 0.5)951 .count();952 println!(953 " {name}: rows {n} chapters {} quests {} lobe {lobe} band {band} comb-half {half} (chance {chance:.1}) comb-one {one} product {product}",954 chapters.len(),955 quests.len()956 );957 if n > 0 {958 println!(959 " rows on one-tile boards (t = 1) {flat}, comb spacing min {:.2} median {:.2} max {:.2}",960 combs[0],961 combs[n / 2],962 combs[n - 1]963 );964 }965 println!(966 " lobe {}",967 tag(lobe, n, rows.iter().find(|r| !r.in_lobe()).copied())968 );969 println!(970 " comb-half {}",971 tag(972 half,973 n,974 rows.iter().find(|r| r.comb_distance() > 0.5).copied()975 )976 );977 println!(978 " product {}",979 tag(980 product,981 n,982 rows.iter()983 .find(|r| !(r.in_lobe() && r.comb_distance() <= 0.5))984 .copied()985 )986 );987}988989fn laws(tally: &Tally) {990 let rows = &tally.rows;991 println!();992 println!(993 "quests {} frames {} skipped {} ring-cut-disagreements {} corner-peaks {}",994 tally.quests, tally.frames, tally.skipped, tally.cut_disagree, tally.corner995 );996 println!(997 "chladni-like frames {} (ring share at least {CHLADNI_GAIN} times the random share at the same ring, wavelength at most twice the mask side), {} at gen 0, {} stills",998 rows.len(),999 rows.iter().filter(|r| r.generation == 0).count(),1000 rows.iter().filter(|r| r.still).count()1001 );1002 let moved: Vec<&Row> = rows.iter().filter(|r| r.generation > 0).collect();1003 let low = moved.iter().filter(|r| r.k <= LOW_RING).count();1004 let long = moved1005 .iter()1006 .filter(|r| r.wavelength > r.crop as f64)1007 .count();1008 let resolved = moved.iter().filter(|r| r.resolved()).count();1009 println!(1010 "envelope of the {} hits past gen 0: {low} peak at ring 1 or 2 of their field, {long} read a wavelength longer than the crop, {resolved} are resolved (crop at least four mask sides); the cut admits all of them",1011 moved.len()1012 );1013 let mut env: HashMap<&'static str, (usize, usize)> = HashMap::new();1014 for row in &moved {1015 let e = env.entry(row.path.name()).or_insert((0, 0));1016 e.0 += 1;1017 if row.k <= LOW_RING {1018 e.1 += 1;1019 }1020 }1021 let mut env: Vec<_> = env.into_iter().collect();1022 env.sort();1023 let cells: Vec<String> = env1024 .iter()1025 .map(|(path, (n, low))| format!("{path} {low} of {n}"))1026 .collect();1027 println!(1028 "envelope by path, ring 1 or 2 past gen 0: {}",1029 cells.join(" ")1030 );1031 let mut by: HashMap<String, usize> = HashMap::new();1032 for row in rows.iter().filter(|r| r.generation > 0) {1033 *by.entry(format!("way {}", row.way.name())).or_default() += 1;1034 *by.entry(format!("path {}", row.path.name())).or_default() += 1;1035 *by.entry(format!("mask {}", row.mask)).or_default() += 1;1036 *by.entry(format!("t {}", row.t)).or_default() += 1;1037 *by.entry(format!("chapter {}", row.chapter)).or_default() += 1;1038 }1039 let mut keys: Vec<_> = by.iter().collect();1040 keys.sort();1041 let cells: Vec<String> = keys.iter().map(|(k, v)| format!("{k}:{v}")).collect();1042 println!("where (gen > 0) {}", cells.join(" "));1043 let mut paths: Vec<_> = tally.per_path.iter().collect();1044 paths.sort();1045 for (path, (frames, hits)) in paths {1046 println!(1047 "path {path} frames {frames} chladni {hits} rate {:.4}",1048 *hits as f64 / (*frames).max(1) as f641049 );1050 }1051 println!("laws: lobe = k in the mask's first negative lobe, band = k in the negative band around the most negative ring, comb = k within half (one) ring of a multiple of field/period, product = lobe and comb-half");1052 let domains: [Domain; 7] = [1053 (1054 "gen > 0, drawn masks",1055 Box::new(|r| r.drawn() && r.generation > 0),1056 ),1057 (1058 "gen > 0, drawn masks, crop >= 4 mask",1059 Box::new(|r| r.drawn() && r.generation > 0 && r.resolved()),1060 ),1061 (1062 "gen > 0, basic path",1063 Box::new(|r| r.path == Path::Basic && r.generation > 0),1064 ),1065 (1066 "gen > 0, copy path",1067 Box::new(|r| r.path == Path::Copy && r.generation > 0),1068 ),1069 (1070 "gen > 0, simple masks",1071 Box::new(|r| !r.drawn() && r.generation > 0),1072 ),1073 ("stills, drawn masks", Box::new(|r| r.drawn() && r.still)),1074 ("stills, simple masks", Box::new(|r| !r.drawn() && r.still)),1075 ];1076 for (name, keep) in &domains {1077 let group: Vec<&Row> = rows.iter().filter(|r| keep(r)).collect();1078 law_table(name, &group);1079 }1080 let sharp: Vec<&Row> = rows1081 .iter()1082 .filter(|r| r.generation > 0 && r.t >= 3 && r.comb >= 4.0)1083 .collect();1084 law_table("gen > 0, t >= 3, comb spacing >= 4", &sharp);1085 for (name, keep) in [1086 ("gen > 0, drawn masks, crop >= 4 mask", true),1087 ("stills, drawn masks", false),1088 ] {1089 let group: Vec<&Row> = rows1090 .iter()1091 .filter(|r| {1092 r.drawn()1093 && if keep {1094 r.generation > 0 && r.resolved()1095 } else {1096 r.still1097 }1098 })1099 .collect();1100 let mut bins = [0usize; 13];1101 let mut near = 0;1102 let mut lobe_centre = Vec::new();1103 for r in &group {1104 let x = r.wavelength / r.mask as f64;1105 bins[((x / 0.25) as usize).min(12)] += 1;1106 if (0.8..=1.25).contains(&x) {1107 near += 1;1108 }1109 if let Some((lo, hi)) = r.lobe {1110 lobe_centre.push(2.0 * r.field as f64 / (lo + hi) as f64 / r.mask as f64);1111 }1112 }1113 lobe_centre.sort_by(|a, b| a.partial_cmp(b).unwrap());1114 let cells: Vec<String> = bins1115 .iter()1116 .enumerate()1117 .map(|(i, c)| format!("{:.2}:{c}", i as f64 * 0.25))1118 .collect();1119 println!(1120 "wavelength over mask side ({name}): rows {} within 0.8..1.25 {near} histogram {}",1121 group.len(),1122 cells.join(" ")1123 );1124 if !lobe_centre.is_empty() {1125 println!(1126 "lobe centre wavelength over mask side ({name}): min {:.2} median {:.2} max {:.2}",1127 lobe_centre[0],1128 lobe_centre[lobe_centre.len() / 2],1129 lobe_centre[lobe_centre.len() - 1]1130 );1131 }1132 }1133 let mut stills: Vec<&Row> = rows.iter().filter(|r| r.still).collect();1134 stills.sort_by(|a, b| b.ratio.partial_cmp(&a.ratio).unwrap());1135 for row in stills.iter().take(3) {1136 println!("best still {}", row.text());1137 }1138 let mut moving: Vec<&Row> = rows1139 .iter()1140 .filter(|r| r.generation > 0 && r.drawn() && r.resolved())1141 .collect();1142 moving.sort_by(|a, b| b.ratio.partial_cmp(&a.ratio).unwrap());1143 for row in moving.iter().take(3) {1144 println!("best resolved drawn-mask frame {}", row.text());1145 }1146 let cells: Vec<String> = tally1147 .verified1148 .iter()1149 .map(|(seed, attempts, climb, copy)| {1150 format!("seed {seed} attempts {attempts} canvas climb {climb} copy path {copy}")1151 })1152 .collect();1153 if cells.is_empty() {1154 println!("no quest here steps under the replay cost {VERIFY_COST}, so none is checked cell for cell");1155 } else {1156 println!(1157 "replay verified against mrlygame::quest cell for cell on the {} cheapest quests, those stepping under the replay cost {VERIFY_COST}, mismatches {}: {}",1158 tally.verified.len(),1159 tally.mismatches,1160 cells.join(", ")1161 );1162 }1163 println!(1164 "the remaining {} quests rest on the same draw order and the stepper's 24-case agreement with mrlymath::life::next_grid; the engine's naive count is the cost, no wall clock is claimed",1165 tally.quests.saturating_sub(tally.verified.len())1166 );1167}11681169const SEEDS: u64 = 64;1170const LARGE_SEEDS: std::ops::RangeInclusive<u64> = 65..=68;1171const BUDGET_MS: u64 = 110_000;11721173fn main() {1174 let start = Instant::now();1175 let failures = stepper_check();1176 println!("stepper check against mrlymath::life::next_grid: failures {failures}");1177 assert_eq!(failures, 0);1178 let config = Config::default();1179 println!(1180 "config default max_generations {} max_segments {} max_canvas {} tile {}..{} mask {}..{} attempts {}; outer seeds 1..={SEEDS}; baseline seed {BASELINE_SEED} samples {BASELINE_SAMPLES} buckets {BUCKETS}",1181 config.max_generations, config.max_segments, config.max_canvas, config.min_tile, config.max_tile, config.min_mask, config.max_mask, config.attempts1182 );1183 println!("frames are cropped by mrlymath::life::crop, mean removed, zero padded to the next power of two at or above the crop and the widest mask; rings read over the full square, a peak ring holds at least {MIN_BINS} bins and sits at or below half the field (wavelength at least 2 cells), peaks past it are counted as corner peaks");1184 let mut baseline = Baseline {1185 cache: HashMap::new(),1186 };1187 let mut tally = Tally::new();1188 for s in 1..=SEEDS {1189 match replay(s, &config, None) {1190 Some(r) => {1191 if r.cost <= VERIFY_COST && tally.verified.len() < VERIFY_CAP {1192 tally.mismatches += verify(&r, &config);1193 tally.verified.push((1194 s,1195 r.attempts,1196 r.climb,1197 r.chapters.iter().any(|c| c.path == Path::Copy),1198 ));1199 }1200 hunt(&r, &mut baseline, &mut tally, "quest");1201 }1202 None => println!("quest seed {s} no settle"),1203 }1204 }1205 laws(&tally);1206 let mut per_field: HashMap<usize, Vec<f64>> = HashMap::new();1207 for ((_, n, _), v) in &baseline.cache {1208 per_field1209 .entry(*n)1210 .or_default()1211 .push(v.iter().skip(1).cloned().fold(0.0, f64::max));1212 }1213 let mut fields: Vec<_> = per_field.into_iter().collect();1214 fields.sort_by_key(|(n, _)| *n);1215 for (n, mut v) in fields {1216 v.sort_by(|a, b| a.partial_cmp(b).unwrap());1217 println!(1218 "baseline field {n} keys {} largest ring share min {:.4} median {:.4} max {:.4}",1219 v.len(),1220 v[0],1221 v[v.len() / 2],1222 v[v.len() - 1]1223 );1224 }1225 let large = Config {1226 max_canvas: 512,1227 max_mask: 128,1228 ..Config::default()1229 };1230 println!(1231 "large config max_canvas 512 max_mask 128 outer seeds {:?}, abandoned past {BUDGET_MS} ms",1232 LARGE_SEEDS1233 );1234 let deadline = start + std::time::Duration::from_millis(BUDGET_MS);1235 let mut large_tally = Tally::new();1236 for s in LARGE_SEEDS {1237 match replay(s, &large, Some(deadline)) {1238 Some(r) => hunt(&r, &mut baseline, &mut large_tally, "large"),1239 None if Instant::now() > deadline => {1240 println!("large seed {s} abandoned at the budget");1241 break;1242 }1243 None => println!("large seed {s} no settle"),1244 }1245 }1246 if large_tally.quests > 0 {1247 laws(&large_tally);1248 }1249}