aoc/year2018/day15.rs
1//! # Beverage Bandits
2//!
3//! This problem is notoriously tricky due to the finicky rules that must be followed precisely and
4//! the fact that not all inputs trigger all edge cases. However, from a performance aspect most
5//! of the time is consumed finding the nearest target whenever a unit needs to move.
6//!
7//! For each move we perform two [BFS](https://en.wikipedia.org/wiki/Breadth-first_search).
8//! The first search from the current unit finds the nearest target in reading order.
9//! The second *reverse* search from the target to the current unit finds the correct direction
10//! to move.
11//!
12//! Since the cave dimensions are 32 x 32 we use a fixed-size array of bitmasks stored in `u32`
13//! to execute each BFS efficiently. Each step we expand the frontier using the bitwise logic
14//! applied to each row:
15//!
16//! ```none
17//! (previous | (current << 1) | current | (current >> 1) | next) & !walls
18//! ```
19//!
20//! We represent the goal using bits and stop searching once that intersects with the frontier.
21//! First example:
22//!
23//! * Goblin's turn.
24//! * We should choose the first target square in reading order (to the right of the nearest elf).
25//! * There are two equal shortest paths to that square, so we should choose the first *step* in
26//! reading order (up).
27//! ```none
28//! Map Walls In Range
29//! ####### 1111111 0000000
30//! #E # 1000001 0110000
31//! # E # 1000001 0111000
32//! # G# 1000001 0010000
33//! ####### 1111111 0000000
34//!
35//! Forward BFS frontier Intersection
36//! 0000000 0000000 0000000 0000000 0000000
37//! 0000000 0000000 0000010 0000110 0000000
38//! 0000000 => 0000010 => 0000110 => 0001110 => 0001000 <= Choose first target square
39//! 0000010 0000110 0001110 0011110 0010000 in reading order
40//! 0000000 0000000 0000000 0000000 0000000
41//!
42//! Reverse BFS frontier Intersection
43//! 0000000 0000000 0000000 0000000
44//! 0000000 0001000 0011100 0000000
45//! 0001000 => 0011100 => 0111110 => 0000010 <= Choose first step
46//! 0000000 0001000 0011100 0000100 in reading order
47//! 0000000 0000000 0000000 0000000
48//! ```
49//!
50//! Choosing the first intersection in reading order the Goblin correctly moves upwards.
51//! Second example:
52//!
53//! * Elf's turn.
54//! * There are two equal shortest paths.
55//! * We should choose the first *unit* in reading order (left).
56//! ```none
57//! Map Walls In Range
58//! ########### 11111111111 00000000000
59//! #G..#....G# 10001000001 01100000110
60//! ###..E##### 11100011111 00000000000
61//! ########### 11111111111 00000000000
62//!
63//! Forward BFS frontier Intersection
64//! 00000000000 00000000000 00000000000 00000000000 00000000000 00000000000
65//! 00000000000 00000100000 00000110000 00010111000 00110111100 00100000100
66//! 00000100000 => 00001100000 => 00011100000 => 00011100000 => 00011100000 => 00000000000
67//! 00000000000 00000000000 00000000000 00000000000 00000000000 00000000000
68//!
69//! Reverse BFS frontier Intersection
70//! 00000000000 00000000000 00000000000 00000000000 00000000000
71//! 00100000000 01110000000 01110000000 01110000000 00000000000
72//! 00000000000 => 00000000000 => 00010000000 => 00011000000 => 00001000000
73//! 00000000000 00000000000 00000000000 00000000000 00000000000
74//! ```
75//!
76//! Choosing the first intersection in reading order the Elf correctly moves left.
77use crate::util::grid::*;
78use crate::util::point::*;
79use crate::util::thread::*;
80
81const READING_ORDER: [Point; 4] = [UP, LEFT, RIGHT, DOWN];
82
83pub struct Input {
84 walls: [u32; 32],
85 elves: Vec<Point>,
86 goblins: Vec<Point>,
87}
88
89#[derive(Clone, Copy, Eq, PartialEq)]
90enum Kind {
91 Elf,
92 Goblin,
93}
94
95struct Unit {
96 position: Point,
97 kind: Kind,
98 health: i32,
99 power: i32,
100}
101
102/// Parse the input into a bitmask for the cave walls
103/// and a list of point coordinates for each Elf and Goblin.
104pub fn parse(input: &str) -> Input {
105 let grid = Grid::parse(input);
106
107 let mut walls = [0; 32];
108 let mut elves = Vec::new();
109 let mut goblins = Vec::new();
110
111 for y in 0..grid.height {
112 for x in 0..grid.width {
113 let position = Point::new(x, y);
114
115 match grid[position] {
116 b'#' => set_bit(&mut walls, position),
117 b'E' => elves.push(position),
118 b'G' => goblins.push(position),
119 _ => (),
120 }
121 }
122 }
123
124 Input { walls, elves, goblins }
125}
126
127/// Simulate a full fight until only Goblins remain.
128pub fn part1(input: &Input) -> i32 {
129 fight(input, 3, false).unwrap()
130}
131
132/// Find the lowest attack power where no Elf dies. We can short circuit any fight once a
133/// single Elf is killed. Since each fight is independent we can parallelize the search over
134/// multiple threads.
135pub fn part2(input: &Input) -> i32 {
136 let iter = AtomicIter::new(4, 1);
137
138 // Use as many cores as possible to parallelize the search.
139 let result = spawn(|| worker(input, &iter));
140 // Find lowest possible power.
141 result.into_iter().flatten().min_by_key(|&(eap, _)| eap).map(|(_, score)| score).unwrap()
142}
143
144fn worker(input: &Input, iter: &AtomicIter) -> Option<(u32, i32)> {
145 while let Some(power) = iter.next() {
146 // If the Elves win then signal all threads to stop.
147 if let Some(score) = fight(input, power as i32, true) {
148 iter.stop();
149 return Some((power, score));
150 }
151 }
152
153 None
154}
155
156/// Careful implementation of the game rules.
157fn fight(input: &Input, elf_attack_power: i32, part_two: bool) -> Option<i32> {
158 let mut units = Vec::new();
159 let mut elves = input.elves.len();
160 let mut goblins = input.goblins.len();
161 let mut grid = Grid::new(32, 32, None);
162
163 // Initialize each unit.
164 for &position in &input.elves {
165 units.push(Unit { position, kind: Kind::Elf, health: 200, power: elf_attack_power });
166 }
167 for &position in &input.goblins {
168 units.push(Unit { position, kind: Kind::Goblin, health: 200, power: 3 });
169 }
170
171 for turn in 0.. {
172 // Remove dead units for efficiency.
173 units.retain(|u| u.health > 0);
174 // Units take turns in reading order.
175 units.sort_unstable_by_key(|u| 32 * u.position.y + u.position.x);
176 // Grid is used for reverse lookup from location to index.
177 units.iter().enumerate().for_each(|(i, u)| grid[u.position] = Some(i));
178
179 for index in 0..units.len() {
180 let Unit { position, kind, health, power } = units[index];
181
182 // Unit may have been killed during this turn.
183 if health <= 0 {
184 continue;
185 }
186
187 // Check if there are no more remaining targets then return *complete* turns.
188 // Determining a complete turn is subtle. If the last unit to act (in reading order)
189 // kills the last remaining enemy then that counts as a complete turn. Otherwise, the
190 // turn is considered incomplete and doesn't count.
191 if elves == 0 || goblins == 0 {
192 return Some(turn * units.iter().map(|u| u.health.max(0)).sum::<i32>());
193 }
194
195 // Search for neighboring enemies.
196 let mut nearby = attack(&grid, &units, position, kind);
197
198 // If no enemy next to unit then move toward nearest enemy in reading order,
199 // breaking equal distance ties in reading order.
200 if nearby.is_none()
201 && let Some(next) = double_bfs(input.walls, &units, position, kind)
202 {
203 grid[position] = None;
204 grid[next] = Some(index);
205 units[index].position = next;
206
207 nearby = attack(&grid, &units, next, kind);
208 }
209
210 // Attack enemy if possible.
211 if let Some(target) = nearby {
212 units[target].health -= power;
213
214 if units[target].health <= 0 {
215 grid[units[target].position] = None;
216
217 // For part two, short circuit if a single elf is killed.
218 match units[target].kind {
219 Kind::Elf if part_two => return None,
220 Kind::Elf => elves -= 1,
221 Kind::Goblin => goblins -= 1,
222 }
223 }
224 }
225 }
226 }
227
228 unreachable!()
229}
230
231/// Search for weakest neighboring enemy. Equal health ties are broken in reading order.
232fn attack(grid: &Grid<Option<usize>>, units: &[Unit], point: Point, kind: Kind) -> Option<usize> {
233 READING_ORDER
234 .iter()
235 .filter_map(|&o| grid[point + o])
236 .filter(|&next| units[next].kind != kind)
237 .min_by_key(|&next| units[next].health)
238}
239
240/// Performs two BFS searches. The first search from the current unit finds the nearest target
241/// in reading order. The second reverse search from the target to the current unit finds the
242/// correct direction to move.
243fn double_bfs(mut walls: [u32; 32], units: &[Unit], point: Point, kind: Kind) -> Option<Point> {
244 let frontier = &mut [0; 32];
245 set_bit(frontier, point);
246
247 let walls = &mut walls;
248 let in_range = &mut [0; 32];
249
250 for unit in units.iter().filter(|u| u.health > 0) {
251 if unit.kind == kind {
252 // Units of the same type are obstacles.
253 set_bit(walls, unit.position);
254 } else {
255 // Add enemy units to the list of potential targets.
256 set_bit(in_range, unit.position);
257 }
258 }
259
260 // We're interested in the 4 orthogonal squares around each enemy unit.
261 expand(walls, in_range);
262
263 // Search for reachable squares. There could be no reachable squares, for example friendly
264 // units already have the enemy surrounded or are blocking the path.
265 while expand(walls, frontier) {
266 if let Some(target) = intersect(in_range, frontier) {
267 // Reverse search from target to determine correct movement direction.
268 let frontier = &mut [0; 32];
269 set_bit(frontier, target);
270
271 let in_range = &mut [0; 32];
272 set_bit(in_range, point);
273 expand(walls, in_range);
274
275 // This will always succeed as there was a path from the current unit.
276 loop {
277 expand(walls, frontier);
278 if let Some(target) = intersect(in_range, frontier) {
279 return Some(target);
280 }
281 }
282 }
283 }
284
285 None
286}
287
288/// Use bitwise logic to expand the frontier. Returns a boolean indicating if the frontier
289/// actually expanded.
290fn expand(walls: &[u32], frontier: &mut [u32]) -> bool {
291 let mut previous = frontier[0];
292 let mut changed = 0;
293
294 for i in 1..31 {
295 let current = frontier[i];
296 let next = frontier[i + 1];
297
298 frontier[i] = (previous | (current << 1) | current | (current >> 1) | next) & !walls[i];
299
300 previous = current;
301 changed |= current ^ frontier[i];
302 }
303
304 changed != 0
305}
306
307/// Check if we have reached a target, returning the first target in reading order.
308fn intersect(in_range: &[u32], frontier: &[u32]) -> Option<Point> {
309 (1..31).find_map(|i| {
310 let both = in_range[i] & frontier[i];
311 both.lowest_one().map(|x| Point::new(x as i32, i as i32))
312 })
313}
314
315/// Convenience function to set a single bit from a point's location.
316#[inline]
317fn set_bit(slice: &mut [u32], point: Point) {
318 slice[point.y as usize] |= 1 << point.x;
319}