life_backend/
rule.rs

1use std::error::Error;
2use std::fmt;
3use std::str::FromStr;
4
5const TRUTH_TABLE_SIZE: usize = 9;
6
7/// A representation of a rule of [Life-like cellular automata](https://conwaylife.com/wiki/Life-like_cellular_automaton).
8///
9/// The following operations are supported:
10///
11/// - Constructing from a pair of truth tables
12/// - Parsing a string into a value of this type, e.g., `"B3/S23"`.
13///   The following notations are supported, see [Rulestring](https://conwaylife.com/wiki/Rulestring):
14///   - The birth/survival notation (e.g., `"B3/S23"`). Lowercase `'b'` or `'s'` are also allowed in the notation instead of `'B'` or `'S'`
15///   - S/B notation (e.g., `"23/3"`)
16/// - Determining whether a new cell will be born from the specified number of alive neighbors
17/// - Determining whether a cell surrounded by the specified number of alive neighbors will survive
18/// - Converting into a [`String`] value, e.g., `"B3/S23"`.
19///   This operation only supports the birth/survival notation
20///
21/// [`String`]: std::string::String
22///
23/// # Examples
24///
25/// ```
26/// use life_backend::Rule;
27/// # fn main() -> Result<(), Box<dyn std::error::Error>> {
28/// let rule = "B3/S23".parse::<Rule>()?;
29/// for i in 0..=8 {
30///     assert_eq!(rule.is_born(i), [3].iter().any(|&x| x == i));
31///     assert_eq!(rule.is_survive(i), [2, 3].iter().any(|&x| x == i));
32/// }
33/// assert_eq!(format!("{rule}"), "B3/S23");
34/// # Ok(())
35/// # }
36/// ```
37///
38#[derive(Clone, PartialEq, Eq, Debug)]
39pub struct Rule {
40    birth: [bool; TRUTH_TABLE_SIZE],
41    survival: [bool; TRUTH_TABLE_SIZE],
42}
43
44// Inherent methods
45
46impl Rule {
47    /// Creates a new rule based on the specified pair of truth tables.
48    ///
49    /// # Examples
50    ///
51    /// ```
52    /// use life_backend::Rule;
53    /// let rule = Rule::new(
54    ///     &[false, false, false, true, false, false, false, false, false],
55    ///     &[false, false, true, true, false, false, false, false, false],
56    /// );
57    /// let b = [3];
58    /// let s = [2, 3];
59    /// for i in 0..=8 {
60    ///     assert_eq!(rule.is_born(i), b.iter().any(|&x| x == i));
61    ///     assert_eq!(rule.is_survive(i), s.iter().any(|&x| x == i));
62    /// }
63    /// ```
64    ///
65    pub const fn new(birth: &[bool; 9], survival: &[bool; 9]) -> Self {
66        Self {
67            birth: *birth,
68            survival: *survival,
69        }
70    }
71
72    /// Returns whether a new cell will be born from the specified number of alive neighbors.
73    ///
74    /// # Panics
75    ///
76    /// Panics if the argument `count` is greater than 8.
77    ///
78    /// # Examples
79    ///
80    /// ```
81    /// use life_backend::Rule;
82    /// let rule = Rule::conways_life();
83    /// let b = [3];
84    /// for i in 0..=8 {
85    ///     assert_eq!(rule.is_born(i), b.iter().any(|&x| x == i));
86    /// }
87    /// ```
88    ///
89    #[inline]
90    pub const fn is_born(&self, count: usize) -> bool {
91        self.birth[count]
92    }
93
94    /// Returns whether a cell surrounded by the specified number of alive neighbors will survive.
95    ///
96    /// # Panics
97    ///
98    /// Panics if the argument `count` is greater than 8.
99    ///
100    /// # Examples
101    ///
102    /// ```
103    /// use life_backend::Rule;
104    /// let rule = Rule::conways_life();
105    /// let s = [2, 3];
106    /// for i in 0..=8 {
107    ///     assert_eq!(rule.is_survive(i), s.iter().any(|&x| x == i));
108    /// }
109    /// ```
110    ///
111    #[inline]
112    pub const fn is_survive(&self, count: usize) -> bool {
113        self.survival[count]
114    }
115
116    /// Returns the rule of [Conway's Game of Life](https://conwaylife.com/wiki/Conway%27s_Game_of_Life).
117    ///
118    /// # Examples
119    ///
120    /// ```
121    /// use life_backend::Rule;
122    /// let rule = Rule::conways_life();
123    /// let b = [3];
124    /// let s = [2, 3];
125    /// for i in 0..=8 {
126    ///     assert_eq!(rule.is_born(i), b.iter().any(|&x| x == i));
127    ///     assert_eq!(rule.is_survive(i), s.iter().any(|&x| x == i));
128    /// }
129    /// ```
130    ///
131    pub const fn conways_life() -> Self {
132        Self::new(
133            &[false, false, false, true, false, false, false, false, false],
134            &[false, false, true, true, false, false, false, false, false],
135        )
136    }
137}
138
139// Trait implementations
140
141impl fmt::Display for Rule {
142    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
143        fn count_slice_numbers(slice: &[bool]) -> usize {
144            slice.iter().filter(|x| **x).count()
145        }
146        fn convert_slice_to_string(slice: &[bool]) -> String {
147            slice
148                .iter()
149                .enumerate()
150                .filter_map(|(i, &x)| if x { Some(i) } else { None })
151                .map(|n| char::from_digit(n as u32, TRUTH_TABLE_SIZE as u32).unwrap()) // this unwrap never panic because `n < TRUTH_TABLE_SIZE` is always guaranteed
152                .collect()
153        }
154        let mut buf = String::with_capacity(count_slice_numbers(&self.birth) + count_slice_numbers(&self.survival));
155        buf += "B";
156        buf += &convert_slice_to_string(&self.birth);
157        buf += "/S";
158        buf += &convert_slice_to_string(&self.survival);
159        f.write_str(&buf)?;
160        Ok(())
161    }
162}
163
164#[derive(Debug)]
165pub struct ParseRuleError;
166
167impl Error for ParseRuleError {}
168
169impl fmt::Display for ParseRuleError {
170    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
171        f.write_str("cannot parse rule from the string")
172    }
173}
174
175impl FromStr for Rule {
176    type Err = ParseRuleError;
177    fn from_str(s: &str) -> Result<Self, Self::Err> {
178        fn convert_numbers_to_slice(numbers: &str) -> Option<[bool; TRUTH_TABLE_SIZE]> {
179            numbers.chars().try_fold([false; TRUTH_TABLE_SIZE], |mut buf, c| {
180                let n = c.to_digit(TRUTH_TABLE_SIZE as u32)? as usize;
181                buf[n] = true;
182                Some(buf)
183            })
184        }
185        let fields_splitted: Vec<_> = s.split('/').collect();
186        if fields_splitted.len() != 2 {
187            return Err(ParseRuleError);
188        }
189        let (labels, numbers): (Vec<_>, Vec<_>) = fields_splitted
190            .iter()
191            .map(|s| s.split_at(s.find(|c: char| c.is_ascii_digit()).unwrap_or(s.len())))
192            .unzip();
193        let numbers = if labels.iter().zip(["B", "S"]).all(|(lhs, rhs)| lhs.eq_ignore_ascii_case(rhs)) {
194            // the birth/survival notation, e.g., "B3/S23"
195            numbers
196        } else if labels.iter().all(|s| s.is_empty()) {
197            // S/B notation, e.g., "23/3"
198            vec![numbers[1], numbers[0]]
199        } else {
200            return Err(ParseRuleError);
201        };
202        let Some(slices) = numbers
203            .into_iter()
204            .map(convert_numbers_to_slice)
205            .collect::<Option<Vec<_>>>() else {
206            return Err(ParseRuleError);
207        };
208        Ok(Self {
209            birth: slices[0],
210            survival: slices[1],
211        })
212    }
213}
214
215// Unit tests
216
217#[cfg(test)]
218mod tests {
219    use super::*;
220    use anyhow::Result;
221    const RULE_HIGHLIFE: Rule = Rule::new(
222        &[false, false, false, true, false, false, true, false, false],
223        &[false, false, true, true, false, false, false, false, false],
224    );
225    fn check_value(target: &Rule, expected_birth: &[usize], expected_survival: &[usize]) {
226        for i in 0..=8 {
227            assert_eq!(target.is_born(i), expected_birth.iter().any(|&x| x == i));
228            assert_eq!(target.is_survive(i), expected_survival.iter().any(|&x| x == i));
229        }
230    }
231    #[test]
232    fn new_conways_life() {
233        let target = Rule::new(
234            &[false, false, false, true, false, false, false, false, false],
235            &[false, false, true, true, false, false, false, false, false],
236        );
237        check_value(&target, &[3], &[2, 3]);
238    }
239    #[test]
240    fn new_highlife() {
241        let target = Rule::new(
242            &[false, false, false, true, false, false, true, false, false],
243            &[false, false, true, true, false, false, false, false, false],
244        );
245        check_value(&target, &[3, 6], &[2, 3]);
246    }
247    #[test]
248    fn conways_life() {
249        let target = Rule::conways_life();
250        check_value(&target, &[3], &[2, 3]);
251    }
252    #[test]
253    fn display_conways_life() {
254        let target = Rule::conways_life();
255        assert_eq!(target.to_string(), "B3/S23");
256    }
257    #[test]
258    fn display_highlife() {
259        let target = RULE_HIGHLIFE;
260        assert_eq!(target.to_string(), "B36/S23");
261    }
262    #[test]
263    fn from_str_birth_survival_notation() -> Result<()> {
264        let target: Rule = "B3/S23".parse()?;
265        check_value(&target, &[3], &[2, 3]);
266        Ok(())
267    }
268    #[test]
269    fn from_str_s_b_notation() -> Result<()> {
270        let target: Rule = "23/3".parse()?;
271        check_value(&target, &[3], &[2, 3]);
272        Ok(())
273    }
274    #[test]
275    fn from_str_birth_survival_notation_without_birth_number() -> Result<()> {
276        let target: Rule = "B/S23".parse()?;
277        check_value(&target, &[], &[2, 3]);
278        Ok(())
279    }
280    #[test]
281    fn from_str_birth_survival_notation_without_survival_number() -> Result<()> {
282        let target: Rule = "B3/S".parse()?;
283        check_value(&target, &[3], &[]);
284        Ok(())
285    }
286    #[test]
287    fn from_str_birth_survival_notation_lowercase_b() -> Result<()> {
288        let target: Rule = "b3/S23".parse()?;
289        check_value(&target, &[3], &[2, 3]);
290        Ok(())
291    }
292    #[test]
293    fn from_str_birth_survival_notation_lowercase_s() -> Result<()> {
294        let target: Rule = "B3/s23".parse()?;
295        check_value(&target, &[3], &[2, 3]);
296        Ok(())
297    }
298    #[test]
299    fn from_str_no_separator() {
300        let target = "B0S0".parse::<Rule>();
301        assert!(target.is_err());
302    }
303    #[test]
304    fn from_str_too_many_separators() {
305        let target = "B0/S0/C0".parse::<Rule>();
306        assert!(target.is_err());
307    }
308    #[test]
309    fn from_str_no_label_birth() {
310        let target = "0/S0".parse::<Rule>();
311        assert!(target.is_err());
312    }
313    #[test]
314    fn from_str_no_label_survival() {
315        let target = "B0/0".parse::<Rule>();
316        assert!(target.is_err());
317    }
318    #[test]
319    fn from_str_birth_survival_notation_too_large_number() {
320        let target = "B9/S0".parse::<Rule>();
321        assert!(target.is_err());
322    }
323}
life_backend/rule.rs

life_backend/
rule.rs
