arcs.rs

1use crate::core::error::{overflow_error, value_error, Result};2use crate::math::bang::factory::{code_to_corners, create};3use crate::math::bang::Code;4use serde::{Deserialize, Serialize};56// THE ARCS78/// One level of a flat design drawn in Truchet arcs: its side, its cells and the curves its arcs join into.9///10/// Cell `(x, y)` is column `x` and row `y`, row 0 at the bottom, stored at `y side + x`. Every cell carries two quarter arcs, each joining the midpoints of two adjacent edges: a filled cell takes the arcs around its lower-left and upper-right corners, a deleted cell the arcs around its lower-right and upper-left corners. The lower arc of a cell is the one ending on its bottom edge, the upper arc the one ending on its top edge. Arcs meeting at an edge midpoint join into curves, closed loops and open strands.11#[derive(Clone, Debug, PartialEq, Eq, Serialize, Deserialize)]12pub struct Arcs {13    /// The cells per axis.14    pub side: usize,15    /// One byte a cell: bit 0 set when the cell is filled, bit 1 when its lower arc lies on a loop, bit 2 when its upper arc does.16    pub cells: Vec<u8>,17    /// The closed loops.18    pub loops: u64,19    /// The open strands, `2 side` at every level: each of the `4 side` boundary midpoints ends one.20    pub strands: u64,21}2223struct Dsu {24    parent: Vec<usize>,25}2627impl Dsu {28    fn find(&mut self, mut i: usize) -> usize {29        while self.parent[i] != i {30            self.parent[i] = self.parent[self.parent[i]];31            i = self.parent[i];32        }33        i34    }3536    fn union(&mut self, a: usize, b: usize) {37        let (ra, rb) = (self.find(a), self.find(b));38        self.parent[ra] = rb;39    }40}4142/// Draws a `side x side` grid of filled and deleted cells in arcs and counts its curves by union-find over the edge midpoints, a curve being a loop when no midpoint of it lies on the boundary.43///44/// # Errors45///46/// Errors on side zero or a cell list that is not `side^2` long.47pub fn trace(side: usize, on: &[bool]) -> Result<Arcs> {48    if side == 0 || on.len() != side * side {49        return value_error("arcs need side^2 cells and a side of at least one.");50    }51    let rows = side * (side + 1);52    let across = |x: usize, y: usize| y * side + x;53    let upright = |x: usize, y: usize| rows + y * (side + 1) + x;54    let pairs = |x: usize, y: usize| {55        let (bottom, top) = (across(x, y), across(x, y + 1));56        let (left, right) = (upright(x, y), upright(x + 1, y));57        if on[y * side + x] {58            [(bottom, left), (top, right)]59        } else {60            [(bottom, right), (top, left)]61        }62    };63    let mut dsu = Dsu {64        parent: (0..2 * rows).collect(),65    };66    let mut ends = vec![0u8; 2 * rows];67    for y in 0..side {68        for x in 0..side {69            for (a, b) in pairs(x, y) {70                ends[a] += 1;71                ends[b] += 1;72                dsu.union(a, b);73            }74        }75    }76    let mut open = vec![false; 2 * rows];77    let mut root = vec![false; 2 * rows];78    for (point, &count) in ends.iter().enumerate() {79        let r = dsu.find(point);80        root[r] = true;81        open[r] |= count == 1;82    }83    let strands = (0..2 * rows).filter(|&r| root[r] && open[r]).count() as u64;84    let loops = (0..2 * rows).filter(|&r| root[r] && !open[r]).count() as u64;85    let mut cells = vec![0u8; side * side];86    for y in 0..side {87        for x in 0..side {88            let [(lower, _), (upper, _)] = pairs(x, y);89            let mut byte = u8::from(on[y * side + x]);90            if !open[dsu.find(lower)] {91                byte |= 2;92            }93            if !open[dsu.find(upper)] {94                byte |= 4;95            }96            cells[y * side + x] = byte;97        }98    }99    Ok(Arcs {100        side,101        cells,102        loops,103        strands,104    })105}106107/// Draws level `level` of `bang dim 2, base b, code c` in arcs: cell `(x, y)` of the `b x b` mask is filled when bit `b y + x` of the code is set, level `level` is its Kronecker power built by [`crate::math::bang::factory::create`], and level 0 is one filled cell.108///109/// # Errors110///111/// Errors on a code outside the digit space of the base, or a side past the machine word.112pub fn draw(code: Code, base: usize, level: usize) -> Result<Arcs> {113    code_to_corners(code, 2, base)?;114    let Some(side) = u32::try_from(level).ok().and_then(|n| base.checked_pow(n)) else {115        return overflow_error(format!("base {base} at level {level} is too wide to draw."));116    };117    if level == 0 {118        return trace(1, &[true]);119    }120    let tensor = create(code, base, 2, base, level)?;121    let on: Vec<bool> = (0..side * side).map(|f| tensor.at(f) == 1).collect();122    trace(side, &on)123}124125// THE LAWS126127/// A proved closed form of a design's loop count, read at one level.128#[derive(Clone, Debug, PartialEq, Eq, Serialize, Deserialize)]129pub struct Law {130    /// The closed form in the level `n`, one line of text.131    pub formula: String,132    /// The loops the law gives at the level asked.133    pub loops: u64,134}135136/// Returns the proved loop law of `bang dim 2, base b, code c` at the level, or none where no law is proved: the carpet, base 3 code 495, has `(8^n - 1)/7 - 3^n + n + 1` loops; at base 2 codes 7 and 14 have `3^(n-1) - 2^n + 1`, codes 11 and 13 have `3^(n-1) - 2^(n-1)`, both from level 1 on, code 9 has `2^n - 1`, and the other eleven codes never loop.137///138/// # Errors139///140/// Errors on a code outside the digit space of the base, or a count past 64 bits.141pub fn law(code: Code, base: usize, level: usize) -> Result<Option<Law>> {142    code_to_corners(code, 2, base)?;143    let Ok(n) = u32::try_from(level) else {144        return overflow_error(format!("level {level} is past any loop law."));145    };146    let power = |b: i128, e: u32| b.checked_pow(e);147    let value = |terms: &[Option<i128>]| -> Option<i128> {148        terms149            .iter()150            .try_fold(0i128, |sum, term| sum.checked_add((*term)?))151    };152    let (formula, loops) = match (base, code.get()) {153        (3, 495) => (154            "(8^n - 1)/7 - 3^n + n + 1",155            power(8, n).map(|p| (p - 1) / 7).and_then(|head| {156                value(&[Some(head), power(3, n).map(|p| -p), Some(i128::from(n) + 1)])157            }),158        ),159        (2, 7 | 14) if n == 0 => ("3^(n-1) - 2^n + 1, n >= 1", Some(0)),160        (2, 7 | 14) => (161            "3^(n-1) - 2^n + 1, n >= 1",162            value(&[power(3, n - 1), power(2, n).map(|p| -p), Some(1)]),163        ),164        (2, 11 | 13) if n == 0 => ("3^(n-1) - 2^(n-1), n >= 1", Some(0)),165        (2, 11 | 13) => (166            "3^(n-1) - 2^(n-1), n >= 1",167            value(&[power(3, n - 1), power(2, n - 1).map(|p| -p)]),168        ),169        (2, 9) => ("2^n - 1", power(2, n).map(|p| p - 1)),170        (2, _) => ("0", Some(0)),171        _ => return Ok(None),172    };173    match loops.and_then(|count| u64::try_from(count).ok()) {174        Some(loops) => Ok(Some(Law {175            formula: formula.to_string(),176            loops,177        })),178        None => overflow_error(format!("the loop law passes 64 bits at level {level}.")),179    }180}181182#[cfg(test)]183mod tests {184    use super::*;185186    fn loops(code: u128, base: usize, levels: std::ops::RangeInclusive<usize>) -> Vec<u64> {187        levels188            .map(|n| draw(Code::from(code), base, n).unwrap().loops)189            .collect()190    }191192    #[test]193    fn the_carpet_and_code_seven_close_their_loops() {194        assert_eq!(loops(495, 3, 1..=4), [0, 3, 50, 509]);195        assert_eq!(loops(7, 2, 1..=4), [0, 0, 2, 12]);196    }197198    #[test]199    fn every_proved_law_meets_the_count_and_strands_are_twice_the_side() {200        let mut cases: Vec<(u128, usize, usize)> = (0..16).map(|code| (code, 2, 7)).collect();201        cases.push((495, 3, 5));202        for (code, base, top) in cases {203            for n in 0..=top {204                let arcs = draw(Code::from(code), base, n).unwrap();205                let law = law(Code::from(code), base, n).unwrap().unwrap();206                assert_eq!(law.loops, arcs.loops, "code {code} base {base} level {n}");207                assert_eq!(arcs.strands, 2 * arcs.side as u64);208            }209        }210        assert_eq!(law(Code::from(511u128), 3, 2).unwrap(), None);211        assert!(law(Code::from(16u128), 2, 2).is_err());212    }213214    #[test]215    fn a_cell_byte_marks_the_filled_cell_and_its_arcs_on_loops() {216        let arcs = draw(Code::from(9u128), 2, 1).unwrap();217        assert_eq!((arcs.side, arcs.loops, arcs.strands), (2, 1, 4));218        assert_eq!(arcs.cells, [5, 4, 2, 3]);219        assert_eq!(draw(Code::from(1u128), 2, 0).unwrap().cells, [1]);220        assert!(trace(2, &[true; 3]).is_err());221    }222}