It’s that time of year again! Just like last year, I’ll be posting my solutions to the Advent of Code puzzles. This year, I’ll be solving the puzzles in Rust. I’ll post my solutions and code to GitHub as well. After finishing last year (and 2015-2019) in Julia, I needed to spend some time with Rust again! If you haven’t given AoC a try, I encourage you to do so along with me!
Day 22 - Monkey Map
Find the problem description HERE.
The Input - Misshapen Maps
Buckle up! This one’s a doozy! Actually, parsing the input itself isn’t bad at all, after all, it’s just a square grid with some spaces missing, right? Sure, yeah, that’s true, but that grid represents a map with some special wrapping rules that aren’t particularly consistent from one spot to another. So, it seemed to me that the best way to handle this was to have each space on the map know where you should end up if you move out of that space in any of the four directions. So, it’s sort of a pseudo 2D linked list. So, there’s a bit of post-processing involved in linking up the spaces. This should make actually solving each part of the puzzle easier, though.
use itertools::Itertools;
use std::ops::{Index, IndexMut};
/// Represents a position on the "map", from a top-down perspective. A
/// Position is given as (row, column).
#[derive(Debug, Default, Copy, Clone, PartialEq, Eq)]
struct Position(usize, usize);
/// Indicates the heading of the current movement on the map, from a
/// top-down perspective.
#[derive(Debug, Copy, Clone, PartialEq, Eq)]
enum Heading {
Up,
Right,
Down,
Left,
}
/// Represents the links from one point on the map to another. This way, each
/// point on the map knows what the heading and position will be for someone
/// who moves in a given direction from that point.
#[derive(Debug, Default, Copy, Clone, PartialEq, Eq)]
struct Links {
up: Option<(Heading, Position)>,
right: Option<(Heading, Position)>,
down: Option<(Heading, Position)>,
left: Option<(Heading, Position)>,
}
/// Represents a tile on the map
#[derive(Debug, Default, Copy, Clone, PartialEq, Eq)]
enum Tile {
#[default]
Void,
Path(Links),
Wall,
}
impl Tile {
/// Sometimes, it's nice to have a function to let us know if the current
/// Tile is a Tile::Path or not.
fn is_path(&self) -> bool {
matches!(self, Tile::Path(_))
}
}
/// Represents a movement direction, given on the last line of the input file.
#[derive(Debug, Copy, Clone)]
enum Direction {
TurnLeft,
TurnRight,
Forward(u32),
}
/// Represents the tiles on the map given to us by the monkeys, with the added
/// metadata from us added in.
#[derive(Debug, Clone)]
struct MonkeyMap(Vec<Vec<Tile>>);
/// Namespacing for the parsers used in today's puzzle.
mod parser {
use super::*;
use anyhow::{anyhow, Result};
use nom::{
branch::alt,
bytes::complete::{tag, take_till, take_while},
character::complete::{alphanumeric0, newline, u32},
combinator::{map, value},
multi::{many0, many1, separated_list0},
sequence::{pair, separated_pair},
Finish, IResult,
};
/// Nom parser for " " -> Tile::Void
fn void(s: &str) -> IResult<&str, Tile> {
value(Tile::Void, tag(" "))(s)
}
/// Nom parser for "." -> Tile::Path()
fn passable(s: &str) -> IResult<&str, Tile> {
value(Tile::Path(Links::default()), tag("."))(s)
}
/// Nom parser for "#" -> Tile::Wall
fn wall(s: &str) -> IResult<&str, Tile> {
value(Tile::Wall, tag("#"))(s)
}
/// Nom parser for all Tile variants
fn tile(s: &str) -> IResult<&str, Tile> {
alt((void, passable, wall))(s)
}
/// Nom parser for a line of Tiles in the input
fn tile_line(s: &str) -> IResult<&str, Vec<Tile>> {
many1(tile)(s)
}
/// Nom parser for all the tiles in the input
fn monkey_map(s: &str) -> IResult<&str, MonkeyMap> {
map(separated_list0(newline, tile_line), MonkeyMap)(s)
}
/// Nom parser for "10" -> Direction::Forward(10)
fn forward(s: &str) -> IResult<&str, Direction> {
map(u32, Direction::Forward)(s)
}
/// Nom parser for "L" -> Direction::TurnLeft
fn left(s: &str) -> IResult<&str, Direction> {
value(Direction::TurnLeft, tag("L"))(s)
}
/// Nom parser for "R" -> Direction::TurnRight
fn right(s: &str) -> IResult<&str, Direction> {
value(Direction::TurnRight, tag("R"))(s)
}
/// Nom parser for all Direction variants
fn direction(s: &str) -> IResult<&str, Direction> {
alt((forward, left, right))(s)
}
/// Nom parser for the entire list of Directions given in the last line of
/// the input.
fn directions(s: &str) -> IResult<&str, Vec<Direction>> {
many0(direction)(s)
}
/// Nom parser for both parts of the input, separated by an empty line.
fn both_parts(s: &str) -> IResult<&str, (MonkeyMap, Vec<Direction>)> {
separated_pair(monkey_map, tag("\n\n"), directions)(s)
}
/// Entrypoint for parser combinators, parses the input file into a
/// MonkeyMap and list of Directions.
pub fn parse(s: &str) -> Result<(MonkeyMap, Vec<Direction>)> {
let (_, result) = both_parts(s).finish().map_err(|e| anyhow!("{e}"))?;
Ok(result)
}
}
/// It's convenient to be able to index into the MonkeyMap using a Position,
/// since Position is used to represent a point on the MonkeyMap.
impl Index<Position> for MonkeyMap {
type Output = Tile;
fn index(&self, index: Position) -> &Self::Output {
let Position(row, col) = index;
&self.0[row][col]
}
}
/// It's also convenient to be able to access these indices mutably.
impl IndexMut<Position> for MonkeyMap {
fn index_mut(&mut self, index: Position) -> &mut Self::Output {
let Position(row, col) = index;
&mut self.0[row][col]
}
}
impl MonkeyMap {
/// Build up the links to other Tiles on each Tile::Path in the MonkeyMap. This
/// way, we can check a given Tile for the heading and position of the tile in
/// each of the four cardinal directions.
fn map_positions(&mut self) {
let rows = self.0.len();
// Iterating over the indices keeps borrow checker wrangling to a minimum
// here. We need to get the number of columns individually for each row,
// since each row has a variable number of columns. The input doesn't have
// spaces at the ends of lines where the map doesn't span to the end of the
// line.
for row in 0..rows {
let cols = self.0.get(row).map(|v| v.len()).unwrap_or_default();
for col in 0..cols {
if let Tile::Path(mut links) = self.0[row][col] {
let position = Position(row, col);
links.up = self.find_next_up(position);
links.right = self.find_next_right(position);
links.down = self.find_next_down(position);
links.left = self.find_next_left(position);
self[position] = Tile::Path(links);
}
}
}
}
/// From a given position, identify the Heading/Position of the Tile that can
/// be achieved by moving up from the current position. Accounts for wrapping
/// around the map when moving up into an unmarked space.
fn find_next_up(&self, position: Position) -> Option<(Heading, Position)> {
let Position(row, col) = position;
let inner_iter = self.0.iter();
// This is a bit of a gnarly iterator chain, but the ultimate outcome is that
// it produces an iterator that starts at the current position and moves along
// the current column by row, in reverse, and returns the first position found
// that isn't a Tile::Void, which provides the wrapping functionality. This
// is probably the gnarliest of the four functions, since it requires iterating
// by column and in reverse. The rest of the `find_next_*()` functions are
// all variations on this one.
let (found_row, found_tile) = inner_iter
.enumerate()
.rev()
.map(|(row_idx, row)| (row_idx, row.get(col).unwrap_or(&Tile::Void)))
.cycle()
.skip(self.0.len() - row)
.find(|(_, tile)| !matches!(tile, Tile::Void))?;
if found_tile.is_path() {
return Some((Heading::Up, Position(found_row, col)));
}
None
}
/// From a given position, identify the Heading/Position of the Tile that can
/// be achieved by moving down from the current position. Accounts for wrapping
/// around the map when moving up into an unmarked space.
fn find_next_down(&self, position: Position) -> Option<(Heading, Position)> {
let Position(row, col) = position;
let inner_iter = self.0.iter();
let (found_row, found_tile) = inner_iter
.enumerate()
.map(|(row_idx, row)| (row_idx, row.get(col).unwrap_or(&Tile::Void)))
.cycle()
.skip(row + 1)
.find(|(_, tile)| **tile != Tile::Void)?;
if found_tile.is_path() {
return Some((Heading::Down, Position(found_row, col)));
}
None
}
/// From a given position, identify the Heading/Position of the Tile that can
/// be achieved by moving left from the current position. Accounts for wrapping
/// around the map when moving up into an unmarked space.
fn find_next_left(&self, position: Position) -> Option<(Heading, Position)> {
let Position(row, col) = position;
let row_of_tiles = self.0.get(row)?;
let (found_col, found_tile) = row_of_tiles
.iter()
.enumerate()
.rev()
.cycle()
.skip(row_of_tiles.len() - col)
.find(|(_, tile)| **tile != Tile::Void)?;
if found_tile.is_path() {
return Some((Heading::Left, Position(row, found_col)));
}
None
}
fn find_next_right(&self, position: Position) -> Option<(Heading, Position)> {
let Position(row, col) = position;
let row_of_tiles = self.0.get(row)?;
// And this one is probably the least gnarly. Which obviously means it was
// the one I wrote last. I really should have written these in reverse,
// because writing the "up" iterator chain as a PITA and I could have
// used this one as a template. Ah, well.
let (found_col, found_tile) = row_of_tiles
.iter()
.enumerate()
.cycle()
.skip(col + 1)
.find(|(_, tile)| **tile != Tile::Void)?;
if found_tile.is_path() {
return Some((Heading::Right, Position(row, found_col)));
}
None
}
}
const INPUT: &str = include_str!("../../input/22/input.txt");
/// Parse that input!
fn read() -> (MonkeyMap, Vec<Direction>) {
let (mut map, directions) = parser::parse(INPUT).unwrap();
map.map_positions();
(map, directions)
}
That’s a neat trick with the iterators for identifying the next space in any given direction, accounting for wrapping, right? I like it, anyway.
Part One - Wrapping and Mapping
Wait, so we’re friendly with the monkeys, now? Ok, seems like elephants make better ambassadors than I thought, although they may just feel bad for us after out pathetic display when they took our stuff. Or, maybe we impressed them with our math prowess. Either way, it beats the alternative. Plus, they’ve given us some notes they took down about the password to get into the star fruit grove. It’s a bit disconcerting that the monkeys are watching the elves put in the password and taking notes, but it’s working in our favor, so let’s not think too deeply about that right now.
/// Solve Day 22, Part 1
fn solve(input: &(MonkeyMap, Vec<Direction>)) -> u32 {
// This bit is just so I can convert the reference to the input into a
// mutable map. I pass in the input as a reference because it keeps me from
// accidentally mutating it in Part 1 and spending hours wondering why
// my solution for Part 2 doesn't work on the input I forgot I had mutated.
let (monkey_map, directions) = input;
let mut board = monkey_map.clone();
// Start at the first path Tile on the first row, facing right
let Some(start_pos) = board.first_path_position() else {
panic!("Cannot find start position!");
};
let mut walker = Walker::new(start_pos);
// Follow each direction
directions
.iter()
.for_each(|direction| walker.follow(&board, *direction));
// Let the walker calculate its own score and return it
walker.score()
}
impl MonkeyMap {
/// Finds the position of the first Tile::Path in the MonkeyMap,
/// in reading order (left to right, top to bottom), if there is
/// one.
fn first_path_position(&self) -> Option<Position> {
let first_row = self.0.first()?;
let first_col = first_row
.iter()
.position(|tile| matches!(tile, Tile::Path(_)))?;
Some(Position(0, first_col))
}
}
impl Tile {
/// Get the links associated with the Tile. If it's a Tile::Void
/// or Tile::Wall, the default is a Links with no links filled in.
/// That doesn't actually come up much, though.
fn links(&self) -> Links {
match self {
Tile::Path(links) => *links,
_ => Links::default(),
}
}
}
/// Represents a "walker" walking the path on the MonkeyMap.
#[derive(Debug)]
struct Walker(Heading, Position);
impl Walker {
fn new(position: Position) -> Self {
Walker(Heading::Right, position)
}
/// Lets the Walker calculate it's own score according to the puzzle description.
fn score(&self) -> u32 {
let Walker(heading, position) = self;
let Position(row, col) = position;
let heading_mod = match heading {
Heading::Right => 0,
Heading::Down => 1,
Heading::Left => 2,
Heading::Up => 3,
};
((*row as u32 + 1) * 1000) + ((*col as u32 + 1) * 4) + heading_mod
}
/// Given a direction and a reference to the map, attempt to follow the
/// direction by moving or turning the Walker.
fn follow(&mut self, map: &MonkeyMap, direction: Direction) {
let Walker(heading, position) = self;
let tile = map[*position];
let Tile::Path(links) = tile else { return; };
use Direction::*;
use Heading::*;
match (heading, direction) {
// Turning is easy, just match and update the Walker with the new heading
(Up, TurnLeft) => *self = Walker(Left, *position),
(Up, TurnRight) => *self = Walker(Right, *position),
(Right, TurnLeft) => *self = Walker(Up, *position),
(Right, TurnRight) => *self = Walker(Down, *position),
(Down, TurnLeft) => *self = Walker(Right, *position),
(Down, TurnRight) => *self = Walker(Left, *position),
(Left, TurnLeft) => *self = Walker(Down, *position),
(Left, TurnRight) => *self = Walker(Up, *position),
// Moving forward is a bit tougher, but not too serious.
(heading, Forward(n)) => {
// As many times as we're suppose to move forward...
for _ in 0..n {
// Unpack the walker again since we're going to modify it
// directly in subsequent loops.
let Walker(heading, position) = self;
// Here's where having the Links stored on the Tiles comes in
// handy. We can just query the links on the current Tile for
// the heading and position we should be at if we move in the
// indicated direction from the current Tile.
let mut links = map[*position].links();
let link = match heading {
Up => links.up,
Right => links.right,
Down => links.down,
Left => links.left,
};
// If there's no link in the indicated direction, just stop.
// Otherwise, update the Walker and keep going.
let Some((heading, position)) = link else { break; };
*self = Walker(heading, position)
}
}
};
}
}
It’s a bit verbose, and there’s a lot of comments there, but all told that’s a pretty straightforward implementation of direction following. We don’t even need to think about the weird map shape anymore since the map links make it a non-issue.
Part Two - Let’s Wrap This Up
You know, I thought that map shape as a bit suspicious, but the whole rectangular nature of ASCII characters threw me off. Of course it’s really a cube, why wouldn’t it be!? To be fair to the monkeys, they probably said something about that, but I don’t speak monkey and the elephants have proven to be a bit unreliable in that regard. The good news here is that our strategy of storing links on each map tile sets us up well for handling part two. The bad news is that it’s going to be super tedious…
/// Solve Day 22, Part 2
fn solve(input: &(MonkeyMap, Vec<Direction>)) -> u32 {
let (board, directions) = input;
let mut board = board.clone();
board.wrap(); // This is the difference!
let Some(start_pos) = board.first_path_position() else {
panic!("Cannot find start position!");
};
let mut walker = Walker::new(start_pos);
directions
.iter()
.for_each(|direction| walker.follow(&board, *direction));
walker.score()
}
impl MonkeyMap {
/// My map looks like this, where the pairs of letters indicate pairs of edges
/// that line up to form the cube if this shape were folded.
///
/// _______ _______
/// | A | B |
/// |C | D|
/// |_______|___F___|
/// | |
/// |E F|
/// _______|_______|
/// | E | |
/// |C | D|
/// |_______|___G___|
/// | |
/// |A G|
/// |___B___|
///
/// Yours probably doesn't. This function re-maps the connections on the linkss
/// on the outside edges to the correct matching edge. The hard part is making
/// sure you match up the right edges in the right order. I recommend cutting
/// out the shape of your map on a sheet of paper, folding it into a cube, and
/// using that cube to determine how to match up the sides. This was an incredibly
/// tedious bit of code to write because the various joins between the open face
/// pairs all had their own bits of uniqueness that prevented me from doing this
/// in a loop. So, each pair of faces is being joined manually.
fn wrap(&mut self) {
let inner = &self.0;
// Match up the (A) sides. All the faces are joined this way, where I
// iterate along the positions from the matching faces in the order that
// they match up and modify their links as needed to have each edge direct
// the Walker to the corresponding Tile on the other face. This was made
// even more tedious by the fact that this approach is completely different
// that the one I'd need to take to do this for the example input, since
// the example map is shaped differently from my input.
let side1 = (50..100).map(|col| Position(0, col));
let side2 = (150..200).map(|row| Position(row, 0));
for (p1, p2) in std::iter::zip(side1, side2) {
if self[p1].is_path() {
let mut links = self[p1].links();
links.up = if self[p2].is_path() {
Some((Heading::Right, p2))
} else {
None
};
self[p1] = Tile::Path(links);
}
if self[p2].is_path() {
let mut links = self[p2].links();
links.left = if self[p1].is_path() {
Some((Heading::Down, p1))
} else {
None
};
self[p2] = Tile::Path(links);
}
}
// Match up the (B) sides.
let side1 = (100..150).map(|col| Position(0, col));
let side2 = (0..50).map(|col| Position(199, col));
for (p1, p2) in std::iter::zip(side1, side2) {
if self[p1].is_path() {
let mut links = self[p1].links();
links.up = if self[p2].is_path() {
Some((Heading::Up, p2))
} else {
None
};
self[p1] = Tile::Path(links);
}
if self[p2].is_path() {
let mut links = self[p2].links();
links.down = if self[p1].is_path() {
Some((Heading::Down, p1))
} else {
None
};
self[p2] = Tile::Path(links);
}
}
// Match up the (C) sides.
let side1 = (0..50).map(|row| Position(row, 50));
let side2 = (100..150).map(|row| Position(row, 0)).rev();
for (p1, p2) in std::iter::zip(side1, side2) {
if self[p1].is_path() {
let mut links = self[p1].links();
links.left = if self[p2].is_path() {
Some((Heading::Right, p2))
} else {
None
};
self[p1] = Tile::Path(links);
}
if self[p2].is_path() {
let mut links = self[p2].links();
links.left = if self[p1].is_path() {
Some((Heading::Right, p1))
} else {
None
};
self[p2] = Tile::Path(links);
}
}
// Match up the (D) sides.
let side1 = (0..50).map(|row| Position(row, 149));
let side2 = (100..150).map(|row| Position(row, 99)).rev();
for (p1, p2) in std::iter::zip(side1, side2) {
if self[p1].is_path() {
let mut links = self[p1].links();
links.right = if self[p2].is_path() {
Some((Heading::Left, p2))
} else {
None
};
self[p1] = Tile::Path(links);
}
if self[p2].is_path() {
let mut links = self[p2].links();
links.right = if self[p1].is_path() {
Some((Heading::Left, p1))
} else {
None
};
self[p2] = Tile::Path(links);
}
}
// Match up the (E) sides.
let side1 = (50..100).map(|row| Position(row, 50));
let side2 = (0..50).map(|col| Position(100, col));
for (p1, p2) in std::iter::zip(side1, side2) {
if self[p1].is_path() {
let mut links = self[p1].links();
links.left = if self[p2].is_path() {
Some((Heading::Down, p2))
} else {
None
};
self[p1] = Tile::Path(links);
}
if self[p2].is_path() {
let mut links = self[p2].links();
links.up = if self[p1].is_path() {
Some((Heading::Right, p1))
} else {
None
};
self[p2] = Tile::Path(links);
}
}
// Match up the (F) sides.
let side1 = (100..150).map(|col| Position(49, col));
let side2 = (50..100).map(|row| Position(row, 99));
for (p1, p2) in std::iter::zip(side1, side2) {
if self[p1].is_path() {
let mut links = self[p1].links();
links.down = if self[p2].is_path() {
Some((Heading::Left, p2))
} else {
None
};
self[p1] = Tile::Path(links);
}
if self[p2].is_path() {
let mut links = self[p2].links();
links.right = if self[p1].is_path() {
Some((Heading::Up, p1))
} else {
None
};
self[p2] = Tile::Path(links);
}
}
// Match up the (G) sides.
let side1 = (50..100).map(|col| Position(149, col));
let side2 = (150..200).map(|row| Position(row, 49));
for (p1, p2) in std::iter::zip(side1, side2) {
if self[p1].is_path() {
let mut links = self[p1].links();
links.down = if self[p2].is_path() {
Some((Heading::Left, p2))
} else {
None
};
self[p1] = Tile::Path(links);
}
if self[p2].is_path() {
let mut links = self[p2].links();
links.right = if self[p1].is_path() {
Some((Heading::Up, p1))
} else {
None
};
self[p2] = Tile::Path(links);
}
}
// And that's that! Seven slightly different edge-to-edge joins! I can't
// tell you how many small "typo" bugs I made in these seven blocks. The
// good news is that once the edges are forwarding correctly, walking the
// "cube" is exactly the same as walking the map in part one.
}
}
Why yes, that is a lot of code! Why do you ask?
Wrap Up
This was the most fun, interesting, and frustrating puzzle so far! Honestly, there’s something in me that rebels at the idea that my solution definitely won’t work for other people’s inputs. Given that the example is also a different shape from my input, every time I considered trying to test my approach on the example, I realized that it would be completely useless because I’d have to write a totally different implementation for the example shape. There’s probably some way I could have abstracted the process enough to cut down on the repetition, but this late in the season, my brain refused to put it together. That said, this was the first puzzle this year that forced me to get crafty with real world materials in order to properly reason about what I was doing, which is really quite charming. So, I give this puzzle a final grade of A with a snarky note written at the top of the page. That’ll show…somebody. I guess.
Oldest comments (0)