NickyMeulemanNime
Metadata
  • Date

  • By

    • Nicky Meuleman
  • Tagged

  • Part of series

  • Older post

    Advent of Code 2022 Day 21

  • Newer post

    Advent of Code 2022 Day 23

Table of contents
  1. Day 22: Monkey Map
  2. Parsing
  3. Part 1
    1. Helpers
    2. Final code
  4. Part 2
    1. Helpers
    2. Final code
  5. Final code

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:

  1. you are at A and move to the right, you arrive at B facing down
  2. 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}

Series navigation for: Advent of Code 2022

1. Advent of Code 2022 Day 1

Designed and developed by Nicky Meuleman

Built with Gatsby. Hosted on Netlify.