NickyMeulemanNime

• ### By

• Nicky Meuleman

• ### Older post

Advent of Code 2022 Day 21

Advent of Code 2022 Day 23

1. Day 22: Monkey Map
2. Parsing
3. Part 1
4. Part 2
5. Final code

# Advent of Code 2022 Day 22

## Day 22: Monkey Map

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        ...#        .#..        #...        .......#.......#........#.....#....#..............#.        ...#....        .....#..        .#......        ......#..css-13aqjzy{display:inline-block;}
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

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 rowlet 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.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 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.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
.css-1mjim83{display:inline-block;width:2ch;text-align:right;-webkit-user-select:none;-moz-user-select:none;-ms-user-select:none;user-select:none;opacity:0.3;margin-right:0.5rem;}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 significant69    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 digits75            let digit = c.to_digit(10).unwrap() as u8;76            digits.push(digit);77        } else {78            // construct number out of digits79            // uses math to concatenate digits instead of turning them into a string first and parsing the string80            let num = digits.iter().fold(0, |num, digit| num * 10 + digit);81            digits.clear();82            instructions.push(Instruction::Forward(num));83
84            // parse turn85            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 digits94    // uses math to concatenate digits instead of turning them into a string first and parsing the string95    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 pos120    while let Some(tile) = map121        .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    curr134}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.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" times152                for _ in 0..*amount {153                    let Coord { row: dr, col: dc } = dir.offset();154                    let new_tile = map155                        .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 moving161                        Tile::Solid => break,162                        // if new tile is open, move there163                        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 around170                        Tile::None => {171                            let new_pos = wrap1(&map, &pos, &dir);172                            // if the new_pos is solid, stop moving173                            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 there177                            pos = new_pos;178                        }179                    }180                }181            }182        }183    }184
185    1000 * (pos.row + 1) + 4 * (pos.col + 1) + dir.score() as i32186}187
188fn wrap2(pos: &Coord, dir: &Direction) -> (Coord, Direction) {189    // find idxes of entire cube190    // this huge match statement only covers cases in the real input, but can be expanded to cover everything. It's just tedious191    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 cube209    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 cube219    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.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" times256                for _ in 0..*amount {257                    let Coord { row: dr, col: dc } = dir.offset();258                    let new_tile = map259                        .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 moving265                        Tile::Solid => break,266                        // if new tile is open, move there267                        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 around274                        Tile::None => {275                            let (new_pos, new_dir) = wrap2(&pos, &dir);276                            // if the new_pos is solid, stop moving277                            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 there281                            pos = new_pos;282                            dir = new_dir283                        }284                    }285                }286            }287        }288    }289
290    1000 * (pos.row + 1) + 4 * (pos.col + 1) + dir.score() as i32291}