aoc/year2022/
day23.rs

1//! # Unstable Diffusion
2//!
3//! We represent elves as bits in a integer then use bitwise operations to efficiently figure
4//! out the movement for multiple elves at once.
5use self::Direction::*;
6use std::ops::{BitAnd, BitAndAssign, BitOr, Not};
7
8/// The initial grid is 70 x 70. Elves stop moving when no other elf is adjacent so the grid
9/// will expand at most 70 in any direction, giving 70 + 70 + 70 = 210 total.
10const HEIGHT: usize = 210;
11
12/// Duct tape two `u128`s together.
13#[derive(Clone, Copy, Default)]
14pub struct U256 {
15    left: u128,
16    right: u128,
17}
18
19impl U256 {
20    fn bit_set(&mut self, offset: usize) {
21        if offset < 128 {
22            self.left |= 1 << (127 - offset);
23        } else {
24            self.right |= 1 << (255 - offset);
25        }
26    }
27
28    fn count_ones(&self) -> u32 {
29        self.left.count_ones() + self.right.count_ones()
30    }
31
32    fn non_zero(&self) -> bool {
33        self.left != 0 || self.right != 0
34    }
35
36    /// Used to find the bounding rectangle for part one.
37    fn min_set(&self) -> Option<u32> {
38        if self.left != 0 {
39            Some(self.left.leading_zeros())
40        } else if self.right != 0 {
41            Some(128 + self.right.leading_zeros())
42        } else {
43            None
44        }
45    }
46
47    /// Used to find the bounding rectangle for part one.
48    fn max_set(&self) -> Option<u32> {
49        if self.right != 0 {
50            Some(255 - self.right.trailing_zeros())
51        } else if self.left != 0 {
52            Some(127 - self.left.trailing_zeros())
53        } else {
54            None
55        }
56    }
57
58    fn left_shift(&self) -> U256 {
59        U256 { left: (self.left << 1) | (self.right >> 127), right: (self.right << 1) }
60    }
61
62    fn right_shift(&self) -> U256 {
63        U256 { left: (self.left >> 1), right: (self.left << 127) | (self.right >> 1) }
64    }
65}
66
67/// Syntactic sugar to provide the regular `&`, `|` and `!` bitwise operator notation.
68impl BitAnd for U256 {
69    type Output = U256;
70
71    fn bitand(self, rhs: U256) -> U256 {
72        U256 { left: self.left & rhs.left, right: self.right & rhs.right }
73    }
74}
75
76impl BitOr for U256 {
77    type Output = U256;
78
79    fn bitor(self, rhs: U256) -> U256 {
80        U256 { left: self.left | rhs.left, right: self.right | rhs.right }
81    }
82}
83
84impl Not for U256 {
85    type Output = U256;
86
87    fn not(self) -> U256 {
88        U256 { left: !self.left, right: !self.right }
89    }
90}
91
92impl BitAndAssign for U256 {
93    fn bitand_assign(&mut self, rhs: U256) {
94        self.left &= rhs.left;
95        self.right &= rhs.right;
96    }
97}
98
99enum Direction {
100    North,
101    South,
102    West,
103    East,
104}
105
106#[derive(Clone, Copy)]
107pub struct Input {
108    grid: [U256; HEIGHT],
109    north: [U256; HEIGHT],
110    south: [U256; HEIGHT],
111    west: [U256; HEIGHT],
112    east: [U256; HEIGHT],
113}
114
115/// Converts the ASCII grid into a bit per elf.
116pub fn parse(input: &str) -> Input {
117    // Enough buffer so that elves won't overflow the edges of the grid.
118    let offset = 70;
119    let raw: Vec<_> = input.lines().map(str::as_bytes).collect();
120    let default = [U256::default(); HEIGHT];
121    let mut grid = default;
122
123    for (y, row) in raw.iter().enumerate() {
124        for (x, col) in row.iter().enumerate() {
125            if *col == b'#' {
126                grid[offset + y].bit_set(offset + x);
127            }
128        }
129    }
130
131    Input { grid, north: default, south: default, west: default, east: default }
132}
133
134pub fn part1(input: &Input) -> u32 {
135    let mut input = *input;
136    let mut order = [North, South, West, East];
137
138    for _ in 0..10 {
139        step(&mut input, &mut order);
140    }
141
142    // Find the bounding rectangle.
143    let grid = input.grid;
144    let elves: u32 = grid.iter().map(U256::count_ones).sum();
145    let min_x = grid.iter().filter_map(U256::min_set).min().unwrap();
146    let max_x = grid.iter().filter_map(U256::max_set).max().unwrap();
147    let min_y = grid.iter().position(U256::non_zero).unwrap() as u32;
148    let max_y = grid.iter().rposition(U256::non_zero).unwrap() as u32;
149
150    (max_x - min_x + 1) * (max_y - min_y + 1) - elves
151}
152
153pub fn part2(input: &Input) -> u32 {
154    let mut input = *input;
155    let mut order = [North, South, West, East];
156    let mut moved = true;
157    let mut count = 0;
158
159    while moved {
160        moved = step(&mut input, &mut order);
161        count += 1;
162    }
163
164    count
165}
166
167fn step(input: &mut Input, order: &mut [Direction]) -> bool {
168    let Input { grid, north, south, west, east } = input;
169    // Optimization to avoid processing empty rows.
170    let start = grid.iter().position(U256::non_zero).unwrap() - 1;
171    let end = grid.iter().rposition(U256::non_zero).unwrap() + 2;
172
173    let mut moved = false;
174
175    let mut prev;
176    // Find horizontal neighbors in each row. To make movement calculations easier
177    // we invert so that a bit is 1 is movement is *possible*.
178    let mut cur = !(grid[0].right_shift() | grid[0] | grid[0].left_shift());
179    let mut next = !(grid[1].right_shift() | grid[1] | grid[1].left_shift());
180
181    for i in start..end {
182        // Calculating neighbors is relatively expensive so re-use results between rows.
183        prev = cur;
184        cur = next;
185        next = !(grid[i + 1].right_shift() | grid[i + 1] | grid[i + 1].left_shift());
186
187        let mut up = prev;
188        let mut down = next;
189        // Find neighours in vertical columns.
190        let vertical = !(grid[i - 1] | grid[i] | grid[i + 1]);
191        let mut left = vertical.right_shift();
192        let mut right = vertical.left_shift();
193        // Elves need at least 1 neighbor to propose moving.
194        let mut remaining = grid[i] & !(up & down & left & right);
195
196        // Consider each direction one at a time, removing any elves who propose it.
197        for direction in &*order {
198            match direction {
199                North => {
200                    up &= remaining;
201                    remaining &= !up;
202                }
203                South => {
204                    down &= remaining;
205                    remaining &= !down;
206                }
207                West => {
208                    left &= remaining;
209                    remaining &= !left;
210                }
211                East => {
212                    right &= remaining;
213                    remaining &= !right;
214                }
215            }
216        }
217
218        // Copy final proposals to an array for each direction.
219        north[i - 1] = up;
220        south[i + 1] = down;
221        west[i] = left.left_shift();
222        east[i] = right.right_shift();
223    }
224
225    // Elves that propose moving to the same spot cancel each other out and no-one moves.
226    // Due to the movement rules we only need to check horizontal and vertical movement into
227    // the same spot (horizontal and vertical movement can never collide with each other).
228    for i in start..end {
229        let up = north[i];
230        let down = south[i];
231        let left = west[i];
232        let right = east[i];
233        north[i] &= !down;
234        south[i] &= !up;
235        west[i] &= !right;
236        east[i] &= !left;
237    }
238
239    for i in start..end {
240        // Stationary elves.
241        let same =
242            grid[i] & !(north[i - 1] | south[i + 1] | west[i].right_shift() | east[i].left_shift());
243        // Moving elves.
244        let change = north[i] | south[i] | west[i] | east[i];
245        grid[i] = same | change;
246        moved |= change.non_zero();
247    }
248
249    // Rotate the order of movement proposals for the next turn.
250    order.rotate_left(1);
251    moved
252}
aoc/year2022/day23.rs

aoc/year2022/
day23.rs
