Advent of code 2024 - Day 15 of 25
Table of Contents
The fifteenth day of Advent of Code was yesterday 15/12/2024! If you’re here for the first time today, don’t forget to read the posts about Day 1, Day 2, Day 3, Day 4, Day 5, Day 6, Day 7, Day 8, Day 9, Day 10, Day 11, Day 12, Day 13 and Day 14.
I classified the fifteenth problem as medium (part 1) and medium (part 2).
Tips#
- The first part of the problem is to read the maze (warehouse) and the robot commands.
- Use the example inputs to test the solution.
- You need to detect in the maze input where the walls, robot, and boxes are.
- The commands are on multiple lines, it’s easier if you concatenate them into a single string.
- You can implement robot directions (commands) using vectors.
- Vectors can also be used to mark box and wall positions.
- The walls surround the entire warehouse, you don’t need to worry about the robot leaving the warehouse.
- To check if the robot can move, verify if the new position is free. In this case, move the robot by updating its position.
- If the next position is occupied by a wall, the robot cannot move and stays in the same place.
- To know if boxes can be moved, you can recursively try all boxes from the movement direction. For each box, check if it can move (blank space in the movement direction). If one of the boxes cannot be moved, the movement is canceled.
- Remember that the robot can push multiple boxes at once. A recursive function can help solve this problem.
- In part 1, boxes are the same size as walls, meaning each box occupies one position. In part 2, each box occupies two positions.
- Part 2 is a bit more complex because you can move more than columns and rows of boxes, but entire parts of the warehouse.
- Horizontal movement is similar to part 1, as each box has a height of only one character, like in part 1.
- Each movement in part 2 can move up to 2 boxes at once. But this movement is done in cascade, so these two boxes can move other 2, 3, or more boxes. Each box movement can move zero, one, or two boxes at each step, but can cause the movement of many others.
- In part 2, you need to verify if the entire movement is valid. For example, when the boxes being pushed form a V or get stuck on a wall, they all have to stop moving. If you implement the movement function as in part 1, you’ll see that the boxes will move in several pieces, which leads to the wrong answer.
How much Python do you need to know?#
The chapters refer to my book Introduction to Programming with Python.
- Lists - Chapter 6
- Strings - Chapter 7
- Recursive Functions - Chapter 8
- Classes, inheritance - Chapter 10
Answer#
Here’s the code that solves the problem. You’ll see the scars in the code from switching between part 1 and part 2, but the code works relatively well.
You can use the Warehouse, Boxes, Wall, Robot, Problem, and Problem2 classes to debug your solution. The draw and prompt methods can help interpret and draw the commands step by step. Although they’re not called in the answer, they’re in the code if you need them.
import sys
from helpers import read_file_without_blank_lines, Vector2d, Maze
TEST_INPUT = """
########
#..O.O.#
##@.O..#
#...O..#
#.#.O..#
#...O..#
#......#
########
<^^>>>vv<v>>v<<
"""
INPUT = """
##########
#..O..O.O#
#......O.#
#.OO..O.O#
#..O@..O.#
#O#..O...#
#O..O..O.#
#.OO.O.OO#
#....O...#
##########
<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^<<^
"""
def read_input(input: str) -> tuple[str, str]:
maze = []
commands = []
for line in input.splitlines():
if not line.strip():
continue
if line.startswith("#"):
maze.append(line)
else:
commands.append(line)
return maze, commands
class Vector2dWithSymbol(Vector2d):
def __init__(self, y, x, symbol):
super().__init__(y, x)
self.symbol = symbol
def __add__(self, other):
return Vector2dWithSymbol(self.y + other.y, self.x + other.x, self.symbol)
def __sub__(self, other):
return Vector2dWithSymbol(self.y - other.y, self.x - other.x, self.symbol)
class Box(Vector2dWithSymbol):
def __init__(self, y, x, symbol="O"):
super().__init__(y, x, symbol)
class Wall(Vector2dWithSymbol):
def __init__(self, y, x):
super().__init__(y, x, "#")
class Robot(Vector2dWithSymbol):
def __init__(self, y, x):
super().__init__(y, x, "@")
class Warehouse(Maze):
def init_drawing(self, background="."):
self.background = background
self.drawing = []
for _ in range(self.max_y):
self.drawing.append([background] * self.max_x)
def draw(self, objects: list[Vector2dWithSymbol]):
for obj in objects:
self.drawing[obj.y][obj.x] = obj.symbol
def dump_drawing(self, output=sys.stdout):
for line in self.drawing:
print("".join(line), file=output)
def __iter__(self):
return iter(self.maze)
class Problem:
DIRECTIONS = {
"<": Vector2d(0, -1),
"^": Vector2d(-1, 0),
">": Vector2d(0, 1),
"v": Vector2d(1, 0),
}
def __init__(self, maze: list[str], commands: list[str]):
self.commands = "".join(commands)
self.warehouse = Warehouse(maze)
self.setup()
def setup(self):
self.walls = set()
self.boxes = dict()
self.robot = None
for y, line in enumerate(self.warehouse):
for x, char in enumerate(line):
if char == "#":
self.walls.add(Wall(y, x))
if char == "O":
box = Box(y, x)
self.boxes[box] = box
if char == "@":
self.robot = Robot(y, x)
def draw(self):
self.warehouse.init_drawing()
self.warehouse.draw(self.walls)
self.warehouse.draw(self.boxes)
self.warehouse.draw([self.robot])
self.warehouse.dump_drawing()
def execute_commands(self):
for command in self.commands:
direction = self.DIRECTIONS[command]
new_position = self.robot + direction
if new_position in self.boxes:
if not self.push(new_position, direction):
continue
elif new_position in self.walls:
continue
self.robot += direction
def push(self, position: Vector2d, direction: Vector2d, execute: bool = True):
new_position = position + direction
if new_position in self.walls:
return False
if new_position in self.boxes:
can_push = self.push(new_position, direction, execute)
if not can_push:
return False
if execute:
box = self.boxes.pop(position)
box.y = new_position.y
box.x = new_position.x
self.boxes[box] = box
return True
def gps_boxes(self):
total = 0
for box in self.boxes:
total += box.y * 100 + box.x
return total
def prompt(self):
while True:
self.draw()
commands = input("Commands: ").lower().strip()
if not commands:
break
self.commands = commands
self.execute_commands()
class Problem2(Problem):
def __init__(self, maze: list[str], commands: list[str]):
super().__init__(maze, commands)
self.warehouse.max_x *= 2
def setup(self):
self.walls = set()
self.boxes = dict()
self.robot = None
for y, line in enumerate(self.warehouse):
for x, char in enumerate(line):
if char == "#":
self.walls.add(Wall(y, x * 2))
self.walls.add(Wall(y, x * 2 + 1))
if char == "O":
box1 = Box(y, x * 2, "[")
box2 = Box(y, x * 2 + 1, "]")
self.boxes[box1] = box1
self.boxes[box2] = box2
if char == "@":
self.robot = Robot(y, x * 2)
def push(self, position: Vector2d, direction: Vector2d, execute: bool = True):
new_position = position + direction
if direction in [Vector2d(0, -1), Vector2d(0, 1)] or new_position in self.walls:
return super().push(position, direction, execute)
if position not in self.boxes:
return True
box1, box2 = self.find_box(position)
can_push1 = super().push(box1, direction, False)
can_push2 = super().push(box2, direction, False)
if can_push1 and can_push2:
if execute:
self.push_v(box1, box2, direction)
return True
return False
def find_box(self, position):
box1 = self.boxes[position]
if box1.symbol == "[":
box2 = self.boxes[position + Vector2d(0, 1)]
else:
box2 = self.boxes[position + Vector2d(0, -1)]
return box1, box2
def push_v(self, position1, position2, direction):
np1 = position1 + direction
np2 = position2 + direction
if np1 in self.boxes:
self.push_v(*self.find_box(np1), direction)
if np2 in self.boxes:
self.push_v(*self.find_box(np2), direction)
for position, new_position in zip([position1, position2], [np1, np2]):
box = self.boxes.pop(position)
box.y = new_position.y
box.x = new_position.x
self.boxes[box] = box
def gps_boxes(self):
total = 0
for box in self.boxes:
if box.symbol == "[":
total += box.y * 100 + box.x
return total
problem = Problem(*read_input(TEST_INPUT))
problem.execute_commands()
gps = problem.gps_boxes()
print("Part 1 - small input test:", gps)
assert gps == 2028
problem = Problem(*read_input(INPUT))
problem.execute_commands()
gps = problem.gps_boxes()
print("Part 1 - large input test:", gps)
assert gps == 10092
problem = Problem(*read_input(read_file_without_blank_lines("15/input.txt")))
problem.execute_commands()
gps = problem.gps_boxes()
print("Part 1 - large input:", gps)
assert gps == 1552463
# Part 2
problem = Problem2(*read_input(INPUT))
problem.execute_commands()
gps = problem.gps_boxes()
print("Part 2 - large input test:", gps)
assert gps == 9021
problem = Problem2(*read_input(read_file_without_blank_lines("15/input.txt")))
problem.execute_commands()
gps = problem.gps_boxes()
print("Part 2 - large input:", gps)
assert gps == 1554058