main.rs
14.2 kB · rust · 428 lines
1mod cocycle;2mod growth;3mod order;4mod series;5mod unsolved;6mod word;78use mrlycore::rng::Rng;9use series::{build, product, Rep, Table};10use word::{render, spell, CODES, LIBRARY, SERIES};1112const SEED: u64 = 1618033988;1314fn line(cells: &[String], widths: &[usize]) -> String {15 cells16 .iter()17 .zip(widths.iter())18 .map(|(cell, width)| {19 let width = *width;20 format!("{cell:>width$}")21 })22 .collect::<Vec<_>>()23 .join(" ")24}2526fn matrix_text(matrix: &[Vec<i64>]) -> String {27 let rows: Vec<String> = matrix28 .iter()29 .map(|row| {30 let cells: Vec<String> = row.iter().map(|value| format!("{value}")).collect();31 format!("[{}]", cells.join(","))32 })33 .collect();34 format!("[{}]", rows.join(","))35}3637fn codes_text(codes: &[u8]) -> String {38 let cells: Vec<String> = codes.iter().map(|code| format!("{code}")).collect();39 format!("{{{}}}", cells.join(","))40}4142fn alphabet() {43 println!("ALPHABET");44 println!("base 2, D = 2, bit i of a code is residue corner i in row-major order, code 3 the top row and code 5 the left column");45 let two = order::sensitivity(&CODES, 2);46 println!(47 "length 2: {} words over the 15 non-empty codes, {} multisets with two or more orderings",48 15 * 15,49 two.total50 );51 let three = order::sensitivity(&LIBRARY, 3);52 println!(53 "length 3: {} words over the library {}, {} multisets with two or more orderings",54 10 * 10 * 10,55 codes_text(&LIBRARY),56 three.total57 );58 println!("the library is every code of fill 2 or 3, the 15 less the four one-cell codes and the full tile");59 let (scanned, hits) = order::library_search();60 println!(61 "the length-3 row 36 188 188 100 is reproduced by {} of the {scanned} ten-code subsets of the 15, namely {}",62 hits.len(),63 hits.iter().map(|hit| codes_text(hit)).collect::<Vec<_>>().join(" ")64 );65 println!();66 println!("ORDER SENSITIVITY");67 let widths = [24usize, 17, 17];68 println!(69 "{}",70 line(71 &[72 "observable".into(),73 "length 2 of 105".into(),74 "length 3 of 210".into()75 ],76 &widths77 )78 );79 let rows: [(&str, usize, usize); 7] = [80 ("fill side density", two.fill, three.fill),81 ("main-diagonal count", two.diagonal, three.diagonal),82 ("boundary", two.boundary, three.boundary),83 ("components", two.components, three.components),84 ("Euler characteristic", two.euler, three.euler),85 ("holes", two.holes, three.holes),86 ("anti-diagonal profile", two.profile, three.profile),87 ];88 for (name, left, right) in rows.iter() {89 println!(90 "{}",91 line(92 &[(*name).into(), format!("{left}"), format!("{right}")],93 &widths94 )95 );96 }97 println!(98 "profile peak sensitive on {} of {} at length 2, profile support on {}",99 two.peak, two.total, two.support100 );101 println!(102 "boundary here is the count of cells with a void or exterior neighbour; the exposed-face count 4N - 2E is a second reading, sensitive on {} of 105 and {} of 210",103 two.perimeter, three.perimeter104 );105 assert_eq!(two.fill, 0, "fill is order-blind");106 assert_eq!(two.diagonal, 0, "the diagonal count is order-blind");107 assert_eq!(three.diagonal, 0, "the diagonal count is order-blind");108 assert_eq!(two.boundary, 0, "boundary is order-blind at length 2");109}110111fn witnesses() {112 println!();113 println!("WITNESSES");114 let left = render(&[3, 6]).components();115 let right = render(&[6, 3]).components();116 println!("comp(A_3 (x) A_6) = {left}, comp(A_6 (x) A_3) = {right}");117 assert_eq!((left, right), (4, 2), "the minimal witness stands");118 let pairs = order::pair_component_table(&[3, 5, 10, 12, 6, 9]);119 let adjacent = [3u8, 5, 10, 12];120 let mut same = 0usize;121 let mut mixed = 0usize;122 for (a, b, one, two) in pairs.iter() {123 let split = adjacent.contains(a) != adjacent.contains(b);124 if split {125 mixed += 1;126 assert_eq!(127 (*one, *two),128 (4, 2),129 "adjacent against diagonal is 4 then 2"130 );131 } else {132 same += 1;133 assert_eq!(one, two, "a pair inside one class commutes");134 }135 }136 let twins = render(&[6, 9]).components();137 println!(138 "k = 2 codes: all {same} pairs inside one class commute of {} in all, diagonal against diagonal at {twins}, and all {mixed} adjacent-against-diagonal pairs give 4 against 2",139 pairs.len()140 );141 let big = order::pair_component_table(&[7, 11, 13, 14, 15]);142 let ones = big.iter().filter(|(_, _, a, b)| *a == 1 && *b == 1).count();143 println!(144 "k >= 3 codes: {} of {} pairs give one component in either order",145 ones,146 big.len()147 );148 assert_eq!(ones, big.len(), "every heavy pair is one component");149}150151fn blind_laws() {152 println!();153 println!("ORDER-BLIND LAWS");154 let diagonal = order::diagonal_factors();155 println!(156 "the main-diagonal count factors on all {} words of length 3, mismatches {diagonal}",157 15 * 15 * 15158 );159 let contacts = order::contacts_multiply();160 println!(161 "row and column contacts multiply on all {} words of length 3, mismatches {contacts}",162 15 * 15 * 15163 );164 let (pairs, bad) = order::boundary_pairs();165 println!("boundary and interior agree under the factor swap on all {pairs} ordered code pairs, the 15 non-empty codes with the empty one, mismatches {bad}");166 assert_eq!(diagonal, 0, "the diagonal count factors");167 assert_eq!(contacts, 0, "contacts multiply");168 assert_eq!(bad, 0, "boundary is order-blind at length 2");169}170171fn representation(table: &mut Table) -> Rep {172 println!();173 println!("RATIONAL SERIES");174 let widths = [24usize, 6, 20];175 println!(176 "{}",177 line(178 &[179 "observable".into(),180 "rank".into(),181 "distinct matrices".into()182 ],183 &widths184 )185 );186 let mut built: Vec<Rep> = Vec::new();187 for which in 0..4 {188 let rep = build(which, table);189 let classes = rep.classes();190 println!(191 "{}",192 line(193 &[194 SERIES[which].into(),195 format!("{}", rep.basis.len()),196 format!("{}", classes.len())197 ],198 &widths199 )200 );201 built.push(rep);202 }203 for which in 0..4 {204 let names: Vec<String> = built[which].basis.iter().map(|word| spell(word)).collect();205 println!("{} basis words: {}", SERIES[which], names.join(", "));206 }207 let components = &built[0];208 println!(209 "components lambda = ({}), gamma = ({})^T",210 components211 .lambda212 .iter()213 .map(|v| format!("{v}"))214 .collect::<Vec<_>>()215 .join(","),216 components217 .gamma218 .iter()219 .map(|v| format!("{v}"))220 .collect::<Vec<_>>()221 .join(",")222 );223 let classes = components.classes();224 for (members, matrix) in classes.iter() {225 println!(226 "class {} matrix {}",227 codes_text(members),228 matrix_text(matrix)229 );230 }231 let mut commuting: Vec<(Vec<u8>, Vec<u8>)> = Vec::new();232 let mut pairs = 0usize;233 for i in 0..classes.len() {234 for j in i + 1..classes.len() {235 pairs += 1;236 if product(&classes[i].1, &classes[j].1) == product(&classes[j].1, &classes[i].1) {237 commuting.push((classes[i].0.clone(), classes[j].0.clone()));238 }239 }240 }241 println!(242 "{} of {} class pairs fail to commute, the commuting pair {}",243 pairs - commuting.len(),244 pairs,245 commuting246 .iter()247 .map(|(a, b)| format!("{} and {}", codes_text(a), codes_text(b)))248 .collect::<Vec<_>>()249 .join(", ")250 );251 let light = components.matrices[&1].clone();252 let diagonal = components.matrices[&6].clone();253 let doubled: Vec<Vec<i64>> = light254 .iter()255 .map(|row| row.iter().map(|v| 2 * v).collect())256 .collect();257 println!("M(6,9) = 2 M(1,2,4,8): {}", doubled == diagonal);258 assert_eq!(259 doubled, diagonal,260 "the two zero-contact classes are proportional"261 );262 let mut checked = 0usize;263 let mut bad = 0usize;264 for length in 1..5 {265 for word in order::words(&CODES, length) {266 let obs = word::observe(&word);267 checked += 1;268 for which in 0..4 {269 if built[which].predict(&word) != word::series_value(&obs, which) {270 bad += 1;271 }272 }273 }274 }275 println!("all {checked} words of length 1 to 4 over the 15 codes, four observables, mismatches {bad}");276 assert_eq!(bad, 0, "the representation is exact to length 4");277 let mut rng = Rng::new(SEED);278 let mut long = 0usize;279 let mut wrong = 0usize;280 for length in 5..8 {281 for _ in 0..40 {282 let word: Vec<u8> = (0..length).map(|_| CODES[rng.below(15)]).collect();283 let obs = word::observe(&word);284 long += 1;285 for which in 0..4 {286 if built[which].predict(&word) != word::series_value(&obs, which) {287 wrong += 1;288 }289 }290 }291 }292 println!(293 "{long} words of length 5 to 7 drawn at seed {SEED}, four observables, mismatches {wrong}"294 );295 assert_eq!(wrong, 0, "the representation is exact on the drawn words");296 built.remove(0)297}298299fn adjudication(rep: &Rep) {300 println!();301 println!("GROWTH");302 let widths = [3usize, 14, 11, 14, 9, 13, 11, 8];303 println!(304 "{}",305 line(306 &[307 "L".into(),308 "(15^(L-1),6)".into(),309 "2*4^(L-1)".into(),310 "(15^(L-1),3)".into(),311 "2^(L-1)".into(),312 "(7^(L-1),6)".into(),313 "2*3^(L-1)".into(),314 "kappa(3)".into(),315 ],316 &widths317 )318 );319 for length in 2..11usize {320 let power = (length - 1) as u32;321 let checker = growth::components(&growth::family(15, 6, length));322 let stripes = growth::components(&growth::family(15, 3, length));323 let gasket = growth::components(&growth::family(7, 6, length));324 let kappa = growth::merging(&growth::family(15, 3, length));325 let expected = [2 * 4u64.pow(power), 2u64.pow(power), 2 * 3u64.pow(power)];326 assert_eq!(checker, expected[0], "the checkerboard family is 2*4^(L-1)");327 assert_eq!(stripes, expected[1], "the striped family is 2^(L-1)");328 assert_eq!(gasket, expected[2], "the gasket family is 2*3^(L-1)");329 assert_eq!(330 kappa, expected[1],331 "the striped family merges on 2^(L-1) components"332 );333 assert_eq!(334 rep.predict(&growth::family(15, 6, length)) as u64,335 checker,336 "the series predicts the checkerboard family"337 );338 assert_eq!(339 rep.predict(&growth::family(15, 3, length)) as u64,340 stripes,341 "the series predicts the striped family"342 );343 assert_eq!(344 rep.predict(&growth::family(7, 6, length)) as u64,345 gasket,346 "the series predicts the gasket family"347 );348 println!(349 "{}",350 line(351 &[352 format!("{length}"),353 format!("{checker}"),354 format!("{}", expected[0]),355 format!("{stripes}"),356 format!("{}", expected[1]),357 format!("{gasket}"),358 format!("{}", expected[2]),359 format!("{kappa}"),360 ],361 &widths362 )363 );364 }365 for length in 2..5usize {366 let (best, witness) = growth::max_components(length);367 let bound = growth::independent_bound(length);368 println!(369 "length {length}: the largest component count over all {} words is {best}, attained by {}, against the independent-set bound {bound}",370 15usize.pow(length as u32),371 spell(&witness)372 );373 assert_eq!(best, bound, "the checkerboard bound is attained");374 }375 let mergers: Vec<String> = (1..5usize)376 .map(|length| {377 let (best, witness) = growth::max_merging(length);378 assert_eq!(379 best,380 1 << (length - 1),381 "the striped family maximises kappa"382 );383 format!("{best} at {}", spell(&witness))384 })385 .collect();386 println!(387 "the largest kappa over all words of length 1 to 4 is {}",388 mergers.join(", ")389 );390 let five = growth::max_predicted(rep, 5);391 println!(392 "length 5: the largest predicted component count over all {} words is {five}, against the independent-set bound {}",393 15usize.pow(5),394 growth::independent_bound(5)395 );396 assert_eq!(397 five as u64,398 growth::independent_bound(5),399 "the bound is attained at length 5"400 );401}402403fn controls() {404 println!();405 println!("CONTROLS");406 for length in 2..4usize {407 let (checked, bad) = order::crate_agreement(length);408 println!("mrlymath::bang::magic agrees cell for cell on all {checked} words of length {length}, mismatches {bad}");409 assert_eq!(bad, 0, "the factory and the study draw one word");410 }411 let (cases, bad) = order::block_reduction();412 println!("a periodic word equals the self-Kronecker power of its one-period composite on {cases} cases at periods 2 and 3 and lengths to 6, mismatches {bad}");413 assert_eq!(bad, 0, "block reduction holds cell for cell");414}415416fn main() {417 println!("MAGIC WORDS");418 println!();419 alphabet();420 witnesses();421 blind_laws();422 let mut table = Table::new();423 let rep = representation(&mut table);424 adjudication(&rep);425 cocycle::study(&rep);426 unsolved::study(&rep);427 controls();428}