aoc/year2019/
day20.rs

1//! # Donut Maze
2//!
3//! The approach to this solution is very similar to [`Day 18`] however parsing the maze
4//! cleanly is quite tricky.
5//!
6//! We first simplify the problem by running a [breadth first search] from each portal
7//! creating a list of distances between each pair of portals.
8//!
9//! Then a second BFS over this list efficiently solves both parts. For part two we use a cache to
10//! memoize previously seen values. We optimize part two further by not recursing deeper than the
11//! number of portals as this would mean a redundant trip to an already visited portal.
12//!
13//! [`Day 18`]: crate::year2019::day18
14//! [breadth first search]: https://en.wikipedia.org/wiki/Breadth-first_search
15use crate::util::grid::*;
16use crate::util::hash::*;
17use crate::util::point::*;
18use std::collections::VecDeque;
19
20type Key = ((u8, u8), Kind);
21
22#[derive(Clone, Copy, PartialEq, Eq, Hash)]
23pub enum Kind {
24    Inner,
25    Outer,
26    Start,
27    End,
28}
29
30enum Tile {
31    Wall,
32    Open,
33    Portal(Key, Kind),
34}
35
36struct Edge {
37    to: usize,
38    kind: Kind,
39    distance: u32,
40}
41
42pub struct Maze {
43    start: usize,
44    portals: Vec<Vec<Edge>>,
45}
46
47/// Parsing takes two passes. First we find the location of each portal. Then we BFS from each
48/// portal to build a list of distance pairs.
49pub fn parse(input: &str) -> Maze {
50    let grid = Grid::parse(input);
51    let width = grid.width as usize;
52
53    let mut tiles: Vec<_> =
54        grid.bytes.iter().map(|&b| if b == b'.' { Tile::Open } else { Tile::Wall }).collect();
55    let mut map = FastMap::new();
56    let mut found = Vec::new();
57    let mut start = usize::MAX;
58
59    // Find all labels
60    for y in (1..grid.height - 1).step_by(2) {
61        for x in (1..grid.width - 1).step_by(2) {
62            let point = Point::new(x, y);
63            if !grid[point].is_ascii_uppercase() {
64                continue;
65            }
66
67            // Decode the relative orientation of the label and the portal
68            let (first, second, third) = if grid[point + UP] == b'.' {
69                (point, point + DOWN, point + UP)
70            } else if grid[point + DOWN] == b'.' {
71                (point + UP, point, point + DOWN)
72            } else if grid[point + LEFT] == b'.' {
73                (point, point + RIGHT, point + LEFT)
74            } else if grid[point + RIGHT] == b'.' {
75                (point + LEFT, point, point + RIGHT)
76            } else {
77                continue;
78            };
79
80            let pair = (grid[first], grid[second]);
81            let index = (grid.width * third.y + third.x) as usize;
82            let inner = 2 < x && x < grid.width - 3 && 2 < y && y < grid.height - 3;
83
84            let (kind, opposite) = if inner {
85                (Kind::Inner, Kind::Outer)
86            } else {
87                match pair {
88                    (b'A', b'A') => {
89                        start = found.len();
90                        (Kind::Start, Kind::Start)
91                    }
92                    (b'Z', b'Z') => (Kind::End, Kind::End),
93                    _ => (Kind::Outer, Kind::Inner),
94                }
95            };
96
97            // `(pair, opposite)` is the key to the linked portal. Start and End map to themselves.
98            tiles[index] = Tile::Portal((pair, opposite), kind);
99            map.insert((pair, kind), found.len());
100            found.push(index);
101        }
102    }
103
104    // BFS from each portal. As a minor optimization we reuse `todo` and `visited`.
105    let mut portals = Vec::new();
106    let mut todo = VecDeque::new();
107    let mut visited = vec![0; tiles.len()];
108
109    for start in found {
110        let mut edges = Vec::new();
111        todo.push_back((start, 0));
112
113        while let Some((index, steps)) = todo.pop_front() {
114            visited[index] = start;
115
116            for next_index in [index + 1, index - 1, index + width, index - width] {
117                let next_steps = steps + 1;
118
119                if visited[next_index] != start {
120                    match tiles[next_index] {
121                        Tile::Wall => (),
122                        Tile::Open => {
123                            todo.push_back((next_index, next_steps));
124                        }
125                        Tile::Portal(key, kind) => {
126                            let to = map[&key];
127                            edges.push(Edge { to, kind, distance: next_steps });
128                        }
129                    }
130                }
131            }
132        }
133
134        portals.push(edges);
135    }
136
137    Maze { start, portals }
138}
139
140/// Straight BFS with no caching or any optimization tricks.
141pub fn part1(input: &Maze) -> u32 {
142    let mut todo = VecDeque::new();
143    todo.push_back((0, input.start));
144
145    while let Some((steps, index)) = todo.pop_front() {
146        for &Edge { to, kind, distance } in &input.portals[index] {
147            let next_steps = steps + distance + 1;
148
149            match kind {
150                Kind::Inner | Kind::Outer => todo.push_back((next_steps, to)),
151                Kind::End => return next_steps - 1,
152                Kind::Start => (),
153            }
154        }
155    }
156
157    unreachable!()
158}
159
160/// BFS with memoization of previously seen states.
161pub fn part2(input: &Maze) -> u32 {
162    let mut cache = FastMap::with_capacity(2_000);
163    let mut todo = VecDeque::new();
164    todo.push_back((0, input.start, 0));
165
166    while let Some((steps, index, level)) = todo.pop_front() {
167        let key = (index, level);
168        if let Some(min) = cache.get(&key)
169            && *min <= steps
170        {
171            continue;
172        }
173        cache.insert(key, steps);
174
175        for &Edge { to, kind, distance } in &input.portals[index] {
176            let next_steps = steps + distance + 1;
177
178            match kind {
179                // No need to recurse further than the number of portals
180                Kind::Inner if level < input.portals.len() => {
181                    todo.push_back((next_steps, to, level + 1));
182                }
183                Kind::Outer if level > 0 => {
184                    todo.push_back((next_steps, to, level - 1));
185                }
186                Kind::End if level == 0 => {
187                    return next_steps - 1;
188                }
189                _ => (),
190            }
191        }
192    }
193
194    unreachable!()
195}
aoc/year2019/day20.rs

aoc/year2019/
day20.rs
