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 pool of sources a tile may draw from.43#[derive(Clone, Debug, PartialEq, Eq)]44pub enum Catalog {45    /// The classic designs only.46    Classics,47    /// The canonical codes, one per symmetry orbit.48    Universe,49    /// An explicit list of codes.50    Codes(Vec<u128>),51}5253impl Group {54    /// Returns the group's display name.55    pub fn name(self) -> &'static str {56        match self {57            Group::General => "General",58            Group::Fractal => "Fractal",59            Group::Magic => "Magic",60            Group::Special => "Special",61            Group::Mosaic => "Mosaic",62        }63    }64    /// Parses a display name back into its group, or an error for an unknown name.65    pub fn parse(name: &str) -> Result<Group> {66        match name {67            "General" => Ok(Group::General),68            "Fractal" => Ok(Group::Fractal),69            "Magic" => Ok(Group::Magic),70            "Special" => Ok(Group::Special),71            "Mosaic" => Ok(Group::Mosaic),72            other => value_error(format!("unknown group {other:?}.")),73        }74    }75    /// Returns every group in canonical order.76    pub fn all() -> [Group; 5] {77        [78            Group::General,79            Group::Fractal,80            Group::Magic,81            Group::Special,82            Group::Mosaic,83        ]84    }85}8687impl Parity {88    /// Returns true when the number passes the filter.89    pub fn keep(self, n: usize) -> bool {90        match self {91            Parity::Evens => n.is_multiple_of(2),92            Parity::Odds => !n.is_multiple_of(2),93            Parity::Both => true,94        }95    }96    /// Returns the parity's display name.97    pub fn name(self) -> &'static str {98        match self {99            Parity::Evens => "Evens",100            Parity::Odds => "Odds",101            Parity::Both => "Both",102        }103    }104    /// Parses a display name back into its parity, or an error for an unknown name.105    pub fn parse(name: &str) -> Result<Parity> {106        match name {107            "Evens" => Ok(Parity::Evens),108            "Odds" => Ok(Parity::Odds),109            "Both" => Ok(Parity::Both),110            other => value_error(format!("unknown parity {other:?}.")),111        }112    }113}114115/// The named designs a source can point at: the four classics and their four antis.116#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash, Serialize, Deserialize)]117pub enum Design {118    /// The carpet with a lattice of holes.119    Carpet,120    /// The net of crossing lines.121    Net,122    /// The stripes along the even rows.123    Htree,124    /// The stripes along the even columns.125    Vtree,126    /// The checkerboard lattice.127    Void,128    /// The beams along the x axis.129    Xtree,130    /// The beams along the y axis.131    Ytree,132    /// The beams along the z axis.133    Ztree,134    /// The points at the odd-odd sites.135    Point,136    /// The dust at the even-even sites.137    Dust,138    /// The lines along the odd rows.139    Hline,140    /// The lines along the odd columns.141    Vline,142    /// The star of sites with exactly one odd coordinate.143    Star,144    /// The rods along the x axis.145    Xline,146    /// The rods along the y axis.147    Yline,148    /// The rods along the z axis.149    Zline,150}151152impl Design {153    /// Returns the design's display name.154    pub fn name(self) -> &'static str {155        match self {156            Design::Carpet => "Carpet",157            Design::Net => "Net",158            Design::Htree => "Htree",159            Design::Vtree => "Vtree",160            Design::Void => "Void",161            Design::Xtree => "Xtree",162            Design::Ytree => "Ytree",163            Design::Ztree => "Ztree",164            Design::Point => "Point",165            Design::Dust => "Dust",166            Design::Hline => "Hline",167            Design::Vline => "Vline",168            Design::Star => "Star",169            Design::Xline => "Xline",170            Design::Yline => "Yline",171            Design::Zline => "Zline",172        }173    }174    /// Parses a display name back into its design, or an error for an unknown name.175    pub fn parse(name: &str) -> Result<Design> {176        match name {177            "Carpet" => Ok(Design::Carpet),178            "Net" => Ok(Design::Net),179            "Htree" => Ok(Design::Htree),180            "Vtree" => Ok(Design::Vtree),181            "Void" => Ok(Design::Void),182            "Xtree" => Ok(Design::Xtree),183            "Ytree" => Ok(Design::Ytree),184            "Ztree" => Ok(Design::Ztree),185            "Point" => Ok(Design::Point),186            "Dust" => Ok(Design::Dust),187            "Hline" => Ok(Design::Hline),188            "Vline" => Ok(Design::Vline),189            "Star" => Ok(Design::Star),190            "Xline" => Ok(Design::Xline),191            "Yline" => Ok(Design::Yline),192            "Zline" => Ok(Design::Zline),193            other => value_error(format!("unknown design {other:?}.")),194        }195    }196}197198/// The five classic designs of the plane.199pub const CLASSICS_2D: [Design; 5] = [200    Design::Carpet,201    Design::Net,202    Design::Htree,203    Design::Vtree,204    Design::Void,205];206207/// The six classic designs of the cube.208pub const CLASSICS_3D: [Design; 6] = [209    Design::Carpet,210    Design::Net,211    Design::Xtree,212    Design::Ytree,213    Design::Ztree,214    Design::Void,215];216217/// The five antis of the plane, the complements of the five classics in order.218pub const ANTIS_2D: [Design; 5] = [219    Design::Point,220    Design::Dust,221    Design::Hline,222    Design::Vline,223    Design::Star,224];225226/// The six antis of the cube: point, dust, the three lines and the star.227pub const ANTIS_3D: [Design; 6] = [228    Design::Point,229    Design::Dust,230    Design::Xline,231    Design::Yline,232    Design::Zline,233    Design::Star,234];235236/// The origin of one tile layer, a one-field json object.237#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash, Serialize, Deserialize)]238pub enum Source {239    /// A classic named design.240    #[serde(rename = "design")]241    Classic(Design),242    /// A numbered rule code, spelled as a decimal string.243    #[serde(rename = "code")]244    Code(#[serde(with = "decimal")] u128),245}246247mod decimal {248    use serde::{Deserialize, Deserializer, Serializer};249250    pub fn serialize<S: Serializer>(code: &u128, serializer: S) -> Result<S::Ok, S::Error> {251        serializer.collect_str(code)252    }253254    pub fn deserialize<'de, D: Deserializer<'de>>(deserializer: D) -> Result<u128, D::Error> {255        #[derive(Deserialize)]256        #[serde(untagged)]257        enum Code {258            Text(String),259            Number(u64),260        }261        match Code::deserialize(deserializer)? {262            Code::Text(text) => text.parse().map_err(serde::de::Error::custom),263            Code::Number(code) => Ok(code.into()),264        }265    }266}267268/// Returns the classic designs for a dimension.269pub fn classics(dimension: usize) -> Vec<Design> {270    match dimension {271        3 => CLASSICS_3D.to_vec(),272        _ => CLASSICS_2D.to_vec(),273    }274}275276/// Returns the anti designs for a dimension.277pub fn antis(dimension: usize) -> Vec<Design> {278    match dimension {279        3 => ANTIS_3D.to_vec(),280        _ => ANTIS_2D.to_vec(),281    }282}283284/// A complete recipe for one tile.285#[derive(Clone, Debug, PartialEq, Eq, Serialize, Deserialize)]286pub struct Tile {287    /// The construction family.288    pub group: Group,289    /// The base factor of the construction.290    pub factor: usize,291    /// The origin of each layer.292    pub sources: Vec<Source>,293    /// The grid size of each source.294    pub numbers: Vec<usize>,295    /// The fractal level of each source.296    pub levels: Vec<usize>,297    /// The quarter-turn rotation of each source.298    pub rotations: Vec<usize>,299    /// Whether each source swaps fill and void.300    pub anti: Vec<bool>,301    /// Whether the finished tile inverts.302    pub invert: bool,303    /// Whether the finished tile flips.304    pub flip: bool,305    /// The tile's width in cells.306    pub width: usize,307    /// The tile's height in cells.308    pub height: usize,309}310311impl Tile {312    /// Builds an empty tile in a group.313    pub fn new(group: Group) -> Tile {314        Tile {315            group,316            factor: 0,317            sources: Vec::new(),318            numbers: Vec::new(),319            levels: Vec::new(),320            rotations: Vec::new(),321            anti: Vec::new(),322            invert: false,323            flip: false,324            width: 0,325            height: 0,326        }327    }328    /// Sets the tile's width and height.329    pub fn size(mut self, width: usize, height: usize) -> Tile {330        self.width = width;331        self.height = height;332        self333    }334    /// Returns the larger of width and height.335    pub fn max_size(&self) -> usize {336        self.width.max(self.height)337    }338    /// Returns whether the recipe is a magic tile of one repeated source at one repeated number,339    /// the shape a fractal tile of the same factor and level already draws.340    pub fn degenerate(&self) -> bool {341        self.group == Group::Magic342            && self.sources.len() > 1343            && uniform(&self.sources)344            && uniform(&self.numbers)345    }346    /// Recomputes the factor and side length the group and numbers imply, zero when they overflow.347    pub fn resize(&mut self) {348        let lead = self.numbers.first().copied().unwrap_or(0);349        if matches!(self.group, Group::General | Group::Fractal | Group::Magic) {350            self.factor = lead;351        }352        let size = match self.group {353            Group::General => lead,354            Group::Fractal => u32::try_from(self.levels.first().copied().unwrap_or(1))355                .ok()356                .and_then(|level| lead.checked_pow(level))357                .unwrap_or(0),358            Group::Magic => self359                .numbers360                .iter()361                .try_fold(1usize, |acc, &n| acc.checked_mul(n))362                .unwrap_or(0),363            Group::Special | Group::Mosaic => self.factor.checked_mul(lead).unwrap_or(0),364        };365        self.width = size;366        self.height = size;367    }368    /// Checks that the slots, numbers and sizes agree, or a terse note for the first broken law.369    pub fn check(&self) -> std::result::Result<(), &'static str> {370        let slots = self.sources.len();371        let wanted = match self.group {372            Group::Mosaic => slots == 3,373            Group::Magic => (2..=MAX_SLOTS).contains(&slots),374            _ => slots == 1,375        };376        if !wanted {377            return Err("wrong slot count");378        }379        if self.numbers.len() != slots380            || self.levels.len() != slots381            || self.rotations.len() != slots382            || self.anti.len() != slots383        {384            return Err("ragged slots");385        }386        if self387            .numbers388            .iter()389            .any(|&n| !(MIN_SIDE..=MAX_SIDE).contains(&n))390        {391            return Err("numbers are 2 to 64");392        }393        if self.rotations.iter().any(|&r| r > 3) {394            return Err("rotation is 0 to 3");395        }396        if self.flip && self.group != Group::Special {397            return Err("flip is special only");398        }399        if self.group == Group::Fractal {400            if !(1..=MAX_LEVEL).contains(&self.levels[0]) {401                return Err("level is 1 to 6");402            }403        } else if self.levels.iter().any(|&l| l != 1) {404            return Err("level is fractal only");405        }406        if matches!(self.group, Group::Special | Group::Mosaic)407            && !(MIN_SIDE..=MAX_SIDE).contains(&self.factor)408        {409            return Err("factor is 2 to 64");410        }411        if self.group == Group::Mosaic && self.numbers.iter().any(|&n| n != self.numbers[0]) {412            return Err("mosaic shares one number");413        }414        let mut probe = self.clone();415        probe.resize();416        if probe.width != self.width || probe.height != self.height || probe.factor != self.factor {417            return Err("sizes disagree");418        }419        if !(MIN_SIDE..=MAX_SIDE).contains(&self.max_size()) {420            return Err("size is 2 to 64");421        }422        Ok(())423    }424}425426const MIN_FACTOR: usize = 2;427428/// Returns whether every item equals the first, vacuously true for an empty or single list.429///430/// ```431/// assert!(mrlyrs::core::tile::uniform(&[3, 3, 3]));432/// assert!(!mrlyrs::core::tile::uniform(&[3, 5, 3]));433/// ```434pub fn uniform<T: PartialEq>(items: &[T]) -> bool {435    items.windows(2).all(|pair| pair[0] == pair[1])436}437438fn factors(min_factor: usize, max_factor: usize, parity: Parity) -> Vec<usize> {439    (min_factor.max(MIN_FACTOR)..=max_factor)440        .filter(|&n| parity.keep(n))441        .collect()442}443444/// Returns every flat size in the range that passes the parity filter.445pub fn generals(min_size: usize, max_size: usize, parity: Parity) -> Vec<usize> {446    factors(min_size, max_size, parity)447}448449/// Returns every factor and level whose power lands in the size range.450pub fn powers(min_size: usize, max_size: usize, parity: Parity) -> Vec<(usize, usize)> {451    let mut out = Vec::new();452    for n in factors(MIN_FACTOR, max_size, parity) {453        let mut level = 2;454        loop {455            match n.checked_pow(level as u32) {456                Some(size) if size <= max_size => {457                    if size >= min_size {458                        out.push((n, level));459                    }460                    level += 1;461                }462                _ => break,463            }464        }465    }466    out467}468469/// Returns the side a factor raised to a level makes, or None when no usize holds it.470///471/// ```472/// assert_eq!(mrlyrs::core::tile::size(3, 3), Some(27));473/// assert_eq!(mrlyrs::core::tile::size(3, 4294967298), None);474/// ```475pub fn size(number: i64, level: i64) -> Option<usize> {476    let number = usize::try_from(number).ok()?;477    let level = u32::try_from(level).ok()?;478    number.checked_pow(level)479}480481/// Returns every count-long factor list whose product lands in the size range.482pub fn products(min_size: usize, max_size: usize, count: usize, parity: Parity) -> Vec<Vec<usize>> {483    if count < 1 {484        return Vec::new();485    }486    fn walk(487        min_size: usize,488        max_size: usize,489        remaining: usize,490        parity: Parity,491        out: &mut Vec<Vec<usize>>,492    ) {493        if remaining == 1 {494            for n in factors(min_size, max_size, parity) {495                out.push(vec![n]);496            }497            return;498        }499        for n in factors(MIN_FACTOR, max_size, parity) {500            let next_min = min_size.div_ceil(n);501            let next_max = max_size / n;502            if next_max < MIN_FACTOR {503                continue;504            }505            let mut tails = Vec::new();506            walk(next_min, next_max, remaining - 1, parity, &mut tails);507            for tail in tails {508                let mut item = vec![n];509                item.extend(tail);510                out.push(item);511            }512        }513    }514    let mut out = Vec::new();515    walk(min_size, max_size, count, parity, &mut out);516    out517}518519/// Returns every factor list of depth two and beyond whose product lands in the size range.520pub fn nestings(min_size: usize, max_size: usize, parity: Parity) -> Vec<Vec<usize>> {521    let mut out = Vec::new();522    let mut depth = 2;523    loop {524        let found = products(min_size, max_size, depth, parity);525        if found.is_empty() {526            if depth > 2 {527                break;528            }529            depth += 1;530            if depth > max_size {531                break;532            }533            continue;534        }535        out.extend(found);536        depth += 1;537    }538    out539}540541#[cfg(test)]542mod tests {543    use super::*;544    use crate::core::json;545    #[test]546    fn parity_filters() {547        assert!(Parity::Odds.keep(3));548        assert!(!Parity::Odds.keep(4));549        assert!(Parity::Evens.keep(4));550        assert!(!Parity::Evens.keep(3));551        assert!(Parity::Both.keep(3));552        assert!(Parity::Both.keep(4));553    }554    #[test]555    fn generals_respects_parity_and_range() {556        assert_eq!(generals(3, 9, Parity::Odds), vec![3, 5, 7, 9]);557        assert_eq!(generals(3, 9, Parity::Evens), vec![4, 6, 8]);558        assert_eq!(generals(3, 9, Parity::Both), vec![3, 4, 5, 6, 7, 8, 9]);559    }560    #[test]561    fn powers_are_in_range() {562        for (n, level) in powers(3, 100, Parity::Odds) {563            let size = n.pow(level as u32);564            assert!((3..=100).contains(&size));565            assert!(level >= 2);566        }567        assert!(powers(3, 100, Parity::Odds).contains(&(3, 2)));568        assert!(powers(3, 100, Parity::Odds).contains(&(3, 4)));569    }570    #[test]571    fn products_multiply_into_range() {572        for option in products(3, 64, 2, Parity::Odds) {573            let size: usize = option.iter().product();574            assert!((3..=64).contains(&size));575            assert_eq!(option.len(), 2);576        }577    }578    #[test]579    fn nestings_go_deeper_than_two() {580        let deep = nestings(3, 300, Parity::Odds);581        assert!(deep.iter().any(|opt| opt.len() >= 3));582        for option in &deep {583            let size: usize = option.iter().product();584            assert!(size <= 300);585        }586    }587    #[test]588    fn tile_json_round_trips() {589        let mut tile = Tile::new(Group::Magic).size(45, 45);590        tile.sources = vec![Source::Classic(Design::Carpet), Source::Code(14)];591        tile.numbers = vec![5, 9];592        tile.levels = vec![1, 1];593        tile.rotations = vec![0, 0];594        tile.anti = vec![false, true];595        tile.factor = 5;596        let json = serde_json::to_value(&tile).unwrap();597        assert_eq!(json["group"], "Magic");598        assert_eq!(json["sources"][1], json!({ "code": "14" }));599        let back: Tile = serde_json::from_value(json).unwrap();600        assert_eq!(tile, back);601    }602    #[test]603    fn source_json_round_trips() {604        for source in [Source::Classic(Design::Vtree), Source::Code(232)] {605            let json = serde_json::to_value(source).unwrap();606            let back: Source = serde_json::from_value(json).unwrap();607            assert_eq!(source, back);608        }609    }610    #[test]611    fn source_json_spells_codes_as_strings() {612        let wide = u128::MAX - 1;613        let json = serde_json::to_value(Source::Code(wide)).unwrap();614        assert_eq!(json, json!({ "code": wide.to_string() }));615        let back: Source = serde_json::from_value(json).unwrap();616        assert_eq!(back, Source::Code(wide));617    }618    #[test]619    fn source_json_reads_bare_int_codes() {620        let read = |value| serde_json::from_value::<Source>(value);621        assert_eq!(read(json!({ "code": 7 })).unwrap(), Source::Code(7));622        assert!(read(json!({ "code": "soup" })).is_err());623        assert!(read(json!({ "code": true })).is_err());624        assert!(read(json!({ "design": "Soup" })).is_err());625    }626    #[test]627    fn resize_follows_the_size_law() {628        let mut tile = Tile::new(Group::Fractal);629        tile.sources = vec![Source::Code(7)];630        tile.numbers = vec![3];631        tile.levels = vec![2];632        tile.rotations = vec![0];633        tile.anti = vec![false];634        tile.resize();635        assert_eq!((tile.factor, tile.width, tile.height), (3, 9, 9));636        tile.group = Group::Special;637        tile.factor = 5;638        tile.resize();639        assert_eq!((tile.width, tile.height), (15, 15));640        tile.group = Group::Magic;641        tile.numbers = vec![3, 5];642        tile.resize();643        assert_eq!((tile.factor, tile.width), (3, 15));644    }645    #[test]646    fn resize_survives_empty_and_huge_tiles() {647        let mut bare = Tile::new(Group::Magic);648        bare.resize();649        assert_eq!(bare.width, 1);650        let mut huge = Tile::new(Group::Fractal);651        huge.numbers = vec![3];652        huge.levels = vec![4_294_967_298];653        huge.resize();654        assert_eq!(huge.width, 0);655    }656    #[test]657    fn check_names_the_first_broken_law() {658        let mut tile = Tile::new(Group::General);659        assert_eq!(tile.check(), Err("wrong slot count"));660        tile.sources = vec![Source::Code(7)];661        assert_eq!(tile.check(), Err("ragged slots"));662        tile.numbers = vec![3];663        tile.levels = vec![1];664        tile.rotations = vec![0];665        tile.anti = vec![false];666        tile.resize();667        assert_eq!(tile.check(), Ok(()));668        tile.rotations = vec![4];669        assert_eq!(tile.check(), Err("rotation is 0 to 3"));670        tile.rotations = vec![0];671        tile.flip = true;672        assert_eq!(tile.check(), Err("flip is special only"));673        tile.flip = false;674        tile.width = 5;675        assert_eq!(tile.check(), Err("sizes disagree"));676    }677    #[test]678    fn powers_generalize_beyond_classic_bases() {679        let options = powers(3, 1000, Parity::Odds);680        assert!(options.contains(&(3, 2)));681        assert!(options.contains(&(5, 2)));682        assert!(options.contains(&(7, 2)));683        assert!(options.contains(&(9, 2)));684        assert!(options.contains(&(13, 2)));685    }686    #[test]687    fn size_refuses_what_it_cannot_hold() {688        assert_eq!(size(3, 3), Some(27));689        assert_eq!(size(3, 0), Some(1));690        assert_eq!(size(-1, 2), None);691        assert_eq!(size(3, -1), None);692        assert_eq!(size(3, 64), None);693        assert_eq!(size(3, 4294967296), None);694        assert_eq!(size(3, 4294967298), None);695    }696    #[test]697    fn degenerate_marks_the_magic_tiles_a_fractal_already_draws() {698        let mut tile = Tile::new(Group::Magic);699        tile.sources = vec![Source::Classic(Design::Carpet); 2];700        tile.numbers = vec![3, 3];701        tile.levels = vec![1, 1];702        tile.rotations = vec![0, 0];703        tile.anti = vec![false, false];704        tile.resize();705        assert_eq!(tile.check(), Ok(()));706        assert!(tile.degenerate());707        tile.numbers = vec![3, 5];708        tile.resize();709        assert!(!tile.degenerate());710        tile.numbers = vec![3, 3];711        tile.sources = vec![Source::Classic(Design::Carpet), Source::Code(7)];712        tile.resize();713        assert!(!tile.degenerate());714    }715    #[test]716    fn degenerate_is_a_magic_law_only() {717        let mut tile = Tile::new(Group::Mosaic);718        tile.sources = vec![Source::Classic(Design::Carpet); 3];719        tile.numbers = vec![3, 3, 3];720        assert!(!tile.degenerate());721        tile.group = Group::General;722        tile.sources = vec![Source::Classic(Design::Carpet)];723        tile.numbers = vec![3];724        assert!(!tile.degenerate());725    }726    #[test]727    fn uniform_holds_for_short_lists() {728        assert!(uniform::<usize>(&[]));729        assert!(uniform(&[3]));730        assert!(uniform(&[3, 3, 3]));731        assert!(!uniform(&[3, 3, 5]));732    }733    #[test]734    fn evens_factors_work() {735        assert!(powers(4, 1000, Parity::Evens)736            .iter()737            .all(|(n, _)| n % 2 == 0));738        assert!(powers(4, 1000, Parity::Evens).contains(&(4, 2)));739        assert!(powers(4, 1000, Parity::Evens).contains(&(6, 2)));740    }741}