mod.rs

1/// The markdown page the ledger renders.2pub mod markdown;3/// The measures and their cost classes.4pub mod measure;5/// The curated OEIS records and the identification against them.6pub mod records;7/// The term generators and the closed forms.8pub mod terms;910pub use markdown::markdown;11pub use measure::{Cost, Measure};12pub use records::{identify, Record, RECORDS};13pub use terms::{closed, fill_polynomial, terms};1415use mrlycore::errors::{value_error, Result};16use mrlymath::bang::{baseq, Code};17use mrlymath::name::{Bang, Named, Sequence as SequenceName};18use std::collections::BTreeMap;19use std::sync::{Mutex, OnceLock};2021type Walked = BTreeMap<(usize, usize), &'static [Code]>;2223/// The dimension and base pairs the ledger walks.24pub const SPACES: [(usize, usize); 9] = [25    (1, 2),26    (2, 2),27    (3, 2),28    (4, 2),29    (1, 3),30    (2, 3),31    (1, 4),32    (2, 4),33    (1, 5),34];3536/// The cells a catalog row may render for one term.37pub const BUDGET: u128 = 500_000;3839/// The terms a catalog row holds.40pub const TERMS: usize = 8;4142/// The index a sequence runs along.43#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]44pub enum Axis {45    /// The fractal level from 1, at side `max(base, 3)`.46    Level,47    /// The odd side `2k - 1` from `k = 2`, at level 1.48    Side,49}5051impl Axis {52    /// Both axes, level first.53    pub const ALL: [Axis; 2] = [Axis::Level, Axis::Side];54    /// Returns the axis's one-word name.55    pub fn slug(self) -> &'static str {56        match self {57            Axis::Level => "level",58            Axis::Side => "side",59        }60    }61    /// Parses a one-word name back into its axis, or an error for any other word.62    pub fn parse(slug: &str) -> Result<Axis> {63        match slug {64            "level" => Ok(Axis::Level),65            "side" => Ok(Axis::Side),66            other => value_error(format!("unknown axis {other:?}.")),67        }68    }69    /// Returns the ledger index of the first term: the level 1 or the `k` of side 3.70    pub fn start(self) -> i32 {71        match self {72            Axis::Level => 1,73            Axis::Side => 2,74        }75    }76    /// Returns the side number and level of the term at the index.77    pub fn place(self, index: usize, number: usize) -> (usize, u32) {78        match self {79            Axis::Level => (number, index as u32 + 1),80            Axis::Side => (2 * index + 3, 1),81        }82    }83}8485/// The status a claim carries.86#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]87pub enum Tag {88    /// Proved on this tree.89    Proved,90    /// Checked against a record or a second generator.91    Verified,92    /// Stated and not yet checked.93    Conjecture,94    /// Checked and found false.95    Refuted,96}9798impl Tag {99    /// Returns the tag's capitalised word.100    pub fn text(self) -> &'static str {101        match self {102            Tag::Proved => "Proved",103            Tag::Verified => "Verified",104            Tag::Conjecture => "Conjecture",105            Tag::Refuted => "Refuted",106        }107    }108}109110/// A design sequence's address: the design, the measure and the axis.111#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]112pub struct Key {113    /// The design's code.114    pub code: Code,115    /// The design's dimension.116    pub dimension: usize,117    /// The numeral base of the corners.118    pub base: usize,119    /// The reading taken.120    pub measure: Measure,121    /// The index the reading runs along.122    pub axis: Axis,123}124125impl Key {126    /// Pins a design sequence to its address.127    pub const fn new(128        code: Code,129        dimension: usize,130        base: usize,131        measure: Measure,132        axis: Axis,133    ) -> Key {134        Key {135            code,136            dimension,137            base,138            measure,139            axis,140        }141    }142    /// Returns the sequence name this key addresses.143    pub fn named(&self) -> SequenceName {144        SequenceName::new(145            self.code,146            self.dimension,147            self.base,148            self.measure.slug(),149            self.axis.slug(),150        )151    }152    /// Returns the sequence's file name.153    ///154    /// ```155    /// use mrlylab::ledger::{Axis, Key, Measure};156    /// let key = Key::new(23, 3, 2, Measure::Surface, Axis::Level);157    /// assert_eq!(key.name(), "sequence_dim=3_code=23_measure=surface_axis=level");158    /// assert_eq!(key.id(), "753b6b49");159    /// ```160    pub fn name(&self) -> String {161        self.named().to_file()162    }163    /// Returns the first eight hex digits of the sha256 of the sequence's canonical JSON.164    pub fn id(&self) -> String {165        self.named().to_id()166    }167    /// Returns the design pinned to its dimension and base.168    pub fn design(&self) -> Bang {169        Bang::new(self.code, self.dimension, self.base)170    }171    /// Returns the side number the level axis runs at.172    pub fn number(&self) -> usize {173        self.base.max(3)174    }175}176177/// A closed form of a sequence.178#[derive(Clone, Debug, PartialEq, Eq)]179pub enum Closed {180    /// `fill^level`.181    Power(u128),182    /// `cells^level - fill^level`.183    Difference(u128, u128),184    /// A polynomial in `k` by rising power, at side `2k - 1`.185    Polynomial(Vec<i128>),186    /// `a(level) = c[0] a(level-1) + c[1] a(level-2) + ...`.187    Recurrence(Vec<i128>),188}189190fn signed(text: &mut String, coefficient: i128, first: bool) {191    if first {192        if coefficient < 0 {193            text.push('-');194        }195    } else {196        text.push_str(if coefficient < 0 { " - " } else { " + " });197    }198}199200impl Closed {201    /// Spells the closed form.202    pub fn text(&self) -> String {203        match self {204            Closed::Power(f) => format!("{f}^level"),205            Closed::Difference(g, f) => format!("{g}^level - {f}^level"),206            Closed::Polynomial(coefficients) => {207                let mut text = String::new();208                for (power, &c) in coefficients.iter().enumerate().rev() {209                    if c == 0 {210                        continue;211                    }212                    let first = text.is_empty();213                    signed(&mut text, c, first);214                    if c.abs() != 1 || power == 0 {215                        text.push_str(&c.abs().to_string());216                    }217                    match power {218                        0 => {}219                        1 => text.push('k'),220                        _ => text.push_str(&format!("k^{power}")),221                    }222                }223                if text.is_empty() {224                    text.push('0');225                }226                text227            }228            Closed::Recurrence(coefficients) => {229                let mut text = String::new();230                for (back, &c) in coefficients.iter().enumerate() {231                    if c == 0 {232                        continue;233                    }234                    let first = text.is_empty();235                    signed(&mut text, c, first);236                    if c.abs() != 1 {237                        text.push_str(&c.abs().to_string());238                        text.push(' ');239                    }240                    text.push_str(&format!("a(level-{})", back + 1));241                }242                if text.is_empty() {243                    text.push('0');244                }245                format!("a(level) = {text}")246            }247        }248    }249}250251/// A cost tier of the catalog.252#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]253pub enum Tier {254    /// The closed measures on both axes.255    Closed,256    /// The profile measures on both axes.257    Convolved,258    /// The grid measures on the side axis.259    SideGrid,260    /// The grid measures on the level axis.261    LevelGrid,262}263264impl Tier {265    /// Every tier, cheapest first.266    pub const ALL: [Tier; 4] = [267        Tier::Closed,268        Tier::Convolved,269        Tier::SideGrid,270        Tier::LevelGrid,271    ];272    /// Returns the tier's one-word name.273    pub fn slug(self) -> &'static str {274        match self {275            Tier::Closed => "closed",276            Tier::Convolved => "convolved",277            Tier::SideGrid => "side",278            Tier::LevelGrid => "level",279        }280    }281    /// Parses a one-word name back into its tier, or an error for any other word.282    pub fn parse(slug: &str) -> Result<Tier> {283        Tier::ALL284            .into_iter()285            .find(|tier| tier.slug() == slug)286            .map_or_else(|| value_error(format!("unknown tier {slug:?}.")), Ok)287    }288    fn cost(self) -> Cost {289        match self {290            Tier::Closed => Cost::Closed,291            Tier::Convolved => Cost::Convolved,292            _ => Cost::Grid,293        }294    }295    fn axes(self) -> &'static [Axis] {296        match self {297            Tier::SideGrid => &[Axis::Side],298            Tier::LevelGrid => &[Axis::Level],299            _ => &Axis::ALL,300        }301    }302}303304/// One row of the catalog: a design sequence with its terms, its closed form and its record.305#[derive(Clone, Debug, PartialEq, Eq)]306pub struct Sequence {307    /// The sequence's address.308    pub key: Key,309    /// The first terms.310    pub terms: Vec<i128>,311    /// Whether the cell budget or a u128 stopped the terms short.312    pub capped: bool,313    /// The closed form, when one is known.314    pub closed: Option<Closed>,315    /// The record the terms match, with the record's index less the ledger's.316    pub record: Option<(&'static Record, i32)>,317    /// The status of the match: the record's when the record names this key, else a collision to explain.318    pub tag: Option<Tag>,319}320321impl Sequence {322    fn mentions(&self, needle: &str) -> bool {323        self.key.name().contains(needle)324            || self.record.is_some_and(|(record, _)| {325                record.id.to_lowercase().contains(needle)326                    || record.name.to_lowercase().contains(needle)327            })328    }329}330331/// Returns the designs of a dimension and base, the least code of every orbit, walked once and cached, or an error past the walk limit.332///333/// ```334/// assert_eq!(mrlylab::ledger::designs(2, 2).unwrap(), [0, 1, 3, 6, 7, 15]);335/// assert_eq!(mrlylab::ledger::designs(2, 3).unwrap().len(), 26);336/// ```337pub fn designs(dimension: usize, base: usize) -> Result<&'static [Code]> {338    static CACHE: OnceLock<Mutex<Walked>> = OnceLock::new();339    let cache = CACHE.get_or_init(|| Mutex::new(BTreeMap::new()));340    let mut guard = cache.lock().expect("the design cache is not poisoned");341    if let Some(codes) = guard.get(&(dimension, base)) {342        return Ok(codes);343    }344    let codes: Vec<Code> = baseq::representatives(base, dimension)?345        .into_iter()346        .map(|(code, _)| code)347        .collect();348    let leaked: &'static [Code] = Box::leak(codes.into_boxed_slice());349    guard.insert((dimension, base), leaked);350    Ok(leaked)351}352353/// Lists every key of a tier: the designs of every space, the measures of the tier's cost that apply, on the tier's axes.354pub fn keys(tier: Tier) -> Vec<Key> {355    let mut out = Vec::new();356    for (dimension, base) in SPACES {357        let codes = designs(dimension, base).expect("the ledger spaces are walkable");358        for &code in codes {359            for measure in Measure::ALL {360                if measure.cost() != tier.cost() || !measure.applies(dimension, base) {361                    continue;362                }363                for &axis in tier.axes() {364                    out.push(Key::new(code, dimension, base, measure, axis));365                }366            }367        }368    }369    out370}371372fn attach(key: &Key, terms: &[i128]) -> Option<(&'static Record, i32)> {373    if terms.len() < 4 || terms.iter().all(|&term| term == terms[0]) {374        return None;375    }376    let found = identify(terms);377    found378        .iter()379        .find(|(record, _)| record.key == Some(*key))380        .or(found.first())381        .map(|&(record, shift)| (record, shift - key.axis.start()))382}383384/// Reads one design sequence: its terms within the budget, its closed form and the record it matches.385pub fn sequence(key: &Key, count: usize, cells: u128) -> Result<Sequence> {386    let (terms, capped) = terms(key, count, cells)?;387    let closed = closed(key)?;388    let record = attach(key, &terms);389    let tag = record.map(|(record, _)| {390        if record.key == Some(*key) {391            record.status392        } else {393            Tag::Conjecture394        }395    });396    Ok(Sequence {397        key: *key,398        terms,399        capped,400        closed,401        record,402        tag,403    })404}405406/// Reads every sequence of a tier at the count of terms, within the standing cell budget.407pub fn catalog(tier: Tier, count: usize) -> Vec<Sequence> {408    keys(tier)409        .iter()410        .filter_map(|key| sequence(key, count, BUDGET).ok())411        .collect()412}413414/// Parses integers separated by commas or spaces, or none when a token is not one.415pub fn numbers(text: &str) -> Option<Vec<i128>> {416    let tokens: Vec<&str> = text417        .split(|c: char| c == ',' || c.is_whitespace())418        .filter(|token| !token.is_empty())419        .collect();420    if tokens.is_empty() {421        return None;422    }423    tokens.iter().map(|token| token.parse().ok()).collect()424}425426/// Finds the catalog rows a query names: the rows holding the typed terms as a window, or the rows whose name or record holds the typed fragment.427pub fn search(catalog: &[Sequence], query: &str) -> Vec<usize> {428    let query = query.trim();429    if query.is_empty() {430        return (0..catalog.len()).collect();431    }432    if let Some(window) = numbers(query) {433        return catalog434            .iter()435            .enumerate()436            .filter(|(_, row)| {437                row.terms438                    .windows(window.len())439                    .any(|w| w == window.as_slice())440            })441            .map(|(index, _)| index)442            .collect();443    }444    let needle = query.to_lowercase();445    catalog446        .iter()447        .enumerate()448        .filter(|(_, row)| row.mentions(&needle))449        .map(|(index, _)| index)450        .collect()451}452453#[cfg(test)]454mod tests {455    use super::*;456457    #[test]458    fn the_classics_read_their_records() {459        let carpet = sequence(&Key::new(7, 2, 2, Measure::Fills, Axis::Side), 4, BUDGET).unwrap();460        assert_eq!(carpet.terms, [8, 21, 40, 65]);461        assert_eq!(carpet.record.map(|(r, s)| (r.id, s)), Some(("A000567", 0)));462        assert_eq!(carpet.tag, Some(Tag::Proved));463        assert_eq!(carpet.closed.unwrap().text(), "3k^2 - 2k");464        let tree = sequence(&Key::new(3, 2, 2, Measure::Fills, Axis::Side), 4, BUDGET).unwrap();465        assert_eq!(tree.terms[..3], [6, 15, 28]);466        assert_eq!(tree.record.map(|(r, s)| (r.id, s)), Some(("A000384", 0)));467        let sponge = sequence(468            &Key::new(23, 3, 2, Measure::Surface, Axis::Level),469            3,470            BUDGET,471        )472        .unwrap();473        assert_eq!(sponge.terms, [72, 1056, 18048]);474        assert_eq!(475            sponge.closed.unwrap().text(),476            "a(level) = 28 a(level-1) - 160 a(level-2)"477        );478        let slice = sequence(479            &Key::new(23, 3, 2, Measure::Triangles, Axis::Level),480            8,481            BUDGET,482        )483        .unwrap();484        assert_eq!(slice.terms, [42, 306, 2250, 16578]);485        assert!(slice.capped);486        assert_eq!(slice.record.map(|(r, s)| (r.id, s)), Some(("A299916", 1)));487        let void = sequence(&Key::new(9, 2, 2, Measure::Voids, Axis::Side), 3, BUDGET).unwrap();488        assert_eq!(void.closed.unwrap().text(), "2k^2 - 2k");489        assert_eq!(void.terms, [4, 12, 24]);490    }491492    #[test]493    fn the_keys_of_the_closed_tier_cover_every_space() {494        let closed = keys(Tier::Closed);495        assert_eq!(closed.len(), 1282 * 3 * 2);496        assert_eq!(keys(Tier::Convolved).len(), (1282 - 3 - 4 - 6 - 8) * 2 * 2);497        assert!(closed.iter().all(|key| key.measure.cost() == Cost::Closed));498        assert!(designs(3, 3).is_err());499    }500501    #[test]502    fn the_search_finds_terms_and_names() {503        let rows: Vec<Sequence> = [504            Key::new(7, 2, 2, Measure::Fills, Axis::Level),505            Key::new(7, 2, 2, Measure::Surface, Axis::Level),506            Key::new(23, 3, 2, Measure::Fills, Axis::Level),507        ]508        .iter()509        .map(|key| sequence(key, 5, BUDGET).unwrap())510        .collect();511        assert_eq!(search(&rows, "64, 512"), [0]);512        assert_eq!(search(&rows, "80 496"), [1]);513        assert_eq!(search(&rows, "dim=3_code=23"), [2]);514        assert_eq!(search(&rows, "A381517"), [1]);515        assert_eq!(search(&rows, "surface"), [1]);516        assert_eq!(search(&rows, ""), [0, 1, 2]);517        assert!(search(&rows, "5, 6, 7").is_empty());518        assert_eq!(numbers("1, 2 3"), Some(vec![1, 2, 3]));519        assert_eq!(numbers("1, x"), None);520    }521522    #[test]523    fn the_closed_forms_spell_themselves() {524        assert_eq!(Closed::Power(8).text(), "8^level");525        assert_eq!(Closed::Difference(9, 8).text(), "9^level - 8^level");526        assert_eq!(Closed::Polynomial(vec![1, -2, 2]).text(), "2k^2 - 2k + 1");527        assert_eq!(Closed::Polynomial(vec![0, 0, 1]).text(), "k^2");528        assert_eq!(Closed::Polynomial(vec![-1, 0, -1]).text(), "-k^2 - 1");529        assert_eq!(Closed::Polynomial(vec![0]).text(), "0");530        assert_eq!(531            Closed::Recurrence(vec![11, -24]).text(),532            "a(level) = 11 a(level-1) - 24 a(level-2)"533        );534        assert_eq!(Closed::Recurrence(vec![1]).text(), "a(level) = a(level-1)");535        assert_eq!(Closed::Recurrence(vec![0]).text(), "a(level) = 0");536        assert_eq!(Axis::Side.place(0, 3), (3, 1));537        assert_eq!(Axis::Level.place(2, 3), (3, 3));538        assert_eq!(Tier::parse("side").unwrap(), Tier::SideGrid);539        assert!(Axis::parse("depth").is_err());540    }541}