use serde::Deserialize;
use serde::de::{self, Deserializer};
use std::fmt;
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct LifeRule {
birth: u16,
survive: u16,
}
impl LifeRule {
pub const LIFE: LifeRule = LifeRule {
birth: bit(3),
survive: bit(2) | bit(3),
};
#[inline]
pub fn next_state(self, alive: bool, live_neighbors: u8) -> bool {
let mask = if alive { self.survive } else { self.birth };
(mask >> live_neighbors) & 1 == 1
}
pub fn to_spec(self) -> String {
let mut spec = String::with_capacity(6);
spec.push('B');
for n in 0..=8u8 {
if (self.birth >> n) & 1 == 1 {
spec.push((b'0' + n) as char);
}
}
spec.push_str("/S");
for n in 0..=8u8 {
if (self.survive >> n) & 1 == 1 {
spec.push((b'0' + n) as char);
}
}
spec
}
pub fn parse(text: &str) -> Result<LifeRule, String> {
let trimmed = text.trim();
if let Some(rule) = named(trimmed) {
return Ok(rule);
}
let lower = trimmed.to_ascii_lowercase();
let (birth_part, survive_part) =
lower.split_once('/').ok_or_else(|| {
Self::parse_error(
text,
"there is no '/' between the B and S sections",
)
})?;
let digits = |part: &str, letter: char| -> Result<u16, String> {
let part = part.trim();
let rest = part.strip_prefix(letter).ok_or_else(|| {
Self::parse_error(
text,
&format!("the section after '/' does not start with {letter}"),
)
})?;
let mut mask = 0u16;
for c in rest.chars().filter(|c| !c.is_whitespace()) {
if c == '-' {
continue;
}
let n = c.to_digit(10).filter(|d| *d <= 8).ok_or_else(|| {
Self::parse_error(
text,
&format!(
"'{c}' is not a neighbour count; counts are 0 to 8"
),
)
})?;
mask |= bit(n as u8);
}
Ok(mask)
};
let birth = digits(birth_part, 'b')?;
let survive = digits(survive_part, 's')?;
Ok(LifeRule { birth, survive })
}
fn parse_error(text: &str, reason: &str) -> String {
format!(
"{text:?} is not a Life rule: {reason}. Write one as \
B<births>/S<survivals> -- \"B3/S23\" is Conway's Life, and \"B2/S\" \
is Seeds -- or use one of the names: {}",
named_names().join(", "),
)
}
}
impl fmt::Display for LifeRule {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
f.write_str(&self.to_spec())
}
}
impl Default for LifeRule {
fn default() -> Self {
LifeRule::LIFE
}
}
const fn bit(n: u8) -> u16 {
1 << n
}
pub const NAMED_RULES: &[(&str, &str)] = &[
("life", "B3/S23"),
("highlife", "B36/S23"),
("seeds", "B2/S"),
("diamoeba", "B35678/S5678"),
("morley", "B368/S245"),
("2x2", "B36/S125"),
("maze", "B3/S1235"),
("coral", "B3/S45678"),
("gnarl", "B1/S1"),
("longlife", "B3/S12345"),
("lotka", "B368/S128"),
("34life", "B34/S34"),
("life34", "B34/S34"),
("mazectric", "B3/S23"),
("assimilation", "B345/S4567"),
("coagulations", "B378/S378"),
("move", "B368/S368"),
("periperiodic3", "B12/S12"),
];
fn named(text: &str) -> Option<LifeRule> {
let lower = text.to_ascii_lowercase();
NAMED_RULES
.iter()
.find(|(name, _)| *name == lower)
.and_then(|(_, spec)| LifeRule::parse(spec).ok())
}
fn named_names() -> Vec<&'static str> {
NAMED_RULES.iter().map(|(name, _)| *name).collect()
}
pub fn deserialize_rule<'de, D>(deserializer: D) -> Result<String, D::Error>
where
D: Deserializer<'de>,
{
let text = String::deserialize(deserializer)?;
LifeRule::parse(&text).map_err(de::Error::custom)?;
Ok(text)
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn life_is_born_on_three_and_survives_on_two_or_three() {
let life = LifeRule::LIFE;
for n in 0..=8u8 {
assert_eq!(life.next_state(false, n), n == 3, "birth on {n}");
assert_eq!(
life.next_state(true, n),
n == 2 || n == 3,
"survival on {n}"
);
}
}
#[test]
fn a_literal_b_s_string_is_accepted() {
for spec in [
"B3/S23",
"B36/S23",
"B2/S",
"B35678/S5678",
"B368/S245",
"B36/S125",
"B3/S1235",
"B3/S45678",
"B1/S1",
"B3/S12345",
"B368/S128",
"B34/S34",
] {
let rule =
LifeRule::parse(spec).unwrap_or_else(|e| panic!("{spec}: {e}"));
assert_eq!(
rule.to_spec(),
spec,
"{spec} did not survive a round trip through the parser"
);
}
}
#[test]
fn named_rules_are_their_own_b_s_notation() {
for (name, spec) in NAMED_RULES {
let by_name = LifeRule::parse(name)
.unwrap_or_else(|e| panic!("{name} did not resolve: {e}"));
let by_spec = LifeRule::parse(spec).unwrap_or_else(|e| {
panic!("{name}'s spec {spec} did not parse: {e}")
});
assert_eq!(
by_name, by_spec,
"the name {name} resolves to a different rule than its own \
notation {spec}"
);
}
}
#[test]
fn highlife_is_life_plus_a_birth_on_six() {
let life = LifeRule::LIFE;
let highlife = LifeRule::parse("highlife").unwrap();
assert!(highlife.next_state(false, 6), "the extra birth on six");
for n in 0..=8u8 {
if n == 6 {
continue;
}
assert_eq!(
highlife.next_state(false, n),
life.next_state(false, n),
"HighLife should differ from Life only at a birth on six, but \
differs at {n}"
);
}
assert_eq!(highlife.survive_mask(), life.survive_mask());
}
#[test]
fn seeds_dies_out_and_life_does_not() {
let seeds = LifeRule::parse("seeds").unwrap();
assert!(seeds.next_state(false, 2), "Seeds is born on exactly two");
assert!(
!seeds.next_state(true, 2) && !seeds.next_state(true, 3),
"Seeds has no survival counts at all"
);
let life = LifeRule::LIFE;
assert!(!life.next_state(false, 2));
assert!(seeds.next_state(false, 2));
}
#[test]
fn a_blinker_oscillates_under_life_and_loses_every_cell_under_seeds() {
let blink =
|(cx, cy): (usize, usize), horizontal: bool| -> Vec<(usize, usize)> {
[-1isize, 0, 1]
.iter()
.map(|d| {
if horizontal {
((cx as isize + d) as usize, cy)
} else {
(cx, (cy as isize + d) as usize)
}
})
.collect()
};
let step =
|cells: &[(usize, usize)], rule: LifeRule| -> Vec<(usize, usize)> {
let mut next = Vec::new();
for y in 0..12usize {
for x in 0..12usize {
let n = cells
.iter()
.filter(|(cx, cy)| {
let dx = (*cx as isize - x as isize).abs();
let dy = (*cy as isize - y as isize).abs();
(dx <= 1 && dy <= 1) && !(dx == 0 && dy == 0)
})
.count() as u8;
let alive = cells.contains(&(x, y));
if rule.next_state(alive, n) {
next.push((x, y));
}
}
}
next
};
let vertical = blink((6, 6), false);
let horizontal = blink((6, 6), true);
assert_eq!(step(&vertical, LifeRule::LIFE), horizontal);
assert_eq!(step(&horizontal, LifeRule::LIFE), vertical);
let after_seeds = step(&vertical, LifeRule::parse("seeds").unwrap());
assert!(
vertical.iter().all(|cell| !after_seeds.contains(cell)),
"every cell that was live should be dead after a Seeds generation"
);
assert!(
!after_seeds.is_empty(),
"Seeds is born on two, so a blinker does leave births behind; if \
this is empty then the birth table is not being consulted"
);
}
#[test]
fn a_bad_rule_is_refused_with_the_value_and_the_alternatives() {
for (bad, expected) in [
("hlghlife", "hlghlife"),
("B3", "no '/'"),
("B3/S2x", "not a neighbour count"),
("B9/S23", "not a neighbour count"),
("", "no '/'"),
] {
let error = LifeRule::parse(bad).unwrap_err();
assert!(
error.contains(expected),
"parsing {bad:?} should mention {expected:?}, got: {error}"
);
assert!(
error.contains("highlife"),
"the message for {bad:?} should list the names it accepts, got: \
{error}"
);
}
}
#[test]
fn a_dash_means_no_counts() {
assert_eq!(
LifeRule::parse("B2/S-").unwrap(),
LifeRule::parse("B2/S").unwrap()
);
assert_eq!(
LifeRule::parse("B2/S-").unwrap(),
LifeRule::parse("seeds").unwrap()
);
}
#[test]
fn spacing_and_case_do_not_matter() {
let canonical = LifeRule::LIFE;
for spelling in [
"life", "LIFE", "Life", " life ", "B3/S23", "b3/s23", "B3 / S23",
] {
assert_eq!(
LifeRule::parse(spelling)
.unwrap_or_else(|e| panic!("{spelling:?}: {e}")),
canonical,
"{spelling:?} should be Conway's Life"
);
}
}
impl LifeRule {
fn survive_mask(self) -> u16 {
self.survive
}
}
}