counting.rs

1use crate::bang::factory;2use crate::bang::universe::Code;3use mrlycore::errors::{value_error, Result};4use mrlynum::classics::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.40pub fn fill(code: Code, number: usize, dimension: usize, level: u32, base: usize) -> Result<u128> {41    let filled = factory::code_to_corners(code, dimension, base)?;42    Ok(fill_from_corners(&filled, number, dimension, level, base))43}4445/// Returns the empty cell count, grid minus fill.46pub fn void(code: Code, number: usize, dimension: usize, level: u32, base: usize) -> Result<u128> {47    Ok(grid(number, dimension, level) - fill(code, number, dimension, level, base)?)48}4950/// Returns the filled fraction of the grid, or 0.0 for an empty grid.51pub fn ratio(code: Code, number: usize, dimension: usize, level: u32, base: usize) -> Result<f64> {52    let total = grid(number, dimension, level);53    if total == 0 {54        return Ok(0.0);55    }56    Ok(fill(code, number, dimension, level, base)? as f64 / total as f64)57}5859/// Returns the exact filled fraction as a fraction of fill over grid, reduced.60///61/// ```62/// assert_eq!(mrlymath::formulas::rational(7, 3, 2, 2, 2).unwrap(), (64, 81));63/// ```64pub fn rational(65    code: Code,66    number: usize,67    dimension: usize,68    level: u32,69    base: usize,70) -> Result<(u128, u128)> {71    let total = grid(number, dimension, level);72    if total == 0 {73        return Ok((0, 1));74    }75    Ok(reduce(fill(code, number, dimension, level, base)?, total))76}7778/// Returns the fill ratio the code walks toward as the side number grows, reduced.79///80/// The ratio is the corner count over the corner slots, so it is always rational: the81/// carpet holds three corners of four and the sponge four of eight.82///83/// ```84/// assert_eq!(mrlymath::formulas::limit(7, 2, 1, 2).unwrap(), (3, 4));85/// assert_eq!(mrlymath::formulas::limit(7, 2, 2, 2).unwrap(), (9, 16));86/// ```87pub fn limit(code: Code, dimension: usize, level: u32, base: usize) -> Result<(u128, u128)> {88    let corners = factory::code_to_corners(code, dimension, base)?.len() as u128;89    let slots = (base as u128).pow(dimension as u32);90    let overflow = || value_error("fill ratio limit overflows at this level.");91    let (Some(top), Some(bottom)) = (corners.checked_pow(level), slots.checked_pow(level)) else {92        return overflow();93    };94    Ok(reduce(top, bottom))95}9697/// Returns the code's fractal dimension, the log of its one-level fill over the log of number.98pub fn dimension(code: Code, number: usize, base_dimension: usize, base: usize) -> Result<f64> {99    if number == 1 {100        return Ok(base_dimension as f64);101    }102    let f = fill(code, number, base_dimension, 1, base)?;103    if f == 0 {104        return Ok(0.0);105    }106    Ok((f as f64).ln() / (number as f64).ln())107}108109#[cfg(test)]110mod tests {111    use super::*;112    use crate::bang::factory;113    #[test]114    fn fill_matches_rendered_sum() {115        for dimension in 2..=3usize {116            for code in [0u128, 1, 7, 23, 100] {117                if code >= factory::total_codes(dimension, 2) {118                    continue;119                }120                for number in 1..6 {121                    for level in 1..3 {122                        let rendered =123                            factory::create(code, number, dimension, 2, level as usize).unwrap();124                        assert_eq!(125                            fill(code, number, dimension, level, 2).unwrap(),126                            rendered.sum() as u128,127                            "code={code} d={dimension} n={number} l={level}"128                        );129                    }130                }131            }132        }133    }134    #[test]135    fn menger_dimension() {136        let d = dimension(23, 3, 3, 2).unwrap();137        assert!((d - 2.7268).abs() < 0.001);138    }139    #[test]140    fn rational_reduces_the_exact_fraction() {141        assert_eq!(rational(7, 3, 2, 1, 2).unwrap(), (8, 9));142        assert_eq!(rational(7, 3, 2, 3, 2).unwrap(), (512, 729));143        assert_eq!(rational(15, 5, 2, 2, 2).unwrap(), (1, 1));144        assert_eq!(rational(0, 5, 2, 2, 2).unwrap(), (0, 1));145        assert_eq!(rational(7, 0, 2, 1, 2).unwrap(), (0, 1));146        for number in 1..6usize {147            let (top, bottom) = rational(23, number, 3, 2, 2).unwrap();148            let exact = fill(23, number, 3, 2, 2).unwrap() as f64 / grid(number, 3, 2) as f64;149            assert!(150                (top as f64 / bottom as f64 - exact).abs() < 1e-12,151                "n={number}"152            );153        }154    }155    #[test]156    fn the_carpet_and_sponge_limits_stay_rational() {157        assert_eq!(limit(7, 2, 1, 2).unwrap(), (3, 4));158        let sponge: Vec<Vec<u8>> = factory::residue_corners(3, 2)159            .into_iter()160            .filter(|corner| corner.iter().filter(|&&r| r == 1).count() <= 1)161            .collect();162        let code = factory::corners_to_code(&sponge, 3, 2);163        assert_eq!(limit(code, 3, 1, 2).unwrap(), (1, 2));164        assert_eq!(limit(code, 3, 3, 2).unwrap(), (1, 8));165        assert_eq!(limit(0, 2, 1, 2).unwrap(), (0, 1));166        assert_eq!(limit(15, 2, 4, 2).unwrap(), (1, 1));167        assert!(limit(7, 2, 1000, 2).is_err());168    }169    #[test]170    fn wide_grids_walk_toward_the_limit() {171        let (top, bottom) = limit(7, 2, 1, 2).unwrap();172        let target = top as f64 / bottom as f64;173        let mut last = f64::MAX;174        for number in [3usize, 9, 27, 81, 243] {175            let gap = (ratio(7, number, 2, 1, 2).unwrap() - target).abs();176            assert!(gap < last, "n={number} gap {gap} did not shrink");177            last = gap;178        }179        assert!(last < 0.01);180    }181    #[test]182    fn fill_plus_void_is_grid() {183        for code in 0..16u128 {184            let f = fill(code, 4, 2, 2, 2).unwrap();185            let v = void(code, 4, 2, 2, 2).unwrap();186            assert_eq!(f + v, grid(4, 2, 2));187        }188    }189}