Advent of Code 2022 Day 22

Day 22: Monkey Map

https://adventofcode.com/2022/day/22

The monkeys take you through the jungle on the way to the grove.

You have to enter a password to get it.

That password can be found be following a specific path through a maze.

The first half of today’s input is the maze. Where ”.” is an open space, and ”#” is a solid wall. The maze is strangely shaped, so there are a bunch of spaces in the input.

The second part of the input is a list of instructions.

Numbers mean “move X steps forward”.
“L” means turn 90 degrees left
“R” means turn 90 degrees right

An example input looks like this:

// input.txt
        ...#
        .#..
        #...
        ....
...#.......#
........#...
..#....#....
..........#.
        ...#....
        .....#..
        .#......
        ......#.

10R5L5R10L4R5L5

You start the maze at first open tile on the top row.
You start facing to the right

So the first instruction tells you to take 10 steps on the map in the right direction.

If an instructions tells you to walk into a wall, stop instead.
If an instruction sends you off an edge, appear at the opposite one.

The password can be constructed using the final row, column, and direction you are facing.

Rows start from 1 at the top and count downward
Columns start from 1 at the left and count rightward.
Facing scores are:
- 0 for right
- 1 for down
- 2 for left
- 3 for up

The password is 1000 * row + 4 * column + facing.

Parsing

An instruction is an enum that’s either a rotation or a movement.

enum Instruction {
    Rotate(Turn),
    Forward(u8),
}

enum Turn {
    L,
    R,
}

I parsed the maze as a list of lists. Where items in the outer list are rows. Items in the rows are a tile or an empty space (because of the weird shape of the maze).

The tiles in the map are either open or solid. Because the maze has such a weird shape, I included the spaces where there isn’t anything too. You could also do this by associating a coordinate to each tile in the maze.

enum Tile {
    Open,
    Solid,
    None,
}

day_22.rs

fn parse(input: &str) -> (Vec<Vec<Tile>>, Vec<Instruction>) {
    // do NOT remove starting whitespace, it's significant
    let (grid, moves) = input.trim_end().split_once("\n\n").unwrap();
    let mut instructions = Vec::new();
    let mut digits = Vec::new();
    for c in moves.chars() {
        if c.is_numeric() {
            // accumulate digits
            let digit = c.to_digit(10).unwrap() as u8;
            digits.push(digit);
        } else {
            // construct number out of digits
            // uses math to concatenate digits instead of turning them into a string first and parsing the string
            let num = digits.iter().fold(0, |num, digit| num * 10 + digit);
            digits.clear();
            instructions.push(Instruction::Forward(num));

            // parse turn
            let turn = match c {
                'L' => Turn::L,
                'R' => Turn::R,
                _ => panic!("Invalid input"),
            };
            instructions.push(Instruction::Rotate(turn));
        }
    }
    // construct number out of any remaining digits
    // uses math to concatenate digits instead of turning them into a string first and parsing the string
    let num = digits.iter().fold(0, |num, digit| num * 10 + digit);
    instructions.push(Instruction::Forward(num));

    let mut map = Vec::new();
    for line in grid.lines() {
        let mut row = Vec::new();
        for c in line.chars() {
            let tile = match c {
                '.' => Tile::Open,
                '#' => Tile::Solid,
                ' ' => Tile::None,
                _ => panic!("invalid input"),
            };
            row.push(tile);
        }
        map.push(row);
    }

    (map, instructions)
}

Part 1

The question asks what the final password is.

If an instruction sends you off the right side of the map, appear left. Same rule for left to right, up to down, and down to up.

It’s possible there is a wall just off the edge of the maze. And you should stop when you encounter a wall.

The question text has a bunch of visual examples that are useful.

Helpers

You better believe I pulled out the Coord struct again to represent a position.

#[derive(Clone)]
struct Coord {
    row: i32,
    col: i32,
}

The direction you’re facing also gets a data type. Along with a few methods on it.

score helps with the scoring logic described above
turn takes in a direction, and applies a left or right turn
offset returns what a step in the current direction would do to the current coordinates on the map.

enum Direction {
    L,
    R,
    U,
    D,
}

impl Direction {
    fn score(&self) -> usize {
        use Direction::*;
        match self {
            R => 0,
            D => 1,
            L => 2,
            U => 3,
        }
    }

    fn turn(self, turn: &Turn) -> Direction {
        use Direction::*;
        match (self, turn) {
            (L, Turn::L) => D,
            (L, Turn::R) => U,
            (R, Turn::L) => U,
            (R, Turn::R) => D,
            (U, Turn::L) => L,
            (U, Turn::R) => R,
            (D, Turn::L) => R,
            (D, Turn::R) => L,
        }
    }

    fn offset(&self) -> Coord {
        use Direction::*;
        match &self {
            L => Coord { row: 0, col: -1 },
            R => Coord { row: 0, col: 1 },
            U => Coord { row: -1, col: 0 },
            D => Coord { row: 1, col: 0 },
        }
    }
}

In a pseudocode/skeletoncode hybrid, this is what I wrote:

skeleton.rs

let mut post = // first open position on the top row
let mut dir = Direction::R;

for ins in instruction {
    match ins {
        // if rotation, turn
        // if movement
            for amount in 0..movement_amount {
                let new_pos = // try to move 1 step
                let new_tile = // try to get new tile
                if new_tile was found {
                    match new_tile {
                        Tile::Open => // apply move,
                        Tile::Solid => // don't move and break out of loop
                    }
                } else {
                    // wrap around
                    let wrapped_pos = // pos after moving 1
                    let wrapped_tile = // get wrapped tile
                    match wrapped_tile {
                        Tile::Open => // apply move,
                        Tile::Solid => // don't move and break out of loop
                    }
                }
            }
    }
}

A helper function that handles the wrapping logic:

fn wrap(map: &[Vec<Tile>], pos: &Coord, dir: &Direction) -> Coord {
    let Coord { row: dr, col: dc } = dir.offset();
    let mut curr = pos.clone();
    // while an open or solid tile exists in the map when walking in the opposite direction, update pos
    while let Some(tile) = map
        .get((curr.row - dr) as usize)
        .and_then(|row| row.get((curr.col - dc) as usize))
    {
        if *tile == Tile::None {
            break;
        }
        curr = Coord {
            row: curr.row - dr,
            col: curr.col - dc,
        };
    }

    curr
}

Final code

day_22.rs

pub fn part_1(input: &str) -> i32 {
    let (map, instructions) = parse(input);
    // go to the first open position on the top row (skip the Nones)
    let start_col = map[0].iter().position(|tile| *tile == Tile::Open).unwrap() as i32;

    let mut pos = Coord {
        row: 0,
        col: start_col,
    };
    let mut dir = Direction::R;

    for inst in &instructions {
        match inst {
            Instruction::Rotate(turn) => dir = dir.turn(turn),
            Instruction::Forward(amount) => {
                // take a step "amount" times
                for _ in 0..*amount {
                    let Coord { row: dr, col: dc } = dir.offset();
                    let new_tile = map
                        .get((pos.row + dr) as usize)
                        .and_then(|row| row.get((pos.col + dc) as usize))
                        .unwrap_or(&Tile::None);

                    match new_tile {
                        // if new tile is solid, stop moving
                        Tile::Solid => break,
                        // if new tile is open, move there
                        Tile::Open => {
                            pos = Coord {
                                row: pos.row + dr,
                                col: pos.col + dc,
                            };
                        }
                        // if new tile is not found, wrap around
                        Tile::None => {
                            let new_pos = wrap(&map, &pos, &dir);
                            // if the new_pos is solid, stop moving
                            if map[new_pos.row as usize][new_pos.col as usize] == Tile::Solid {
                                break;
                            }
                            // if the new_pos is open, move there
                            pos = new_pos;
                        }
                    }
                }
            }
        }
    }

    1000 * (pos.row + 1) + 4 * (pos.col + 1) + dir.score() as i32
}

Part 2

The maze isn’t flat, it’s a very large cube. Each side is 50 tiles long.

So, that’s what that weird shape was about. The input “folds” into a cube shape.

The wrapping rules are different now. You continue along the cube instead.

Again, the question text has a few useful examples.

// example cube
        ...#
        .#..
        #...
        ....
...#.......#
........#..A
..#....#....
.D........#.
        ...#..B.
        .....#..
        .#......
        ..C...#.

2 example movements around the cube:

you are at A and move to the right, you arrive at B facing down
you are at C and move down, you arrive at D facing up:

The question asks what the final password is.

The code for part2 is very similar again. The part in the logic where we apply the wrapping logic is now different.

A step to a different cube face also changes the direction you are facing! So if we take a step, we not only update the current coordinate, but also the facing direction.

Helpers

The helper that handles the wrapping logic got way more complicated.

fn wrap(pos: &Coord, dir: &Direction) -> (Coord, Direction) {
    // find idxes of entire cube
    // this huge match statement only covers cases in the real input, but can be expanded to cover everything. It's just tedious
    let (cube_row, cube_col, new_dir) = match (pos.row / 50, pos.col / 50, dir) {
        (0, 1, Direction::U) => (3, 0, Direction::R),
        (0, 1, Direction::L) => (2, 0, Direction::R),
        (0, 2, Direction::U) => (3, 0, Direction::U),
        (0, 2, Direction::R) => (2, 1, Direction::L),
        (0, 2, Direction::D) => (1, 1, Direction::L),
        (1, 1, Direction::R) => (0, 2, Direction::U),
        (1, 1, Direction::L) => (2, 0, Direction::D),
        (2, 0, Direction::U) => (1, 1, Direction::R),
        (2, 0, Direction::L) => (0, 1, Direction::R),
        (2, 1, Direction::R) => (0, 2, Direction::L),
        (2, 1, Direction::D) => (3, 0, Direction::L),
        (3, 0, Direction::R) => (2, 1, Direction::U),
        (3, 0, Direction::D) => (0, 2, Direction::D),
        (3, 0, Direction::L) => (0, 1, Direction::D),
        _ => unreachable!(),
    };
    // find idxes within the cube
    let (row_idx, col_idx) = (pos.row % 50, pos.col % 50);

    let i = match dir {
        Direction::L => 49 - row_idx,
        Direction::R => row_idx,
        Direction::U => col_idx,
        Direction::D => 49 - col_idx,
    };

    // find new idxes within the cube
    let new_row = match new_dir {
        Direction::L => 49 - i,
        Direction::R => i,
        Direction::U => 49,
        Direction::D => 0,
    };
    let new_col = match new_dir {
        Direction::L => 49,
        Direction::R => 0,
        Direction::U => i,
        Direction::D => 49 - i,
    };

    let new_pos = Coord {
        row: cube_row * 50 + new_row,
        col: cube_col * 50 + new_col,
    };

    (new_pos, new_dir)
}

Final code

day_22.rs

pub fn part_2(input: &str) -> i32 {
    let (map, instructions) = parse(input);
    // go to the first open position on the top row (skip the Nones)
    let start_col = map[0].iter().position(|tile| *tile == Tile::Open).unwrap() as i32;

    let mut pos = Coord {
        row: 0,
        col: start_col,
    };
    let mut dir = Direction::R;

    for inst in &instructions {
        match inst {
            Instruction::Rotate(turn) => dir = dir.turn(turn),
            Instruction::Forward(amount) => {
                // take a step "amount" times
                for _ in 0..*amount {
                    let Coord { row: dr, col: dc } = dir.offset();
                    let new_tile = map
                        .get((pos.row + dr) as usize)
                        .and_then(|row| row.get((pos.col + dc) as usize))
                        .unwrap_or(&Tile::None);

                    match new_tile {
                        // if new tile is solid, stop moving
                        Tile::Solid => break,
                        // if new tile is open, move there
                        Tile::Open => {
                            pos = Coord {
                                row: pos.row + dr,
                                col: pos.col + dc,
                            };
                        }
                        // if new tile is not found, wrap around
                        Tile::None => {
                            let (new_pos, new_dir) = wrap(&pos, &dir);
                            // if the new_pos is solid, stop moving
                            if map[new_pos.row as usize][new_pos.col as usize] == Tile::Solid {
                                break;
                            }
                            // if the new_pos is open, move there
                            pos = new_pos;
                            dir = new_dir
                        }
                    }
                }
            }
        }
    }

    1000 * (pos.row + 1) + 4 * (pos.col + 1) + dir.score() as i32
}

Final code

day_22.rs

1#[derive(Clone)]
2struct Coord {
3    row: i32,
4    col: i32,
5}
6
7enum Direction {
8    L,
9    R,
10    U,
11    D,
12}
13
14enum Turn {
15    L,
16    R,
17}
18
19#[derive(PartialEq)]
20enum Tile {
21    Open,
22    Solid,
23    None,
24}
25
26enum Instruction {
27    Rotate(Turn),
28    Forward(u8),
29}
30
31impl Direction {
32    fn score(&self) -> usize {
33        use Direction::*;
34        match self {
35            R => 0,
36            D => 1,
37            L => 2,
38            U => 3,
39        }
40    }
41
42    fn turn(self, turn: &Turn) -> Direction {
43        use Direction::*;
44        match (self, turn) {
45            (L, Turn::L) => D,
46            (L, Turn::R) => U,
47            (R, Turn::L) => U,
48            (R, Turn::R) => D,
49            (U, Turn::L) => L,
50            (U, Turn::R) => R,
51            (D, Turn::L) => R,
52            (D, Turn::R) => L,
53        }
54    }
55
56    fn offset(&self) -> Coord {
57        use Direction::*;
58        match &self {
59            L => Coord { row: 0, col: -1 },
60            R => Coord { row: 0, col: 1 },
61            U => Coord { row: -1, col: 0 },
62            D => Coord { row: 1, col: 0 },
63        }
64    }
65}
66
67fn parse(input: &str) -> (Vec<Vec<Tile>>, Vec<Instruction>) {
68    // do NOT remove starting whitespace, it's significant
69    let (grid, moves) = input.trim_end().split_once("\n\n").unwrap();
70    let mut instructions = Vec::new();
71    let mut digits = Vec::new();
72    for c in moves.chars() {
73        if c.is_numeric() {
74            // accumulate digits
75            let digit = c.to_digit(10).unwrap() as u8;
76            digits.push(digit);
77        } else {
78            // construct number out of digits
79            // uses math to concatenate digits instead of turning them into a string first and parsing the string
80            let num = digits.iter().fold(0, |num, digit| num * 10 + digit);
81            digits.clear();
82            instructions.push(Instruction::Forward(num));
83
84            // parse turn
85            let turn = match c {
86                'L' => Turn::L,
87                'R' => Turn::R,
88                _ => panic!("Invalid input"),
89            };
90            instructions.push(Instruction::Rotate(turn));
91        }
92    }
93    // construct number out of any remaining digits
94    // uses math to concatenate digits instead of turning them into a string first and parsing the string
95    let num = digits.iter().fold(0, |num, digit| num * 10 + digit);
96    instructions.push(Instruction::Forward(num));
97
98    let mut map = Vec::new();
99    for line in grid.lines() {
100        let mut row = Vec::new();
101        for c in line.chars() {
102            let tile = match c {
103                '.' => Tile::Open,
104                '#' => Tile::Solid,
105                ' ' => Tile::None,
106                _ => panic!("invalid input"),
107            };
108            row.push(tile);
109        }
110        map.push(row);
111    }
112
113    (map, instructions)
114}
115
116fn wrap1(map: &[Vec<Tile>], pos: &Coord, dir: &Direction) -> Coord {
117    let Coord { row: dr, col: dc } = dir.offset();
118    let mut curr = pos.clone();
119    // while an open or solid tile exists in the map when walking in the opposite direction, update pos
120    while let Some(tile) = map
121        .get((curr.row - dr) as usize)
122        .and_then(|row| row.get((curr.col - dc) as usize))
123    {
124        if *tile == Tile::None {
125            break;
126        }
127        curr = Coord {
128            row: curr.row - dr,
129            col: curr.col - dc,
130        };
131    }
132
133    curr
134}
135
136pub fn part_1(input: &str) -> i32 {
137    let (map, instructions) = parse(input);
138    // go to the first open position on the top row (skip the Nones)
139    let start_col = map[0].iter().position(|tile| *tile == Tile::Open).unwrap() as i32;
140
141    let mut pos = Coord {
142        row: 0,
143        col: start_col,
144    };
145    let mut dir = Direction::R;
146
147    for inst in &instructions {
148        match inst {
149            Instruction::Rotate(turn) => dir = dir.turn(turn),
150            Instruction::Forward(amount) => {
151                // take a step "amount" times
152                for _ in 0..*amount {
153                    let Coord { row: dr, col: dc } = dir.offset();
154                    let new_tile = map
155                        .get((pos.row + dr) as usize)
156                        .and_then(|row| row.get((pos.col + dc) as usize))
157                        .unwrap_or(&Tile::None);
158
159                    match new_tile {
160                        // if new tile is solid, stop moving
161                        Tile::Solid => break,
162                        // if new tile is open, move there
163                        Tile::Open => {
164                            pos = Coord {
165                                row: pos.row + dr,
166                                col: pos.col + dc,
167                            };
168                        }
169                        // if new tile is not found, wrap around
170                        Tile::None => {
171                            let new_pos = wrap1(&map, &pos, &dir);
172                            // if the new_pos is solid, stop moving
173                            if map[new_pos.row as usize][new_pos.col as usize] == Tile::Solid {
174                                break;
175                            }
176                            // if the new_pos is open, move there
177                            pos = new_pos;
178                        }
179                    }
180                }
181            }
182        }
183    }
184
185    1000 * (pos.row + 1) + 4 * (pos.col + 1) + dir.score() as i32
186}
187
188fn wrap2(pos: &Coord, dir: &Direction) -> (Coord, Direction) {
189    // find idxes of entire cube
190    // this huge match statement only covers cases in the real input, but can be expanded to cover everything. It's just tedious
191    let (cube_row, cube_col, new_dir) = match (pos.row / 50, pos.col / 50, dir) {
192        (0, 1, Direction::U) => (3, 0, Direction::R),
193        (0, 1, Direction::L) => (2, 0, Direction::R),
194        (0, 2, Direction::U) => (3, 0, Direction::U),
195        (0, 2, Direction::R) => (2, 1, Direction::L),
196        (0, 2, Direction::D) => (1, 1, Direction::L),
197        (1, 1, Direction::R) => (0, 2, Direction::U),
198        (1, 1, Direction::L) => (2, 0, Direction::D),
199        (2, 0, Direction::U) => (1, 1, Direction::R),
200        (2, 0, Direction::L) => (0, 1, Direction::R),
201        (2, 1, Direction::R) => (0, 2, Direction::L),
202        (2, 1, Direction::D) => (3, 0, Direction::L),
203        (3, 0, Direction::R) => (2, 1, Direction::U),
204        (3, 0, Direction::D) => (0, 2, Direction::D),
205        (3, 0, Direction::L) => (0, 1, Direction::D),
206        _ => unreachable!(),
207    };
208    // find idxes within the cube
209    let (row_idx, col_idx) = (pos.row % 50, pos.col % 50);
210
211    let i = match dir {
212        Direction::L => 49 - row_idx,
213        Direction::R => row_idx,
214        Direction::U => col_idx,
215        Direction::D => 49 - col_idx,
216    };
217
218    // find new idxes within the cube
219    let new_row = match new_dir {
220        Direction::L => 49 - i,
221        Direction::R => i,
222        Direction::U => 49,
223        Direction::D => 0,
224    };
225    let new_col = match new_dir {
226        Direction::L => 49,
227        Direction::R => 0,
228        Direction::U => i,
229        Direction::D => 49 - i,
230    };
231
232    let new_pos = Coord {
233        row: cube_row * 50 + new_row,
234        col: cube_col * 50 + new_col,
235    };
236
237    (new_pos, new_dir)
238}
239
240pub fn part_2(input: &str) -> i32 {
241    let (map, instructions) = parse(input);
242    // go to the first open position on the top row (skip the Nones)
243    let start_col = map[0].iter().position(|tile| *tile == Tile::Open).unwrap() as i32;
244
245    let mut pos = Coord {
246        row: 0,
247        col: start_col,
248    };
249    let mut dir = Direction::R;
250
251    for inst in &instructions {
252        match inst {
253            Instruction::Rotate(turn) => dir = dir.turn(turn),
254            Instruction::Forward(amount) => {
255                // take a step "amount" times
256                for _ in 0..*amount {
257                    let Coord { row: dr, col: dc } = dir.offset();
258                    let new_tile = map
259                        .get((pos.row + dr) as usize)
260                        .and_then(|row| row.get((pos.col + dc) as usize))
261                        .unwrap_or(&Tile::None);
262
263                    match new_tile {
264                        // if new tile is solid, stop moving
265                        Tile::Solid => break,
266                        // if new tile is open, move there
267                        Tile::Open => {
268                            pos = Coord {
269                                row: pos.row + dr,
270                                col: pos.col + dc,
271                            };
272                        }
273                        // if new tile is not found, wrap around
274                        Tile::None => {
275                            let (new_pos, new_dir) = wrap2(&pos, &dir);
276                            // if the new_pos is solid, stop moving
277                            if map[new_pos.row as usize][new_pos.col as usize] == Tile::Solid {
278                                break;
279                            }
280                            // if the new_pos is open, move there
281                            pos = new_pos;
282                            dir = new_dir
283                        }
284                    }
285                }
286            }
287        }
288    }
289
290    1000 * (pos.row + 1) + 4 * (pos.col + 1) + dir.score() as i32
291}

Date

By

Tagged

Part of series

Older post

Newer post

Advent of Code 2022 Day 22

Day 22: Monkey Map

Parsing

Part 1

Helpers

Final code

Part 2

Helpers

Final code

Final code