morse.rs

1use mrlycore::errors::{value_error, Result};23// THE WORD45/// Returns the Thue-Morse letter at the place, the parity of its binary digit sum.6///7/// ```8/// let word: Vec<u8> = (0..8).map(mrlynum::morse::letter).collect();9/// assert_eq!(word, vec![0, 1, 1, 0, 1, 0, 0, 1]);10/// ```11pub fn letter(place: u64) -> u8 {12    (place.count_ones() % 2) as u813}1415/// Builds the first letters of the Thue-Morse word by the digit rule.16pub fn digits(length: usize) -> Vec<u8> {17    (0..length as u64).map(letter).collect()18}1920/// Builds the first letters of the Thue-Morse word by the substitution `0 -> 01`, `1 -> 10`.21///22/// The seed is the single letter 0, and the rounds double the length until it covers the ask.23///24/// ```25/// assert_eq!(mrlynum::morse::substitution(8), mrlynum::morse::digits(8));26/// ```27pub fn substitution(length: usize) -> Vec<u8> {28    let mut word = vec![0u8];29    while word.len() < length {30        word = word.iter().flat_map(|&bit| [bit, 1 - bit]).collect();31    }32    word.truncate(length);33    word34}3536/// Returns the substitution stage after the rounds, a word of length two to the rounds.37pub fn stage(rounds: usize) -> Vec<u8> {38    let mut word = vec![0u8];39    for _ in 0..rounds {40        word = word.iter().flat_map(|&bit| [bit, 1 - bit]).collect();41    }42    word43}4445// RUNS4647/// Returns the lengths of the maximal blocks of one repeated letter, in order.48///49/// ```50/// assert_eq!(mrlynum::morse::runs(&[0, 1, 1, 0]), vec![1, 2, 1]);51/// ```52pub fn runs(word: &[u8]) -> Vec<usize> {53    let mut out: Vec<usize> = Vec::new();54    for (place, &bit) in word.iter().enumerate() {55        if place > 0 && bit == word[place - 1] {56            *out.last_mut().unwrap() += 1;57        } else {58            out.push(1);59        }60    }61    out62}6364/// Returns the run-boundary word, one wherever a letter differs from the next.65pub fn boundary(word: &[u8]) -> Vec<u8> {66    word.windows(2).map(|pair| pair[0] ^ pair[1]).collect()67}6869/// Builds the period-doubling word by the substitution `1 -> 10`, `0 -> 11`, from the seed 1.70///71/// ```72/// let word = mrlynum::morse::doubling(8);73/// assert_eq!(word, vec![1, 0, 1, 1, 1, 0, 1, 0]);74/// assert_eq!(word, mrlynum::morse::boundary(&mrlynum::morse::digits(9)));75/// ```76pub fn doubling(length: usize) -> Vec<u8> {77    let mut word = vec![1u8];78    while word.len() < length {79        word = word80            .iter()81            .flat_map(|&bit| if bit == 1 { [1, 0] } else { [1, 1] })82            .collect();83    }84    word.truncate(length);85    word86}8788// LIFTS8990/// The four ways the word lifts from a line to the plane, one sign at every site.91#[derive(Clone, Copy, Debug, PartialEq, Eq)]92pub enum Lift {93    /// `t(i) xor t(j)`, the sign grid of the two-by-two tile `[[+1, -1], [-1, +1]]`.94    Parity,95    /// `t(i and j)`, the Walsh-Hadamard pattern.96    And,97    /// `t(i xor j)`, which the parity of a xor forces equal to the first lift.98    Xor,99    /// `t(i + j)`, the one that carries and so does not fold.100    Sum,101}102103/// Lists the lifts in the order the gallery draws them.104pub const LIFTS: [Lift; 4] = [Lift::Parity, Lift::And, Lift::Xor, Lift::Sum];105106impl Lift {107    /// Parses a lift's display name, or errs on an unknown name.108    pub fn parse(name: &str) -> Result<Lift> {109        match name {110            "parity" => Ok(Lift::Parity),111            "and" => Ok(Lift::And),112            "xor" => Ok(Lift::Xor),113            "sum" => Ok(Lift::Sum),114            other => value_error(format!("unknown lift {other:?}.")),115        }116    }117    /// Returns the lift's display name.118    pub fn name(self) -> &'static str {119        match self {120            Lift::Parity => "parity",121            Lift::And => "and",122            Lift::Xor => "xor",123            Lift::Sum => "sum",124        }125    }126    /// Returns the lift's formula, written the way the page prints it.127    pub fn formula(self) -> &'static str {128        match self {129            Lift::Parity => "t(i) xor t(j)",130            Lift::And => "t(i and j)",131            Lift::Xor => "t(i xor j)",132            Lift::Sum => "t(i + j)",133        }134    }135    /// Returns the sign at a site, zero for plus one and one for minus one.136    pub fn at(self, i: u64, j: u64) -> u8 {137        match self {138            Lift::Parity => letter(i) ^ letter(j),139            Lift::And => letter(i & j),140            Lift::Xor => letter(i ^ j),141            Lift::Sum => letter(i + j),142        }143    }144}145146/// Builds a lift as a row-major sign grid of the side, zero for plus one and one for minus one.147pub fn lift(kind: Lift, side: usize) -> Vec<u8> {148    let mut out = vec![0u8; side * side];149    for i in 0..side {150        for j in 0..side {151            out[i * side + j] = kind.at(i as u64, j as u64);152        }153    }154    out155}156157// KRONECKER158159/// Folds a tile of the side into its Kronecker power at the level, one bit per site.160///161/// The bits ride the exclusive or, so the power is the digit rule of the tile: a site takes the162/// exclusive or of the tile's bits at its base-side digit pairs.163pub fn power(tile: &[u8], number: usize, level: usize) -> Result<Vec<u8>> {164    if tile.len() != number * number {165        return value_error(format!(166            "a side-{number} tile wants {} bits.",167            number * number168        ));169    }170    let side = match number.checked_pow(level as u32) {171        Some(side) => side,172        None => return value_error("that level passes what a machine holds."),173    };174    let mut out = vec![0u8; side * side];175    for r in 0..side {176        for c in 0..side {177            let (mut bit, mut row, mut col) = (0u8, r, c);178            for _ in 0..level {179                bit ^= tile[(row % number) * number + col % number];180                row /= number;181                col /= number;182            }183            out[r * side + c] = bit;184        }185    }186    Ok(out)187}188189/// The verdict on whether a grid is the Kronecker power of its own corner tile.190#[derive(Clone, Debug)]191pub struct Fold {192    /// The corner tile the test folds, row major.193    pub tile: Vec<u8>,194    /// The side of the tile.195    pub number: usize,196    /// The count of tile factors the side asks for.197    pub level: usize,198    /// Whether the grid is that tile's Kronecker power.199    pub folds: bool,200    /// The count of sites where the grid and the power differ.201    pub faults: usize,202    /// The first differing site in row-major order, when there is one.203    pub first: Option<(usize, usize)>,204}205206/// Tests a grid against the Kronecker power of its own corner tile.207///208/// The corner tile is the only candidate worth testing. If the grid is `T` folded `L` times then209/// its corner block is `T` with every bit flipped by `(L - 1) t00`, and folding that block `L`210/// times flips the grid by `L (L - 1) t00`, which is even. So a grid folds if and only if it211/// folds from its corner block, and no search over tiles is needed.212pub fn fold(grid: &[u8], side: usize, number: usize) -> Result<Fold> {213    if grid.len() != side * side {214        return value_error(format!("a side-{side} grid wants {} bits.", side * side));215    }216    if number < 2 {217        return value_error("a tile side is two or more.");218    }219    let mut level = 0usize;220    let mut reach = 1usize;221    while reach < side {222        reach *= number;223        level += 1;224    }225    if reach != side {226        return value_error(format!("side {side} is no power of {number}."));227    }228    let mut tile = vec![0u8; number * number];229    for r in 0..number {230        for c in 0..number {231            tile[r * number + c] = grid[r * side + c];232        }233    }234    let folded = power(&tile, number, level)?;235    let mut faults = 0usize;236    let mut first = None;237    for (at, (&here, &there)) in grid.iter().zip(&folded).enumerate() {238        if here != there {239            faults += 1;240            first.get_or_insert((at / side, at % side));241        }242    }243    Ok(Fold {244        tile,245        number,246        level,247        folds: faults == 0,248        faults,249        first,250    })251}252253// THE FILTER254255/// Blows a grid up by the scale, every site becoming a scale-by-scale block.256pub fn upsample(grid: &[u8], side: usize, scale: usize) -> Vec<u8> {257    let wide = side * scale;258    let mut out = vec![0u8; wide * wide];259    for r in 0..wide {260        for c in 0..wide {261            out[r * wide + c] = grid[(r / scale) * side + c / scale];262        }263    }264    out265}266267/// Repeats a tile until it fills a grid of the side.268pub fn repeat(tile: &[u8], number: usize, side: usize) -> Vec<u8> {269    let mut out = vec![0u8; side * side];270    for r in 0..side {271        for c in 0..side {272            out[r * side + c] = tile[(r % number) * number + c % number];273        }274    }275    out276}277278/// Exclusive-ors two grids of the same length, site by site.279pub fn difference(a: &[u8], b: &[u8]) -> Vec<u8> {280    a.iter().zip(b).map(|(&x, &y)| x ^ y).collect()281}282283/// Counts the sites where two grids of the same length differ.284pub fn faults(a: &[u8], b: &[u8]) -> usize {285    a.iter().zip(b).filter(|(x, y)| x != y).count()286}287288#[cfg(test)]289mod tests {290    use super::*;291292    #[test]293    fn the_two_constructions_of_the_word_agree() {294        assert_eq!(digits(4096), substitution(4096));295        assert_eq!(stage(6), digits(64));296        assert_eq!(297            digits(16),298            vec![0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0]299        );300    }301302    #[test]303    fn the_word_is_cube_free_at_the_letter() {304        let word = digits(1 << 16);305        assert_eq!(runs(&word).into_iter().max(), Some(2));306        let counts = runs(&word);307        assert_eq!(counts.iter().filter(|&&run| run == 1).count(), 21846);308        assert_eq!(counts.iter().filter(|&&run| run == 2).count(), 21845);309        assert_eq!(word.iter().map(|&bit| bit as usize).sum::<usize>(), 1 << 15);310    }311312    #[test]313    fn the_boundary_word_is_the_period_doubling_word() {314        let word = digits(65537);315        assert_eq!(boundary(&word), doubling(65536));316    }317318    #[test]319    fn three_of_the_four_lifts_fold_and_the_sum_does_not() {320        let side = 64;321        for kind in [Lift::Parity, Lift::And, Lift::Xor] {322            let read = fold(&lift(kind, side), side, 2).unwrap();323            assert!(read.folds, "{}", kind.formula());324            assert_eq!(read.level, 6);325        }326        assert_eq!(327            fold(&lift(Lift::Parity, side), side, 2).unwrap().tile,328            vec![0, 1, 1, 0]329        );330        assert_eq!(331            fold(&lift(Lift::And, side), side, 2).unwrap().tile,332            vec![0, 0, 0, 1]333        );334        let sum = fold(&lift(Lift::Sum, side), side, 2).unwrap();335        assert!(!sum.folds);336        assert_eq!(sum.first, Some((1, 3)));337        assert_eq!(sum.faults, 1376);338    }339340    #[test]341    fn the_xor_lift_is_the_parity_lift() {342        for side in [2, 4, 8, 16, 32] {343            assert_eq!(lift(Lift::Xor, side), lift(Lift::Parity, side));344        }345        assert_eq!(faults(&lift(Lift::Sum, 32), &lift(Lift::Parity, 32)), 448);346    }347348    #[test]349    fn the_sum_lift_is_flat_on_every_antidiagonal() {350        let side = 32;351        let grid = lift(Lift::Sum, side);352        for r in 0..side {353            for c in 0..side {354                assert_eq!(grid[r * side + c], grid[c * side + r]);355                if r > 0 && c + 1 < side {356                    assert_eq!(grid[r * side + c], grid[(r - 1) * side + c + 1]);357                }358            }359        }360    }361362    #[test]363    fn the_difference_of_two_sign_levels_is_the_tile_repeated() {364        let tile = vec![0, 1, 1, 0];365        for level in 1..6 {366            let coarse = power(&tile, 2, level).unwrap();367            let fine = power(&tile, 2, level + 1).unwrap();368            let side = 1 << level;369            let grown = upsample(&coarse, side, 2);370            assert_eq!(difference(&grown, &fine), repeat(&tile, 2, side * 2));371        }372    }373}