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 a 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 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 6x6 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 represents 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 possibilites 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. Joing 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` convert 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` convert to an `E` to maintain balance.
167//!
168//! ```none
169//! Previous S..E ┌──┐
170//! Previous SSEE |┌┐|
171//! Current SE.. ||└┘
172//! ```
173use crate::util::bitset::*;
174use crate::util::grid::*;
175use crate::util::hash::*;
176use crate::util::point::*;
177use std::collections::VecDeque;
178
179/// We only use 6 elements but 8 is faster to hash.
180type Row = [u8; 8];
181
182/// Undirected weighted graph representing the compressed maze.
183struct Graph {
184 start: Point,
185 end: Point,
186 edges: FastMap<Point, Vec<Point>>,
187 weight: FastMap<(Point, Point), u32>,
188}
189
190/// Distilled two dimensional array of only weights.
191pub struct Input {
192 extra: u32,
193 horizontal: [[u32; 6]; 6],
194 vertical: [[u32; 6]; 6],
195}
196
197/// Simplify input for faster processing.
198pub fn parse(input: &str) -> Input {
199 // Convert the raw maze input into a compressed graph.
200 let graph = compress(input);
201 // Convert graph to a 6x6 square grid.
202 graph_to_grid(&graph)
203}
204
205/// The graph is directed so the only allowed steps are down or to the right. The maximum value
206/// for any cell is the maximum of either the cell to the left or above.
207pub fn part1(input: &Input) -> u32 {
208 let mut total = [[0; 6]; 6];
209
210 for y in 0..6 {
211 for x in 0..6 {
212 let left = if x > 0 { total[y][x - 1] + input.horizontal[y][x - 1] } else { 0 };
213 let above = if y > 0 { total[y - 1][x] + input.vertical[y - 1][x] } else { 0 };
214 total[y][x] = left.max(above);
215 }
216 }
217
218 input.extra + total[5][5]
219}
220
221/// Graph is undirected so we can also move up or to the right.
222pub fn part2(input: &Input) -> u32 {
223 let start = [b'S', 0, 0, 0, 0, 0, 0, 0];
224 let end = [0, 0, 0, 0, 0, b'S', 0, 0];
225
226 // Compute all possible different 76 rows and the next possible row.
227 let mut todo = VecDeque::new();
228 let mut seen = FastSet::new();
229 let mut graph = FastMap::new();
230
231 todo.push_back(start);
232 seen.insert(start);
233
234 while let Some(row) = todo.pop_front() {
235 let mut neighbors = Vec::new();
236 dfs(&mut neighbors, row, [0; 8], 0, false, 0, 0);
237
238 for &(next, ..) in &neighbors {
239 if seen.insert(next) {
240 todo.push_back(next);
241 }
242 }
243
244 graph.insert(row, neighbors);
245 }
246
247 // Step through each row of the grid, keeping track of the maximum value for each
248 // row type.
249 let mut current = FastMap::new();
250 let mut next = FastMap::new();
251
252 current.insert((start, false), 0);
253
254 for y in 0..6 {
255 for ((row, gap), steps) in current.drain() {
256 for &(next_row, next_gap, horizontal, vertical) in &graph[&row] {
257 // Only 1 gap total is allowed, otherwise we can make a longer path.
258 if gap && next_gap {
259 continue;
260 }
261
262 // The bit sets represent the horizontal and vertical moves from the previous row.
263 let extra = horizontal.biterator().map(|x| input.horizontal[y][x]).sum::<u32>()
264 + vertical.biterator().map(|x| input.vertical[y][x]).sum::<u32>();
265
266 // De-duplicate states so that each row has at most 76 states.
267 let e = next.entry((next_row, gap || next_gap)).or_insert(0);
268 *e = (*e).max(steps + extra);
269 }
270 }
271
272 (current, next) = (next, current);
273 }
274
275 // The maximum path must have skipped 1 node.
276 input.extra + current[&(end, true)]
277}
278
279/// Convert maze to undirected graph.
280fn compress(input: &str) -> Graph {
281 let mut grid = Grid::parse(input);
282 let width = grid.width;
283 let height = grid.height;
284
285 // Move start and end away from edge.
286 let start = Point::new(1, 1);
287 let end = Point::new(width - 2, height - 2);
288
289 // Modify edge of grid to remove the need for boundary checks.
290 grid[start + UP] = b'#';
291 grid[end + DOWN] = b'#';
292
293 // BFS to find distances between POIs. Points of interest are the start, the end and junctions.
294 let mut poi = VecDeque::new();
295 let mut seen = FastSet::new();
296 let mut edges = FastMap::new();
297 let mut weight = FastMap::new();
298
299 poi.push_back(start);
300 grid[end] = b'P';
301
302 while let Some(from) = poi.pop_front() {
303 // Mark this POI as done.
304 grid[from] = b'#';
305
306 for direction in ORTHOGONAL {
307 if grid[from + direction] != b'#' {
308 let mut to = from + direction;
309 let mut cost = 1;
310
311 while grid[to] != b'P' {
312 let mut neighbors =
313 ORTHOGONAL.iter().map(|&o| to + o).filter(|&n| grid[n] != b'#');
314 let next = neighbors.next().unwrap();
315
316 // More than 1 neighbor means that we've reached a junction.
317 // Mark it as a POI then stop.
318 if neighbors.next().is_some() {
319 grid[to] = b'P';
320 break;
321 }
322
323 // Follow maze path toward next POI.
324 grid[to] = b'#';
325 to = next;
326 cost += 1;
327 }
328
329 // Graph is undirected so add both edges.
330 edges.entry(from).or_insert(Vec::new()).push(to);
331 edges.entry(to).or_insert(Vec::new()).push(from);
332 weight.insert((from, to), cost);
333 weight.insert((to, from), cost);
334
335 // Queue POI for processing if we haven't seen it before.
336 if seen.insert(to) {
337 poi.push_back(to);
338 }
339 }
340 }
341 }
342
343 Graph { start, end, edges, weight }
344}
345
346/// Convert graph to 6 x6 two dimensional array of weights.
347fn graph_to_grid(graph: &Graph) -> Input {
348 let Graph { start, end, edges, weight } = graph;
349
350 // There's only 1 edge from both the start and end nodes, so we always have to travel these
351 // steps. Add 2 steps to account for moving the start and end positions in the previous step.
352 let extra = 2 + weight[&(*start, edges[start][0])] + weight[&(*end, edges[end][0])];
353
354 // Perimeter nodes only have 3 edges. Interior nodes have 4 edges.
355 let mut seen = FastSet::new();
356 let mut next_perimeter = |point: &Point| {
357 *edges[point].iter().find(|&&next| edges[&next].len() == 3 && seen.insert(next)).unwrap()
358 };
359
360 let mut grid = [[ORIGIN; 6]; 6];
361 let mut horizontal = [[0; 6]; 6];
362 let mut vertical = [[0; 6]; 6];
363
364 // Place start in top left.
365 grid[0][0] = next_perimeter(start);
366
367 // Fill out top edge and left edge. Since the graph is square it doesn't matter which of the
368 // 2 children becomes top and which becomes left.
369 for i in 1..5 {
370 let left = grid[0][i - 1];
371 let above = grid[i - 1][0];
372
373 let next_left = next_perimeter(&left);
374 let next_above = next_perimeter(&above);
375
376 grid[0][i] = next_left;
377 grid[i][0] = next_above;
378 horizontal[0][i - 1] = weight[&(left, next_left)];
379 vertical[i - 1][0] = weight[&(above, next_above)];
380 }
381
382 // Add two extra corners by duplicating the last node in the row or column.
383 // This won't affect the overall path as the weight of the added edge is 0.
384 grid[0][5] = grid[0][4];
385 grid[5][0] = grid[4][0];
386
387 // Add remaining interior nodes.
388 for y in 1..6 {
389 for x in 1..6 {
390 let left = grid[y][x - 1];
391 let above = grid[y - 1][x];
392
393 let (&next, _) = edges
394 .iter()
395 .find(|&(&k, v)| v.contains(&above) && v.contains(&left) && seen.insert(k))
396 .unwrap();
397
398 grid[y][x] = next;
399 horizontal[y][x - 1] = weight[&(left, next)];
400 vertical[y - 1][x] = weight[&(above, next)];
401 }
402 }
403
404 Input { extra, horizontal, vertical }
405}
406
407/// Modified depth first search that only allows rows that skip one node.
408fn dfs(
409 result: &mut Vec<(Row, bool, u32, u32)>,
410 previous: Row,
411 current: Row,
412 start: usize,
413 gap: bool,
414 horizontal: u32,
415 vertical: u32,
416) {
417 // We're done, push the result to the possible successors.
418 if start == 6 {
419 result.push((current, gap, horizontal, vertical));
420 return;
421 }
422
423 // Previous row above has no vertical descending path.
424 if previous[start] == 0 {
425 // Skip at most 1 column per row.
426 if !gap {
427 dfs(result, previous, current, start + 1, true, horizontal, vertical);
428 }
429
430 let mut horizontal = horizontal;
431
432 for end in (start + 1)..6 {
433 horizontal |= 1 << (end - 1);
434
435 if previous[end] == 0 {
436 // Start a new path pair.
437 let mut next = current;
438 next[start] = b'S';
439 next[end] = b'E';
440
441 let vertical = vertical | (1 << start) | (1 << end);
442
443 dfs(result, previous, next, end + 1, gap, horizontal, vertical);
444 } else {
445 // Move an existing path.
446 let mut next = current;
447 next[start] = previous[end];
448
449 let vertical = vertical | (1 << start);
450
451 dfs(result, previous, next, end + 1, gap, horizontal, vertical);
452 break;
453 }
454 }
455 } else {
456 // Continue vertical path straight down.
457 let mut next = current;
458 next[start] = previous[start];
459 dfs(result, previous, next, start + 1, gap, horizontal, vertical | (1 << start));
460
461 let mut horizontal = horizontal;
462
463 for end in (start + 1)..6 {
464 horizontal |= 1 << (end - 1);
465
466 if previous[end] == 0 {
467 // Move existing path.
468 let mut next = current;
469 next[end] = previous[start];
470
471 let vertical = vertical | (1 << end);
472
473 dfs(result, previous, next, end + 1, gap, horizontal, vertical);
474 } else {
475 // Merge two path segments.
476 match (previous[start], previous[end]) {
477 // No other changes needed.
478 (b'E', b'S') => {
479 dfs(result, previous, current, end + 1, gap, horizontal, vertical);
480 }
481 // Convert previous S to E.
482 (b'E', b'E') => {
483 let mut next = current;
484
485 for i in (0..start).rev() {
486 if current[i] == b'S' {
487 next[i] = b'E';
488 break;
489 }
490 }
491
492 dfs(result, previous, next, end + 1, gap, horizontal, vertical);
493 }
494 // Convert next E to S.
495 (b'S', b'S') => {
496 let mut modified = previous;
497 let mut level = 0;
498
499 for i in (end + 1)..6 {
500 if previous[i] == b'S' {
501 level += 1;
502 }
503 if previous[i] == b'E' {
504 if level == 0 {
505 modified[i] = b'S';
506 break;
507 }
508 level -= 1;
509 }
510 }
511
512 dfs(result, modified, current, end + 1, gap, horizontal, vertical);
513 }
514 _ => (), // (S, E) not allowed
515 }
516 break;
517 }
518 }
519 }
520}