seed.rs

1use crate::rules::{evolve, mirrored, RULES};2use std::collections::{BTreeMap, BTreeSet};34pub const STEPS: usize = 256;56pub struct Census {7    pub class: Vec<usize>,8    pub occurring: Vec<u8>,9}1011struct Pass {12    class: Vec<usize>,13    occurring: Vec<u8>,14    distinct: usize,15    reflected: usize,16    histogram: BTreeMap<usize, usize>,17}1819fn classify(steps: usize, pad: usize) -> Pass {20    let mut seen: BTreeMap<Vec<u8>, usize> = BTreeMap::new();21    let mut folded: BTreeSet<Vec<u8>> = BTreeSet::new();22    let mut class = vec![0usize; RULES];23    let mut occurring = vec![0u8; RULES];24    for rule in 0..RULES {25        let (diagram, met) = evolve(rule, steps, pad);26        occurring[rule] = met;27        let mirror = mirrored(&diagram);28        let next = seen.len();29        class[rule] = *seen.entry(diagram.cells.clone()).or_insert(next);30        folded.insert(diagram.cells.min(mirror));31    }32    let mut sizes: BTreeMap<usize, usize> = BTreeMap::new();33    for rule in 0..RULES {34        *sizes.entry(class[rule]).or_insert(0) += 1;35    }36    let mut histogram: BTreeMap<usize, usize> = BTreeMap::new();37    for size in sizes.values() {38        *histogram.entry(*size).or_insert(0) += 1;39    }40    Pass {41        distinct: seen.len(),42        reflected: folded.len(),43        class,44        occurring,45        histogram,46    }47}4849pub fn report() -> Census {50    println!("SINGLE-SEED CENSUS");51    println!("one live cell on a line padded by pad cells beyond the 2T+1 window that is cropped and compared");52    let mut last: Option<Pass> = None;53    for steps in [64usize, 128, STEPS] {54        let narrow = classify(steps, steps);55        let wide = classify(steps, 2 * steps);56        assert_eq!(57            narrow.class, wide.class,58            "the diagrams move between pad = T and pad = 2T at T = {steps}"59        );60        assert_eq!(61            narrow.occurring, wide.occurring,62            "the occurring neighbourhoods move between pad = T and pad = 2T at T = {steps}"63        );64        println!(65            "T = {steps}: {} distinct diagrams, {} up to left-right reflection, class-size histogram {:?}, identical at pad = T and pad = 2T",66            narrow.distinct, narrow.reflected, narrow.histogram67        );68        if let Some(before) = &last {69            assert_eq!(70                before.occurring, narrow.occurring,71                "the occurring neighbourhoods move with T at {steps}"72            );73        }74        last = Some(narrow);75    }76    let pass = last.expect("three depths ran");77    let (class, occurring, distinct) = (pass.class, pass.occurring, pass.distinct);78    println!("the occurring neighbourhood set is the same at T = 64, 128 and {STEPS}");79    let mut failures = 0usize;80    for a in 0..RULES {81        for b in 0..RULES {82            let mask = occurring[a] as usize;83            if occurring[a] == occurring[b] && a & mask == b & mask && class[a] != class[b] {84                failures += 1;85            }86        }87    }88    assert_eq!(89        failures, 0,90        "rules sharing the occurring key do not share the diagram"91    );92    println!("law: equal key implies equal diagram, 0 failures over all {} ordered pairs, the key being the occurring set together with the rule restricted to it", RULES * RULES);93    let keys: BTreeSet<(u8, usize)> = (0..RULES)94        .map(|r| (occurring[r], r & occurring[r] as usize))95        .collect();96    let mut members: BTreeMap<usize, Vec<usize>> = BTreeMap::new();97    for rule in 0..RULES {98        members.entry(class[rule]).or_default().push(rule);99    }100    let split: Vec<usize> = members101        .values()102        .filter(|rules| {103            rules104                .iter()105                .map(|r| (occurring[*r], r & occurring[*r] as usize))106                .collect::<BTreeSet<_>>()107                .len()108                > 1109        })110        .flatten()111        .copied()112        .collect();113    let split_classes: BTreeSet<usize> = split.iter().map(|r| class[*r]).collect();114    let split_keys: BTreeSet<(u8, usize)> = split115        .iter()116        .map(|r| (occurring[*r], r & occurring[*r] as usize))117        .collect();118    println!(119        "the key takes {} values against {distinct} distinct diagrams, so it separates strictly more than the diagram does and is not a complete invariant",120        keys.len()121    );122    println!("over-separated rules, {} of them spread over {} diagram classes carrying {} keys in all: {split:?}", split.len(), split_classes.len(), split_keys.len());123    assert_eq!(split_keys.len(), 11);124    assert!(125        keys.len() > distinct,126        "the key no longer over-separates the diagram"127    );128    assert_eq!(129        split,130        vec![23, 31, 55, 63, 87, 95, 119, 127, 151, 159, 183, 191, 215, 223, 247, 255],131        "the over-separated rules are not the expected 16"132    );133    assert_eq!(134        split_classes.len(),135        2,136        "the over-separated rules do not fall into two diagram classes"137    );138    let mut occ_sizes: BTreeMap<u32, usize> = BTreeMap::new();139    for rule in 0..RULES {140        *occ_sizes.entry(occurring[rule].count_ones()).or_insert(0) += 1;141    }142    println!("occurring-set sizes {occ_sizes:?}");143    Census { class, occurring }144}