word.rs
18.1 kB · rust · 552 lines
1use super::factory::{self, MagicLayer};2use crate::name::Bang;3use mrlycore::errors::{value_error, Result};4use mrlycore::Tensor;56/// The plane geometry of one letter, the numbers a word's counts fold through.7#[derive(Clone, Copy, Debug, PartialEq, Eq)]8pub struct Letter {9 /// The count of filled cells.10 pub fill: u128,11 /// The count of maximal horizontal runs of filled cells.12 pub runs_h: u128,13 /// The count of maximal vertical runs of filled cells.14 pub runs_v: u128,15 /// The count of rows whose first and last cells are both filled.16 pub touch_h: u128,17 /// The count of columns whose first and last cells are both filled.18 pub touch_v: u128,19 /// The count of 4-connected components.20 pub components: u128,21}2223/// The counts a word carries at one prefix length.24#[derive(Clone, Copy, Debug, PartialEq, Eq)]25pub struct Counts {26 /// The side, the product of the prefix's letter sides.27 pub side: u128,28 /// The filled cells, the product of the prefix's letter fills.29 pub fill: u128,30 /// The 4-connected components.31 pub components: u128,32 /// The maximal horizontal runs of filled cells.33 pub runs_h: u128,34 /// The maximal vertical runs of filled cells.35 pub runs_v: u128,36}3738// GEOMETRY3940fn tile_of(layer: &MagicLayer) -> Result<Tensor> {41 factory::create(42 layer.design.code,43 layer.number,44 layer.design.dim,45 layer.design.base,46 1,47 )48}4950fn pieces(tile: &Tensor) -> u128 {51 let (rows, cols) = (tile.shape[0], tile.shape[1]);52 let bytes = tile.bytes();53 let mut seen = vec![false; rows * cols];54 let mut count = 0u128;55 let mut stack: Vec<usize> = Vec::new();56 for start in 0..rows * cols {57 if bytes[start] == 0 || seen[start] {58 continue;59 }60 count += 1;61 seen[start] = true;62 stack.push(start);63 while let Some(at) = stack.pop() {64 let (r, c) = (at / cols, at % cols);65 let walk = |next: usize, seen: &mut Vec<bool>, stack: &mut Vec<usize>| {66 if bytes[next] != 0 && !seen[next] {67 seen[next] = true;68 stack.push(next);69 }70 };71 if r > 0 {72 walk(at - cols, &mut seen, &mut stack);73 }74 if r + 1 < rows {75 walk(at + cols, &mut seen, &mut stack);76 }77 if c > 0 {78 walk(at - 1, &mut seen, &mut stack);79 }80 if c + 1 < cols {81 walk(at + 1, &mut seen, &mut stack);82 }83 }84 }85 count86}8788/// Reads one plane letter: its fill, its runs, the rows and columns that wrap into a89/// neighbouring copy, and its own components.90///91/// ```92/// use mrlymath::bang::{word, MagicLayer};93/// use mrlymath::name::Bang;94/// let gasket = word::letter(&MagicLayer::new(Bang::new(7, 2, 2), 2)).unwrap();95/// assert_eq!((gasket.fill, gasket.components), (3, 1));96/// assert_eq!((gasket.touch_h, gasket.touch_v), (1, 1));97/// ```98pub fn letter(layer: &MagicLayer) -> Result<Letter> {99 if layer.design.dim != 2 {100 return value_error("a letter's run and contact counts are a plane reading.");101 }102 let tile = tile_of(layer)?;103 let (rows, cols) = (tile.shape[0], tile.shape[1]);104 let on = |r: usize, c: usize| tile.bytes()[r * cols + c] != 0;105 let (mut fill, mut runs_h, mut runs_v) = (0u128, 0u128, 0u128);106 let (mut touch_h, mut touch_v) = (0u128, 0u128);107 for r in 0..rows {108 for c in 0..cols {109 if !on(r, c) {110 continue;111 }112 fill += 1;113 if c == 0 || !on(r, c - 1) {114 runs_h += 1;115 }116 if r == 0 || !on(r - 1, c) {117 runs_v += 1;118 }119 }120 if on(r, 0) && on(r, cols - 1) {121 touch_h += 1;122 }123 }124 for c in 0..cols {125 if on(0, c) && on(rows - 1, c) {126 touch_v += 1;127 }128 }129 Ok(Letter {130 fill,131 runs_h,132 runs_v,133 touch_h,134 touch_v,135 components: pieces(&tile),136 })137}138139// FOLD140141fn mul(a: u128, b: u128) -> Option<u128> {142 a.checked_mul(b)143}144145fn closed(read: &Letter) -> bool {146 read.components == 1 || (read.touch_h == 0 && read.touch_v == 0)147}148149fn grow(state: &Counts, side: u128, read: &Letter) -> Option<Counts> {150 let fill = mul(state.fill, read.fill)?;151 let runs_h = mul(state.fill, read.runs_h - read.touch_h)?152 .checked_add(mul(state.runs_h, read.touch_h)?)?;153 let runs_v = mul(state.fill, read.runs_v - read.touch_v)?154 .checked_add(mul(state.runs_v, read.touch_v)?)?;155 let components = match (read.touch_h, read.touch_v) {156 (0, 0) => mul(state.fill, read.components)?,157 (0, _) => state.runs_v,158 (_, 0) => state.runs_h,159 _ => state.components,160 };161 Some(Counts {162 side: mul(state.side, side)?,163 fill,164 components,165 runs_h,166 runs_v,167 })168}169170/// Folds a plane word letter by letter and returns the counts at every prefix.171///172/// Each letter folds the component count by its own geometry: a letter with no wrap-around173/// contact isolates every block, so the count becomes the outer fill times the letter's own174/// pieces; a connected letter with contacts on one axis merges blocks along that axis alone,175/// so the count becomes the outer run count; a connected letter with both contacts leaves the176/// block graph isomorphic to the cell graph and the count unmoved. A letter that is neither177/// connected nor contact-free both splits and merges and is refused.178///179/// The list stops at the last prefix whose counts fit a u128 rather than wrapping.180pub fn prefixes(layers: &[MagicLayer]) -> Result<Vec<Counts>> {181 let mut state = Counts {182 side: 1,183 fill: 1,184 components: 1,185 runs_h: 1,186 runs_v: 1,187 };188 let mut out = Vec::with_capacity(layers.len());189 for layer in layers {190 let read = letter(layer)?;191 if !closed(&read) {192 return value_error(format!(193 "letter c{} at side {} is neither connected nor contact-free, so its word has no closed component count.",194 layer.design.code, layer.number195 ));196 }197 match grow(&state, layer.number as u128, &read) {198 Some(next) => state = next,199 None => break,200 }201 out.push(state);202 }203 Ok(out)204}205206/// Counts the 4-connected components of a plane word without drawing it.207///208/// ```209/// use mrlymath::bang::{word, MagicLayer};210/// use mrlymath::name::Bang;211/// let domino = MagicLayer::new(Bang::new(3, 2, 2), 2);212/// let diagonal = MagicLayer::new(Bang::new(6, 2, 2), 2);213/// assert_eq!(word::components(&[domino.clone(), diagonal.clone()]).unwrap(), 4);214/// assert_eq!(word::components(&[diagonal, domino]).unwrap(), 2);215/// ```216pub fn components(layers: &[MagicLayer]) -> Result<u128> {217 let counts = prefixes(layers)?;218 if counts.len() < layers.len() {219 return value_error("the word's component count passes what a u128 holds.");220 }221 match counts.last() {222 Some(last) => Ok(last.components),223 None => value_error("a word needs at least one letter."),224 }225}226227// PRODUCTS228229/// Lists the filled cells of every letter, the product of which is the word's fill.230pub fn fills(layers: &[MagicLayer]) -> Result<Vec<u128>> {231 layers232 .iter()233 .map(|layer| Ok(u128::from(tile_of(layer)?.sum())))234 .collect()235}236237/// Returns the side of a word, the product of its letter sides.238pub fn side(layers: &[MagicLayer]) -> Result<u128> {239 let mut out = 1u128;240 for layer in layers {241 match out.checked_mul(layer.number as u128) {242 Some(next) => out = next,243 None => return value_error("the word's side passes what a u128 holds."),244 }245 }246 Ok(out)247}248249/// Returns the filled cells of a word, the product of its letter fills.250pub fn fill(layers: &[MagicLayer]) -> Result<u128> {251 let mut out = 1u128;252 for count in fills(layers)? {253 match out.checked_mul(count) {254 Some(next) => out = next,255 None => return value_error("the word's fill passes what a u128 holds."),256 }257 }258 Ok(out)259}260261/// Returns the scale dimension of a word, the sum of the log fills over the sum of the log sides.262///263/// ```264/// use mrlymath::bang::{word, MagicLayer};265/// use mrlymath::name::Bang;266/// let carpet = MagicLayer::new(Bang::new(7, 2, 2), 3);267/// let two = word::dimension(&[carpet.clone(), carpet]).unwrap();268/// assert!((two - 8f64.ln() / 3f64.ln()).abs() < 1e-12);269/// ```270pub fn dimension(layers: &[MagicLayer]) -> Result<f64> {271 if layers.is_empty() {272 return value_error("a word needs at least one letter.");273 }274 let counts = fills(layers)?;275 let mut top = 0.0;276 let mut bottom = 0.0;277 for (layer, count) in layers.iter().zip(&counts) {278 top += (*count as f64).ln();279 bottom += (layer.number as f64).ln();280 }281 if bottom <= 0.0 {282 return value_error("a word needs a letter of side two or more.");283 }284 Ok(top / bottom)285}286287/// Returns the shortest whole period of the letter list, its own length when no shorter block repeats.288///289/// ```290/// use mrlymath::bang::{word, MagicLayer};291/// use mrlymath::name::Bang;292/// let a = MagicLayer::new(Bang::new(7, 2, 2), 3);293/// let b = MagicLayer::new(Bang::new(9, 2, 2), 5);294/// assert_eq!(word::period(&[a.clone(), b.clone(), a.clone(), b.clone()]), 2);295/// assert_eq!(word::period(&[a.clone(), b, a]), 3);296/// ```297pub fn period(layers: &[MagicLayer]) -> usize {298 let length = layers.len();299 for step in 1..length {300 if !length.is_multiple_of(step) {301 continue;302 }303 if (0..length).all(|i| layers[i] == layers[i % step]) {304 return step;305 }306 }307 length308}309310/// Returns whether every letter renders at its own residue base, the native case where a311/// periodic word folds to one residue rule at the product base.312pub fn native(layers: &[MagicLayer]) -> bool {313 !layers.is_empty() && layers.iter().all(|l| l.number == l.design.base)314}315316/// Returns the constant-word component functional of a plane word's letter frequencies,317/// in log two units.318///319/// It reads `sum_c f_c log2 comp(A_c)`, the one linear functional exact on constant words,320/// which on the plane alphabet at side two is `(f_6 + f_9) log 2`. It is a prediction and not321/// a theorem: at interior frequency it is refuted on 78 of the 105 letter pairs and exact on 27.322pub fn constant_functional(layers: &[MagicLayer]) -> Result<f64> {323 if layers.is_empty() {324 return value_error("a word needs at least one letter.");325 }326 let mut total = 0.0;327 for layer in layers {328 total += (letter(layer)?.components as f64).log2();329 }330 Ok(total / layers.len() as f64)331}332333// SCHEDULES334335/// The named infinite schedules over an ordered pair of letters.336#[derive(Clone, Copy, Debug, PartialEq, Eq)]337pub enum Schedule {338 /// The Thue-Morse word, the parity of the binary digit sum of the place.339 ThueMorse,340 /// The two letters alternating, the periodic control at the same frequencies.341 Periodic,342 /// The first letter repeated, the constant control.343 Constant,344}345346impl Schedule {347 /// Parses a schedule's display name, or an error for an unknown name.348 pub fn parse(name: &str) -> Result<Schedule> {349 match name {350 "thue-morse" => Ok(Schedule::ThueMorse),351 "periodic" => Ok(Schedule::Periodic),352 "constant" => Ok(Schedule::Constant),353 other => value_error(format!("unknown schedule {other:?}.")),354 }355 }356 /// Returns the letter frequencies the schedule tends to.357 pub fn frequencies(self) -> (f64, f64) {358 match self {359 Schedule::Constant => (1.0, 0.0),360 _ => (0.5, 0.5),361 }362 }363 /// Returns the letter the schedule takes at the place, zero or one.364 pub fn place(self, index: usize) -> usize {365 match self {366 Schedule::ThueMorse => thue_morse(index),367 Schedule::Periodic => index % 2,368 Schedule::Constant => 0,369 }370 }371}372373/// Returns the Thue-Morse letter at the place, the parity of its binary digit sum.374///375/// ```376/// let word: Vec<usize> = (0..8).map(mrlymath::bang::word::thue_morse).collect();377/// assert_eq!(word, vec![0, 1, 1, 0, 1, 0, 0, 1]);378/// ```379pub fn thue_morse(index: usize) -> usize {380 index.count_ones() as usize % 2381}382383/// Spells the first letters of a schedule over an ordered pair of letters.384pub fn spell(schedule: Schedule, pair: (MagicLayer, MagicLayer), length: usize) -> Vec<MagicLayer> {385 (0..length)386 .map(|index| {387 if schedule.place(index) == 0 {388 pair.0.clone()389 } else {390 pair.1.clone()391 }392 })393 .collect()394}395396/// Returns the prefix rates of a plane word in log two units, the component rate397/// `(1/L) log2 comp` and the fill rate `(1/L) log2 fill` at every prefix length.398///399/// At interior letter frequency the two meet: the component exponent is order-blind and equals400/// the fill exponent on every one of the 105 letter pairs but the domino against the full tile.401/// The list stops at the last prefix whose counts fit a u128.402pub fn rates(layers: &[MagicLayer]) -> Result<Vec<(f64, f64)>> {403 Ok(prefixes(layers)?404 .iter()405 .enumerate()406 .map(|(index, counts)| {407 let length = (index + 1) as f64;408 (409 (counts.components as f64).log2() / length,410 (counts.fill as f64).log2() / length,411 )412 })413 .collect())414}415416// STAIRCASE417418/// Builds the carpet staircase word to the depth, the stacked prefixes `magic(3)`,419/// then `magic(3,5)`, then `magic(3,5,7)`, and so on.420///421/// The letter at odd side `2j + 1` occurs `depth - j + 1` times in the first `depth` blocks,422/// so the word holds `depth (depth + 1) / 2` letters and its dimension is the occurrence-weighted423/// average of the per-letter dimensions.424///425/// ```426/// use mrlymath::bang::word;427/// assert_eq!(word::staircase(3).unwrap().len(), 6);428/// let one = word::dimension(&word::staircase(1).unwrap()).unwrap();429/// assert!((one - 8f64.ln() / 3f64.ln()).abs() < 1e-9);430/// ```431pub fn staircase(depth: usize) -> Result<Vec<MagicLayer>> {432 if depth < 1 {433 return value_error("a staircase needs at least one block.");434 }435 let carpet = Bang::new(7, 2, 2);436 let mut out = Vec::new();437 for step in 1..=depth {438 for place in 1..=step {439 out.push(MagicLayer::new(carpet.clone(), 2 * place + 1));440 }441 }442 Ok(out)443}444445#[cfg(test)]446mod tests {447 use super::*;448 use crate::bang::magic;449450 const CODES: [u128; 15] = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15];451452 fn plain(code: u128, number: usize) -> MagicLayer {453 MagicLayer::new(Bang::new(code, 2, 2), number)454 }455456 #[test]457 fn the_fold_matches_the_drawn_word_on_every_short_plane_word() {458 for a in CODES {459 for b in CODES {460 let two = [plain(a, 2), plain(b, 2)];461 assert_eq!(462 components(&two).unwrap(),463 pieces(&magic(&two).unwrap()),464 "({a},{b})"465 );466 for c in CODES {467 let three = [plain(a, 2), plain(b, 2), plain(c, 2)];468 assert_eq!(469 components(&three).unwrap(),470 pieces(&magic(&three).unwrap()),471 "({a},{b},{c})"472 );473 }474 }475 }476 }477478 #[test]479 fn order_moves_the_component_count_on_the_minimal_pair() {480 let a = [plain(3, 2), plain(6, 2)];481 let b = [plain(6, 2), plain(3, 2)];482 assert_eq!((components(&a).unwrap(), components(&b).unwrap()), (4, 2));483 assert_eq!(fill(&a).unwrap(), fill(&b).unwrap());484 assert_eq!(side(&a).unwrap(), side(&b).unwrap());485 }486487 #[test]488 fn the_checkerboard_family_reaches_the_component_ceiling() {489 for length in 2..=8usize {490 let mut word = vec![plain(15, 2); length - 1];491 word.push(plain(6, 2));492 assert_eq!(components(&word).unwrap(), 2 * 4u128.pow(length as u32 - 1));493 }494 }495496 #[test]497 fn a_heavy_letter_never_moves_the_count() {498 for code in [7, 11, 13, 14, 15] {499 let word = [plain(6, 2), plain(9, 2), plain(code, 2)];500 assert_eq!(components(&word).unwrap(), components(&word[..2]).unwrap());501 }502 }503504 #[test]505 fn a_letter_that_splits_and_merges_is_refused() {506 let void = plain(9, 5);507 assert!(components(&[plain(7, 3), void]).is_err());508 }509510 #[test]511 fn the_staircase_prints_its_five_dimensions() {512 let pinned = [513 1.892789261,514 1.892315261,515 1.893034267,516 1.894190425,517 1.895495742,518 ];519 for (step, want) in pinned.iter().enumerate() {520 let got = dimension(&staircase(step + 1).unwrap()).unwrap();521 assert!((got - want).abs() < 5e-10, "n={} {got}", step + 1);522 }523 assert!(pinned[1] < pinned[0]);524 }525526 #[test]527 fn the_thue_morse_rate_climbs_to_the_fill_exponent() {528 let pair = (plain(3, 2), plain(7, 2));529 let word = spell(Schedule::ThueMorse, pair, 120);530 let rows = rates(&word).unwrap();531 assert_eq!(rows.len(), 98);532 for (at, row) in rows.iter().enumerate() {533 if (at + 1).is_multiple_of(2) {534 assert!((row.1 - 0.5 * 6f64.log2()).abs() < 1e-12, "L={}", at + 1);535 }536 }537 let (component, fill) = rows[97];538 assert!(component < fill && fill - component < 0.05);539 assert!(component > rows[31].0);540 assert_eq!(components(&word[..16]).unwrap(), 390573);541 assert_eq!(constant_functional(&word).unwrap(), 0.0);542 }543544 #[test]545 fn the_period_reads_the_block_and_the_native_letters() {546 let carpet = plain(7, 3);547 let native_pair = [MagicLayer::new(Bang::new(7, 2, 2), 2), carpet.clone()];548 assert_eq!(period(&[carpet.clone(), carpet.clone(), carpet]), 1);549 assert!(native(&[MagicLayer::new(Bang::new(7, 2, 2), 2)]));550 assert!(!native(&native_pair));551 }552}