year2015/
day18.rs

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

year2015/
day18.rs
