tile.rs

1use super::errors::{value_error, Result};2use serde::{Deserialize, Serialize};34/// The smallest side, number or factor a tile may take.5pub const MIN_SIDE: usize = 2;67/// The largest side, number or factor a tile may take.8pub const MAX_SIDE: usize = 64;910/// The deepest fractal level a tile may take.11pub const MAX_LEVEL: usize = 6;1213/// The most slots a magic tile may take.14pub const MAX_SLOTS: usize = 6;1516/// The five construction families a tile can belong to.17#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash, Serialize, Deserialize)]18pub enum Group {19    /// One source at one flat size.20    General,21    /// One source raised to a power.22    Fractal,23    /// A magic-recipe construction.24    Magic,25    /// A one-off special construction.26    Special,27    /// Sources nested as a product of factors.28    Mosaic,29}3031/// The parity filter over candidate sizes.32#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]33pub enum Parity {34    /// Even sizes only.35    Evens,36    /// Odd sizes only.37    Odds,38    /// Every size.39    Both,40}4142/// The numeral base tile codes are read in.43#[derive(Clone, Copy, Debug, Default, PartialEq, Eq, Hash, Serialize, Deserialize)]44pub enum Base {45    /// Base two.46    #[default]47    Two,48}4950/// The pool of sources a tile may draw from.51#[derive(Clone, Debug, PartialEq, Eq)]52pub enum Catalog {53    /// The classic designs only.54    Classics,55    /// The canonical codes, one per symmetry orbit.56    Universe,57    /// An explicit list of codes.58    Codes(Vec<u128>),59}6061impl Group {62    /// Returns the group's display name.63    pub fn name(self) -> &'static str {64        match self {65            Group::General => "General",66            Group::Fractal => "Fractal",67            Group::Magic => "Magic",68            Group::Special => "Special",69            Group::Mosaic => "Mosaic",70        }71    }72    /// Parses a display name back into its group, or an error for an unknown name.73    pub fn parse(name: &str) -> Result<Group> {74        match name {75            "General" => Ok(Group::General),76            "Fractal" => Ok(Group::Fractal),77            "Magic" => Ok(Group::Magic),78            "Special" => Ok(Group::Special),79            "Mosaic" => Ok(Group::Mosaic),80            other => value_error(format!("unknown group {other:?}.")),81        }82    }83    /// Returns every group in canonical order.84    pub fn all() -> [Group; 5] {85        [86            Group::General,87            Group::Fractal,88            Group::Magic,89            Group::Special,90            Group::Mosaic,91        ]92    }93}9495impl Parity {96    /// Returns true when the number passes the filter.97    pub fn keep(self, n: usize) -> bool {98        match self {99            Parity::Evens => n.is_multiple_of(2),100            Parity::Odds => !n.is_multiple_of(2),101            Parity::Both => true,102        }103    }104    /// Returns the parity's display name.105    pub fn name(self) -> &'static str {106        match self {107            Parity::Evens => "Evens",108            Parity::Odds => "Odds",109            Parity::Both => "Both",110        }111    }112    /// Parses a display name back into its parity, or an error for an unknown name.113    pub fn parse(name: &str) -> Result<Parity> {114        match name {115            "Evens" => Ok(Parity::Evens),116            "Odds" => Ok(Parity::Odds),117            "Both" => Ok(Parity::Both),118            other => value_error(format!("unknown parity {other:?}.")),119        }120    }121}122123impl Base {124    /// Returns the base as a number.125    pub fn value(self) -> usize {126        match self {127            Base::Two => 2,128        }129    }130}131132/// The named designs a source can point at: the four classics and their four antis.133#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash, Serialize, Deserialize)]134pub enum Design {135    /// The carpet with a lattice of holes.136    Carpet,137    /// The net of crossing lines.138    Net,139    /// The stripes along the even rows.140    Htree,141    /// The stripes along the even columns.142    Vtree,143    /// The checkerboard lattice.144    Void,145    /// The beams along the x axis.146    Xtree,147    /// The beams along the y axis.148    Ytree,149    /// The beams along the z axis.150    Ztree,151    /// The points at the odd-odd sites.152    Point,153    /// The dust at the even-even sites.154    Dust,155    /// The lines along the odd rows.156    Hline,157    /// The lines along the odd columns.158    Vline,159    /// The star of sites with exactly one odd coordinate.160    Star,161    /// The rods along the x axis.162    Xline,163    /// The rods along the y axis.164    Yline,165    /// The rods along the z axis.166    Zline,167}168169impl Design {170    /// Returns the design's display name.171    pub fn name(self) -> &'static str {172        match self {173            Design::Carpet => "Carpet",174            Design::Net => "Net",175            Design::Htree => "Htree",176            Design::Vtree => "Vtree",177            Design::Void => "Void",178            Design::Xtree => "Xtree",179            Design::Ytree => "Ytree",180            Design::Ztree => "Ztree",181            Design::Point => "Point",182            Design::Dust => "Dust",183            Design::Hline => "Hline",184            Design::Vline => "Vline",185            Design::Star => "Star",186            Design::Xline => "Xline",187            Design::Yline => "Yline",188            Design::Zline => "Zline",189        }190    }191    /// Parses a display name back into its design, or an error for an unknown name.192    pub fn parse(name: &str) -> Result<Design> {193        match name {194            "Carpet" => Ok(Design::Carpet),195            "Net" => Ok(Design::Net),196            "Htree" => Ok(Design::Htree),197            "Vtree" => Ok(Design::Vtree),198            "Void" => Ok(Design::Void),199            "Xtree" => Ok(Design::Xtree),200            "Ytree" => Ok(Design::Ytree),201            "Ztree" => Ok(Design::Ztree),202            "Point" => Ok(Design::Point),203            "Dust" => Ok(Design::Dust),204            "Hline" => Ok(Design::Hline),205            "Vline" => Ok(Design::Vline),206            "Star" => Ok(Design::Star),207            "Xline" => Ok(Design::Xline),208            "Yline" => Ok(Design::Yline),209            "Zline" => Ok(Design::Zline),210            other => value_error(format!("unknown design {other:?}.")),211        }212    }213}214215/// The five classic designs of the plane.216pub const CLASSICS_2D: [Design; 5] = [217    Design::Carpet,218    Design::Net,219    Design::Htree,220    Design::Vtree,221    Design::Void,222];223224/// The six classic designs of the cube.225pub const CLASSICS_3D: [Design; 6] = [226    Design::Carpet,227    Design::Net,228    Design::Xtree,229    Design::Ytree,230    Design::Ztree,231    Design::Void,232];233234/// The five antis of the plane, the complements of the five classics in order.235pub const ANTIS_2D: [Design; 5] = [236    Design::Point,237    Design::Dust,238    Design::Hline,239    Design::Vline,240    Design::Star,241];242243/// The six antis of the cube: point, dust, the three lines and the star.244pub const ANTIS_3D: [Design; 6] = [245    Design::Point,246    Design::Dust,247    Design::Xline,248    Design::Yline,249    Design::Zline,250    Design::Star,251];252253/// The origin of one tile layer, a one-field json object.254#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash, Serialize, Deserialize)]255pub enum Source {256    /// A classic named design.257    #[serde(rename = "design")]258    Classic(Design),259    /// A numbered rule code, spelled as a decimal string.260    #[serde(rename = "code")]261    Code(#[serde(with = "decimal")] u128),262}263264mod decimal {265    use serde::{Deserialize, Deserializer, Serializer};266267    pub fn serialize<S: Serializer>(code: &u128, serializer: S) -> Result<S::Ok, S::Error> {268        serializer.collect_str(code)269    }270271    pub fn deserialize<'de, D: Deserializer<'de>>(deserializer: D) -> Result<u128, D::Error> {272        #[derive(Deserialize)]273        #[serde(untagged)]274        enum Code {275            Text(String),276            Number(u64),277        }278        match Code::deserialize(deserializer)? {279            Code::Text(text) => text.parse().map_err(serde::de::Error::custom),280            Code::Number(code) => Ok(code.into()),281        }282    }283}284285/// Returns the classic designs for a dimension.286pub fn classics(dimension: usize) -> Vec<Design> {287    match dimension {288        3 => CLASSICS_3D.to_vec(),289        _ => CLASSICS_2D.to_vec(),290    }291}292293/// Returns the anti designs for a dimension.294pub fn antis(dimension: usize) -> Vec<Design> {295    match dimension {296        3 => ANTIS_3D.to_vec(),297        _ => ANTIS_2D.to_vec(),298    }299}300301/// A complete recipe for one tile.302#[derive(Clone, Debug, PartialEq, Eq, Serialize, Deserialize)]303pub struct Tile {304    /// The construction family.305    pub group: Group,306    /// The base factor of the construction.307    pub factor: usize,308    /// The origin of each layer.309    pub sources: Vec<Source>,310    /// The grid size of each source.311    pub numbers: Vec<usize>,312    /// The fractal level of each source.313    pub levels: Vec<usize>,314    /// The quarter-turn rotation of each source.315    pub rotations: Vec<usize>,316    /// Whether each source swaps fill and void.317    pub anti: Vec<bool>,318    /// Whether the finished tile inverts.319    pub invert: bool,320    /// Whether the finished tile flips.321    pub flip: bool,322    /// The numeral base of the codes.323    #[serde(default)]324    pub base: Base,325    /// The tile's width in cells.326    pub width: usize,327    /// The tile's height in cells.328    pub height: usize,329}330331impl Tile {332    /// Builds an empty tile in a group.333    pub fn new(group: Group) -> Tile {334        Tile {335            group,336            factor: 0,337            sources: Vec::new(),338            numbers: Vec::new(),339            levels: Vec::new(),340            rotations: Vec::new(),341            anti: Vec::new(),342            invert: false,343            flip: false,344            base: Base::Two,345            width: 0,346            height: 0,347        }348    }349    /// Sets the tile's width and height.350    pub fn size(mut self, width: usize, height: usize) -> Tile {351        self.width = width;352        self.height = height;353        self354    }355    /// Returns the larger of width and height.356    pub fn max_size(&self) -> usize {357        self.width.max(self.height)358    }359    /// Returns whether the recipe is a magic tile of one repeated source at one repeated number,360    /// the shape a fractal tile of the same factor and level already draws.361    pub fn degenerate(&self) -> bool {362        self.group == Group::Magic363            && self.sources.len() > 1364            && uniform(&self.sources)365            && uniform(&self.numbers)366    }367    /// Recomputes the factor and side length the group and numbers imply, zero when they overflow.368    pub fn resize(&mut self) {369        let lead = self.numbers.first().copied().unwrap_or(0);370        if matches!(self.group, Group::General | Group::Fractal | Group::Magic) {371            self.factor = lead;372        }373        let size = match self.group {374            Group::General => lead,375            Group::Fractal => u32::try_from(self.levels.first().copied().unwrap_or(1))376                .ok()377                .and_then(|level| lead.checked_pow(level))378                .unwrap_or(0),379            Group::Magic => self380                .numbers381                .iter()382                .try_fold(1usize, |acc, &n| acc.checked_mul(n))383                .unwrap_or(0),384            Group::Special | Group::Mosaic => self.factor.checked_mul(lead).unwrap_or(0),385        };386        self.width = size;387        self.height = size;388    }389    /// Checks that the slots, numbers and sizes agree, or a terse note for the first broken law.390    pub fn check(&self) -> std::result::Result<(), &'static str> {391        let slots = self.sources.len();392        let wanted = match self.group {393            Group::Mosaic => slots == 3,394            Group::Magic => (2..=MAX_SLOTS).contains(&slots),395            _ => slots == 1,396        };397        if !wanted {398            return Err("wrong slot count");399        }400        if self.numbers.len() != slots401            || self.levels.len() != slots402            || self.rotations.len() != slots403            || self.anti.len() != slots404        {405            return Err("ragged slots");406        }407        if self408            .numbers409            .iter()410            .any(|&n| !(MIN_SIDE..=MAX_SIDE).contains(&n))411        {412            return Err("numbers are 2 to 64");413        }414        if self.rotations.iter().any(|&r| r > 3) {415            return Err("rotation is 0 to 3");416        }417        if self.flip && self.group != Group::Special {418            return Err("flip is special only");419        }420        if self.group == Group::Fractal {421            if !(1..=MAX_LEVEL).contains(&self.levels[0]) {422                return Err("level is 1 to 6");423            }424        } else if self.levels.iter().any(|&l| l != 1) {425            return Err("level is fractal only");426        }427        if matches!(self.group, Group::Special | Group::Mosaic)428            && !(MIN_SIDE..=MAX_SIDE).contains(&self.factor)429        {430            return Err("factor is 2 to 64");431        }432        if self.group == Group::Mosaic && self.numbers.iter().any(|&n| n != self.numbers[0]) {433            return Err("mosaic shares one number");434        }435        let mut probe = self.clone();436        probe.resize();437        if probe.width != self.width || probe.height != self.height || probe.factor != self.factor {438            return Err("sizes disagree");439        }440        if !(MIN_SIDE..=MAX_SIDE).contains(&self.max_size()) {441            return Err("size is 2 to 64");442        }443        Ok(())444    }445}446447const MIN_FACTOR: usize = 2;448449/// Returns whether every item equals the first, vacuously true for an empty or single list.450///451/// ```452/// assert!(mrlycore::tile::uniform(&[3, 3, 3]));453/// assert!(!mrlycore::tile::uniform(&[3, 5, 3]));454/// ```455pub fn uniform<T: PartialEq>(items: &[T]) -> bool {456    items.windows(2).all(|pair| pair[0] == pair[1])457}458459fn factors(min_factor: usize, max_factor: usize, parity: Parity) -> Vec<usize> {460    (min_factor.max(MIN_FACTOR)..=max_factor)461        .filter(|&n| parity.keep(n))462        .collect()463}464465/// Returns every flat size in the range that passes the parity filter.466pub fn generals(min_size: usize, max_size: usize, parity: Parity) -> Vec<usize> {467    factors(min_size, max_size, parity)468}469470/// Returns every factor and level whose power lands in the size range.471pub fn powers(min_size: usize, max_size: usize, parity: Parity) -> Vec<(usize, usize)> {472    let mut out = Vec::new();473    for n in factors(MIN_FACTOR, max_size, parity) {474        let mut level = 2;475        loop {476            match n.checked_pow(level as u32) {477                Some(size) if size <= max_size => {478                    if size >= min_size {479                        out.push((n, level));480                    }481                    level += 1;482                }483                _ => break,484            }485        }486    }487    out488}489490/// Returns the side a factor raised to a level makes, or None when no usize holds it.491///492/// ```493/// assert_eq!(mrlycore::tile::size(3, 3), Some(27));494/// assert_eq!(mrlycore::tile::size(3, 4294967298), None);495/// ```496pub fn size(number: i64, level: i64) -> Option<usize> {497    let number = usize::try_from(number).ok()?;498    let level = u32::try_from(level).ok()?;499    number.checked_pow(level)500}501502/// Returns every count-long factor list whose product lands in the size range.503pub fn products(min_size: usize, max_size: usize, count: usize, parity: Parity) -> Vec<Vec<usize>> {504    if count < 1 {505        return Vec::new();506    }507    fn walk(508        min_size: usize,509        max_size: usize,510        remaining: usize,511        parity: Parity,512        out: &mut Vec<Vec<usize>>,513    ) {514        if remaining == 1 {515            for n in factors(min_size, max_size, parity) {516                out.push(vec![n]);517            }518            return;519        }520        for n in factors(MIN_FACTOR, max_size, parity) {521            let next_min = min_size.div_ceil(n);522            let next_max = max_size / n;523            if next_max < MIN_FACTOR {524                continue;525            }526            let mut tails = Vec::new();527            walk(next_min, next_max, remaining - 1, parity, &mut tails);528            for tail in tails {529                let mut item = vec![n];530                item.extend(tail);531                out.push(item);532            }533        }534    }535    let mut out = Vec::new();536    walk(min_size, max_size, count, parity, &mut out);537    out538}539540/// Returns every factor list of depth two and beyond whose product lands in the size range.541pub fn nestings(min_size: usize, max_size: usize, parity: Parity) -> Vec<Vec<usize>> {542    let mut out = Vec::new();543    let mut depth = 2;544    loop {545        let found = products(min_size, max_size, depth, parity);546        if found.is_empty() {547            if depth > 2 {548                break;549            }550            depth += 1;551            if depth > max_size {552                break;553            }554            continue;555        }556        out.extend(found);557        depth += 1;558    }559    out560}561562#[cfg(test)]563mod tests {564    use super::*;565    use crate::json;566    #[test]567    fn parity_filters() {568        assert!(Parity::Odds.keep(3));569        assert!(!Parity::Odds.keep(4));570        assert!(Parity::Evens.keep(4));571        assert!(!Parity::Evens.keep(3));572        assert!(Parity::Both.keep(3));573        assert!(Parity::Both.keep(4));574    }575    #[test]576    fn generals_respects_parity_and_range() {577        assert_eq!(generals(3, 9, Parity::Odds), vec![3, 5, 7, 9]);578        assert_eq!(generals(3, 9, Parity::Evens), vec![4, 6, 8]);579        assert_eq!(generals(3, 9, Parity::Both), vec![3, 4, 5, 6, 7, 8, 9]);580    }581    #[test]582    fn powers_are_in_range() {583        for (n, level) in powers(3, 100, Parity::Odds) {584            let size = n.pow(level as u32);585            assert!((3..=100).contains(&size));586            assert!(level >= 2);587        }588        assert!(powers(3, 100, Parity::Odds).contains(&(3, 2)));589        assert!(powers(3, 100, Parity::Odds).contains(&(3, 4)));590    }591    #[test]592    fn products_multiply_into_range() {593        for option in products(3, 64, 2, Parity::Odds) {594            let size: usize = option.iter().product();595            assert!((3..=64).contains(&size));596            assert_eq!(option.len(), 2);597        }598    }599    #[test]600    fn nestings_go_deeper_than_two() {601        let deep = nestings(3, 300, Parity::Odds);602        assert!(deep.iter().any(|opt| opt.len() >= 3));603        for option in &deep {604            let size: usize = option.iter().product();605            assert!(size <= 300);606        }607    }608    #[test]609    fn tile_json_round_trips() {610        let mut tile = Tile::new(Group::Magic).size(45, 45);611        tile.sources = vec![Source::Classic(Design::Carpet), Source::Code(14)];612        tile.numbers = vec![5, 9];613        tile.levels = vec![1, 1];614        tile.rotations = vec![0, 0];615        tile.anti = vec![false, true];616        tile.factor = 5;617        let json = serde_json::to_value(&tile).unwrap();618        assert_eq!(json["group"], "Magic");619        assert_eq!(json["sources"][1], json!({ "code": "14" }));620        let back: Tile = serde_json::from_value(json).unwrap();621        assert_eq!(tile, back);622    }623    #[test]624    fn source_json_round_trips() {625        for source in [Source::Classic(Design::Vtree), Source::Code(232)] {626            let json = serde_json::to_value(source).unwrap();627            let back: Source = serde_json::from_value(json).unwrap();628            assert_eq!(source, back);629        }630    }631    #[test]632    fn source_json_spells_codes_as_strings() {633        let wide = u128::MAX - 1;634        let json = serde_json::to_value(Source::Code(wide)).unwrap();635        assert_eq!(json, json!({ "code": wide.to_string() }));636        let back: Source = serde_json::from_value(json).unwrap();637        assert_eq!(back, Source::Code(wide));638    }639    #[test]640    fn source_json_reads_bare_int_codes() {641        let read = |value| serde_json::from_value::<Source>(value);642        assert_eq!(read(json!({ "code": 7 })).unwrap(), Source::Code(7));643        assert!(read(json!({ "code": "soup" })).is_err());644        assert!(read(json!({ "code": true })).is_err());645        assert!(read(json!({ "design": "Soup" })).is_err());646    }647    #[test]648    fn resize_follows_the_size_law() {649        let mut tile = Tile::new(Group::Fractal);650        tile.sources = vec![Source::Code(7)];651        tile.numbers = vec![3];652        tile.levels = vec![2];653        tile.rotations = vec![0];654        tile.anti = vec![false];655        tile.resize();656        assert_eq!((tile.factor, tile.width, tile.height), (3, 9, 9));657        tile.group = Group::Special;658        tile.factor = 5;659        tile.resize();660        assert_eq!((tile.width, tile.height), (15, 15));661        tile.group = Group::Magic;662        tile.numbers = vec![3, 5];663        tile.resize();664        assert_eq!((tile.factor, tile.width), (3, 15));665    }666    #[test]667    fn resize_survives_empty_and_huge_tiles() {668        let mut bare = Tile::new(Group::Magic);669        bare.resize();670        assert_eq!(bare.width, 1);671        let mut huge = Tile::new(Group::Fractal);672        huge.numbers = vec![3];673        huge.levels = vec![4_294_967_298];674        huge.resize();675        assert_eq!(huge.width, 0);676    }677    #[test]678    fn check_names_the_first_broken_law() {679        let mut tile = Tile::new(Group::General);680        assert_eq!(tile.check(), Err("wrong slot count"));681        tile.sources = vec![Source::Code(7)];682        assert_eq!(tile.check(), Err("ragged slots"));683        tile.numbers = vec![3];684        tile.levels = vec![1];685        tile.rotations = vec![0];686        tile.anti = vec![false];687        tile.resize();688        assert_eq!(tile.check(), Ok(()));689        tile.rotations = vec![4];690        assert_eq!(tile.check(), Err("rotation is 0 to 3"));691        tile.rotations = vec![0];692        tile.flip = true;693        assert_eq!(tile.check(), Err("flip is special only"));694        tile.flip = false;695        tile.width = 5;696        assert_eq!(tile.check(), Err("sizes disagree"));697    }698    #[test]699    fn powers_generalize_beyond_classic_bases() {700        let options = powers(3, 1000, Parity::Odds);701        assert!(options.contains(&(3, 2)));702        assert!(options.contains(&(5, 2)));703        assert!(options.contains(&(7, 2)));704        assert!(options.contains(&(9, 2)));705        assert!(options.contains(&(13, 2)));706    }707    #[test]708    fn size_refuses_what_it_cannot_hold() {709        assert_eq!(size(3, 3), Some(27));710        assert_eq!(size(3, 0), Some(1));711        assert_eq!(size(-1, 2), None);712        assert_eq!(size(3, -1), None);713        assert_eq!(size(3, 64), None);714        assert_eq!(size(3, 4294967296), None);715        assert_eq!(size(3, 4294967298), None);716    }717    #[test]718    fn degenerate_marks_the_magic_tiles_a_fractal_already_draws() {719        let mut tile = Tile::new(Group::Magic);720        tile.sources = vec![Source::Classic(Design::Carpet); 2];721        tile.numbers = vec![3, 3];722        tile.levels = vec![1, 1];723        tile.rotations = vec![0, 0];724        tile.anti = vec![false, false];725        tile.resize();726        assert_eq!(tile.check(), Ok(()));727        assert!(tile.degenerate());728        tile.numbers = vec![3, 5];729        tile.resize();730        assert!(!tile.degenerate());731        tile.numbers = vec![3, 3];732        tile.sources = vec![Source::Classic(Design::Carpet), Source::Code(7)];733        tile.resize();734        assert!(!tile.degenerate());735    }736    #[test]737    fn degenerate_is_a_magic_law_only() {738        let mut tile = Tile::new(Group::Mosaic);739        tile.sources = vec![Source::Classic(Design::Carpet); 3];740        tile.numbers = vec![3, 3, 3];741        assert!(!tile.degenerate());742        tile.group = Group::General;743        tile.sources = vec![Source::Classic(Design::Carpet)];744        tile.numbers = vec![3];745        assert!(!tile.degenerate());746    }747    #[test]748    fn uniform_holds_for_short_lists() {749        assert!(uniform::<usize>(&[]));750        assert!(uniform(&[3]));751        assert!(uniform(&[3, 3, 3]));752        assert!(!uniform(&[3, 3, 5]));753    }754    #[test]755    fn evens_factors_work() {756        assert!(powers(4, 1000, Parity::Evens)757            .iter()758            .all(|(n, _)| n % 2 == 0));759        assert!(powers(4, 1000, Parity::Evens).contains(&(4, 2)));760        assert!(powers(4, 1000, Parity::Evens).contains(&(6, 2)));761    }762}