aoc/year2022/
day22.rs

1//! # Monkey Map
2//!
3//! Parses any arbitrary cube map calculating the transitions between faces dynamically
4//! using 3D vectors.
5//!
6//! We build the transitions with a BFS over the connected cube map. The first face we find
7//! is labelled A in the diagram below. For each face we define 3 vectors:
8//!
9//! * `i` Horizontal from left to right in the plane of the face.
10//! * `j` Vertical from top to bottom in the plane of the face.
11//! * `k` Perpendicular to the face pointing into the body of the cube.
12//!
13//! ```none
14//!              k (0, 0, 1)
15//!             ^
16//!            /
17//!           /
18//!          -------------+
19//!         /            /|
20//!        /    B       / |
21//!       /            /  |
22//!      +------------+---->i (1, 0, 0)
23//!      |            | C |
24//!      |     A      |  /
25//!      |            | /
26//!      |            |/
27//!      +------------+
28//!      |
29//!      |
30//!      v
31//!      j (0, 1, 0)
32//!
33//! ```
34//!
35//! Then for each neighboring face we can find its `i`, `j` and `k` vectors depending on which
36//! edge it shares in common. For example, if we move from face A to face B along the top edge
37//! then the new vectors are:
38//!
39//! * `i` (1, 0, 0) Remains unchanged
40//! * `j` (0, 0, -1) Minus previous `k`
41//! * `k` (0, 1, 0) Previous `j`
42//!
43//! If faces B and C are connected then the vectors for face C are:
44//!
45//! * `i` (0, 1, 0)
46//! * `j` (0, 0, -1)
47//! * `k` (-1, 0, 0)
48//!
49//! However, if A and C were connected then the vectors for face C are:
50//!
51//! * `i` (0, 0, 1)
52//! * `j` (0, 1, 0)
53//! * `k` (-1, 0, 0)
54//!
55//! The really neat part is that when we leave the edge of a cube face the next
56//! 3D vector *is always `k`* no matter which edge. We can find the new direction by comparing
57//! the previous `k` against the new `i` and `j` vectors.
58//!
59//! For example, say we transition from face `A` to face `B`. Our `k` is (0, 1, 0) which is
60//! equal to minus the new `j`, so we know that we're travelling upwards from the bottom edge.
61//! Then we can use this information to figure out the two-dimensional offsets into the new face.
62use crate::util::hash::*;
63use crate::util::math::*;
64use crate::util::parse::*;
65use crate::util::point::*;
66use std::collections::VecDeque;
67use std::ops::Neg;
68
69#[derive(Clone, Copy, PartialEq, Eq)]
70enum Tile {
71    None,
72    Open,
73    Wall,
74}
75
76enum Move {
77    Left,
78    Right,
79    Forward(u32),
80}
81
82pub struct Grid {
83    width: usize,
84    height: usize,
85    tiles: Vec<Tile>,
86    start: i32,
87    block: i32,
88}
89
90/// Return [`Tile::None`] for any point out of bounds.
91impl Grid {
92    fn tile(&self, point: Point) -> Tile {
93        // Negative coordinates wrap to a huge value, so a single comparison covers both bounds.
94        let x = point.x as usize;
95        let y = point.y as usize;
96        if x < self.width && y < self.height { self.tiles[y * self.width + x] } else { Tile::None }
97    }
98}
99
100/// Minimal 3D vector implementation.
101#[derive(Copy, Clone, Hash, PartialEq, Eq)]
102struct Vector {
103    x: i32,
104    y: i32,
105    z: i32,
106}
107
108// Syntactic sugar to implement the `-` operator.
109impl Neg for Vector {
110    type Output = Self;
111
112    fn neg(self) -> Self::Output {
113        Self { x: -self.x, y: -self.y, z: -self.z }
114    }
115}
116
117/// 2D coordinates of the top left corner plus 3D vectors for the cube face.
118#[derive(Clone, Copy)]
119struct Face {
120    corner: Point,
121    i: Vector,
122    j: Vector,
123    k: Vector,
124}
125
126pub struct Input {
127    grid: Grid,
128    moves: Vec<Move>,
129}
130
131pub fn parse(input: &str) -> Input {
132    let (prefix, suffix) = input.rsplit_once("\n\n").unwrap();
133    let grid = parse_grid(prefix);
134    let moves = parse_moves(suffix);
135    Input { grid, moves }
136}
137
138pub fn part1(input: &Input) -> i32 {
139    let grid = &input.grid;
140    let block = grid.block;
141
142    // Wrap around to the other side of the row or column depending on direction.
143    let handle_none = |position, direction| {
144        let reverse = direction * -block;
145        let mut next = position + reverse;
146
147        while grid.tile(next) != Tile::None {
148            next += reverse;
149        }
150
151        next += direction;
152        (next, direction)
153    };
154
155    password(input, handle_none)
156}
157
158pub fn part2(input: &Input) -> i32 {
159    let grid = &input.grid;
160    let block = grid.block;
161    let edge = block - 1;
162
163    // Build the cube map dynamically.
164    let start = Face {
165        corner: Point::new(grid.start - grid.start % block, 0),
166        i: Vector { x: 1, y: 0, z: 0 },
167        j: Vector { x: 0, y: 1, z: 0 },
168        k: Vector { x: 0, y: 0, z: 1 },
169    };
170    let mut todo = VecDeque::from([start]);
171    let mut faces = FastMap::build([(start.k, start)]);
172    let mut corners = FastMap::build([(start.corner, start)]);
173
174    while let Some(next) = todo.pop_front() {
175        let Face { corner, i, j, k } = next;
176
177        // Define the transitions from each edge.
178        let neighbors = [
179            Face { corner: corner + Point::new(-block, 0), i: -k, j, k: i }, // Left
180            Face { corner: corner + Point::new(block, 0), i: k, j, k: -i },  // Right
181            Face { corner: corner + Point::new(0, -block), i, j: -k, k: j }, // Up
182            Face { corner: corner + Point::new(0, block), i, j: k, k: -j },  // Down
183        ];
184
185        // Potentially add the candidate edge to the frontier.
186        for next in neighbors {
187            if grid.tile(next.corner) != Tile::None && !faces.contains_key(&next.k) {
188                todo.push_back(next);
189                faces.insert(next.k, next);
190                corners.insert(next.corner, next);
191            }
192        }
193    }
194
195    let handle_none = |position: Point, direction| {
196        // Our (x, y) offset within the face.
197        let offset = Point::new(position.x % block, position.y % block);
198        // The (x, y) coordinate of the top left corner of the face.
199        let corner = position - offset;
200        // Lookup the 3D vectors associated with the current face.
201        let Face { i, j, k, .. } = corners[&corner];
202        // These transitions are the same as used during the BFS above.
203        let next_k = match direction {
204            LEFT => i,
205            RIGHT => -i,
206            UP => j,
207            DOWN => -j,
208            _ => unreachable!(),
209        };
210        let Face { corner: next_corner, i: next_i, j: next_j, .. } = faces[&next_k];
211        // Here's the really neat part. Our new 3D direction will *always* be `k`.
212        // We can find the relative orientation in the plane of the face by checking against
213        // `i` and `j`. This also tells us which edge we're entering.
214        let next_direction = if k == next_i {
215            RIGHT
216        } else if k == -next_i {
217            LEFT
218        } else if k == next_j {
219            DOWN
220        } else if k == -next_j {
221            UP
222        } else {
223            unreachable!()
224        };
225        // 4 possible leaving edges and 4 possible entering edges gives 16 total possible
226        // combinations.
227        let next_offset = match (direction, next_direction) {
228            (LEFT, LEFT) => Point::new(edge, offset.y),
229            (LEFT, RIGHT) => Point::new(0, edge - offset.y),
230            (LEFT, DOWN) => Point::new(offset.y, 0),
231            (LEFT, UP) => Point::new(edge - offset.y, edge),
232            (RIGHT, LEFT) => Point::new(edge, edge - offset.y),
233            (RIGHT, RIGHT) => Point::new(0, offset.y),
234            (RIGHT, DOWN) => Point::new(edge - offset.y, 0),
235            (RIGHT, UP) => Point::new(offset.y, edge),
236            (DOWN, LEFT) => Point::new(edge, offset.x),
237            (DOWN, RIGHT) => Point::new(0, edge - offset.x),
238            (DOWN, DOWN) => Point::new(offset.x, 0),
239            (DOWN, UP) => Point::new(edge - offset.x, edge),
240            (UP, LEFT) => Point::new(edge, edge - offset.x),
241            (UP, RIGHT) => Point::new(0, offset.x),
242            (UP, DOWN) => Point::new(edge - offset.x, 0),
243            (UP, UP) => Point::new(offset.x, edge),
244            _ => unreachable!(),
245        };
246        let next_position = next_corner + next_offset;
247        (next_position, next_direction)
248    };
249
250    password(input, handle_none)
251}
252
253fn parse_grid(input: &str) -> Grid {
254    let raw: Vec<_> = input.lines().map(str::as_bytes).collect();
255    // Width is the maximum width of any row.
256    let width = raw.iter().map(|line| line.len()).max().unwrap();
257    let height = raw.len();
258    let mut tiles = vec![Tile::None; width * height];
259
260    // Convert ASCII to enums.
261    for (y, row) in raw.iter().enumerate() {
262        for (x, &col) in row.iter().enumerate() {
263            tiles[y * width + x] = match col {
264                b'.' => Tile::Open,
265                b'#' => Tile::Wall,
266                _ => Tile::None,
267            };
268        }
269    }
270
271    // Find the first open tile in the top row.
272    let start = tiles.iter().position(|&t| t == Tile::Open).unwrap() as i32;
273    // Find the size of each face (4 in the sample or 50 in the actual input).
274    let block = width.gcd(height) as i32;
275    Grid { width, height, tiles, start, block }
276}
277
278fn parse_moves(input: &str) -> Vec<Move> {
279    let mut letters = input.bytes().filter(u8::is_ascii_uppercase);
280    let mut moves = Vec::new();
281
282    // Numbers and letters alternate, with numbers first.
283    for n in input.iter_unsigned() {
284        moves.push(Move::Forward(n));
285
286        if let Some(d) = letters.next() {
287            moves.push(if d == b'L' { Move::Left } else { Move::Right });
288        }
289    }
290
291    moves
292}
293
294/// Common code shared between part one and two. The `handle_none` closure defines how
295/// to transition when we leave an edge.
296fn password(input: &Input, handle_none: impl Fn(Point, Point) -> (Point, Point)) -> i32 {
297    let Input { grid, moves } = input;
298    let mut position = Point::new(grid.start, 0);
299    let mut direction = RIGHT;
300
301    for command in moves {
302        match command {
303            Move::Left => direction = direction.counter_clockwise(),
304            Move::Right => direction = direction.clockwise(),
305            Move::Forward(n) => {
306                for _ in 0..*n {
307                    let next = position + direction;
308                    match grid.tile(next) {
309                        // Not possible to move any further so we can break out of the loop.
310                        Tile::Wall => break,
311                        // Move within the 2D cube map.
312                        Tile::Open => position = next,
313                        Tile::None => {
314                            let (next_position, next_direction) = handle_none(position, direction);
315                            // The new position on a different face may be a wall.
316                            if grid.tile(next_position) == Tile::Open {
317                                position = next_position;
318                                direction = next_direction;
319                            } else {
320                                break;
321                            }
322                        }
323                    }
324                }
325            }
326        }
327    }
328
329    // Calculate the final score.
330    let position_score = 1000 * (position.y + 1) + 4 * (position.x + 1);
331    let direction_score = match direction {
332        RIGHT => 0,
333        DOWN => 1,
334        LEFT => 2,
335        UP => 3,
336        _ => unreachable!(),
337    };
338    position_score + direction_score
339}
aoc/year2022/day22.rs

aoc/year2022/
day22.rs
