source.rs
21.1 kB · rust · 612 lines
1use crate::core::error::{value_error, Result};2use crate::core::rng::Rng;3use crate::math::bang::Code;4use crate::math::counts;5use crate::math::two::{self, census};6use crate::num::prime;7use crate::num::series;8use serde::{Deserialize, Serialize};910const DIM: usize = 2;11const BASE: usize = 2;1213/// A named source of neighbor-count values.14///15/// | Source | OEIS |16/// |---|---|17/// | Evens | A005843 |18/// | Odds | A005408 |19/// | Primes | A000040 |20/// | Binary | A000079 |21/// | Fibonacci | A000045 |22/// | GridSquares | A016754 |23///24/// Random, the other mrly families and the code families carry no OEIS id.25#[derive(Clone, Copy, Debug, PartialEq, Eq, Serialize, Deserialize)]26pub enum Source {27 /// The even numbers.28 Evens,29 /// The odd numbers.30 Odds,31 /// The random subset its seed draws.32 Random(u64),33 /// The primes.34 Primes,35 /// The powers of two.36 Binary,37 /// The Fibonacci numbers.38 Fibonacci,39 /// The squares of the odd numbers.40 GridSquares,41 /// The carpet fill counts.42 CarpetFills,43 /// The carpet void counts.44 CarpetVoids,45 /// The net fill counts.46 NetFills,47 /// The net void counts.48 NetVoids,49 /// The H-tree fill counts.50 TreeFills,51 /// The H-tree void counts.52 TreeVoids,53 /// The void design fill counts.54 VoidFills,55 /// The void design void counts.56 VoidVoids,57 /// The point fill counts.58 PointFills,59 /// The point void counts.60 PointVoids,61 /// The dust fill counts.62 DustFills,63 /// The dust void counts.64 DustVoids,65 /// The H-line fill counts.66 LineFills,67 /// The H-line void counts.68 LineVoids,69 /// The star fill counts.70 StarFills,71 /// The star void counts.72 StarVoids,73 /// The fill counts of a coded design.74 CodeFills(u128),75 /// The void counts of a coded design.76 CodeVoids(u128),77}7879impl Source {80 /// Returns the sequence's parseable name, the one string that regenerates it.81 pub fn name(self) -> String {82 let fixed = match self {83 Source::Evens => "evens",84 Source::Odds => "odds",85 Source::Random(seed) => return format!("random_{seed}"),86 Source::Primes => "primes",87 Source::Binary => "binary",88 Source::Fibonacci => "fibonacci",89 Source::GridSquares => "grid_squares",90 Source::CarpetFills => "carpet_fills",91 Source::CarpetVoids => "carpet_voids",92 Source::NetFills => "net_fills",93 Source::NetVoids => "net_voids",94 Source::TreeFills => "tree_fills",95 Source::TreeVoids => "tree_voids",96 Source::VoidFills => "void_fills",97 Source::VoidVoids => "void_voids",98 Source::PointFills => "point_fills",99 Source::PointVoids => "point_voids",100 Source::DustFills => "dust_fills",101 Source::DustVoids => "dust_voids",102 Source::LineFills => "line_fills",103 Source::LineVoids => "line_voids",104 Source::StarFills => "star_fills",105 Source::StarVoids => "star_voids",106 Source::CodeFills(code) => return format!("code_fills_{code}"),107 Source::CodeVoids(code) => return format!("code_voids_{code}"),108 };109 fixed.to_string()110 }111 /// Parses a sequence name back to its source.112 ///113 /// # Errors114 ///115 /// Errs when the name is not a known sequence, or a code family carries no plain number.116 pub fn parse(name: &str) -> Result<Source> {117 let lower = name.to_lowercase();118 if HEADS.iter().any(|head| lower.starts_with(head)) {119 return match Source::read(&lower) {120 Some((seq, "")) => Ok(seq),121 _ => value_error(format!("sequence {lower:?} wants a plain number.")),122 };123 }124 let seq = match lower.as_str() {125 "evens" => Source::Evens,126 "odds" => Source::Odds,127 "primes" | "prime" => Source::Primes,128 "binary" => Source::Binary,129 "fibonacci" | "fib" => Source::Fibonacci,130 "grid_squares" | "grid" => Source::GridSquares,131 "carpet_fills" => Source::CarpetFills,132 "carpet_voids" => Source::CarpetVoids,133 "net_fills" => Source::NetFills,134 "net_voids" => Source::NetVoids,135 "tree_fills" => Source::TreeFills,136 "tree_voids" => Source::TreeVoids,137 "void_fills" => Source::VoidFills,138 "void_voids" => Source::VoidVoids,139 "point_fills" => Source::PointFills,140 "point_voids" => Source::PointVoids,141 "dust_fills" => Source::DustFills,142 "dust_voids" => Source::DustVoids,143 "line_fills" => Source::LineFills,144 "line_voids" => Source::LineVoids,145 "star_fills" => Source::StarFills,146 "star_voids" => Source::StarVoids,147 other => {148 let alias = Source::all()149 .into_iter()150 .find(|s| s.oeis().is_some_and(|id| id.eq_ignore_ascii_case(other)));151 match alias {152 Some(seq) => seq,153 None => return value_error(format!("unknown sequence {other:?}.")),154 }155 }156 };157 Ok(seq)158 }159 /// Reads a canonical name off the front of the text, returning the tail left over.160 pub fn read(text: &str) -> Option<(Source, &str)> {161 if let Some(rest) = text.strip_prefix("random_") {162 let (seed, tail) = seed_of(rest)?;163 return Some((Source::Random(u64::try_from(seed).ok()?), tail));164 }165 if let Some(rest) = text.strip_prefix("code_fills_") {166 let (code, tail) = seed_of(rest)?;167 return Some((Source::CodeFills(code), tail));168 }169 if let Some(rest) = text.strip_prefix("code_voids_") {170 let (code, tail) = seed_of(rest)?;171 return Some((Source::CodeVoids(code), tail));172 }173 let fixed: Vec<Source> = Source::all()174 .into_iter()175 .filter(|seq| !seq.is_random())176 .collect();177 let names: Vec<String> = fixed.iter().map(|seq| seq.name()).collect();178 let (i, rest) = crate::math::name::text::longest(text, &names)?;179 Some((fixed[i], rest))180 }181 /// Returns every fixed sequence, the seeded and coded families excluded.182 pub fn all() -> [Source; 23] {183 [184 Source::Evens,185 Source::Odds,186 Source::Random(0),187 Source::Primes,188 Source::Binary,189 Source::Fibonacci,190 Source::GridSquares,191 Source::CarpetFills,192 Source::CarpetVoids,193 Source::NetFills,194 Source::NetVoids,195 Source::TreeFills,196 Source::TreeVoids,197 Source::VoidFills,198 Source::VoidVoids,199 Source::PointFills,200 Source::PointVoids,201 Source::DustFills,202 Source::DustVoids,203 Source::LineFills,204 Source::LineVoids,205 Source::StarFills,206 Source::StarVoids,207 ]208 }209 /// Returns the six number sequences, the random one listed under seed zero.210 pub fn numbers() -> [Source; 6] {211 [212 Source::Evens,213 Source::Odds,214 Source::Random(0),215 Source::Primes,216 Source::Binary,217 Source::Fibonacci,218 ]219 }220 /// Returns the seventeen mrly design families: the grid, the four classics and their antis.221 pub fn designs() -> [Source; 17] {222 [223 Source::GridSquares,224 Source::CarpetFills,225 Source::CarpetVoids,226 Source::NetFills,227 Source::NetVoids,228 Source::TreeFills,229 Source::TreeVoids,230 Source::VoidFills,231 Source::VoidVoids,232 Source::PointFills,233 Source::PointVoids,234 Source::DustFills,235 Source::DustVoids,236 Source::LineFills,237 Source::LineVoids,238 Source::StarFills,239 Source::StarVoids,240 ]241 }242 /// Returns the sequence's OEIS id, or None off the encyclopedia.243 pub fn oeis(self) -> Option<&'static str> {244 match self {245 Source::Evens => Some("A005843"),246 Source::Odds => Some("A005408"),247 Source::Primes => Some("A000040"),248 Source::Binary => Some("A000079"),249 Source::Fibonacci => Some("A000045"),250 Source::GridSquares => Some("A016754"),251 _ => None,252 }253 }254 /// Returns whether the sequence is a seeded random draw.255 pub fn is_random(self) -> bool {256 matches!(self, Source::Random(_))257 }258}259260const HEADS: [&str; 3] = ["random_", "code_fills_", "code_voids_"];261262fn seed_of(text: &str) -> Option<(u128, &str)> {263 let end = text.bytes().take_while(u8::is_ascii_digit).count();264 if end == 0 || (end > 1 && text.starts_with('0')) {265 return None;266 }267 Some((text[..end].parse().ok()?, &text[end..]))268}269270fn random_subset(seed: u64, limit: usize) -> Vec<usize> {271 let mut rng = Rng::new(seed);272 let mut options: Vec<usize> = (0..=limit).collect();273 let count = 1 + rng.below(options.len());274 for i in 0..count {275 let j = i + rng.below(options.len() - i);276 options.swap(i, j);277 }278 let mut out = options[..count].to_vec();279 out.sort_unstable();280 out281}282283fn mrly_sequence(limit: usize, count_of: impl Fn(usize) -> Result<usize>) -> Result<Vec<usize>> {284 let mut out = Vec::new();285 let mut number = 1;286 loop {287 let value = count_of(number)?;288 if value > limit {289 break;290 }291 if !out.contains(&value) {292 out.push(value);293 }294 number += 2;295 if number > limit + 3 {296 break;297 }298 }299 out.sort_unstable();300 Ok(out)301}302303/// Generates the sequence's values up to the limit.304///305/// # Errors306///307/// Errs when a design behind the sequence will not build or count.308pub fn sequence(seq: Source, limit: usize) -> Result<Vec<usize>> {309 match seq {310 Source::Evens => Ok(series::evens(limit)),311 Source::Odds => Ok(series::odds(limit)),312 Source::Random(seed) => Ok(random_subset(seed, limit)),313 Source::Primes => Ok(prime::primes(limit)),314 Source::Binary => Ok(series::binary(limit)),315 Source::Fibonacci => Ok(series::fibonacci(limit)),316 Source::GridSquares => mrly_sequence(limit, |n| Ok(n * n)),317 Source::CarpetFills => mrly_sequence(limit, |n| Ok(census::fills(&two::carpet(n, 1)?))),318 Source::CarpetVoids => mrly_sequence(limit, |n| Ok(census::voids(&two::carpet(n, 1)?))),319 Source::NetFills => mrly_sequence(limit, |n| Ok(census::fills(&two::net(n, 1)?))),320 Source::NetVoids => mrly_sequence(limit, |n| Ok(census::voids(&two::net(n, 1)?))),321 Source::TreeFills => mrly_sequence(limit, |n| Ok(census::fills(&two::htree(n, 1)?))),322 Source::TreeVoids => mrly_sequence(limit, |n| Ok(census::voids(&two::htree(n, 1)?))),323 Source::VoidFills => mrly_sequence(limit, |n| Ok(census::fills(&two::void(n, 1)?))),324 Source::VoidVoids => mrly_sequence(limit, |n| Ok(census::voids(&two::void(n, 1)?))),325 Source::PointFills => mrly_sequence(limit, |n| Ok(census::fills(&two::point(n, 1)?))),326 Source::PointVoids => mrly_sequence(limit, |n| Ok(census::voids(&two::point(n, 1)?))),327 Source::DustFills => mrly_sequence(limit, |n| Ok(census::fills(&two::dust(n, 1)?))),328 Source::DustVoids => mrly_sequence(limit, |n| Ok(census::voids(&two::dust(n, 1)?))),329 Source::LineFills => mrly_sequence(limit, |n| Ok(census::fills(&two::hline(n, 1)?))),330 Source::LineVoids => mrly_sequence(limit, |n| Ok(census::voids(&two::hline(n, 1)?))),331 Source::StarFills => mrly_sequence(limit, |n| Ok(census::fills(&two::star(n, 1)?))),332 Source::StarVoids => mrly_sequence(limit, |n| Ok(census::voids(&two::star(n, 1)?))),333 Source::CodeFills(code) => mrly_sequence(limit, |n| {334 Ok(counts::fill(Code::from(code), n, DIM, 1, BASE)? as usize)335 }),336 Source::CodeVoids(code) => mrly_sequence(limit, |n| {337 Ok(counts::void(Code::from(code), n, DIM, 1, BASE)? as usize)338 }),339 }340}341342/// Returns the sequence up to max_neighbors, keeping zeros and ones only on request.343///344/// ```345/// use mrlyrs::life::{counts, Source};346/// assert_eq!(counts(Source::Binary, 8, false, false)?, vec![2, 4, 8]);347/// # Ok::<(), mrlyrs::Error>(())348/// ```349///350/// # Errors351///352/// Errs when a design behind the sequence will not build or count.353pub fn counts(354 seq: Source,355 max_neighbors: usize,356 include_zeros: bool,357 include_ones: bool,358) -> Result<Vec<usize>> {359 let raw = sequence(seq, max_neighbors)?;360 Ok(raw361 .into_iter()362 .filter(|&x| (x != 0 || include_zeros) && (x != 1 || include_ones))363 .collect())364}365366/// The neighbor counts one side of a rule fires on.367///368/// A list spells its counts outright and holds them all; a drawn side names the369/// sequence behind them, so any budget of neighbors rebuilds the same counts.370#[derive(Clone, Debug, PartialEq, Eq, Serialize, Deserialize)]371pub enum Counts {372 /// The counts listed outright.373 List(Vec<usize>),374 /// The counts a named sequence lays down inside the budget.375 Drawn {376 /// The sequence behind the counts.377 seq: Source,378 /// Whether zero stays in the counts.379 zeros: bool,380 /// Whether one stays in the counts.381 ones: bool,382 },383}384385impl Counts {386 /// Builds the counts a sequence lays down, keeping zeros and ones on request.387 pub fn drawn(seq: Source, zeros: bool, ones: bool) -> Counts {388 Counts::Drawn { seq, zeros, ones }389 }390 /// Returns the counts, a drawn side resolved against the mask's neighbor budget.391 ///392 /// # Errors393 ///394 /// Errs when a drawn side's sequence will not build inside the budget.395 pub fn values(&self, budget: usize) -> Result<Vec<usize>> {396 match self {397 Counts::List(list) => {398 let mut out = list.clone();399 out.sort_unstable();400 out.dedup();401 Ok(out)402 }403 Counts::Drawn { seq, zeros, ones } => counts(*seq, budget, *zeros, *ones),404 }405 }406}407408impl From<Vec<usize>> for Counts {409 fn from(list: Vec<usize>) -> Counts {410 Counts::List(list)411 }412}413414#[cfg(test)]415mod tests {416 use super::*;417 #[test]418 fn number_sequences_clip_to_limit() {419 assert_eq!(sequence(Source::Primes, 8).unwrap(), vec![2, 3, 5, 7]);420 assert_eq!(sequence(Source::Binary, 8).unwrap(), vec![1, 2, 4, 8]);421 }422 #[test]423 fn grid_squares_walk() {424 assert_eq!(sequence(Source::GridSquares, 8).unwrap(), vec![1]);425 assert_eq!(sequence(Source::GridSquares, 30).unwrap(), vec![1, 9, 25]);426 }427 #[test]428 fn counts_can_drop_zero_and_one() {429 let c = counts(Source::Evens, 8, false, true).unwrap();430 assert_eq!(c, vec![2, 4, 6, 8]);431 let c = counts(Source::Evens, 8, true, true).unwrap();432 assert_eq!(c, vec![0, 2, 4, 6, 8]);433 }434 #[test]435 fn parse_roundtrips() {436 for s in Source::all() {437 assert_eq!(Source::parse(&s.name()).unwrap(), s);438 }439 }440 #[test]441 fn random_draws_a_seeded_sorted_subset() {442 let a = sequence(Source::Random(42), 8).unwrap();443 let b = sequence(Source::Random(42), 8).unwrap();444 assert_eq!(a, b);445 assert!(!a.is_empty() && a.len() <= 9);446 assert!(a.windows(2).all(|w| w[0] < w[1]));447 assert!(a.iter().all(|&x| x <= 8));448 assert_ne!(sequence(Source::Random(43), 64).unwrap(), a);449 }450 #[test]451 fn a_random_name_regenerates_its_counts() {452 let seq = Source::Random(4848495);453 assert_eq!(seq.name(), "random_4848495");454 let back = Source::parse(&seq.name()).unwrap();455 assert_eq!(back, seq);456 assert_eq!(sequence(back, 48).unwrap(), sequence(seq, 48).unwrap());457 assert!(Source::parse("random").is_err());458 assert!(Source::parse("random_").is_err());459 assert!(Source::parse("random_007").is_err());460 }461 #[test]462 fn read_leaves_the_tail_behind() {463 assert_eq!(464 Source::read("fibonacciz_s3"),465 Some((Source::Fibonacci, "z_s3"))466 );467 assert_eq!(468 Source::read("grid_squares_sgrid_squares"),469 Some((Source::GridSquares, "_sgrid_squares"))470 );471 assert_eq!(472 Source::read("random_12_s3"),473 Some((Source::Random(12), "_s3"))474 );475 assert_eq!(Source::read("fib"), None);476 assert_eq!(Source::read("3"), None);477 }478 #[test]479 fn read_takes_the_longest_name_not_the_first() {480 for short in Source::all() {481 for long in Source::all() {482 if short == long || short.is_random() || long.is_random() {483 continue;484 }485 if !long.name().starts_with(&short.name()) {486 continue;487 }488 let name = long.name();489 assert_eq!(Source::read(&name), Some((long, "")), "{name}");490 }491 }492 assert_eq!(493 Source::read("code_fills_12"),494 Some((Source::CodeFills(12), ""))495 );496 assert_eq!(497 Source::read("random_4848495z_s3"),498 Some((Source::Random(4848495), "z_s3"))499 );500 }501 #[test]502 fn every_fixed_name_reads_back_whole() {503 for seq in Source::all() {504 if seq.is_random() {505 continue;506 }507 let name = seq.name();508 assert_eq!(Source::read(&name), Some((seq, "")), "{name}");509 }510 }511 #[test]512 fn tiers_split_the_fixed_sequences() {513 assert!(Source::numbers().iter().any(|s| s.is_random()));514 assert!(Source::designs().contains(&Source::GridSquares));515 let mut both = Source::numbers().to_vec();516 both.extend(Source::designs());517 assert_eq!(both, Source::all().to_vec());518 }519 #[test]520 fn oeis_aliases_parse_either_case() {521 assert_eq!(Source::parse("A005843").unwrap(), Source::Evens);522 assert_eq!(Source::parse("a000045").unwrap(), Source::Fibonacci);523 assert_eq!(Source::parse("A016754").unwrap(), Source::GridSquares);524 assert!(Source::parse("A999999").is_err());525 }526 #[test]527 fn oeis_ids_roundtrip_through_parse() {528 let mut listed = 0;529 for s in Source::all() {530 if let Some(id) = s.oeis() {531 assert_eq!(Source::parse(id).unwrap(), s);532 listed += 1;533 }534 }535 assert_eq!(listed, 6);536 assert_eq!(Source::Random(0).oeis(), None);537 assert_eq!(Source::CarpetFills.oeis(), None);538 assert_eq!(Source::CodeFills(7).oeis(), None);539 }540 #[test]541 fn names_stay_canonical() {542 let expected = [543 "evens",544 "odds",545 "random_0",546 "primes",547 "binary",548 "fibonacci",549 "grid_squares",550 "carpet_fills",551 "carpet_voids",552 "net_fills",553 "net_voids",554 "tree_fills",555 "tree_voids",556 "void_fills",557 "void_voids",558 ];559 for (s, want) in Source::all().into_iter().zip(expected) {560 assert_eq!(s.name(), want);561 }562 }563 #[test]564 fn code_sequences_match_formulas() {565 use crate::math::counts;566 for code in [1u128, 7, 14, 15] {567 let seq = sequence(Source::CodeFills(code), 50).unwrap();568 let expected: Vec<usize> = {569 let mut v = Vec::new();570 let mut n = 1;571 while n <= 53 {572 let f = counts::fill(Code::from(code), n, 2, 1, 2).unwrap() as usize;573 if f <= 50 && !v.contains(&f) {574 v.push(f);575 }576 n += 2;577 }578 v.sort_unstable();579 v580 };581 assert_eq!(seq, expected, "code {code}");582 }583 }584 #[test]585 fn code_name_roundtrips() {586 let s = Source::CodeVoids(9);587 assert_eq!(s.name(), "code_voids_9");588 assert_eq!(Source::parse("code_fills_7").unwrap(), Source::CodeFills(7));589 assert!(Source::parse("code_fills_x").is_err());590 }591 #[test]592 fn counts_carry_a_list_or_a_sequence() {593 let listed = Counts::from(vec![3, 3, 1]);594 assert_eq!(listed.values(8).unwrap(), vec![1, 3]);595 let drawn = Counts::drawn(Source::Fibonacci, false, false);596 assert_eq!(drawn.values(8).unwrap(), vec![2, 3, 5, 8]);597 let wide = Counts::drawn(Source::Fibonacci, true, true);598 assert_eq!(wide.values(24).unwrap(), vec![0, 1, 2, 3, 5, 8, 13, 21]);599 }600 #[test]601 fn refuses_counts() {602 assert!(counts(Source::CodeFills(1 << 20), 8, true, true).is_err());603 assert!(counts(Source::CodeVoids(1 << 20), 8, true, true).is_err());604 assert!(Counts::drawn(Source::CodeFills(1 << 20), false, false)605 .values(8)606 .is_err());607 assert_eq!(608 counts(Source::Evens, 0, false, false).unwrap(),609 Vec::<usize>::new()610 );611 }612}