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
52    let mut tiles: Vec<_> =
53        grid.bytes.iter().map(|&b| if b == b'.' { Tile::Open } else { Tile::Wall }).collect();
54    let mut map = FastMap::new();
55    let mut found = Vec::new();
56    let mut start = usize::MAX;
57
58    // Find all labels
59    for y in (1..grid.height - 1).step_by(2) {
60        for x in (1..grid.width - 1).step_by(2) {
61            let point = Point::new(x, y);
62            if !grid[point].is_ascii_uppercase() {
63                continue;
64            }
65
66            // Decode the relative orientation of the label and the portal
67            let (first, second, third) = if grid[point + UP] == b'.' {
68                (point, point + DOWN, point + UP)
69            } else if grid[point + DOWN] == b'.' {
70                (point + UP, point, point + DOWN)
71            } else if grid[point + LEFT] == b'.' {
72                (point, point + RIGHT, point + LEFT)
73            } else if grid[point + RIGHT] == b'.' {
74                (point + LEFT, point, point + RIGHT)
75            } else {
76                continue;
77            };
78
79            let pair = (grid[first], grid[second]);
80            let index = (grid.width * third.y + third.x) as usize;
81            let inner = 2 < x && x < grid.width - 3 && 2 < y && y < grid.height - 3;
82
83            let (kind, opposite) = if inner {
84                (Kind::Inner, Kind::Outer)
85            } else {
86                match pair {
87                    (b'A', b'A') => {
88                        start = found.len();
89                        (Kind::Start, Kind::Start)
90                    }
91                    (b'Z', b'Z') => (Kind::End, Kind::End),
92                    _ => (Kind::Outer, Kind::Inner),
93                }
94            };
95
96            // `(pair, opposite)` is the key to the linked portal. Start and End map to themselves.
97            tiles[index] = Tile::Portal((pair, opposite), kind);
98            map.insert((pair, kind), found.len());
99            found.push(index);
100        }
101    }
102
103    // BFS from each portal. As a minor optimization we reuse `todo` and `visited`.
104    let mut portals = Vec::new();
105    let mut todo = VecDeque::new();
106    let mut visited = vec![0; tiles.len()];
107    let orthogonal = [1, -1, grid.width, -grid.width].map(|i| i as usize);
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 offset in orthogonal {
117                let next_index = index.wrapping_add(offset);
118                let next_steps = steps + 1;
119
120                if visited[next_index] != start {
121                    match tiles[next_index] {
122                        Tile::Wall => (),
123                        Tile::Open => {
124                            todo.push_back((next_index, next_steps));
125                        }
126                        Tile::Portal(key, kind) => {
127                            let to = map[&key];
128                            edges.push(Edge { to, kind, distance: next_steps });
129                        }
130                    }
131                }
132            }
133        }
134
135        portals.push(edges);
136    }
137
138    Maze { start, portals }
139}
140
141/// Straight BFS with no caching or any optimization tricks.
142pub fn part1(input: &Maze) -> u32 {
143    let mut todo = VecDeque::new();
144    todo.push_back((0, input.start));
145
146    while let Some((steps, index)) = todo.pop_front() {
147        for &Edge { to, kind, distance } in &input.portals[index] {
148            let next_steps = steps + distance + 1;
149
150            match kind {
151                Kind::Inner | Kind::Outer => todo.push_back((next_steps, to)),
152                Kind::End => return next_steps - 1,
153                Kind::Start => (),
154            }
155        }
156    }
157
158    unreachable!()
159}
160
161/// BFS with memoization of previously seen states.
162pub fn part2(input: &Maze) -> u32 {
163    let mut cache = FastMap::with_capacity(2_000);
164    let mut todo = VecDeque::new();
165    todo.push_back((0, input.start, 0));
166
167    while let Some((steps, index, level)) = todo.pop_front() {
168        let key = (index, level);
169        if let Some(min) = cache.get(&key) {
170            if *min <= steps {
171                continue;
172            }
173        }
174        cache.insert(key, steps);
175
176        for &Edge { to, kind, distance } in &input.portals[index] {
177            let next_steps = steps + distance + 1;
178
179            match kind {
180                // No need to recurse further than the number of portals
181                Kind::Inner if level < input.portals.len() => {
182                    todo.push_back((next_steps, to, level + 1));
183                }
184                Kind::Outer if level > 0 => {
185                    todo.push_back((next_steps, to, level - 1));
186                }
187                Kind::End if level == 0 => {
188                    return next_steps - 1;
189                }
190                _ => (),
191            }
192        }
193    }
194
195    unreachable!()
196}
aoc/year2019/day20.rs

aoc/year2019/
day20.rs
