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