counting.rs

1use crate::core::error::{value_error, Result};2use crate::math::bang::factory;3use crate::math::bang::Code;4use crate::num::factor::reduce;56/// Counts the indices below number that equal residue modulo base.7pub fn positions(residue: usize, number: usize, base: usize) -> u128 {8    if residue >= number {9        return 0;10    }11    (number - residue).div_ceil(base) as u12812}1314/// Returns the total cells of the grid, number to the dimension, to the level.15pub fn grid(number: usize, dimension: usize, level: u32) -> u128 {16    (number as u128).pow(dimension as u32).pow(level)17}1819/// Sums each corner's position products into a base fill and raises it to the level.20pub fn fill_from_corners(21    filled: &[Vec<u8>],22    number: usize,23    _dimension: usize,24    level: u32,25    base: usize,26) -> u128 {27    let base_fill: u128 = filled28        .iter()29        .map(|corner| {30            corner31                .iter()32                .map(|&r| positions(r as usize, number, base))33                .product::<u128>()34        })35        .sum();36    base_fill.pow(level)37}3839/// Returns the filled cell count of the code's fractal at the given level, without rendering it.40///41/// ```42/// use mrlyrs::math::bang::Code;43/// assert_eq!(mrlyrs::math::counts::fill(Code::from(7u64), 3, 2, 2, 2).unwrap(), 64);44/// ```45///46/// # Errors47///48/// Errors when the code is out of range for the dimension and base.49pub fn fill(code: Code, number: usize, dimension: usize, level: u32, base: usize) -> Result<u128> {50    let filled = factory::code_to_corners(code, dimension, base)?;51    Ok(fill_from_corners(&filled, number, dimension, level, base))52}5354/// Returns the empty cell count, grid minus fill.55///56/// # Errors57///58/// Errors when the code is out of range for the dimension and base.59pub fn void(code: Code, number: usize, dimension: usize, level: u32, base: usize) -> Result<u128> {60    Ok(grid(number, dimension, level) - fill(code, number, dimension, level, base)?)61}6263/// Returns the filled fraction of the grid, or 0.0 for an empty grid.64///65/// # Errors66///67/// Errors when the code is out of range for the dimension and base.68pub fn ratio(code: Code, number: usize, dimension: usize, level: u32, base: usize) -> Result<f64> {69    let total = grid(number, dimension, level);70    if total == 0 {71        return Ok(0.0);72    }73    Ok(fill(code, number, dimension, level, base)? as f64 / total as f64)74}7576/// Returns the exact filled fraction as a fraction of fill over grid, reduced.77///78/// ```79/// use mrlyrs::math::bang::Code;80/// assert_eq!(mrlyrs::math::counts::rational(Code::from(7u64), 3, 2, 2, 2).unwrap(), (64, 81));81/// ```82///83/// # Errors84///85/// Errors when the code is out of range for the dimension and base.86pub fn rational(87    code: Code,88    number: usize,89    dimension: usize,90    level: u32,91    base: usize,92) -> Result<(u128, u128)> {93    let total = grid(number, dimension, level);94    if total == 0 {95        return Ok((0, 1));96    }97    Ok(reduce(fill(code, number, dimension, level, base)?, total))98}99100/// Returns the fill ratio the code walks toward as the side number grows, reduced.101///102/// The ratio is the corner count over the corner slots, so it is always rational: the103/// carpet holds three corners of four and the sponge four of eight.104///105/// ```106/// use mrlyrs::math::bang::Code;107/// assert_eq!(mrlyrs::math::counts::limit(Code::from(7u64), 2, 1, 2).unwrap(), (3, 4));108/// assert_eq!(mrlyrs::math::counts::limit(Code::from(7u64), 2, 2, 2).unwrap(), (9, 16));109/// ```110///111/// # Errors112///113/// Errors when the code is out of range, or the limit overflows at this level.114pub fn limit(code: Code, dimension: usize, level: u32, base: usize) -> Result<(u128, u128)> {115    let corners = factory::code_to_corners(code, dimension, base)?.len() as u128;116    let slots = (base as u128).pow(dimension as u32);117    let overflow = || value_error("fill ratio limit overflows at this level.");118    let (Some(top), Some(bottom)) = (corners.checked_pow(level), slots.checked_pow(level)) else {119        return overflow();120    };121    Ok(reduce(top, bottom))122}123124/// Returns the code's fractal dimension, the log of its one-level fill over the log of number.125///126/// # Errors127///128/// Errors when the code is out of range for the dimension and base.129pub fn dimension(code: Code, number: usize, base_dimension: usize, base: usize) -> Result<f64> {130    if number == 1 {131        return Ok(base_dimension as f64);132    }133    let f = fill(code, number, base_dimension, 1, base)?;134    if f == 0 {135        return Ok(0.0);136    }137    Ok((f as f64).ln() / (number as f64).ln())138}139140#[cfg(test)]141mod tests {142    use super::*;143    use crate::math::bang::factory;144    #[test]145    fn fill_matches_rendered_sum() {146        for dimension in 2..=3usize {147            for code in [Code(0), Code(1), Code(7), Code(23), Code(100)] {148                if code >= factory::total_codes(dimension, 2).unwrap() {149                    continue;150                }151                for number in 1..6 {152                    for level in 1..3 {153                        let rendered =154                            factory::create(code, number, dimension, 2, level as usize).unwrap();155                        assert_eq!(156                            fill(code, number, dimension, level, 2).unwrap(),157                            rendered.sum() as u128,158                            "code={code} d={dimension} n={number} l={level}"159                        );160                    }161                }162            }163        }164    }165    #[test]166    fn menger_dimension() {167        let d = dimension(Code(23), 3, 3, 2).unwrap();168        assert!((d - 2.7268).abs() < 0.001);169    }170    #[test]171    fn rational_reduces_the_exact_fraction() {172        assert_eq!(rational(Code(7), 3, 2, 1, 2).unwrap(), (8, 9));173        assert_eq!(rational(Code(7), 3, 2, 3, 2).unwrap(), (512, 729));174        assert_eq!(rational(Code(15), 5, 2, 2, 2).unwrap(), (1, 1));175        assert_eq!(rational(Code(0), 5, 2, 2, 2).unwrap(), (0, 1));176        assert_eq!(rational(Code(7), 0, 2, 1, 2).unwrap(), (0, 1));177        for number in 1..6usize {178            let (top, bottom) = rational(Code(23), number, 3, 2, 2).unwrap();179            let exact = fill(Code(23), number, 3, 2, 2).unwrap() as f64 / grid(number, 3, 2) as f64;180            assert!(181                (top as f64 / bottom as f64 - exact).abs() < 1e-12,182                "n={number}"183            );184        }185    }186    #[test]187    fn the_carpet_and_sponge_limits_stay_rational() {188        assert_eq!(limit(Code(7), 2, 1, 2).unwrap(), (3, 4));189        let sponge: Vec<Vec<u8>> = factory::residue_corners(3, 2)190            .into_iter()191            .filter(|corner| corner.iter().filter(|&&r| r == 1).count() <= 1)192            .collect();193        let code = factory::corners_to_code(&sponge, 3, 2);194        assert_eq!(limit(code, 3, 1, 2).unwrap(), (1, 2));195        assert_eq!(limit(code, 3, 3, 2).unwrap(), (1, 8));196        assert_eq!(limit(Code(0), 2, 1, 2).unwrap(), (0, 1));197        assert_eq!(limit(Code(15), 2, 4, 2).unwrap(), (1, 1));198    }199    #[test]200    fn refuses_a_code_past_its_range_and_a_level_past_a_u128() {201        assert!(fill(Code(16), 3, 2, 1, 2).is_err());202        assert!(void(Code(16), 3, 2, 1, 2).is_err());203        assert!(ratio(Code(16), 3, 2, 1, 2).is_err());204        assert!(rational(Code(16), 3, 2, 1, 2).is_err());205        assert!(dimension(Code(16), 3, 2, 2).is_err());206        assert!(fill(Code(1), 3, 7, 1, 2).is_err());207        assert!(limit(Code(16), 2, 1, 2).is_err());208        assert!(limit(Code(7), 2, 1000, 2).is_err());209    }210    #[test]211    fn wide_grids_walk_toward_the_limit() {212        let (top, bottom) = limit(Code(7), 2, 1, 2).unwrap();213        let target = top as f64 / bottom as f64;214        let mut last = f64::MAX;215        for number in [3usize, 9, 27, 81, 243] {216            let gap = (ratio(Code(7), number, 2, 1, 2).unwrap() - target).abs();217            assert!(gap < last, "n={number} gap {gap} did not shrink");218            last = gap;219        }220        assert!(last < 0.01);221    }222    #[test]223    fn fill_plus_void_is_grid() {224        for bits in 0..16u128 {225            let code = Code(bits);226            let f = fill(code, 4, 2, 2, 2).unwrap();227            let v = void(code, 4, 2, 2, 2).unwrap();228            assert_eq!(f + v, grid(4, 2, 2));229        }230    }231}