main.rs

1use mrlyrs::math::bang::factory::create;2use mrlyrs::math::bang::Code;3use std::collections::{BTreeMap, BTreeSet, HashMap, HashSet};4use std::env;5use std::hash::{BuildHasherDefault, Hasher};6use std::time::Instant;78// HASH910#[derive(Default)]11struct Fx(u64);1213impl Hasher for Fx {14    fn finish(&self) -> u64 {15        self.016    }17    fn write(&mut self, bytes: &[u8]) {18        for &byte in bytes {19            self.write_u64(byte as u64);20        }21    }22    fn write_u64(&mut self, n: u64) {23        self.0 = (self.0.rotate_left(5) ^ n).wrapping_mul(0x517c_c1b7_2722_0a95);24    }25}2627type Fast = BuildHasherDefault<Fx>;2829// PICTURE3031#[derive(Clone, PartialEq, Eq)]32struct Pic {33    side: usize,34    cells: Vec<u8>,35}3637impl Pic {38    fn one() -> Pic {39        Pic {40            side: 1,41            cells: vec![1],42        }43    }44    fn block(window: [u8; 4]) -> Pic {45        Pic {46            side: 2,47            cells: window.to_vec(),48        }49    }50    fn at(&self, row: usize, col: usize) -> u8 {51        self.cells[row * self.side + col]52    }53    fn pairs(&self) -> BTreeSet<[u8; 4]> {54        let mut out = BTreeSet::new();55        for row in 0..self.side - 1 {56            for col in 0..self.side - 1 {57                out.insert([58                    self.at(row, col),59                    self.at(row, col + 1),60                    self.at(row + 1, col),61                    self.at(row + 1, col + 1),62                ]);63            }64        }65        out66    }67}6869// DESIGN7071#[derive(Clone)]72struct Design {73    base: usize,74    code: u32,75    tile: Vec<u8>,76}7778impl Design {79    fn new(base: usize, code: u32) -> Design {80        let tile = (0..base * base)81            .map(|cell| ((code >> cell) & 1) as u8)82            .collect();83        Design { base, code, tile }84    }85    fn filled(&self) -> Vec<(usize, usize)> {86        let b = self.base;87        (0..b * b)88            .filter(|&cell| self.tile[cell] == 1)89            .map(|cell| (cell / b, cell % b))90            .collect()91    }92    fn empty(&self) -> bool {93        self.code == 094    }95    fn full(&self) -> bool {96        self.tile.iter().all(|&cell| cell == 1)97    }98    fn degenerate(&self) -> bool {99        let cells = self.filled();100        let last = self.base - 1;101        !cells.is_empty()102            && (cells.iter().all(|c| c.0 == 0)103                || cells.iter().all(|c| c.0 == last)104                || cells.iter().all(|c| c.1 == 0)105                || cells.iter().all(|c| c.1 == last))106    }107    fn image(&self, g: usize) -> Design {108        let b = self.base;109        let mut code = 0u32;110        for (row, col) in self.filled() {111            let (mut r, mut c) = if g & 4 != 0 { (col, row) } else { (row, col) };112            for _ in 0..g & 3 {113                (r, c) = (c, b - 1 - r);114            }115            code |= 1 << (r * b + c);116        }117        Design::new(b, code)118    }119    fn canonical(&self) -> u32 {120        (0..8).map(|g| self.image(g).code).min().unwrap()121    }122    fn substitute(&self, pic: &Pic) -> Pic {123        let b = self.base;124        let side = pic.side * b;125        let mut cells = vec![0u8; side * side];126        for row in 0..side {127            for col in 0..side {128                cells[row * side + col] =129                    pic.at(row / b, col / b) & self.tile[(row % b) * b + col % b];130            }131        }132        Pic { side, cells }133    }134    fn render(&self, level: usize) -> Pic {135        let mut pic = Pic::one();136        for _ in 0..level {137            pic = self.substitute(&pic);138        }139        pic140    }141    fn language(&self) -> (Vec<[u8; 4]>, usize) {142        let mut set = self.render(1).pairs();143        let mut level = 1;144        loop {145            let mut next = BTreeSet::new();146            for window in &set {147                next.extend(self.substitute(&Pic::block(*window)).pairs());148            }149            assert!(150                next.is_superset(&set),151                "the 2 x 2 windows of a render shrank one level up"152            );153            if next == set {154                return (set.into_iter().collect(), level);155            }156            set = next;157            level += 1;158        }159    }160}161162// COUNT163164fn depth(base: usize, top: usize) -> usize {165    let mut n = 0;166    while base.pow(n as u32) + 1 < top {167        n += 1;168    }169    n170}171172fn count(design: &Design, top: usize) -> Vec<usize> {173    let (pairs, _) = design.language();174    let n = depth(design.base, top);175    let pics: Vec<Pic> = pairs176        .iter()177        .map(|window| {178            let mut pic = Pic::block(*window);179            for _ in 0..n {180                pic = design.substitute(&pic);181            }182            pic183        })184        .collect();185    let side = 2 * design.base.pow(n as u32);186    let mut ids: Vec<Vec<u32>> = pics187        .iter()188        .map(|pic| pic.cells.iter().map(|&cell| cell as u32).collect())189        .collect();190    let values: BTreeSet<u8> = pics191        .iter()192        .flat_map(|pic| pic.cells.iter().copied())193        .collect();194    let mut out = vec![values.len()];195    for k in 1..top {196        let wide = side - k + 1;197        let narrow = wide - 1;198        let mut map: HashMap<u64, u32, Fast> = HashMap::default();199        for (pic, id) in pics.iter().zip(ids.iter_mut()) {200            let mut next = vec![0u32; narrow * narrow];201            for x in 0..narrow {202                for y in 0..narrow {203                    let key = (id[x * wide + y] as u64) << 34204                        | (id[(x + 1) * wide + y + 1] as u64) << 2205                        | (pic.at(x + k, y) as u64) << 1206                        | pic.at(x, y + k) as u64;207                    let fresh = map.len() as u32;208                    next[x * narrow + y] = *map.entry(key).or_insert(fresh);209                }210            }211            *id = next;212        }213        assert!(map.len() < 1 << 30, "window names overflow the key");214        out.push(map.len());215    }216    out217}218219// SCAN220221fn brute(pic: &Pic, top: usize) -> Vec<usize> {222    let side = pic.side;223    let mut out = Vec::new();224    for k in 1..=top.min(side).min(64) {225        let mask = if k == 64 { u64::MAX } else { (1u64 << k) - 1 };226        let wide = side - k + 1;227        let mut words = vec![0u64; side * wide];228        for row in 0..side {229            let mut word = 0u64;230            for col in 0..side {231                word = ((word << 1) | pic.at(row, col) as u64) & mask;232                if col + 1 >= k {233                    words[row * wide + col + 1 - k] = word;234                }235            }236        }237        let mut seen: HashSet<Vec<u64>, Fast> = HashSet::default();238        for x in 0..wide {239            for y in 0..wide {240                seen.insert((0..k).map(|t| words[(x + t) * wide + y]).collect());241            }242        }243        out.push(seen.len());244    }245    out246}247248fn crate_render(design: &Design, level: usize) -> Pic {249    let b = design.base;250    let tensor = create(Code::from(design.code as u64), b, 2, b, level).unwrap();251    Pic {252        side: b.pow(level as u32),253        cells: tensor.bytes().unwrap().to_vec(),254    }255}256257// KIND258259fn blocks(pairs: &BTreeSet<[u8; 4]>) -> Option<(usize, u32, u32)> {260    for s in 1..=2usize {261        let total = 1u32 << (s * s);262        for a in 0..total {263            for b in a + 1..total {264                let free = (0..16u32).all(|arrangement| {265                    let side = 2 * s;266                    let mut cells = vec![0u8; side * side];267                    for row in 0..side {268                        for col in 0..side {269                            let slot = (row / s) * 2 + col / s;270                            let block = if (arrangement >> slot) & 1 == 1 { b } else { a };271                            cells[row * side + col] =272                                ((block >> ((row % s) * s + col % s)) & 1) as u8;273                        }274                    }275                    Pic { side, cells }.pairs().is_subset(pairs)276                });277                if free {278                    return Some((s, a, b));279                }280            }281        }282    }283    None284}285286fn branching(states: usize, edges: &[(usize, usize)]) -> bool {287    let mut reach = vec![vec![false; states]; states];288    for &(from, to) in edges {289        reach[from][to] = true;290    }291    for mid in 0..states {292        for from in 0..states {293            for to in 0..states {294                if reach[from][mid] && reach[mid][to] {295                    reach[from][to] = true;296                }297            }298        }299    }300    (0..states).any(|root| {301        let class: Vec<usize> = (0..states)302            .filter(|&v| reach[root][v] && reach[v][root])303            .collect();304        let inner = edges305            .iter()306            .filter(|(f, t)| class.contains(f) && class.contains(t))307            .count();308        !class.is_empty() && inner > class.len()309    })310}311312fn lines(pairs: &BTreeSet<[u8; 4]>) -> Option<&'static str> {313    let has = |w: [u8; 4]| pairs.contains(&w);314    let mut two = Vec::new();315    let mut cols = Vec::new();316    for a in 0..2u8 {317        for b in 0..2u8 {318            if has([a, a, b, b]) {319                two.push((a as usize, b as usize));320            }321            if has([a, b, a, b]) {322                cols.push((a as usize, b as usize));323            }324        }325    }326    let mut diag = Vec::new();327    let mut anti = Vec::new();328    for p in 0..2u8 {329        for q in 0..2u8 {330            for s in 0..2u8 {331                let from = (p * 2 + q) as usize;332                let to = (q * 2 + s) as usize;333                if has([q, s, p, q]) {334                    diag.push((from, to));335                }336                if has([p, q, q, s]) {337                    anti.push((from, to));338                }339            }340        }341    }342    if branching(2, &two) {343        Some("rows")344    } else if branching(2, &cols) {345        Some("columns")346    } else if branching(4, &diag) {347        Some("diagonals")348    } else if branching(4, &anti) {349        Some("antidiagonals")350    } else {351        None352    }353}354355fn xor(pairs: &BTreeSet<[u8; 4]>) -> bool {356    [(0, 1, 2), (1, 0, 3), (2, 0, 3), (3, 1, 2)]357        .iter()358        .any(|&(corner, left, right)| {359            let rule: BTreeSet<[u8; 4]> = (0..16u8)360                .map(|bits| [bits & 1, (bits >> 1) & 1, (bits >> 2) & 1, (bits >> 3) & 1])361                .filter(|w| w[corner] == w[left] ^ w[right])362                .collect();363            &rule == pairs364        })365}366367fn shape(s: usize, block: u32) -> String {368    (0..s)369        .map(|row| {370            (0..s)371                .map(|col| ((block >> (row * s + col)) & 1).to_string())372                .collect::<String>()373        })374        .collect::<Vec<_>>()375        .join("/")376}377378fn aligned(design: &Design, m: usize) -> bool {379    let (pairs, _) = design.language();380    let unit = design.base.pow(m as u32);381    let render = design.render(m);382    pairs.iter().all(|window| {383        let mut pic = Pic::block(*window);384        for _ in 0..m {385            pic = design.substitute(&pic);386        }387        (0..=unit).all(|u| {388            (0..=unit).all(|v| {389                (u % unit == 0 && v % unit == 0)390                    || (0..unit).any(|r| (0..unit).any(|c| pic.at(u + r, v + c) != render.at(r, c)))391            })392        })393    })394}395396fn recognised(design: &Design) -> Option<usize> {397    (1..=3).find(|&m| aligned(design, m))398}399400fn kind(design: &Design) -> String {401    if design.empty() {402        return "sft empty".into();403    }404    if design.full() {405        return "sft full".into();406    }407    if design.degenerate() {408        return "sft boundary".into();409    }410    let pairs: BTreeSet<[u8; 4]> = design.language().0.into_iter().collect();411    if let Some((s, a, b)) = blocks(&pairs) {412        return format!("not-sft blocks {} {}", shape(s, a), shape(s, b));413    }414    if xor(&pairs) {415        return "not-sft xor".into();416    }417    if let Some(direction) = lines(&pairs) {418        return format!("not-sft lines {direction}");419    }420    "open".into()421}422423// CENSUS424425fn orbits(base: usize) -> Vec<(u32, usize)> {426    let mut sizes: BTreeMap<u32, usize> = BTreeMap::new();427    for code in 0..1u32 << (base * base) {428        *sizes429            .entry(Design::new(base, code).canonical())430            .or_insert(0) += 1;431    }432    sizes.into_iter().collect()433}434435fn row(values: &[usize]) -> String {436    values437        .iter()438        .map(|v| v.to_string())439        .collect::<Vec<_>>()440        .join(",")441}442443fn periodic(p: &[usize]) -> Option<usize> {444    p.iter()445        .enumerate()446        .map(|(i, &v)| (i + 1, v))447        .find(|&(k, v)| 2 * v <= k * k)448        .map(|(k, _)| k)449}450451// FORMULAS452453fn carpet(k: i64) -> i64 {454    let mut n = 1i64;455    while 3 * n + 1 < k {456        n *= 3;457    }458    if k <= 2 * n + 1 {459        6 * k * k + 12 * (n - 1) * k - 10 * n * n - 12 * n + 8460    } else {461        2 * k * k + (24 * n - 4) * k - 18 * n * n - 24 * n + 4462    }463}464465fn gasket(k: i64) -> i64 {466    4 * k * k - 6 * k + 4467}468469fn formula(base: usize, code: u32, p: &[usize]) -> Option<String> {470    let rule: fn(i64) -> i64 = match (base, code) {471        (3, 495) => carpet,472        (2, 7) => gasket,473        _ => return None,474    };475    let first = if base == 3 { 2 } else { 1 };476    let miss = (first..=p.len()).find(|&k| rule(k as i64) != p[k - 1] as i64);477    Some(match miss {478        Some(k) => format!("formula fails at {k}"),479        None => format!("formula holds for {first} <= k <= {}", p.len()),480    })481}482483fn quadratic(p: &[usize]) -> Option<String> {484    let v: Vec<i64> = p.iter().map(|&x| x as i64).collect();485    (1..=3usize).find_map(|first| {486        let i = first - 1;487        if v.len() < i + 4 {488            return None;489        }490        let d2 = v[i + 2] - 2 * v[i + 1] + v[i];491        if (i..v.len() - 2).any(|j| v[j + 2] - 2 * v[j + 1] + v[j] != d2) {492            return None;493        }494        let k = first as i64;495        let b2 = 2 * (v[i + 1] - v[i]) - d2 * (2 * k + 1);496        let c2 = 2 * v[i] - d2 * k * k - b2 * k;497        if d2 % 2 != 0 || b2 % 2 != 0 || c2 % 2 != 0 {498            return Some(format!(499                "quadratic from {first} ({d2} k^2 + {b2} k + {c2})/2"500            ));501        }502        Some(format!(503            "quadratic from {first} {} k^2 + {} k + {}",504            d2 / 2,505            b2 / 2,506            c2 / 2507        ))508    })509}510511// VERBS512513fn verb_count(base: usize, top: usize, only: Option<u32>) {514    let codes: Vec<(u32, usize)> = match only {515        Some(code) => vec![(code, 1)],516        None => orbits(base),517    };518    let mut distinct: BTreeSet<Vec<usize>> = BTreeSet::new();519    let mut tally: BTreeMap<&str, (usize, usize)> = BTreeMap::new();520    for (code, size) in codes {521        let design = Design::new(base, code);522        let p = count(&design, top);523        if only.is_none() {524            for g in 1..8 {525                let image = design.image(g);526                assert_eq!(527                    count(&image, top.min(12)),528                    p[..top.min(12)],529                    "code {code} image {g}"530                );531            }532        }533        let (pairs, level) = design.language();534        let (tag, shown) = if design.degenerate() {535            (format!("boundary edge {}", row(&p)), vec![1; p.len()])536        } else {537            ("plane".to_string(), p)538        };539        let flat = match periodic(&shown) {540            Some(k) => format!("periodic@{k}"),541            None => "above".into(),542        };543        println!(544            "base {base} code {code} orbit {size} fill {} pairs {} settle {level} {flat} p {} {tag}",545            design.filled().len(),546            pairs.len(),547            row(&shown)548        );549        let class = if shown.iter().all(|&v| v == 1) {550            "constant"551        } else if periodic(&shown).is_some() {552            "periodic"553        } else {554            "above"555        };556        let entry = tally.entry(class).or_insert((0, 0));557        entry.0 += 1;558        entry.1 += size;559        distinct.insert(shown.clone());560        if let Some(line) = quadratic(&shown) {561            println!("base {base} code {code} {line}");562        }563        if let Some(line) = formula(base, code, &shown) {564            println!("base {base} code {code} {line}");565        }566    }567    if only.is_none() {568        summary(base, &distinct, &tally);569    }570}571572fn summary(base: usize, distinct: &BTreeSet<Vec<usize>>, tally: &BTreeMap<&str, (usize, usize)>) {573    for (class, (orbits, codes)) in tally {574        println!("base {base} class {class} orbits {orbits} codes {codes}");575    }576    println!("base {base} distinct sequences {}", distinct.len());577}578579fn verb_pairs(base: usize, code: u32) {580    let (pairs, level) = Design::new(base, code).language();581    let shown: Vec<String> = pairs582        .iter()583        .map(|w| format!("{}{}/{}{}", w[0], w[1], w[2], w[3]))584        .collect();585    println!(586        "base {base} code {code} settle {level} pairs {} {}",587        pairs.len(),588        shown.join(" ")589    );590}591592fn verb_scan(base: usize, level: usize, top: usize, only: Option<u32>) {593    let carpet = crate_render(&Design::new(3, 495), level.min(6));594    let tile = create(Code::from(7u64), 3, 2, 2, level.min(6)).unwrap();595    assert_eq!(596        carpet.cells,597        tile.bytes().unwrap(),598        "code 7 side 3 is not base 3 code 495"599    );600    let mut worst = 0usize;601    let codes: Vec<(u32, usize)> = match only {602        Some(code) => vec![(code, 1)],603        None => orbits(base),604    };605    for (code, _) in codes {606        let design = Design::new(base, code);607        let pic = crate_render(&design, level);608        assert!(609            pic == design.render(level),610            "code {code} renders differently"611        );612        let seen = brute(&pic, top);613        let p = count(&design, seen.len());614        let gaps = seen.iter().zip(&p).filter(|(a, b)| a != b).count();615        worst = worst.max(gaps);616        println!(617            "base {base} code {code} level {level} scan {} gaps {gaps}",618            row(&seen)619        );620    }621    println!("base {base} level {level} worst {worst}");622}623624fn verb_kind(base: usize) {625    let mut tally: BTreeMap<String, usize> = BTreeMap::new();626    for (code, size) in orbits(base) {627        let design = Design::new(base, code);628        let verdict = match (629            design.empty() || design.full() || design.degenerate(),630            recognised(&design),631        ) {632            (true, _) => kind(&design),633            (false, Some(m)) => format!("{} recognised {m}", kind(&design)),634            (false, None) => format!("{} unrecognised", kind(&design)),635        };636        let head = verdict.split(' ').take(2).collect::<Vec<_>>().join(" ");637        *tally.entry(head).or_insert(0) += size;638        println!("base {base} code {code} orbit {size} {verdict}");639    }640    for (head, total) in tally {641        println!("base {base} codes {total} {head}");642    }643}644645fn main() {646    let args: Vec<String> = env::args().collect();647    let arg =648        |i: usize, default: usize| args.get(i).and_then(|s| s.parse().ok()).unwrap_or(default);649    let clock = Instant::now();650    match args.get(1).map(String::as_str) {651        Some("count") => verb_count(arg(2, 3), arg(3, 28), args.get(4).and_then(|s| s.parse().ok())),652        Some("scan") => verb_scan(arg(2, 3), arg(3, 6), arg(4, 12), args.get(5).and_then(|s| s.parse().ok())),653        Some("kind") => verb_kind(arg(2, 3)),654        Some("pairs") => verb_pairs(arg(2, 3), arg(3, 495) as u32),655        _ => eprintln!("verbs: count <base> <top> [code], scan <base> <level> <top> [code], kind <base>, pairs <base> <code>"),656    }657    eprintln!("seconds {:.1}", clock.elapsed().as_secs_f64());658}