year2015/
day18.rs

1use utils::grid;
2use utils::prelude::*;
3
4/// Game of Life.
5#[derive(Clone, Debug)]
6pub struct Day18 {
7    data: Vec<bool>,
8    size: usize,
9    part1_steps: u32,
10    part2_steps: u32,
11}
12
13impl Day18 {
14    pub fn new(input: &str, input_type: InputType) -> Result<Self, InputError> {
15        let (rows, columns, data) = grid::parse(
16            input,
17            1,
18            false,
19            |b| b == b'#',
20            |b| b == b'#' || b == b'.',
21            |_, _| Err("expected '.' or '#'"),
22        )?;
23
24        if rows != columns {
25            return Err(InputError::new(input, input, "expected square grid"));
26        }
27
28        let (part1_steps, part2_steps) = match input_type {
29            InputType::Example => (4, 5),
30            InputType::Real => (100, 100),
31        };
32
33        Ok(Self {
34            size: rows,
35            data,
36            part1_steps,
37            part2_steps,
38        })
39    }
40
41    #[must_use]
42    pub fn part1(&self) -> u32 {
43        self.count_lights(self.part1_steps, |_| {})
44    }
45
46    #[must_use]
47    pub fn part2(&self) -> u32 {
48        let top_left = self.size + 1;
49        let top_right = self.size + (self.size - 2);
50        let bottom_left = (self.size - 2) * self.size + 1;
51        let bottom_right = (self.size - 2) * self.size + (self.size - 2);
52
53        self.count_lights(self.part2_steps, |grid| {
54            grid[top_left] = true;
55            grid[top_right] = true;
56            grid[bottom_left] = true;
57            grid[bottom_right] = true;
58        })
59    }
60
61    fn count_lights(&self, steps: u32, callback: impl Fn(&mut [bool])) -> u32 {
62        let mut grid = self.data.clone();
63        let mut grid2 = vec![false; grid.len()];
64
65        callback(&mut grid);
66
67        for _ in 0..steps {
68            self.advance(&grid, &mut grid2);
69            callback(&mut grid2);
70            (grid, grid2) = (grid2, grid);
71        }
72
73        grid.iter().copied().filter(|&x| x).count() as u32
74    }
75
76    fn advance(&self, input: &[bool], output: &mut [bool]) {
77        // Avoids bounds checks, allowing the inner loop to be vectorized
78        for (((above, row), below), out) in input
79            .chunks_exact(self.size)
80            .zip(input.chunks_exact(self.size).skip(1))
81            .zip(input.chunks_exact(self.size).skip(2))
82            .zip(output.chunks_exact_mut(self.size).skip(1))
83        {
84            for i in 1..self.size - 1 {
85                let neighbours = u8::from(above[i - 1])
86                    + u8::from(above[i])
87                    + u8::from(above[i + 1])
88                    + u8::from(row[i - 1])
89                    + u8::from(row[i + 1])
90                    + u8::from(below[i - 1])
91                    + u8::from(below[i])
92                    + u8::from(below[i + 1]);
93                out[i] = (neighbours | u8::from(row[i])) == 3;
94            }
95        }
96    }
97}
98
99examples!(Day18 -> (u32, u32) [
100    {input: ".#.#.#\n...##.\n#....#\n..#...\n#.#..#\n####..", part1: 4, part2: 17},
101]);
year2015/day18.rs

year2015/
day18.rs
