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 optimisation 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 towards 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}