-
Notifications
You must be signed in to change notification settings - Fork 4
/
day18.rs
253 lines (218 loc) · 9.76 KB
/
day18.rs
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
//! # Many-Worlds Interpretation
//!
//! Our high level approach is to simplify the problem into graph path finding. We only
//! ever need to move directly from key to key, so the maze becomes a graph where the nodes are
//! keys and the edge weight is the distance between keys. Doors modify which edges
//! are connected depending on the keys currently possessed.
//!
//! We first find the distance betweeen every pair of keys then run
//! [Dijkstra's algorithm](https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm) to find the
//! shortest path that visits every node in the graph.
//! The maze is also constructed in such a way to make our life easier:
//! * There is only ever one possible path to each key. We do not need to consider
//! paths of different lengths that need different keys.
//! * As a corollary, if key `b` lies between `a` and `c` then `|ac| = |ab| + |bc|`. This
//! enables a huge optimization that we only need to consider immediate neighbours.
//! If we do not possess key `b` then it never makes sense to skip from `a` to `c` since `b` is
//! along the way. We can model this by treating keys the same as doors. This optimization
//! sped up my solution by a factor of 30.
//!
//! On top of this approach we apply some high level tricks to go faster:
//! * We store previously seen pairs of `(location, keys collected)` to `total distance` in a map.
//! If we are in the same location with the same keys but at a higher cost, then this situation
//! can never be optimal so the solution can be discarded.
//! * When finding the distance between every pair of keys, it's faster to first only find the immediate
//! neighbors of each key using a [Breadth first search](https://en.wikipedia.org/wiki/Breadth-first_search)
//! then run the [Floyd-Warshall algorithm](https://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm)
//! to contruct the rest of the graph. Even though the Floyd-Warshall asymptotic bound of `O(n³)`
//! is higher than the asymptotic bounds of repeated BFS, this was twice as fast in practise
//! for my input.
//!
//! We also apply some low level tricks to go even faster:
//! * The set of remaining keys needed is stored as bits in an `u32`. We can have at most 26 keys
//! so this will always fit. For example needing `a`, `b` and `e` is represented as `10011`.
//! * Robot location is also stored the same way. Robots can only ever be in their initial location
//! or at a key, so this gives a max of 26 + 4 = 30 locations. As a nice bonus this allows
//! part one and part two to share the same code.
//! * For fast lookup of distance between keys, the maze is stored as
//! [adjacency matrix](https://en.wikipedia.org/wiki/Adjacency_matrix). `a` is index 0, `b` is
//! index 1 and robots's initial positions are from 26 to 29 inclusive.
//! For example (simplifying by moving robot from index 26 to 2):
//!
//! ```none
//! ######### [0 6 2]
//! #b.A.@.a# => [6 0 4]
//! ######### [2 4 0]
//! ```
// Disable lints with false positives
#![allow(clippy::needless_range_loop)]
#![allow(clippy::unnecessary_lazy_evaluations)]
use crate::util::grid::*;
use crate::util::hash::*;
use crate::util::heap::*;
use std::collections::VecDeque;
/// `position` and `remaining` are both bitfields. For example a robot at key `d` that needs
/// `b` and `c` would be stored as `position = 1000` and `remaining = 110`.
#[derive(Clone, Copy, Default, PartialEq, Eq, Hash)]
struct State {
position: u32,
remaining: u32,
}
/// `distance` in the edge weight between nodes. `needed` stores any doors in between as a bitfield.
#[derive(Clone, Copy)]
struct Door {
distance: u32,
needed: u32,
}
/// `initial` is the complete set of keys that we need to collect. Will always be binary
/// `11111111111111111111111111` for the real input but fewer for sample data.
///
/// `maze` is the adjacency of distances and doors between each pair of keys and the robots
/// starting locations.
struct Maze {
initial: State,
maze: [[Door; 30]; 30],
}
pub fn parse(input: &str) -> Grid<u8> {
Grid::parse(input)
}
pub fn part1(input: &Grid<u8>) -> u32 {
explore(input.width, &input.bytes)
}
pub fn part2(input: &Grid<u8>) -> u32 {
let mut modified = input.bytes.clone();
let mut patch = |s: &str, offset: i32| {
let middle = (input.width * input.height) / 2;
let index = (middle + offset * input.width - 1) as usize;
modified[index..index + 3].copy_from_slice(s.as_bytes());
};
patch("@#@", -1);
patch("###", 0);
patch("@#@", 1);
explore(input.width, &modified)
}
fn parse_maze(width: i32, bytes: &[u8]) -> Maze {
let mut initial = State::default();
let mut found = Vec::new();
let mut robots = 26;
// Find the location of every key and robot in the maze.
for (i, &b) in bytes.iter().enumerate() {
if let Some(key) = is_key(b) {
initial.remaining |= 1 << key;
found.push((i, key));
}
if b == b'@' {
initial.position |= 1 << robots;
found.push((i, robots));
robots += 1;
}
}
// Start a BFS from each key and robot's location stopping at the nearest neighbor.
// As a minor optimization we re-use the same `todo` and `visited` between each search.
let default = Door { distance: u32::MAX, needed: 0 };
let orthogonal = [1, -1, width, -width].map(|i| i as usize);
let mut maze = [[default; 30]; 30];
let mut visited = vec![usize::MAX; bytes.len()];
let mut todo = VecDeque::new();
for (start, from) in found {
todo.push_front((start, 0, 0));
visited[start] = from;
while let Some((index, distance, mut needed)) = todo.pop_front() {
if let Some(door) = is_door(bytes[index]) {
needed |= 1 << door;
}
if let Some(to) = is_key(bytes[index]) {
if distance > 0 {
// Store the reciprocal edge weight and doors in the adjacency matrix.
maze[from][to] = Door { distance, needed };
maze[to][from] = Door { distance, needed };
// Faster to stop here and use Floyd-Warshall later.
continue;
}
}
for delta in orthogonal {
let next_index = index.wrapping_add(delta);
if bytes[next_index] != b'#' && visited[next_index] != from {
todo.push_back((next_index, distance + 1, needed));
visited[next_index] = from;
}
}
}
}
// Fill in the rest of the graph using the Floyd–Warshal algorithm.
// As a slight twist we also build the list of intervening doors at the same time.
for i in 0..30 {
maze[i][i].distance = 0;
}
for k in 0..30 {
for i in 0..30 {
for j in 0..30 {
let candidate = maze[i][k].distance.saturating_add(maze[k][j].distance);
if maze[i][j].distance > candidate {
maze[i][j].distance = candidate;
// `(1 << k)` is a crucial optimization. By treating intermediate keys like
// doors we speed things up by a factor of 30.
maze[i][j].needed = maze[i][k].needed | (1 << k) | maze[k][j].needed;
}
}
}
}
Maze { initial, maze }
}
fn explore(width: i32, bytes: &[u8]) -> u32 {
let mut todo = MinHeap::with_capacity(5_000);
let mut cache = FastMap::with_capacity(5_000);
let Maze { initial, maze } = parse_maze(width, bytes);
todo.push(0, initial);
while let Some((total, State { position, remaining })) = todo.pop() {
// Finish immediately if no keys left.
// Since we're using Dijkstra this will always be the optimal solution.
if remaining == 0 {
return total;
}
let mut robots = position;
while robots != 0 {
// The set of robots is stored as bits in a `u32` shifted by the index of the location.
let from = robots.trailing_zeros() as usize;
let from_mask = 1 << from;
robots ^= from_mask;
let mut keys = remaining;
while keys != 0 {
// The set of keys still needed is also stored as bits in a `u32` similar as robots.
let to = keys.trailing_zeros() as usize;
let to_mask = 1 << to;
keys ^= to_mask;
let Door { distance, needed } = maze[from][to];
// u32::MAX indicates that two nodes are not connected. Only possible in part two.
if distance != u32::MAX && remaining & needed == 0 {
let next_total = total + distance;
let next_state = State {
position: position ^ from_mask ^ to_mask,
remaining: remaining ^ to_mask,
};
// Memoize previously seen states to eliminate suboptimal states right away.
cache
.entry(next_state)
.and_modify(|e| {
if next_total < *e {
todo.push(next_total, next_state);
*e = next_total;
}
})
.or_insert_with(|| {
todo.push(next_total, next_state);
next_total
});
}
}
}
}
unreachable!()
}
// Convenience functions to find keys and robots
fn is_key(b: u8) -> Option<usize> {
b.is_ascii_lowercase().then(|| (b - b'a') as usize)
}
fn is_door(b: u8) -> Option<usize> {
b.is_ascii_uppercase().then(|| (b - b'A') as usize)
}