elementary.rs

1use crate::bang::universe::{apply, corner_index, corners, degree, orbit, symmetries, Code};2use crate::name::{Bang, Named};3use mrlycore::tensor::Tensor;4use std::collections::BTreeSet;56/// Returns the bit a rule sends the neighbourhood to, reading bit `4l + 2c + r` in Wolfram's numbering.7pub fn output(rule: u8, l: u8, c: u8, r: u8) -> u8 {8    (rule >> (4 * l + 2 * c + r)) & 19}1011/// Advances one row one generation, a constant-0 boundary unless the edges wrap.12pub fn step(row: &[u8], rule: u8, wrap: bool) -> Vec<u8> {13    let width = row.len();14    (0..width)15        .map(|i| {16            let l = if i == 0 {17                if wrap {18                    row[width - 1]19                } else {20                    021                }22            } else {23                row[i - 1]24            };25            let r = if i + 1 == width {26                if wrap {27                    row[0]28                } else {29                    030                }31            } else {32                row[i + 1]33            };34            output(rule, l, row[i], r)35        })36        .collect()37}3839/// Returns the space-time diagram of a seed row: row 0 the seed, then one row per generation.40pub fn history(row: &[u8], rule: u8, steps: usize, wrap: bool) -> Tensor {41    let width = row.len();42    let mut cells = Vec::with_capacity((steps + 1) * width);43    cells.extend_from_slice(row);44    let mut current = row.to_vec();45    for _ in 0..steps {46        current = step(&current, rule, wrap);47        cells.extend_from_slice(&current);48    }49    Tensor::of(cells, vec![steps + 1, width])50}5152/// Returns the single-seed diagram: one live cell run the given generations on a line padded by `steps` cells beyond the `2 steps + 1` window on each side, cropped back to that window.53pub fn single_seed(rule: u8, steps: usize) -> Tensor {54    let window = 2 * steps + 1;55    let width = window + 2 * steps;56    let mut row = vec![0u8; width];57    row[width / 2] = 1;58    let full = history(&row, rule, steps, false);59    let mut cells = Vec::with_capacity((steps + 1) * window);60    for t in 0..=steps {61        let start = t * width + steps;62        cells.extend_from_slice(&full.bytes()[start..start + window]);63    }64    Tensor::of(cells, vec![steps + 1, window])65}6667/// Returns the eight output bits of a rule, corner `i` at index `i = 4 x0 + 2 x1 + x2`.68pub fn corner_bits(rule: u8) -> Vec<u8> {69    (0..8).map(|i| (rule >> i) & 1).collect()70}7172/// Returns the count of neighbourhoods a rule sends to one.73pub fn popcount(rule: u8) -> u32 {74    rule.count_ones()75}7677/// Returns Langton's lambda, the popcount over eight.78pub fn lambda(rule: u8) -> f64 {79    rule.count_ones() as f64 / 8.080}8182/// Returns the GF(2) algebraic degree of a rule, minus one for the zero rule.83pub fn rule_degree(rule: u8) -> i32 {84    degree(rule as Code, 3)85}8687/// Returns whether a rule is affine, its algebraic degree at most one.88pub fn affine(rule: u8) -> bool {89    rule_degree(rule) <= 190}9192/// Returns the design name a rule carries, `bang dim 3, code <rule>`.93pub fn rule_name(rule: u8) -> String {94    Bang::new(rule as Code, 3, 2).to_mrly()95}9697fn act(rule: u8, element: &(Vec<usize>, Vec<u8>), complement: bool) -> u8 {98    let cells = corners(3);99    let mut image = 0u8;100    for (i, cell) in cells.iter().enumerate() {101        if (rule >> i) & 1 == 1 {102            image |= 1 << corner_index(&apply(element, cell));103        }104    }105    if complement {106        image ^ 0xff107    } else {108        image109    }110}111112/// Returns the rules a rule reaches under the signed axis permutations of the cube, in ascending order.113pub fn cube_orbit(rule: u8) -> Vec<u8> {114    orbit(rule as Code, 3)115        .into_iter()116        .map(|c| c as u8)117        .collect()118}119120/// Returns the rules a rule reaches under left-right reflection and conjugation, Wolfram's equivalence, in ascending order.121pub fn wolfram_class(rule: u8) -> Vec<u8> {122    let plain = (vec![0, 1, 2], vec![0, 0, 0]);123    let mirror = (vec![2, 1, 0], vec![0, 0, 0]);124    let mut out = BTreeSet::new();125    out.insert(act(rule, &plain, false));126    out.insert(act(rule, &mirror, false));127    out.insert(act(rule, &(plain.0.clone(), vec![1, 1, 1]), true));128    out.insert(act(rule, &(mirror.0.clone(), vec![1, 1, 1]), true));129    out.into_iter().collect()130}131132/// Returns the rules a rule reaches under the cube group together with the output complement, its NPN class, in ascending order.133pub fn npn_class(rule: u8) -> Vec<u8> {134    let mut out = BTreeSet::new();135    for element in symmetries(3) {136        out.insert(act(rule, &element, false));137        out.insert(act(rule, &element, true));138    }139    out.into_iter().collect()140}141142fn level_set(rule: u8) -> bool {143    let mut value = [-1i8; 4];144    for i in 0..8usize {145        let bit = ((rule >> i) & 1) as i8;146        let weight = i.count_ones() as usize;147        if value[weight] != -1 && value[weight] != bit {148            return false;149        }150        value[weight] = bit;151    }152    true153}154155fn pinned(rule: u8) -> bool {156    let cells: Vec<usize> = (0..8).filter(|&i| (rule >> i) & 1 == 1).collect();157    if cells.is_empty() {158        return false;159    }160    let fixed = (0..3)161        .filter(|axis| {162            cells163                .iter()164                .map(|c| (c >> axis) & 1)165                .collect::<BTreeSet<usize>>()166                .len()167                == 1168        })169        .count();170    cells.len() == 1 << (3 - fixed)171}172173/// Returns the genus of a rule's cube class: `iso` when it meets a level set, `axis` when it meets an axis-pinned block, else `comp`.174pub fn genus(rule: u8) -> &'static str {175    let class = cube_orbit(rule);176    if class.iter().any(|&c| level_set(c)) {177        "iso"178    } else if class.iter().any(|&c| pinned(c)) {179        "axis"180    } else {181        "comp"182    }183}184185fn arrows(rule: u8) -> Vec<(usize, usize, u8)> {186    let mut out = Vec::new();187    for a in 0..2u8 {188        for b in 0..2u8 {189            for c in 0..2u8 {190                out.push((191                    2 * a as usize + b as usize,192                    2 * b as usize + c as usize,193                    output(rule, a, b, c),194                ));195            }196        }197    }198    out199}200201/// Returns whether a rule is surjective on bi-infinite lines, by the de Bruijn subset walk from the full node set.202pub fn surjective(rule: u8) -> bool {203    let edges = arrows(rule);204    let start = 0b1111usize;205    let mut seen = BTreeSet::from([start]);206    let mut stack = vec![start];207    while let Some(set) = stack.pop() {208        for label in 0..2u8 {209            let mut next = 0usize;210            for &(u, v, l) in &edges {211                if l == label && (set >> u) & 1 == 1 {212                    next |= 1 << v;213                }214            }215            if next == 0 {216                return false;217            }218            if seen.insert(next) {219                stack.push(next);220            }221        }222    }223    true224}225226/// Returns whether a rule is reversible, by the pair graph on the de Bruijn nodes pruned to its bi-infinite core.227pub fn reversible(rule: u8) -> bool {228    let edges = arrows(rule);229    let mut adjacency = vec![BTreeSet::new(); 16];230    for &(u1, v1, l1) in &edges {231        for &(u2, v2, l2) in &edges {232            if l1 == l2 {233                adjacency[4 * u1 + u2].insert(4 * v1 + v2);234            }235        }236    }237    let mut core: BTreeSet<usize> = (0..16).collect();238    loop {239        let outs: BTreeSet<usize> = core240            .iter()241            .filter(|p| adjacency[**p].iter().any(|q| core.contains(q)))242            .copied()243            .collect();244        let ins: BTreeSet<usize> = outs245            .iter()246            .flat_map(|p| adjacency[*p].iter().filter(|q| outs.contains(q)).copied())247            .collect();248        let next: BTreeSet<usize> = outs.intersection(&ins).copied().collect();249        if next == core {250            break;251        }252        core = next;253    }254    !core.iter().any(|p| p / 4 != p % 4)255}256257/// Returns the birth and survive counts of a rule read outer-totalistically on its two outer cells, or None when it does not read them by count alone.258pub fn outer_totalistic(rule: u8) -> Option<(Vec<usize>, Vec<usize>)> {259    let mut table = [[-1i8; 3]; 2];260    for l in 0..2u8 {261        for c in 0..2u8 {262            for r in 0..2u8 {263                let bit = output(rule, l, c, r) as i8;264                let slot = &mut table[c as usize][(l + r) as usize];265                if *slot != -1 && *slot != bit {266                    return None;267                }268                *slot = bit;269            }270        }271    }272    let birth = (0..3).filter(|&n| table[0][n] == 1).collect();273    let survive = (0..3).filter(|&n| table[1][n] == 1).collect();274    Some((birth, survive))275}276277/// Returns the base-2 plane design a rule's single seed draws, or None when it draws none.278pub fn gasket(rule: u8) -> Option<&'static str> {279    match rule {280        60 | 90 => Some("bang dim 2, code 13"),281        102 => Some("bang dim 2, code 14"),282        _ => None,283    }284}285286#[cfg(test)]287mod tests {288    use super::*;289    use crate::life::{next_grid, Boundary};290    use crate::two::Cell2d;291    fn rules() -> impl Iterator<Item = u8> {292        0..=255u8293    }294    #[test]295    fn thirty_rules_are_surjective() {296        assert_eq!(rules().filter(|&r| surjective(r)).count(), 30);297    }298    #[test]299    fn the_reversible_rules_are_the_six_single_axis_ones() {300        let six: Vec<u8> = rules().filter(|&r| reversible(r)).collect();301        assert_eq!(six, vec![15, 51, 85, 170, 204, 240]);302        assert!(six.iter().all(|&r| surjective(r)));303    }304    #[test]305    fn the_class_counts_are_eighty_eight_twenty_two_and_fourteen() {306        let count = |f: fn(u8) -> Vec<u8>| rules().map(|r| f(r)[0]).collect::<BTreeSet<u8>>().len();307        assert_eq!(count(wolfram_class), 88);308        assert_eq!(count(cube_orbit), 22);309        assert_eq!(count(npn_class), 14);310    }311    #[test]312    fn rule_110_holds_a_cube_orbit_of_twenty_four() {313        let cube = cube_orbit(110);314        assert_eq!(cube.len(), 24);315        assert!(cube.contains(&94));316        assert!(!cube.contains(&137));317        assert_eq!(wolfram_class(110), vec![110, 124, 137, 193]);318    }319    #[test]320    fn rule_60_draws_the_level_four_gasket() {321        let diagram = single_seed(60, 16);322        let tile = crate::two::create(13, 2, 4, 0, 2).unwrap();323        let centre = diagram.shape[1] / 2;324        for t in 0..16 {325            for j in 0..16 {326                assert_eq!(327                    diagram.get(&[t, centre + j]),328                    tile.types().get(&[t, j]),329                    "t={t} j={j}"330                );331            }332        }333        assert_eq!(gasket(60), Some("bang dim 2, code 13"));334    }335    #[test]336    fn rule_150_row_populations_are_a071053() {337        let diagram = single_seed(150, 11);338        let width = diagram.shape[1];339        let counts: Vec<u32> = (0..12)340            .map(|t| (0..width).map(|i| diagram.get(&[t, i]) as u32).sum())341            .collect();342        assert_eq!(counts, vec![1, 3, 3, 5, 3, 9, 5, 11, 3, 9, 9, 15]);343    }344    #[test]345    fn sixty_four_rules_read_their_outer_cells_by_count() {346        assert_eq!(347            rules().filter(|&r| outer_totalistic(r).is_some()).count(),348            64349        );350        assert!(outer_totalistic(110).is_none());351        assert_eq!(outer_totalistic(94), Some((vec![1], vec![0, 1])));352    }353    #[test]354    fn the_genus_and_affine_counts_hold() {355        assert_eq!(rules().filter(|&r| affine(r)).count(), 16);356        let genus_of = |name| rules().filter(|&r| genus(r) == name).count();357        assert_eq!(358            (genus_of("iso"), genus_of("axis"), genus_of("comp")),359            (52, 18, 186)360        );361    }362    #[test]363    fn a_ring_steps_around_itself() {364        let row = [1, 0, 0, 0, 0];365        assert_eq!(step(&row, 170, true), vec![0, 0, 0, 0, 1]);366        assert_eq!(step(&row, 170, false), vec![0, 0, 0, 0, 0]);367    }368    #[test]369    fn a_line_steps_through_the_grid_stepper() {370        let row = vec![0, 1, 1, 0, 1, 0, 0];371        let mask = Tensor::of(vec![1, 0, 1], vec![1, 3]);372        let cell = Cell2d::new(Tensor::of(row.clone(), vec![1, 7]));373        let next = next_grid(&cell, &[1], &[0, 1], &mask, Boundary::Constant).unwrap();374        assert_eq!(next.types().bytes(), step(&row, 94, false));375    }376    #[test]377    fn the_card_pieces_read_rule_110() {378        assert_eq!(rule_name(110), "bang dim 3, code 110");379        assert_eq!(corner_bits(110), vec![0, 1, 1, 1, 0, 1, 1, 0]);380        assert_eq!(381            (popcount(110), rule_degree(110), genus(110)),382            (5, 3, "comp")383        );384        assert!((lambda(110) - 0.625).abs() < 1e-12);385        assert!(!surjective(110) && !reversible(110) && !affine(110));386    }387}