year2017/
day22.rs

1use utils::geometry::Direction;
2use utils::grid;
3use utils::prelude::*;
4
5/// Simulating virus spread through a grid.
6#[derive(Clone, Debug)]
7pub struct Day22 {
8    size: usize,
9    grid: Vec<State>,
10}
11
12#[derive(Copy, Clone, Debug, PartialEq)]
13enum State {
14    // The enum discriminants are set such that:
15    // - The next direction can be found by adding the current state and direction (mod 4)
16    // - The next state in part 1 is found by adding 2 (mod 4), cycling between Clean and Infected
17    // - The next state in part 2 is found by adding 1 (mod 4)
18    // They must also match the From implementation
19    Clean = 3,
20    Weakened = 0,
21    Infected = 1,
22    Flagged = 2,
23}
24
25const PADDING: usize = 250;
26
27impl Day22 {
28    pub fn new(input: &str, _: InputType) -> Result<Self, InputError> {
29        let (rows, cols, grid) = grid::parse(
30            input,
31            0,
32            State::Weakened,
33            |b| {
34                if b == b'.' {
35                    State::Clean
36                } else {
37                    State::Infected
38                }
39            },
40            |b| matches!(b, b'.' | b'#'),
41            |_, _| Err("expected '.', '#'"),
42        )?;
43        if rows != cols || rows.is_multiple_of(2) {
44            return Err(InputError::new(input, 0, "expected odd size square grid"));
45        }
46        Ok(Self { size: rows, grid })
47    }
48
49    #[must_use]
50    pub fn part1(&self) -> u32 {
51        self.simulate(10_000, |state| State::from(state as usize + 2))
52    }
53
54    #[must_use]
55    pub fn part2(&self) -> u32 {
56        self.simulate(10_000_000, |state| State::from(state as usize + 1))
57    }
58
59    fn simulate(&self, bursts: u32, next_state: impl Fn(State) -> State) -> u32 {
60        let size = self.size + (2 * PADDING);
61        let mut grid = vec![State::Clean; size * size];
62
63        for row in 0..self.size {
64            let offset = ((PADDING + row) * size) + PADDING;
65            grid[offset..offset + self.size]
66                .copy_from_slice(&self.grid[row * self.size..(row + 1) * self.size]);
67        }
68
69        let direction_offsets = [-(size as isize), 1, size as isize, -1];
70        let mut direction = Direction::Up;
71        let mut index = grid.len() / 2;
72
73        let mut infected_transitions = 0;
74        for _ in 0..bursts {
75            let state = grid[index];
76            let next = next_state(state);
77
78            direction = Direction::from(state as u8 + direction as u8);
79            grid[index] = next;
80            index = index.wrapping_add_signed(direction_offsets[direction as usize]);
81
82            infected_transitions += u32::from(next == State::Infected);
83        }
84
85        infected_transitions
86    }
87}
88
89impl From<usize> for State {
90    #[inline]
91    fn from(value: usize) -> Self {
92        match value % 4 {
93            3 => State::Clean,
94            0 => State::Weakened,
95            1 => State::Infected,
96            2 => State::Flagged,
97            _ => unreachable!(),
98        }
99    }
100}
101
102examples!(Day22 -> (u32, u32) [
103    {input: "..#\n#..\n...", part1: 5587, part2: 2511944},
104]);