aoc/year2023/day23.rs
1//! # A Long Walk
2//!
3//! The [longest path problem](https://en.wikipedia.org/wiki/Longest_path_problem) is NP-hard and
4//! requires an exhaustive search through all possible permutations. To speed things up we use
5//! several tricks to reduce the complexity.
6//!
7//! ## Compression
8//!
9//! First we "compress" the maze into a much smaller simpler graph. For example, the following maze
10//! converts into an undirected weighted graph.
11//!
12//! ```none
13//! #.#####
14//! #....## Start - A - B
15//! ##.#.## => | |
16//! ##....# C - D - End (edge weights are 2)
17//! #####.#
18//! ```
19//!
20//! Each actual input forms a graph of the same shape but with different edge weights that
21//! looks like:
22//!
23//! ```none
24//! Start - a - b - c - d - e
25//! | | | | | \
26//! f - A - B - C - D - g
27//! | | | | | |
28//! h - E - F - G - H - k
29//! | | | | | |
30//! m - K - M - N - P - n
31//! | | | | | |
32//! p - Q - R - S - T - q
33//! \ | | | | |
34//! r - s - t - u - v - End
35//! ```
36//!
37//! ## Conversion to grid
38//!
39//! Next we convert this graph into a 6 x 6 square graph that can be represented in an array. The
40//! start and end are moved to the corners and extra nodes added to the other corners.
41//!
42//! ```none
43//! Start - b - c - d - e - e`
44//! | | | | | |
45//! f - A - B - C - D - g
46//! | | | | | |
47//! h - E - F - G - H - k
48//! | | | | | |
49//! m - K - M - N - P - n
50//! | | | | | |
51//! p - Q - R - S - T - q
52//! | | | | | |
53//! p`- r - s - t - u - End
54//! ```
55//!
56//! ## Dynamic programming
57//!
58//! For a 6 x 6 grid graph there are 1262816 total possible rook walks, given by
59//! [OEIS A007764](https://oeis.org/A007764). However, since we want the longest path it only makes
60//! sense to consider the paths that visit the most possible nodes, in this case 35 (we have to
61//! skip 1). There are only 10180 of these paths making it much faster.
62//!
63//! A row by row dynamic programming approach from top to bottom finds these paths. For each row
64//! we calculate all possible next rows. Interestingly, it turns out that there are only 76 possible
65//! different rows. Then at each y coordinate we **deduplicate** rows to find the maximum value.
66//! This is the most important optimization as it means that each row is at most 76 elements
67//! instead of growing exponentially (76², 76³, ...).
68//!
69//! ## Example paths
70//!
71//! Using `S` to represent the start of a line segment and `E` to represent the end, the starting
72//! state looks like `S.....` and the end state `.....S`. One example:
73//!
74//! ```none
75//! Start S..... |
76//! Row 0 ..SS.E └─┐┌─┐
77//! Row 1 S..S.E ┌─┘|.|
78//! Row 2 ..SSE. └─┐|┌┘
79//! Row 3 SE...S ┌┐└┘└┐
80//! Row 4 S..... |└───┘
81//! Row 5 .....S └────┐
82//! End .....S |
83//! ```
84//!
85//! Another example:
86//!
87//! ```none
88//! Start S..... |
89//! Row 0 .SSESE └┐┌┐┌┐
90//! Row 1 S.SESE ┌┘||||
91//! Row 2 ...SSE └─┘|||
92//! Row 3 S.E..S ┌─┐└┘|
93//! Row 4 S..... |.└──┘
94//! Row 5 .....S └────┐
95//! End .....S |
96//! ```
97//!
98//! ## Next row generation
99//!
100//! To create the next row from a given row, there are 5 possibilities for each of the 6 columns.
101//!
102//! ### Leave a blank space, skipping over the column.
103//!
104//! We do this at most once per row. For example:
105//!
106//! ```none
107//! Previous .SSESE └┐┌┐┌┐
108//! Current .....S .└┘└┘|
109//! ^ Blank space
110//! ```
111//!
112//! ### Start a new (start, end) pair of lines.
113//!
114//! All lines must eventually connect so we must create lines in pairs. For example:
115//!
116//! ```none
117//! Previous .....S └────┐
118//! Current S...ES ┌───┐|
119//! ^ ^
120//! New pair
121//! ```
122//!
123//! ### Continue a straight line down from the previous row.
124//!
125//! The line stays the same kind (`S` or `E`).
126//!
127//! ```none
128//! Previous .....S └────┐
129//! Current S...ES ┌───┐|
130//! ^ Continuation
131//! ```
132//!
133//! ### Move a previous downwards line to the left or right into a different column.
134//!
135//! The line stays the same kind (`S` or `E`).
136//!
137//! ```none
138//! Previous .....S └────┐
139//! Current S..... ┌────┘
140//! ^ Move
141//! ```
142//!
143//! ### Join two open segments from a previous row.
144//!
145//! A restriction is that we can't create closed cycles that don't connect to the start or end,
146//! as this would skip several nodes. For example, this is not allowed:
147//!
148//! ```none
149//! Previous .....S |┌───┐
150//! Current S..... |└───┘
151//! ^ Closed cycles not allowed
152//! ```
153//!
154//! We implement this by not joining any (`S`, `E`) pairs in that order. Joining the reverse order
155//! (`E`, `S`) is allowed.
156//!
157//! Finally, there are two special rules when joining two nested line segments.
158//! When joining (`S`, `S`) the next `E` converts to an `S` to maintain balance.
159//!
160//! ```none
161//! Previous S..E ┌──┐
162//! Previous SSEE |┌┐|
163//! Current ..SE └┘||
164//! ```
165//!
166//! When joining (`E`, `E`) the previous `S` converts to an `E` to maintain balance.
167//!
168//! ```none
169//! Previous S..E ┌──┐
170//! Previous SSEE |┌┐|
171//! Current SE.. ||└┘
172//! ```
173use std::collections::VecDeque;
174
175use crate::util::bitset::*;
176use crate::util::grid::*;
177use crate::util::hash::*;
178use crate::util::point::*;
179
180/// We only use 6 elements but 8 is faster to hash.
181type Row = [u8; 8];
182
183/// Undirected weighted graph representing the compressed maze.
184struct Graph {
185 start: Point,
186 end: Point,
187 edges: FastMap<Point, Vec<Point>>,
188 weight: FastMap<(Point, Point), u32>,
189}
190
191/// Distilled two-dimensional array of only weights.
192pub struct Input {
193 extra: u32,
194 horizontal: [[u32; 6]; 6],
195 vertical: [[u32; 6]; 6],
196}
197
198/// Simplify input for faster processing.
199pub fn parse(input: &str) -> Input {
200 // Convert the raw maze input into a compressed graph.
201 let graph = compress(input);
202 // Convert graph to a 6x6 square grid.
203 graph_to_grid(&graph)
204}
205
206/// The graph is directed so the only allowed steps are down or to the right. The maximum value
207/// for any cell is the maximum of either the cell to the left or above.
208pub fn part1(input: &Input) -> u32 {
209 let mut total = [[0; 6]; 6];
210
211 for y in 0..6 {
212 for x in 0..6 {
213 let left = if x > 0 { total[y][x - 1] + input.horizontal[y][x - 1] } else { 0 };
214 let above = if y > 0 { total[y - 1][x] + input.vertical[y - 1][x] } else { 0 };
215 total[y][x] = left.max(above);
216 }
217 }
218
219 input.extra + total[5][5]
220}
221
222/// Graph is undirected so we can also move up or to the right.
223pub fn part2(input: &Input) -> u32 {
224 let start = [b'S', 0, 0, 0, 0, 0, 0, 0];
225 let end = [0, 0, 0, 0, 0, b'S', 0, 0];
226
227 // Compute all possible different 76 rows and the next possible row.
228 let mut todo = VecDeque::new();
229 let mut seen = FastSet::new();
230 let mut graph = FastMap::new();
231
232 todo.push_back(start);
233 seen.insert(start);
234
235 while let Some(row) = todo.pop_front() {
236 let mut neighbors = Vec::new();
237 dfs(&mut neighbors, row, [0; 8], 0, false, 0, 0);
238
239 for &(next, ..) in &neighbors {
240 if seen.insert(next) {
241 todo.push_back(next);
242 }
243 }
244
245 graph.insert(row, neighbors);
246 }
247
248 // Step through each row of the grid, keeping track of the maximum value for each
249 // row type.
250 let mut current = FastMap::new();
251 let mut next = FastMap::new();
252
253 current.insert((start, false), 0);
254
255 for y in 0..6 {
256 for ((row, gap), steps) in current.drain() {
257 for &(next_row, next_gap, horizontal, vertical) in &graph[&row] {
258 // Only 1 gap total is allowed, otherwise we can make a longer path.
259 if gap && next_gap {
260 continue;
261 }
262
263 // The bit sets represent the horizontal and vertical moves from the previous row.
264 let extra = horizontal.biterator().map(|x| input.horizontal[y][x]).sum::<u32>()
265 + vertical.biterator().map(|x| input.vertical[y][x]).sum::<u32>();
266
267 // De-duplicate states so that each row has at most 76 states.
268 let e = next.entry((next_row, gap || next_gap)).or_insert(0);
269 *e = (*e).max(steps + extra);
270 }
271 }
272
273 (current, next) = (next, current);
274 }
275
276 // The maximum path must have skipped 1 node.
277 input.extra + current[&(end, true)]
278}
279
280/// Convert maze to undirected graph.
281fn compress(input: &str) -> Graph {
282 let mut grid = Grid::parse(input);
283 let width = grid.width;
284 let height = grid.height;
285
286 // Move start and end away from edge.
287 let start = Point::new(1, 1);
288 let end = Point::new(width - 2, height - 2);
289
290 // Modify edge of grid to remove the need for boundary checks.
291 grid[start + UP] = b'#';
292 grid[end + DOWN] = b'#';
293
294 // BFS to find distances between POIs. Points of interest are the start, the end and junctions.
295 let mut poi = VecDeque::new();
296 let mut seen = FastSet::new();
297 let mut edges = FastMap::new();
298 let mut weight = FastMap::new();
299
300 poi.push_back(start);
301 grid[end] = b'P';
302
303 while let Some(from) = poi.pop_front() {
304 // Mark this POI as done.
305 grid[from] = b'#';
306
307 for direction in ORTHOGONAL {
308 if grid[from + direction] != b'#' {
309 let mut to = from + direction;
310 let mut cost = 1;
311
312 while grid[to] != b'P' {
313 let mut neighbors =
314 ORTHOGONAL.iter().map(|&o| to + o).filter(|&n| grid[n] != b'#');
315 let next = neighbors.next().unwrap();
316
317 // More than 1 neighbor means that we've reached a junction.
318 // Mark it as a POI then stop.
319 if neighbors.next().is_some() {
320 grid[to] = b'P';
321 break;
322 }
323
324 // Follow maze path toward next POI.
325 grid[to] = b'#';
326 to = next;
327 cost += 1;
328 }
329
330 // Graph is undirected so add both edges.
331 edges.entry(from).or_insert_with(Vec::new).push(to);
332 edges.entry(to).or_insert_with(Vec::new).push(from);
333 weight.insert((from, to), cost);
334 weight.insert((to, from), cost);
335
336 // Queue POI for processing if we haven't seen it before.
337 if seen.insert(to) {
338 poi.push_back(to);
339 }
340 }
341 }
342 }
343
344 Graph { start, end, edges, weight }
345}
346
347/// Convert graph to 6 x 6 two-dimensional array of weights.
348fn graph_to_grid(graph: &Graph) -> Input {
349 let Graph { start, end, edges, weight } = graph;
350
351 // There's only 1 edge from both the start and end nodes, so we always have to travel these
352 // steps. Add 2 steps to account for moving the start and end positions in the previous step.
353 let extra = 2 + weight[&(*start, edges[start][0])] + weight[&(*end, edges[end][0])];
354
355 // Perimeter nodes only have 3 edges. Interior nodes have 4 edges.
356 let mut seen = FastSet::new();
357 let mut next_perimeter = |point: &Point| {
358 *edges[point].iter().find(|&&next| edges[&next].len() == 3 && seen.insert(next)).unwrap()
359 };
360
361 let mut grid = [[ORIGIN; 6]; 6];
362 let mut horizontal = [[0; 6]; 6];
363 let mut vertical = [[0; 6]; 6];
364
365 // Place start in top left.
366 grid[0][0] = next_perimeter(start);
367
368 // Fill out top edge and left edge. Since the graph is square it doesn't matter which of the
369 // 2 children becomes top and which becomes left.
370 for i in 1..5 {
371 let left = grid[0][i - 1];
372 let above = grid[i - 1][0];
373
374 let next_left = next_perimeter(&left);
375 let next_above = next_perimeter(&above);
376
377 grid[0][i] = next_left;
378 grid[i][0] = next_above;
379 horizontal[0][i - 1] = weight[&(left, next_left)];
380 vertical[i - 1][0] = weight[&(above, next_above)];
381 }
382
383 // Add two extra corners by duplicating the last node in the row or column.
384 // This won't affect the overall path as the weight of the added edge is 0.
385 grid[0][5] = grid[0][4];
386 grid[5][0] = grid[4][0];
387
388 // Add remaining interior nodes.
389 for y in 1..6 {
390 for x in 1..6 {
391 let left = grid[y][x - 1];
392 let above = grid[y - 1][x];
393
394 let (&next, _) = edges
395 .iter()
396 .find(|&(&k, v)| v.contains(&above) && v.contains(&left) && seen.insert(k))
397 .unwrap();
398
399 grid[y][x] = next;
400 horizontal[y][x - 1] = weight[&(left, next)];
401 vertical[y - 1][x] = weight[&(above, next)];
402 }
403 }
404
405 Input { extra, horizontal, vertical }
406}
407
408/// Modified depth-first search that only allows rows that skip one node.
409fn dfs(
410 result: &mut Vec<(Row, bool, u32, u32)>,
411 previous: Row,
412 current: Row,
413 start: usize,
414 gap: bool,
415 horizontal: u32,
416 vertical: u32,
417) {
418 // We're done, push the result to the possible successors.
419 if start == 6 {
420 result.push((current, gap, horizontal, vertical));
421 return;
422 }
423
424 // Previous row above has no vertical descending path.
425 if previous[start] == 0 {
426 // Skip at most 1 column per row.
427 if !gap {
428 dfs(result, previous, current, start + 1, true, horizontal, vertical);
429 }
430
431 let mut horizontal = horizontal;
432
433 for end in (start + 1)..6 {
434 horizontal |= 1 << (end - 1);
435
436 if previous[end] == 0 {
437 // Start a new path pair.
438 let mut next = current;
439 next[start] = b'S';
440 next[end] = b'E';
441
442 let vertical = vertical | (1 << start) | (1 << end);
443
444 dfs(result, previous, next, end + 1, gap, horizontal, vertical);
445 } else {
446 // Move an existing path.
447 let mut next = current;
448 next[start] = previous[end];
449
450 let vertical = vertical | (1 << start);
451
452 dfs(result, previous, next, end + 1, gap, horizontal, vertical);
453 break;
454 }
455 }
456 } else {
457 // Continue vertical path straight down.
458 let mut next = current;
459 next[start] = previous[start];
460 dfs(result, previous, next, start + 1, gap, horizontal, vertical | (1 << start));
461
462 let mut horizontal = horizontal;
463
464 for end in (start + 1)..6 {
465 horizontal |= 1 << (end - 1);
466
467 if previous[end] == 0 {
468 // Move existing path.
469 let mut next = current;
470 next[end] = previous[start];
471
472 let vertical = vertical | (1 << end);
473
474 dfs(result, previous, next, end + 1, gap, horizontal, vertical);
475 } else {
476 // Merge two path segments.
477 match (previous[start], previous[end]) {
478 // No other changes needed.
479 (b'E', b'S') => {
480 dfs(result, previous, current, end + 1, gap, horizontal, vertical);
481 }
482 // Convert previous S to E.
483 (b'E', b'E') => {
484 let mut next = current;
485
486 for i in (0..start).rev() {
487 if current[i] == b'S' {
488 next[i] = b'E';
489 break;
490 }
491 }
492
493 dfs(result, previous, next, end + 1, gap, horizontal, vertical);
494 }
495 // Convert next E to S.
496 (b'S', b'S') => {
497 let mut modified = previous;
498 let mut level = 0;
499
500 for i in (end + 1)..6 {
501 if previous[i] == b'S' {
502 level += 1;
503 }
504 if previous[i] == b'E' {
505 if level == 0 {
506 modified[i] = b'S';
507 break;
508 }
509 level -= 1;
510 }
511 }
512
513 dfs(result, modified, current, end + 1, gap, horizontal, vertical);
514 }
515 _ => (), // (S, E) not allowed
516 }
517 break;
518 }
519 }
520 }
521}