year2020/
day11.rs

1use utils::bit::bitwise_count8;
2use utils::grid;
3use utils::prelude::*;
4
5/// Simulating a cellular automaton with line-of-sight rules.
6#[derive(Clone, Debug)]
7pub struct Day11 {
8    cols: usize,
9    seats: Vec<u128>,
10}
11
12const MAX_COLS: usize = u128::BITS as usize - 2;
13
14impl Day11 {
15    pub fn new(input: &str, _: InputType) -> Result<Self, InputError> {
16        // Bitmask per row with 1 bit of padding on each side, plus padding rows above and below
17        let mut seats = vec![0u128];
18        let (_, cols) = grid::for_each_row(
19            input,
20            |b| matches!(b, b'.' | b'L'),
21            || "expected '.' or 'L'",
22            |row, cols, row_bytes| {
23                if row == 0 && cols > MAX_COLS {
24                    return Err(InputError::new(
25                        input,
26                        row_bytes,
27                        format!("expected at most {MAX_COLS} columns"),
28                    ));
29                }
30
31                let bits = row_bytes
32                    .iter()
33                    .rfold(0u128, |acc, &b| (acc << 1) | u128::from(b == b'L'));
34                seats.push(bits << 1);
35
36                Ok(())
37            },
38        )?;
39        seats.push(0);
40
41        Ok(Self { cols, seats })
42    }
43
44    #[must_use]
45    pub fn part1(&self) -> u32 {
46        let rows = self.seats.len();
47        let mut first = self.seats.clone();
48        let mut second = vec![0u128; rows];
49        let (mut grid, mut next) = (&mut first, &mut second);
50
51        loop {
52            for row in 1..rows - 1 {
53                let (above, middle, below) = (grid[row - 1], grid[row], grid[row + 1]);
54
55                let [bit0, bit1, bit2, bit3] = bitwise_count8(&[
56                    above << 1,
57                    above,
58                    above >> 1,
59                    middle << 1,
60                    middle >> 1,
61                    below << 1,
62                    below,
63                    below >> 1,
64                ]);
65
66                let none = !(bit0 | bit1 | bit2 | bit3);
67                let gte4 = bit2 | bit3;
68                next[row] = self.seats[row] & (none | (middle & !gte4));
69            }
70
71            if next == grid {
72                return grid.iter().map(|m| m.count_ones()).sum();
73            }
74            (grid, next) = (next, grid);
75        }
76    }
77
78    #[must_use]
79    pub fn part2(&self) -> u32 {
80        let rows = self.seats.len();
81        let col_mask = ((1u128 << self.cols) - 1) << 1;
82        let floor = self
83            .seats
84            .iter()
85            .map(|&s| col_mask & !s)
86            .collect::<Vec<_>>();
87
88        let mut first = self.seats.clone();
89        let mut second = vec![0u128; rows];
90        let (mut grid, mut next) = (&mut first, &mut second);
91        let mut above_nw = vec![0u128; rows];
92        let mut above_n = vec![0u128; rows];
93        let mut above_ne = vec![0u128; rows];
94
95        loop {
96            // Iterate down the grid to find the seats visible above each row
97            let (mut nw, mut n, mut ne) = (0, 0, 0);
98            for row in 1..rows - 1 {
99                let (above, above_floor) = (grid[row - 1], floor[row - 1]);
100                nw = (above | (above_floor & nw)) << 1;
101                n = above | (above_floor & n);
102                ne = (above | (above_floor & ne)) >> 1;
103                above_nw[row] = nw;
104                above_n[row] = n;
105                above_ne[row] = ne;
106            }
107
108            // Iterate back up the grid to find the seats visible below each row
109            let (mut sw, mut s, mut se) = (0, 0, 0);
110            for row in (1..rows - 1).rev() {
111                let (below, below_floor) = (grid[row + 1], floor[row + 1]);
112                sw = (below | (below_floor & sw)) << 1;
113                s = below | (below_floor & s);
114                se = (below | (below_floor & se)) >> 1;
115
116                let (nw, n, ne) = (above_nw[row], above_n[row], above_ne[row]);
117                let middle = grid[row];
118
119                // Adding the occupied mask shifted 1 bit east to the floor mask carries through
120                // the floor and stops at the next seat. XOR with the floor mask then sets every
121                // cell that can see an occupied seat to its west.
122                let w = floor[row].wrapping_add(middle << 1) ^ floor[row];
123
124                // Carries only propagate east, so find cells that can see an occupied seat to
125                // their east by repeatedly shifting the occupied mask west
126                let mut e = middle >> 1;
127                let mut pending = e;
128                while pending != 0 {
129                    pending = (pending >> 1) & (floor[row] >> 1);
130                    e |= pending;
131                }
132
133                let [bit0, bit1, bit2, bit3] = bitwise_count8(&[nw, n, ne, w, e, sw, s, se]);
134                let none = !(bit0 | bit1 | bit2 | bit3);
135                let gte5 = bit3 | (bit2 & (bit0 | bit1));
136                next[row] = self.seats[row] & (none | (middle & !gte5));
137            }
138
139            if next == grid {
140                return grid.iter().map(|m| m.count_ones()).sum();
141            }
142            (grid, next) = (next, grid);
143        }
144    }
145}
146
147examples!(Day11 -> (u32, u32) [
148    {file: "day11_example0.txt", part1: 37, part2: 26},
149]);
year2020/day11.rs

year2020/
day11.rs
