terms.rs

1use super::{Axis, Closed, Key, Measure};2use mrlycore::errors::{value_error, Result};3use mrlycore::tensor::Tensor;4use mrlymath::bang::{code_to_corners, factory};5use mrlymath::formulas;6use mrlymath::{six, three, two};78fn binomial(n: usize, k: usize) -> i128 {9    (0..k).fold(1i128, |acc, i| acc * (n - i) as i128 / (i as i128 + 1))10}1112fn grid(number: usize, dimension: usize, level: u32) -> Option<u128> {13    (number as u128).checked_pow((dimension as u32).checked_mul(level)?)14}1516fn tile(key: &Key, number: usize) -> Result<Tensor> {17    factory::create(key.code, number, key.dimension, key.base, 1)18}1920fn complex(key: &Key, number: usize, level: u32) -> Result<i128> {21    let Key {22        code,23        dimension,24        base,25        measure,26        ..27    } = *key;28    let value = match dimension {29        2 => {30            let tally = two::census(&two::create(code, number, level as usize, 0, base)?)?;31            match measure {32                Measure::Vertices => tally.vertices as i128,33                Measure::Edges => tally.edges as i128,34                Measure::Euler => tally.euler as i128,35                _ => return value_error("the plane carries no faces."),36            }37        }38        _ => {39            let tally = three::census(&three::create(code, number, level as usize, base)?)?;40            match measure {41                Measure::Vertices => tally.vertices as i128,42                Measure::Edges => tally.edges as i128,43                Measure::Faces => tally.faces as i128,44                _ => tally.euler as i128,45            }46        }47    };48    Ok(value)49}5051fn term(key: &Key, number: usize, level: u32, cells: u128) -> Result<Option<i128>> {52    let Key {53        code,54        dimension,55        base,56        measure,57        ..58    } = *key;59    let fill = || -> Result<Option<u128>> {60        Ok(formulas::fill(code, number, dimension, 1, base)?.checked_pow(level))61    };62    let within = |cost: Option<u128>| cost.is_some_and(|cost| cost <= cells);63    let value = match measure {64        Measure::Fills => fill()?.and_then(|fill| i128::try_from(fill).ok()),65        Measure::Voids => grid(number, dimension, level)66            .zip(fill()?)67            .map(|(grid, fill)| (grid - fill) as i128),68        Measure::Surface => {69            let corners = code_to_corners(code, dimension, base)?;70            formulas::Exposure::from_corners(&corners, number, dimension, base)71                .at(level)72                .map(|faces| faces as i128)73        }74        Measure::Peak | Measure::Heights => {75            let span = (number as u128)76                .checked_pow(level)77                .map(|side| dimension as u128 * (side - 1) + 1);78            if !within(span) {79                return Ok(None);80            }81            let counts = formulas::profile_of_tile(&tile(key, number)?, level)?;82            Some(if measure == Measure::Peak {83                counts.iter().max().copied().unwrap_or(0) as i12884            } else {85                counts.iter().filter(|&&count| count > 0).count() as i12886            })87        }88        Measure::Vertices | Measure::Edges | Measure::Faces | Measure::Euler => {89            if !within(grid(number, dimension, level)) {90                return Ok(None);91            }92            Some(complex(key, number, level)?)93        }94        Measure::Triangles => {95            let cost = (number as u128)96                .checked_pow(2 * level)97                .and_then(|side| side.checked_mul(16));98            if !within(cost) {99                return Ok(None);100            }101            Some(formulas::cut_fills(code, number, level)? as i128)102        }103        Measure::Holes | Measure::Pieces => {104            if !within(grid(number, dimension, level)) {105                return Ok(None);106            }107            let slice = six::cut(&three::create(code, number, level as usize, base)?)?;108            Some(if measure == Measure::Holes {109                six::holes(&slice)? as i128110            } else {111                six::components(&slice)? as i128112            })113        }114    };115    Ok(value)116}117118/// Reads the first terms of a design sequence within a cell budget, and whether the budget or a u128 cut them short.119///120/// ```121/// use mrlylab::ledger::{terms, Axis, Key, Measure, BUDGET};122/// let carpet = Key::new(7, 2, 2, Measure::Fills, Axis::Level);123/// assert_eq!(terms(&carpet, 3, BUDGET).unwrap(), (vec![8, 64, 512], false));124/// let sponge = Key::new(23, 3, 2, Measure::Surface, Axis::Level);125/// assert_eq!(terms(&sponge, 3, BUDGET).unwrap(), (vec![72, 1056, 18048], false));126/// ```127pub fn terms(key: &Key, count: usize, cells: u128) -> Result<(Vec<i128>, bool)> {128    code_to_corners(key.code, key.dimension, key.base)?;129    if !key.measure.applies(key.dimension, key.base) {130        return value_error(format!(131            "{} does not read dimension {} base {}.",132            key.measure.slug(),133            key.dimension,134            key.base135        ));136    }137    let mut out = Vec::with_capacity(count);138    for index in 0..count {139        let (number, level) = key.axis.place(index, key.number());140        match term(key, number, level, cells)? {141            Some(value) => out.push(value),142            None => return Ok((out, true)),143        }144    }145    Ok((out, false))146}147148/// Expands the odd-side fill at side `2k - 1`, `sum over the corners of k^(zeros) (k - 1)^(ones)`, into coefficients by rising power of `k`.149///150/// ```151/// let carpet = mrlymath::bang::code_to_corners(7, 2, 2).unwrap();152/// assert_eq!(mrlylab::ledger::fill_polynomial(&carpet, 2), [0, -2, 3]);153/// ```154pub fn fill_polynomial(corners: &[Vec<u8>], dimension: usize) -> Vec<i128> {155    let mut out = vec![0i128; dimension + 1];156    for corner in corners {157        let ones = corner.iter().filter(|&&r| r != 0).count();158        for j in 0..=ones {159            let sign = if (ones - j).is_multiple_of(2) { 1 } else { -1 };160            out[dimension - ones + j] += sign * binomial(ones, j);161        }162    }163    out164}165166fn odd_power(dimension: usize) -> Vec<i128> {167    (0..=dimension)168        .map(|j| {169            let sign = if (dimension - j).is_multiple_of(2) {170                1171            } else {172                -1173            };174            sign * binomial(dimension, j) * (1i128 << j)175        })176        .collect()177}178179/// Returns the closed form of a design sequence when the ledger knows one.180///181/// Level fills are a power and level voids a difference of powers; base-2 side fills and voids182/// are polynomials in `k` at side `2k - 1`; the level surface obeys the exposure recurrence.183pub fn closed(key: &Key) -> Result<Option<Closed>> {184    let Key {185        code,186        dimension,187        base,188        measure,189        axis,190    } = *key;191    let corners = code_to_corners(code, dimension, base)?;192    let fill = || formulas::fill(code, key.number(), dimension, 1, base);193    let form = match (measure, axis) {194        (Measure::Fills, Axis::Level) => Closed::Power(fill()?),195        (Measure::Voids, Axis::Level) => {196            Closed::Difference((key.number() as u128).pow(dimension as u32), fill()?)197        }198        (Measure::Fills, Axis::Side) if base == 2 => {199            Closed::Polynomial(fill_polynomial(&corners, dimension))200        }201        (Measure::Voids, Axis::Side) if base == 2 => Closed::Polynomial(202            odd_power(dimension)203                .iter()204                .zip(fill_polynomial(&corners, dimension))205                .map(|(all, filled)| all - filled)206                .collect(),207        ),208        (Measure::Surface, Axis::Level) => Closed::Recurrence(209            formulas::Exposure::from_corners(&corners, key.number(), dimension, base).recurrence(),210        ),211        _ => return Ok(None),212    };213    Ok(Some(form))214}215216#[cfg(test)]217mod tests {218    use super::super::BUDGET;219    use super::*;220221    fn read(code: u128, dimension: usize, measure: Measure, axis: Axis, count: usize) -> Vec<i128> {222        terms(&Key::new(code, dimension, 2, measure, axis), count, BUDGET)223            .unwrap()224            .0225    }226227    #[test]228    fn the_closed_measures_read_the_classics() {229        assert_eq!(read(7, 2, Measure::Voids, Axis::Level, 3), [1, 17, 217]);230        assert_eq!(231            read(7, 2, Measure::Surface, Axis::Level, 4),232            [16, 80, 496, 3536]233        );234        assert_eq!(235            read(23, 3, Measure::Fills, Axis::Side, 4),236            [20, 81, 208, 425]237        );238        assert_eq!(239            read(23, 3, Measure::Voids, Axis::Side, 4),240            [7, 44, 135, 304]241        );242        assert_eq!(read(1, 2, Measure::Fills, Axis::Side, 3), [4, 9, 16]);243        assert_eq!(read(9, 2, Measure::Fills, Axis::Side, 3), [5, 13, 25]);244        assert_eq!(read(11, 2, Measure::Fills, Axis::Side, 3), [7, 19, 37]);245        assert_eq!(read(15, 2, Measure::Fills, Axis::Side, 3), [9, 25, 49]);246        assert_eq!(read(129, 3, Measure::Fills, Axis::Side, 3), [9, 35, 91]);247        assert_eq!(read(255, 3, Measure::Fills, Axis::Side, 3), [27, 125, 343]);248    }249250    #[test]251    fn the_grid_measures_agree_with_the_censuses() {252        assert_eq!(read(7, 2, Measure::Euler, Axis::Level, 3), [0, -8, -72]);253        assert_eq!(read(23, 3, Measure::Euler, Axis::Level, 2), [-4, -80]);254        assert_eq!(read(23, 3, Measure::Faces, Axis::Level, 1), [96]);255        assert_eq!(read(23, 3, Measure::Vertices, Axis::Level, 1), [64]);256        assert_eq!(read(23, 3, Measure::Edges, Axis::Level, 1), [144]);257        assert_eq!(read(7, 2, Measure::Vertices, Axis::Side, 2), [16, 36]);258        assert_eq!(read(23, 3, Measure::Triangles, Axis::Level, 2), [42, 306]);259        assert_eq!(read(23, 3, Measure::Pieces, Axis::Side, 2), [1, 7]);260        assert_eq!(read(255, 3, Measure::Holes, Axis::Level, 2), [0, 0]);261        assert_eq!(read(23, 3, Measure::Peak, Axis::Level, 2), [6, 42]);262        assert_eq!(read(23, 3, Measure::Heights, Axis::Level, 2), [7, 25]);263    }264265    #[test]266    fn the_budget_caps_honestly() {267        let key = Key::new(23, 3, 2, Measure::Euler, Axis::Level);268        assert_eq!(terms(&key, 8, 1000).unwrap(), (vec![-4, -80], true));269        assert_eq!(terms(&key, 8, 26).unwrap(), (vec![], true));270        let deep = Key::new(23, 3, 2, Measure::Fills, Axis::Level);271        let (fills, capped) = terms(&deep, 40, BUDGET).unwrap();272        assert!(capped && fills.len() == 29);273        let base3 = Key::new(100, 2, 3, Measure::Surface, Axis::Side);274        assert_eq!(terms(&base3, 2, BUDGET).unwrap().0.len(), 2);275        assert!(terms(&Key::new(7, 2, 2, Measure::Faces, Axis::Level), 1, BUDGET).is_err());276        assert!(terms(&Key::new(16, 2, 2, Measure::Fills, Axis::Level), 1, BUDGET).is_err());277    }278279    #[test]280    fn the_closed_forms_match_the_terms() {281        for code in 0..16u128 {282            for measure in [Measure::Fills, Measure::Voids] {283                let key = Key::new(code, 2, 2, measure, Axis::Side);284                let Some(Closed::Polynomial(poly)) = closed(&key).unwrap() else {285                    panic!("no polynomial");286                };287                let (terms, _) = terms(&key, 5, BUDGET).unwrap();288                for (index, &term) in terms.iter().enumerate() {289                    let k = index as i128 + 2;290                    let value: i128 = poly291                        .iter()292                        .enumerate()293                        .map(|(p, &c)| c * k.pow(p as u32))294                        .sum();295                    assert_eq!(value, term, "code={code} k={k}");296                }297            }298        }299        assert_eq!(300            closed(&Key::new(23, 3, 2, Measure::Fills, Axis::Level)).unwrap(),301            Some(Closed::Power(20))302        );303        assert_eq!(304            closed(&Key::new(7, 2, 2, Measure::Voids, Axis::Level)).unwrap(),305            Some(Closed::Difference(9, 8))306        );307        assert_eq!(308            closed(&Key::new(7, 2, 3, Measure::Fills, Axis::Side)).unwrap(),309            None310        );311        assert_eq!(312            closed(&Key::new(7, 2, 2, Measure::Euler, Axis::Level)).unwrap(),313            None314        );315    }316}