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