Today’s puzzle was my favourite type of Advent of Code puzzles: pure programming and data structure manipulation and no need to know any specific tricks. It was also quite a long one, took me a good five and a half hours to get through.
Read input
Today’s input is two-parter.
First section is a map:
##########
#..O..O.O#
#......O.#
#.OO..O.O#
#..O@..O.#
#O#..O...#
#O..O..O.#
#.OO.O.OO#
#....O...#
##########where # is a wall, O is a box, @ is a robot and . is an empty space.
Second section is a sequence of movements:
<vv>^<v^>v>^vv^v>v<>v^v<v<^vv<<<^><<><>>v<vvv<>^v^>^<<<><<v<<<v^vv^v>^
vvv<<^>^v^^><<>>><>^<<><^vv^^<>vvv<>><^^v>^>vv<>v<<<<v<^v>^<^^>>>^<v<v
><>vv>v^v^<>><>>>><^^>vv>v<^^^>>v^v^<^^>v^^>v^<^v>v<>>v^v^<v>v^^<^^vv<
<<v<^>>^^^^>>>v^<>vvv^><v<<<>^^^vv^<vvv>^>v<^^^^v<>^>vvvv><>>v^<<^^^^^
^><^><>>><>^^<<^^v>>><^<v>^<vv>>v>>>^v><>^v><<<<v>>v<v<v>vvv>^<><<>^><
^>><>^v<><^vvv<^^<><v<<<<<><^v<<<><<<^^<v<^^^><^>>^<v^><<<^>>^v<v^v<v^
>^>>^v>vv>^<<^v<>><<><<v<<v><>v<^vv<<<>^^v^>^^>>><<^v>>v^v><^^>>^<>vv^
<><^^>^^^<><vvvvv^v<v<<>^v<v>v<<^><<><<><<<^^<<<^<<>><<><^^^>^^<>^>v<>
^^>vv<^v^v<vv>^<><v<^v>^^^>>>^^vvv^>vvv<>>>^<^>>>>>^<<^v>^vvv<>^<><<v>
v^^>>><<^^<>>^v^<v^vv<>v^<<>^<^v^v><^<<<><<^<v><v<>vv>>v><v^<vv<>v^<<^The movements are split to multiple lines for readability but they are interpreted as one continuous set of movements.
map_data, movement_data = read_multisection_input(15, [str, str])
grid = create_grid(map_data.split("\n"), predicate=lambda x: x != ".")
position = [key for key, value in grid.items() if value == "@"][0]
del grid[position]
movements = "".join(movement_data.split("\n"))We read the sections as strings, then create a sparse grid where empty spaces are ignored. I then find the starting position (@) and delete that from the grid as we don’t need to keep the robot in the field.
Movements we combine into a single string.
Part 1
In the first part, we need to simulate the movements of the robot. Every time a robot is next to a box (O) and is moving towards it, it tries to push it. If there’s empty space behind it (or a line of boxes), each box in the sequence gets moved.
For example:
Move >:
########
#..@OO.#
##..O..#
#...O..#
#.#.O..#
#...O..#
#......#
########moves both top row boxes one step to right:
########
#...@OO#
##..O..#
#...O..#
#.#.O..#
#...O..#
#......#
########We start by defining a few helpers:
class Delta(NamedTuple):
dx: int
dy: int
MapData = list[str]
Grid = dict[Coordinate, str]
Direction = Literal["^", ">", "<", "v"]
directions = {
"^": Delta(0, -1),
">": Delta(1, 0),
"v": Delta(0, 1),
"<": Delta(-1, 0),
}Delta is a namedtuple that is used to calculate new positions. MapData, Grid and Direction are type aliases to better communicate what types of values are passed in and out of functions.
directions is a map that tells us how we calculate the next location based on the direction.
First, we find the next position and its contents from the current position:
def move(
position: Coordinate,
direction: Literal["^", ">", "<", "v"],
grid: Grid,
) -> Tuple[Coordinate, Grid]:
delta = directions[direction]
next_position = Coordinate(position.x + delta.dx, position.y + delta.dy)
next_spot = grid.get(next_position, None)If we run into an empty space, we move to that new location:
if next_spot is None:
return next_position, gridIf we run into a wall, we don’t do anything:
elif next_spot == "#":
return position, gridThe main logic happens when we run into a box. Here we keep track of all the positions that need to move (to_move) and keep calculating those positions for as long as there is another box.
Once we’ve run out of boxes, we check if we hit the wall and if we did, don’t move anything.
If we didn’t hit a wall, we move every item (starting from the last) one position and delete the old location. After that, we update the robot’s position and return both the new position and the grid.
elif next_spot == "O":
to_move = [next_position]
next_next_position = Coordinate(
next_position.x + delta.dx, next_position.y + delta.dy
)
next_spot = grid.get(next_next_position, None)
while next_spot == "O":
to_move.append(next_next_position)
next_next_position = Coordinate(
next_next_position.x + delta.dx, next_next_position.y + delta.dy
)
next_spot = grid.get(next_next_position, None)
if next_spot == "#":
return position, grid
for coord in to_move[::-1]:
n = Coordinate(coord.x + delta.dx, coord.y + delta.dy)
grid[n] = "O"
del grid[coord]
position = next_position
return position, gridThe desired output is a sum of each box’s GPS (Goods Positioning System) value. It’s calculated as 100 * distance from left edge + distance from top edge. In our coordinate system terms, it’s 100 * x + y.
def part_1():
map_data, movement_data = read_multisection_input(15, [str, str])
grid = create_grid(map_data.split("\n"), predicate=lambda x: x != ".")
position = [key for key, value in grid.items() if value == "@"][0]
del grid[position]
movements = "".join(movement_data.split("\n"))
for movement in movements:
position, grid = move(position, movement, grid)
gps = 0
for coord, value in grid.items():
if value == "O":
gps += coord.y * 100 + coord.x
print(f"Part 1: {gps}")That was fun!
Part 2
The second part adds a bit of complexity but without increasing the computational complexity in any meaningful way.
To do that, we need to expand the map input, making everything but the robot twice as wide:
#becomes##.becomes..Obecomes[]@becomes@.
The twist of this part is that boxes now take up two spaces so calculating how to push them up and down changes significantly.
To create this new expanded grid, we do:
def create_expanded_grid(data: MapData) -> Tuple[Grid, Coordinate]:
"""Creates a grid based on the expansion rules:
1. . -> ..
2. # -> ##
3. O -> []
4. @ -> @.
:returns Grid
"""
grid = {}
start_position = None
for y, row in enumerate(data):
x = 0
for _, cell in enumerate(row):
if cell == "#":
grid[Coordinate(x, y)] = cell
grid[Coordinate(x + 1, y)] = cell
elif cell == "O":
grid[Coordinate(x, y)] = "["
grid[Coordinate(x + 1, y)] = "]"
elif cell == "@":
start_position = Coordinate(x, y)
x += 2
return grid, start_positionWe move 2 x positions for each cell in the input and expand according to the rules.
The new move function starts as previously:
def move_expanded(
position: Coordinate,
direction: Direction,
grid: Grid,
) -> Tuple[Coordinate, Grid]:
delta = directions[direction]
next_position = Coordinate(position.x + delta.dx, position.y + delta.dy)
next_spot = grid.get(next_position, None)
if next_spot is None:
return next_position, grid
elif next_spot == "#":
return position, gridIf we encounter a wall or an empty spot, we either move to it or stop.
If the spot is part of a box ([ or ]), we need new logic:
elif next_spot in "[]":
if direction in "<>":
return push_horizontally(position, direction, grid)
if direction in "^v":
return push_vertically(position, direction, grid)Since going left/right is very different from going up/down, I split those two in separate functions.
Left/right is the easier. Compared to our first part’s solution, the only difference is that now each box is two coordinates wide.
def push_horizontally(position: Coordinate, direction: Direction, grid: Grid):
delta = directions[direction]
next_position = Coordinate(position.x + delta.dx, position.y + delta.dy)
next_spot = grid.get(next_position, None)
x = next_position.x
# Go to the end of a line of boxes
while next_spot in "[]":
next_spot = grid.get(Coordinate(x + delta.dx, next_position.y), ".")
x += delta.dx
# If there's a wall at the end, move nothing
if next_spot == "#":
return position, grid
# If there's an empty spot
if next_spot == ".":
# Walk back from the empty spot
while x != next_position.x:
# Replace spot with its neighbour
grid[Coordinate(x, next_position.y)] = grid[
Coordinate(x - delta.dx, next_position.y)
]
x -= delta.dx
# Remove the first moved item so we don't duplicate
del grid[next_position]
return next_position, grid
We continue walking along the x axis until we find something that is not part of a box (either [ or ]). If it’s a wall, we do nothing. If it’s an empty space, we move all the items to that direction one at a time and finally we return robot’s new location and the modified grid.
The real challenge comes in the vertical push. I feel like my solution is overly complex and it does some double work but it helped me build it step-by-step and after it took so long, I didn’t feel like refactoring it today.
def push_vertically(position: Coordinate, direction: Direction, grid: Grid):
delta = directions[direction]
# Check if we can push the full stack
if not can_push_up_or_down(position, direction, grid):
return position, gridFirst we check if the stack can be pushed to the desired direction.
def can_push_up_or_down(position: Coordinate, direction: Direction, grid: Grid) -> bool:
"""Determines recursively if a stack of [] boxes can be moved to given up/down direction"""
delta = directions[direction]
above_or_below = grid.get((position.x, position.y + delta.dy))
if above_or_below is None:
return True
coordinates: list[Coordinate] = []
if above_or_below == "[":
coordinates.append(Coordinate(position.x, position.y + delta.dy))
coordinates.append(Coordinate(position.x + 1, position.y + delta.dy))
elif above_or_below == "]":
coordinates.append(Coordinate(position.x, position.y + delta.dy))
coordinates.append(Coordinate(position.x - 1, position.y + delta.dy))
elif above_or_below == "#":
return False
return all(
can_push_up_or_down(coordinate, direction, grid) for coordinate in coordinates
)Every time we see part of a box in the next row, we add both of its coordinates into the next row to be checked. If at any point, we run into a wall, the stack cannot be moved. If all paths lead to empty slots, we know we can move the stack.
# Find coordinates for each item to be pushed
to_move = get_coordinates_for_vertical_push(direction, grid, set([position])) - set(
[position]
) # Remove starting position as that gets moved separatelyTo move the stack, we then find all the coordinates for the box pieces that are part of that stack. Here we do a lot of repeated work that likely could be combined with the above:
def get_coordinates_for_vertical_push(
direction: Direction,
grid: Grid,
coordinates: set[Coordinate],
) -> list[Coordinate]:
delta = directions[direction]
# If we have coordinates and all of the spots
# above or below them are empty, return all current coordinates
if coordinates and all(
grid.get((c.x, c.y + delta.dy)) is None for c in coordinates
):
return coordinates
# Find the next row to check
next_row = set()
# For every coordinate in the previous row
for coord in coordinates:
above_or_below = grid.get((coord.x, coord.y + delta.dy))
# If left side of the box, add it and its right neighbour
if above_or_below == "[":
next_row.add(Coordinate(coord.x, coord.y + delta.dy))
next_row.add(Coordinate(coord.x + 1, coord.y + delta.dy))
# If right side of the box, add it and its left neighbour
elif above_or_below == "]":
next_row.add(Coordinate(coord.x, coord.y + delta.dy))
next_row.add(Coordinate(coord.x - 1, coord.y + delta.dy))
# Recusively go through every position
return coordinates | get_coordinates_for_vertical_push(direction, grid, next_row)If all the coordinates above/below the current row are empty, we’ve reached the end of the stack. Otherwise we go through each of those above/below coordinates and if we find more boxes, we add them to the next check.
Then we move all of those box pieces to their correct next spots:
# Sort them by y axis so we're always moving from the end first
reverse = not (direction == "^")
to_move = sorted(to_move, key=lambda x: x.y, reverse=reverse)
for coordinate in to_move:
# Move each item to their next position
grid[Coordinate(coordinate.x, coordinate.y + delta.dy)] = grid[coordinate]
# Delete moved item
del grid[coordinate]We sort the coordinates by y axis so that I don’t accidentally overwrite some coordinates.
Finally, we return the new position for our robot and the updated grid:
return Coordinate(position.x, position.y + delta.dy), gridSecond part’s wrapper is then almost the same as first one:
def part_2():
map_data, movement_data = read_multisection_input(15, [str, str])
movements = "".join(movement_data.split("\n"))
grid, position = create_expanded_grid(map_data.split("\n"))
for movement in movements:
position, grid = move_expanded(position, movement, grid)
gps = 0
for coord, value in grid.items():
if value == "[":
gps += coord.y * 100 + coord.x
print(f"Part 2: {gps}")I managed to get it to work with the test input but it failed with my full input. (The above code is my working final code.)
Given that there are 20 000 steps and a grid of 99x49, finding the mistake manually was not gonna get me through it and I got quite frustrated. All the corner cases I was able to come up with passed and I had a hard time finding what the issue could be.
Luckily, I’m not the only one solving these puzzles.
Toni offered his code so I can print the grids for each step with my malfunctioning code and his correct code. So I did and saved both to text files:
python day_15.py > incorrect
python tonis_solution.py > correctI then compared them line by line to find the first occasion where the mistake happened using cmp:
cmp incorrect correct
and it immediately found the mistake. On line 330 735. Good thing I didn’t try to go through them manually:
correct incorret differ: char 32170234, line 330735I searched the output file for the given line, found the issue and created a reproduction to test:
0 ####################
1 ##................##
2 ##................##
3 ##......[][]......##
4 ##........[]......##
5 ##.......[].......##
6 ##.......@........##
7 ##................##
8 ##................##
9 ####################It turned out, my original code moved the top left box. I found the issue, fixed the code and got to the right outcome.
Team work makes the dream work!