I used Rust for day 15.
Parsing
There are two parts in the puzzle input, a grid consisting of empty spots, walls, boxes and a robot, and multiline list of moves, separated by a blank line. We split on the blank line and parse each part.
fn parse_input(input: String) -> (HashMap<Point, GridValue>, Vec<Vec<Move>>) {
let (grid_s, moves_s) = input.split_once("\n\n").expect("invalid input");
(parse_grid(grid_s), parse_moves(moves_s))
}To parse the grid, we iterate over each line, then iterate over each char in the line, using the enumerate method to get the coordinates. We create a Point struct to represent the coordinate of a point on the grid and a GridValue enum for the value at a point. Finally, we collect the grid points and values into a hashmap.
fn parse_grid(input: &str) -> HashMap<Point, GridValue> {
input
.trim()
.lines()
.enumerate()
.flat_map(|(row, line)| {
line.chars().enumerate().map(move |(col, ch)| {
(Point::new(row as i32, col as i32), GridValue::from_char(ch))
})
})
.collect()
}
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
struct Point {
row: i32,
col: i32,
}
impl Point {
fn new(row: i32, col: i32) -> Self {
Point { row, col }
}
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
enum GridValue {
Wall,
Box,
Robot,
Blank,
}
impl GridValue {
fn from_char(ch: char) -> Self {
match ch {
'@' => GridValue::Robot,
'.' => GridValue::Blank,
'O' => GridValue::Box,
'#' => GridValue::Wall,
other @ _ => panic!("invalid gridvalue {}", other),
}
}
}For the moves, we create an enum to represent each move, and parse the list of moves into a list of lists of moves. The reason we parse into a nested list rather than a flat list is because I thought that the moves being in different lines would be relevant in some way but it ended not mattering.
fn parse_moves(input: &str) -> Vec<Vec<Move>> {
input
.trim()
.lines()
.map(|line| line.chars().map(Move::from_char).collect())
.collect()
}
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
enum Move {
North,
South,
East,
West,
}
impl Move {
fn from_char(ch: char) -> Self {
match ch {
'^' => Move::North,
'v' => Move::South,
'<' => Move::West,
'>' => Move::East,
other @ _ => panic!("invalid move {}", other),
}
}
}Part One
We need to move the robot in the directions specified by the moves list. The robot can push boxes around if they come in the way of the robot. A box being pushed can push the box next to it if that box is in the way and this chain continues until there is either a blank spot or a wall at the end. Walls cannot be pushed so if there is a wall at the end, nothing moves.
After executing all the moves specified, we need to find the sum of the “GPS coordinates” of each box in the grid. The GPS coordinate of a point is specified as 100 × its row coordinate + its column coordinate.
fn part1((grid, moves): &(HashMap<Point, GridValue>, Vec<Vec<Move>>)) -> i32 {
let mut grid = grid.clone();
let mut robot_position = grid
.iter()
.find(|(_pt, val)| **val == GridValue::Robot)
.map(|(pt, _val)| *pt)
.expect("no robot in input");
for move_line in moves {
for &move_ in move_line {
make_move(&mut grid, &mut robot_position, move_)
}
}
grid.into_iter()
.filter(|(_pt, val)| val == &GridValue::Box)
.map(|(pt, _val)| pt.gps())
.sum()
}
impl Point {
fn gps(self) -> i32 {
100 * self.row + self.col
}
}To execute a move, we first need to find where the robot would move to given a move direction. Then we have 3 cases depending on the value of the grid at the next position of the robot. If that position is blank, we move the robot one unit. If it is a wall, we do nothing. The third case of that position containing a box is more complicated.
In the box case, we find the end of the chain of boxes. If the point after that end is a wall, we do nothing. Otherwise, it could be a blank spot, and in that case we swap the box at the next position of the robot with the blank spot after the end of the box chain and then swap the robot with the blank spot now there at its next position, effectively shifting the chain of boxes.
impl Point {
fn next(self, move_: Move) -> Self {
match move_ {
Move::North => Point {
row: self.row - 1,
col: self.col,
},
Move::South => Point {
row: self.row + 1,
col: self.col,
},
Move::East => Point {
row: self.row,
col: self.col + 1,
},
Move::West => Point {
row: self.row,
col: self.col - 1,
},
}
}
}
fn make_move(grid: &mut HashMap<Point, GridValue>, robot_position: &mut Point, move_: Move) {
let next_position = robot_position.next(move_);
match grid.get(&next_position).copied() {
Some(GridValue::Blank) => {
swap_points(grid, *robot_position, next_position);
*robot_position = next_position;
}
Some(GridValue::Wall) => {}
Some(GridValue::Box) => {
let mut far_position = next_position;
while let Some(GridValue::Box) = grid.get(&far_position.next(move_)) {
far_position = far_position.next(move_);
}
far_position = far_position.next(move_);
match grid.get(&far_position) {
Some(GridValue::Wall) => {}
Some(GridValue::Blank) => {
swap_points(grid, next_position, far_position);
swap_points(grid, *robot_position, next_position);
*robot_position = next_position;
}
_ => unreachable!(),
}
}
_ => unreachable!(),
}
}
#[inline]
fn swap_points(grid: &mut HashMap<Point, GridValue>, point_a: Point, point_b: Point) {
if point_a == point_b {
return;
}
let value_a = grid.remove(&point_a).unwrap();
let value_b = grid.remove(&point_b).unwrap();
grid.insert(point_b, value_a);
grid.insert(point_a, value_b);
}Part Two
Now, the grid needs to be widened horizontally and each spot on the grid that earlier occupied one spot will now occupy 2 spots. The robot remains one point large but the boxes now consist of two points next to each other.
This now means that boxes can be aligned such that a single box can push two boxes when moving vertically (see the puzzle description for more details and an example). Those two boxes could then also push many more boxes. We still need to find the sum of the final GPS coordinates of each box to get our answer.
To solve part 2, we first extend our GridValue enum to handle the new type of boxes. We then need to widen the grid. We then continue similarily to part 1 but with a different function for executing moves.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
enum GridValue {
Wall,
Box,
Robot,
Blank,
// Part 2 values
BoxOpening,
BoxClosing,
}
fn widen_grid(grid: &mut HashMap<Point, GridValue>) {
let mut new_grid = HashMap::with_capacity(grid.len() * 2);
for (&Point { row, col }, &v) in grid.iter() {
new_grid.extend(
[
Point {
row: row,
col: 2 * col,
},
Point {
row: row,
col: 2 * col + 1,
},
]
.iter()
.copied()
.zip(match v {
v @ GridValue::Wall | v @ GridValue::Blank => [v, v],
GridValue::Box => [GridValue::BoxOpening, GridValue::BoxClosing],
GridValue::Robot => [GridValue::Robot, GridValue::Blank],
_ => unreachable!(),
}),
);
}
*grid = new_grid;
}
fn part2((grid, moves): &(HashMap<Point, GridValue>, Vec<Vec<Move>>)) -> i32 {
let mut grid = grid.clone();
widen_grid(&mut grid);
let mut robot_position = grid
.iter()
.find(|(_pt, val)| **val == GridValue::Robot)
.map(|(pt, _val)| *pt)
.expect("no robot in input");
for move_line in moves {
for &move_ in move_line {
make_move_p2(&mut grid, &mut robot_position, move_);
}
}
grid.into_iter()
.filter(|(_pt, val)| val == &GridValue::BoxOpening)
.map(|(pt, _val)| pt.gps())
.sum()
}Our new movement execution function is the same when the next position is a wall or is blank but now has two cases when pushing boxes, one for moving horizontally and one for moving vertically.
The horizontal case is the simpler one and is similar to the part 1 code. We find the chain of box spots and if the spot after the end of the chain is empty, we now shift each box value starting from the end of chain one by one since there are now two types of box values on the grid. We then move the robot to the newly formed blank spot at its next position.
The vertical case is more complex. We maintain a group of points that we have to shift as a list of levels to move. This list is initialized with a single level with a single point: the robot position. We then continually add the next level of points to this list by looking in the direction of the move from the current level points. This next level is then expanded to cover both points of each box before the next iteration of the loop. If we encounter any wall in the next level, we break the loop of adding new levels to our group, ending the function. If the next level of points completely consists of blank spots, we shift the entire group of points level by level starting from the last added level and then update the robot position variable, then end the function by breaking the loop.
fn make_move_p2(grid: &mut HashMap<Point, GridValue>, robot_position: &mut Point, move_: Move) {
let next_position = robot_position.next(move_);
match grid.get(&next_position).copied() {
Some(GridValue::Blank) => {
swap_points(grid, *robot_position, next_position);
*robot_position = next_position;
}
Some(GridValue::Wall) => {}
Some(GridValue::BoxOpening | GridValue::BoxClosing) => {
if let Move::West | Move::East = move_ {
let mut shifted_points = vec![next_position];
while let Some(GridValue::BoxOpening | GridValue::BoxClosing) =
grid.get(&shifted_points.last().copied().unwrap().next(move_))
{
shifted_points.push(shifted_points.last().copied().unwrap().next(move_));
}
shifted_points.push(shifted_points.last().copied().unwrap().next(move_));
match grid.get(shifted_points.last().unwrap()) {
Some(GridValue::Wall) => {}
Some(GridValue::Blank) => {
shifted_points.reverse();
for points_to_swap in shifted_points.windows(2) {
swap_points(grid, points_to_swap[0], points_to_swap[1]);
}
swap_points(grid, *robot_position, next_position);
*robot_position = next_position;
}
_ => unreachable!(),
}
} else {
let mut shifted_points = {
let mut x = HashSet::new();
x.insert(*robot_position);
vec![x]
};
'outer: loop {
let mut next_level = HashSet::new();
let mut all_blank = true;
for &last_level_point in shifted_points.last().unwrap() {
match grid.get(&last_level_point.next(move_)) {
Some(GridValue::Wall) => {
break 'outer;
},
Some(GridValue::Blank) => {}
Some(GridValue::BoxOpening) | Some(GridValue::BoxClosing) => {
all_blank = false;
next_level.insert(last_level_point.next(move_));
}
other @ _ => {
panic!("{:?} @ {:?}", other, &last_level_point.next(move_))
}
}
}
if all_blank {
// shift boxes and robot
for point_set in shifted_points.into_iter().rev() {
for point in point_set {
swap_points(grid, point, point.next(move_));
}
}
*robot_position = next_position;
break;
}
// expand next level
let mut next_level_extra = Vec::new();
for &point in next_level.iter() {
let extra_point = match grid.get(&point) {
Some(GridValue::BoxOpening) => point.next(Move::East),
Some(GridValue::BoxClosing) => point.next(Move::West),
_ => unreachable!(),
};
next_level_extra.push(extra_point);
}
next_level.extend(next_level_extra);
shifted_points.push(next_level);
}
}
}
_ => unreachable!(),
}
}