terms.rs

1use super::{Axis, Closed, Key, Measure};2use mrlyrs::core::error::{value_error, Result};3use mrlyrs::core::tensor::Tensor;4use mrlyrs::math::bang::{code_to_corners, factory, Code};5use mrlyrs::math::counts;6use mrlyrs::math::{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(Code::from(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(31                Code::from(code),32                number,33                level as usize,34                0,35                base,36            )?)?;37            match measure {38                Measure::Vertices => tally.vertices as i128,39                Measure::Edges => tally.edges as i128,40                Measure::Euler => tally.euler as i128,41                _ => return value_error("the plane carries no faces."),42            }43        }44        _ => {45            let tally = three::census(&three::create(46                Code::from(code),47                number,48                level as usize,49                base,50            )?)?;51            match measure {52                Measure::Vertices => tally.vertices as i128,53                Measure::Edges => tally.edges as i128,54                Measure::Faces => tally.faces as i128,55                _ => tally.euler as i128,56            }57        }58    };59    Ok(value)60}6162fn term(key: &Key, number: usize, level: u32, cells: u128) -> Result<Option<i128>> {63    let Key {64        code,65        dimension,66        base,67        measure,68        ..69    } = *key;70    let fill = || -> Result<Option<u128>> {71        Ok(counts::fill(Code::from(code), number, dimension, 1, base)?.checked_pow(level))72    };73    let within = |cost: Option<u128>| cost.is_some_and(|cost| cost <= cells);74    let value = match measure {75        Measure::Fills => fill()?.and_then(|fill| i128::try_from(fill).ok()),76        Measure::Voids => grid(number, dimension, level)77            .zip(fill()?)78            .map(|(grid, fill)| (grid - fill) as i128),79        Measure::Surface => {80            let corners = code_to_corners(Code::from(code), dimension, base)?;81            counts::Exposure::from_corners(&corners, number, dimension, base)82                .at(level)83                .map(|faces| faces as i128)84        }85        Measure::Peak | Measure::Heights => {86            let span = (number as u128)87                .checked_pow(level)88                .map(|side| dimension as u128 * (side - 1) + 1);89            if !within(span) {90                return Ok(None);91            }92            let counts = counts::profile_of_tile(&tile(key, number)?, level)?;93            Some(if measure == Measure::Peak {94                counts.iter().max().copied().unwrap_or(0) as i12895            } else {96                counts.iter().filter(|&&count| count > 0).count() as i12897            })98        }99        Measure::Vertices | Measure::Edges | Measure::Faces | Measure::Euler => {100            if !within(grid(number, dimension, level)) {101                return Ok(None);102            }103            Some(complex(key, number, level)?)104        }105        Measure::Triangles => {106            let cost = (number as u128)107                .checked_pow(2 * level)108                .and_then(|side| side.checked_mul(16));109            if !within(cost) {110                return Ok(None);111            }112            Some(counts::cut_fills(Code::from(code), number, level)? as i128)113        }114        Measure::Holes | Measure::Pieces => {115            if !within(grid(number, dimension, level)) {116                return Ok(None);117            }118            let slice = six::cut(&three::create(119                Code::from(code),120                number,121                level as usize,122                base,123            )?)?;124            Some(if measure == Measure::Holes {125                six::holes(&slice)? as i128126            } else {127                six::components(&slice)? as i128128            })129        }130    };131    Ok(value)132}133134/// Reads the first terms of a design sequence within a cell budget, and whether the budget or a u128 cut them short.135///136/// ```137/// use ledger::{terms, Axis, Key, Measure, BUDGET};138/// let carpet = Key::new(7, 2, 2, Measure::Fills, Axis::Level);139/// assert_eq!(terms(&carpet, 3, BUDGET).unwrap(), (vec![8, 64, 512], false));140/// let sponge = Key::new(23, 3, 2, Measure::Surface, Axis::Level);141/// assert_eq!(terms(&sponge, 3, BUDGET).unwrap(), (vec![72, 1056, 18048], false));142/// ```143pub fn terms(key: &Key, count: usize, cells: u128) -> Result<(Vec<i128>, bool)> {144    code_to_corners(Code::from(key.code), key.dimension, key.base)?;145    if !key.measure.applies(key.dimension, key.base) {146        return value_error(format!(147            "{} does not read dimension {} base {}.",148            key.measure.slug(),149            key.dimension,150            key.base151        ));152    }153    let mut out = Vec::with_capacity(count);154    for index in 0..count {155        let (number, level) = key.axis.place(index, key.number());156        match term(key, number, level, cells)? {157            Some(value) => out.push(value),158            None => return Ok((out, true)),159        }160    }161    Ok((out, false))162}163164/// 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`.165///166/// ```167/// let carpet = mrlyrs::math::bang::code_to_corners(mrlyrs::math::bang::Code::from(7u64), 2, 2).unwrap();168/// assert_eq!(ledger::fill_polynomial(&carpet, 2), [0, -2, 3]);169/// ```170pub fn fill_polynomial(corners: &[Vec<u8>], dimension: usize) -> Vec<i128> {171    let mut out = vec![0i128; dimension + 1];172    for corner in corners {173        let ones = corner.iter().filter(|&&r| r != 0).count();174        for j in 0..=ones {175            let sign = if (ones - j).is_multiple_of(2) { 1 } else { -1 };176            out[dimension - ones + j] += sign * binomial(ones, j);177        }178    }179    out180}181182fn odd_power(dimension: usize) -> Vec<i128> {183    (0..=dimension)184        .map(|j| {185            let sign = if (dimension - j).is_multiple_of(2) {186                1187            } else {188                -1189            };190            sign * binomial(dimension, j) * (1i128 << j)191        })192        .collect()193}194195/// Returns the closed form of a design sequence when the ledger knows one.196///197/// Level fills are a power and level voids a difference of powers; base-2 side fills and voids198/// are polynomials in `k` at side `2k - 1`; the level surface obeys the exposure recurrence.199pub fn closed(key: &Key) -> Result<Option<Closed>> {200    let Key {201        code,202        dimension,203        base,204        measure,205        axis,206    } = *key;207    let corners = code_to_corners(Code::from(code), dimension, base)?;208    let fill = || counts::fill(Code::from(code), key.number(), dimension, 1, base);209    let form = match (measure, axis) {210        (Measure::Fills, Axis::Level) => Closed::Power(fill()?),211        (Measure::Voids, Axis::Level) => {212            Closed::Difference((key.number() as u128).pow(dimension as u32), fill()?)213        }214        (Measure::Fills, Axis::Side) if base == 2 => {215            Closed::Polynomial(fill_polynomial(&corners, dimension))216        }217        (Measure::Voids, Axis::Side) if base == 2 => Closed::Polynomial(218            odd_power(dimension)219                .iter()220                .zip(fill_polynomial(&corners, dimension))221                .map(|(all, filled)| all - filled)222                .collect(),223        ),224        (Measure::Surface, Axis::Level) => Closed::Recurrence(225            counts::Exposure::from_corners(&corners, key.number(), dimension, base).recurrence(),226        ),227        _ => return Ok(None),228    };229    Ok(Some(form))230}231232#[cfg(test)]233mod tests {234    use super::super::BUDGET;235    use super::*;236237    fn read(code: u128, dimension: usize, measure: Measure, axis: Axis, count: usize) -> Vec<i128> {238        terms(&Key::new(code, dimension, 2, measure, axis), count, BUDGET)239            .unwrap()240            .0241    }242243    #[test]244    fn the_closed_measures_read_the_classics() {245        assert_eq!(read(7, 2, Measure::Voids, Axis::Level, 3), [1, 17, 217]);246        assert_eq!(247            read(7, 2, Measure::Surface, Axis::Level, 4),248            [16, 80, 496, 3536]249        );250        assert_eq!(251            read(23, 3, Measure::Fills, Axis::Side, 4),252            [20, 81, 208, 425]253        );254        assert_eq!(255            read(23, 3, Measure::Voids, Axis::Side, 4),256            [7, 44, 135, 304]257        );258        assert_eq!(read(1, 2, Measure::Fills, Axis::Side, 3), [4, 9, 16]);259        assert_eq!(read(9, 2, Measure::Fills, Axis::Side, 3), [5, 13, 25]);260        assert_eq!(read(11, 2, Measure::Fills, Axis::Side, 3), [7, 19, 37]);261        assert_eq!(read(15, 2, Measure::Fills, Axis::Side, 3), [9, 25, 49]);262        assert_eq!(read(129, 3, Measure::Fills, Axis::Side, 3), [9, 35, 91]);263        assert_eq!(read(255, 3, Measure::Fills, Axis::Side, 3), [27, 125, 343]);264    }265266    #[test]267    fn the_grid_measures_agree_with_the_censuses() {268        assert_eq!(read(7, 2, Measure::Euler, Axis::Level, 3), [0, -8, -72]);269        assert_eq!(read(23, 3, Measure::Euler, Axis::Level, 2), [-4, -80]);270        assert_eq!(read(23, 3, Measure::Faces, Axis::Level, 1), [96]);271        assert_eq!(read(23, 3, Measure::Vertices, Axis::Level, 1), [64]);272        assert_eq!(read(23, 3, Measure::Edges, Axis::Level, 1), [144]);273        assert_eq!(read(7, 2, Measure::Vertices, Axis::Side, 2), [16, 36]);274        assert_eq!(read(23, 3, Measure::Triangles, Axis::Level, 2), [42, 306]);275        assert_eq!(read(23, 3, Measure::Pieces, Axis::Side, 2), [1, 7]);276        assert_eq!(read(255, 3, Measure::Holes, Axis::Level, 2), [0, 0]);277        assert_eq!(read(23, 3, Measure::Peak, Axis::Level, 2), [6, 42]);278        assert_eq!(read(23, 3, Measure::Heights, Axis::Level, 2), [7, 25]);279    }280281    #[test]282    fn the_budget_caps_honestly() {283        let key = Key::new(23, 3, 2, Measure::Euler, Axis::Level);284        assert_eq!(terms(&key, 8, 1000).unwrap(), (vec![-4, -80], true));285        assert_eq!(terms(&key, 8, 26).unwrap(), (vec![], true));286        let deep = Key::new(23, 3, 2, Measure::Fills, Axis::Level);287        let (fills, capped) = terms(&deep, 40, BUDGET).unwrap();288        assert!(capped && fills.len() == 29);289        let base3 = Key::new(100, 2, 3, Measure::Surface, Axis::Side);290        assert_eq!(terms(&base3, 2, BUDGET).unwrap().0.len(), 2);291        assert!(terms(&Key::new(7, 2, 2, Measure::Faces, Axis::Level), 1, BUDGET).is_err());292        assert!(terms(&Key::new(16, 2, 2, Measure::Fills, Axis::Level), 1, BUDGET).is_err());293    }294295    #[test]296    fn the_closed_forms_match_the_terms() {297        for code in 0..16u128 {298            for measure in [Measure::Fills, Measure::Voids] {299                let key = Key::new(code, 2, 2, measure, Axis::Side);300                let Some(Closed::Polynomial(poly)) = closed(&key).unwrap() else {301                    panic!("no polynomial");302                };303                let (terms, _) = terms(&key, 5, BUDGET).unwrap();304                for (index, &term) in terms.iter().enumerate() {305                    let k = index as i128 + 2;306                    let value: i128 = poly307                        .iter()308                        .enumerate()309                        .map(|(p, &c)| c * k.pow(p as u32))310                        .sum();311                    assert_eq!(value, term, "code={code} k={k}");312                }313            }314        }315        assert_eq!(316            closed(&Key::new(23, 3, 2, Measure::Fills, Axis::Level)).unwrap(),317            Some(Closed::Power(20))318        );319        assert_eq!(320            closed(&Key::new(7, 2, 2, Measure::Voids, Axis::Level)).unwrap(),321            Some(Closed::Difference(9, 8))322        );323        assert_eq!(324            closed(&Key::new(7, 2, 3, Measure::Fills, Axis::Side)).unwrap(),325            None326        );327        assert_eq!(328            closed(&Key::new(7, 2, 2, Measure::Euler, Axis::Level)).unwrap(),329            None330        );331    }332}