Advent of code 2024 - Day 14 of 25
Table of Contents
The fourteenth day of Advent of Code was yesterday 14/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 and Day 13.
I classified the fourteenth problem as medium (part 1) and medium (part 2).
Tips#
- Another maze problem :-D It’s very good to have a Maze class.
- This problem also uses vectors, the Vector2d class will be very useful.
- You can use a regular expression to extract data from the input.
- Organizing code into classes is good practice. In this case, each robot is clearly an object.
- Remember integer division to calculate the middle column and rows.
- Each robot has a position and a velocity vector.
- When the robot moves to a position outside the maze (Zone), it can be corrected using the modulo operator (see chapter 2, properties of division remainder).
- You can see time advancement as a simulation.
- Use test values to verify if your solution answers the problem. Start by testing robot movement and then the teleportation that occurs when they move outside the Zone.
- Part 2 is a bit different from the others. We need to find a Christmas pattern in the robots’ positions.
- After manually running the simulation and examining the output frames, we can determine that the solution appears when the robots form a Christmas figure a bit less than 8000 seconds. This occurs at the first simulation step where no robots overlap (occupy the same position). The problem statement doesn’t make this requirement explicit.
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
- Reduce - Chapter 8
- Classes, inheritance - Chapter 10
- Regular expressions - Chapter 12
Answer#
import sys
import re
from functools import reduce
from aux import (
Vector2d,
Maze,
string_to_list,
read_file_without_blank_lines,
)
E_REGEX = r"p=(\-*\d+),(\-*\d+) v=(\-*\d+),(\-*\d+)"
robot_line = re.compile(E_REGEX)
INPUT = """
p=0,4 v=3,-3
p=6,3 v=-1,-3
p=10,3 v=-1,2
p=2,0 v=2,-1
p=0,0 v=1,3
p=3,0 v=-2,-2
p=7,6 v=-1,-3
p=3,0 v=-1,-2
p=9,3 v=2,3
p=7,3 v=-1,2
p=2,4 v=2,-3
p=9,5 v=-3,-3
"""
class Robot:
def __init__(self, position: Vector2d, velocity: Vector2d):
self.position = position
self.velocity = velocity
def move(self, limits: Vector2d):
self.position.x = (self.position.x + self.velocity.x) % limits.x
self.position.y = (self.position.y + self.velocity.y) % limits.y
def __repr__(self):
return f"Robot(position={self.position}, velocity={self.velocity})"
def get_input(input: str) -> list[Robot]:
robots = []
for line in input:
robot = [int(x) for x in robot_line.findall(line)[0]]
robots.append(Robot(Vector2d(robot[1], robot[0]), Vector2d(robot[3], robot[2])))
return robots
class Zone(Maze):
def __init__(self, width, height):
maze = [" " * width for _ in range(height)]
super().__init__(maze)
def draw(self, background="."):
self.background = background
self.drawing = []
for _ in range(self.max_y):
self.drawing.append([background] * self.max_x)
def draw_robots(self, robots: list[Robot]):
for robot in robots:
current = self.drawing[robot.position.y][robot.position.x]
new = chr(ord(current) + 1) if current != self.background else "1"
self.drawing[robot.position.y][robot.position.x] = new
def dump_drawing(self, output=sys.stdout):
for line in self.drawing:
print("".join(line), file=output)
class Problem:
def __init__(self, input: str, width: int, height: int):
self.robots = get_input(string_to_list(input))
self.zone = Zone(width, height)
def draw(self):
self.zone.draw()
self.zone.draw_robots(self.robots)
self.zone.dump_drawing()
def move(self):
for robot in self.robots:
robot.move(Vector2d(self.zone.max_y, self.zone.max_x))
def calculate_safety_factor(self):
quadrants = [0, 0, 0, 0]
middle = Vector2d(self.zone.max_y // 2, self.zone.max_x // 2)
for robot in self.robots:
if robot.position.x == middle.x or robot.position.y == middle.y:
continue
qx = 1 if robot.position.x > middle.x else 0
qy = 1 if robot.position.y > middle.y else 0
quadrants[qx + qy * 2] += 1
return reduce(lambda x, y: x * y, quadrants, 1)
def check_overlap(self):
occupied = set()
for robot in self.robots:
if robot.position in occupied:
return True
occupied.add(robot.position)
return False
# Part 1 - Test
problem = Problem(INPUT, width=11, height=7)
for i in range(100):
problem.move()
safety_factor = problem.calculate_safety_factor()
print("Safety factor - Part 1 - Test:", safety_factor)
assert safety_factor == 12
# Part 1
problem = Problem(
read_file_without_blank_lines("14/input.txt"), width=101, height=103
)
for i in range(100):
problem.move()
safety_factor = problem.calculate_safety_factor()
print("Safety factor - Part 1:", safety_factor)
assert safety_factor == 221655456
# Part 2 - Looking for the Christmas pattern
problem = Problem(
read_file_without_blank_lines("14/input.txt"), width=101, height=103
)
for i in range(1, 100000):
problem.move()
if not problem.check_overlap():
problem.draw()
print(f"Part 2 - No overlap found at second {i}")
break
# Output:
# Safety factor - Part 1 - Test: 12
# Safety factor - Part 1: 221655456
# 1........11..................1.......................................................................
# .................................................................................................1...
# .............................................1.......................................................
# ................1................11..................1....................1..........................
# .......1.............................................................................................
# ........................................................................1............................
# .....................................................................................................
# .....................................................................................................
# .........................................1...........................................................
# ..............1..............................................1.......................................
# .....................................................................................................
# ...................................................1..................................1..............
# ...................................................................1.................................
# ........1...........................................................................1................
# .................................1...................................................................
# ..1.................1................................................................................
# .............1..................1.....................................1..............................
# ...................1......................................................................1..........
# ................1..................1..............................1..................................
# .......1.............................................................................................
# .............................................11.....................1..............1.................
# ............................................................................1........................
# .............1.......................................................................................
# ...................................................1.................................................
# .................1...................................................................................
# ........................................................1............................................
# ...................1.................................................................................
# .................1.................................................................................1.
# ................................1...........1..................................................1.....
# ...................1.............................................................1...................
# ..................................................1.............................1.1.............1....
# .....................................................................................................
# .............................................................................1.......................
# ..................................................................1..................................
# .....................................................1...............1...............................
# 1...............................................................................1............1.......
# ...........................................................................................1.........
# ..................................................1..........................................1.......
# ...................1......................................................................1..........
# .......................................................................1........................1....
# ......................1..........................................................................1...
# .............................................1.......................................................
# ..........................................................................................1..........
# ............1.............................................................................1..........
# ...................................1111111111111111111111111111111...................................
# ...................................1.............................1..........1........................
# ...................................1.............................1...................................
# ...................................1.............................1...................................
# ...................................1.............................1...................................
# ...................................1..............1..............1.....................1.............
# ...................................1.............111.............1...................................
# ....1..............................1............11111............1...................................
# ...................................1...........1111111...........1...................................
# ..............................1....1..........111111111..........1...................................
# ...................................1............11111............1...................1...............
# ................1..................1...........1111111...........1...................................
# ...................................1..........111111111..........1...................................
# ....................1..............1.........11111111111.........1...................................
# ...................................1........1111111111111........1...................................
# ..1..........1..........1..........1..........111111111..........1......................1............
# ...................................1.........11111111111.........1...............1...................
# ...................................1........1111111111111........1...................................
# ...................................1.......111111111111111.......1..............1....................
# ...................................1......11111111111111111......1..................1.............1..
# ...............................1...1........1111111111111........1..1................................
# ........................1..........1.......111111111111111.......1......1............................
# .................1.....1...........1......11111111111111111......1...................................
# ...................................1.....1111111111111111111.....1......1............................
# ...............1...................1....111111111111111111111....1..........1........................
# .....................1.....1.......1.............111.............1.........................1.........
# ..........................1........1.............111.............1...................................
# ...................................1.............111.............1...................................
# ...................................1.............................1...................................
# ...................................1.............................1.....................1.............
# .....1.............................1.............................1...................................
# ...................................1.............................1............1........1.............
# ...................................1111111111111111111111111111111...................................
# .....................................................................................................
# .....................................................................................................
# ..................1.........................................1....................................1...
# .....................................................................................................
# 1.................................................................................................1..
# .......................................1...............1.............................................
# ...............................................1.....................................................
# .....................................................................................1...............
# ..........................................11................1........................................
# ....1................................................................................................
# 1...1.........................................1...........................1.....1....................
# .............................1.....1...........................................1.....................
# .1..................................................1............................................1...
# ...............1...........................................1...........................1.......1.....
# .....................................................................................................
# .......1.............................................................................................
# .....................................................................................................
# ...........................................1..................................1......................
# .....................1.............................................................................1.
# .................................................................1...................................
# .....................................................................................................
# ...1..1.....1........................................................................................
# .....................................................................................................
# ............................1........................................................................
# ......................................................1......................1.......................
# .........................................1...........................................................
# Part 2 - No overlap found at second 7858
Aux module#
from functools import total_ordering
def signal(x: int) -> int:
return 1 if x > 0 else -1 if x < 0 else 0
def string_to_list(input: str) -> list[str]:
return [line.strip() for line in input.splitlines() if line]
def string_to_matrix(input: str) -> list[list[str]]:
return [list(line.strip()) for line in input.splitlines() if line]
def string_to_int_matrix(input: str, separator=" ") -> list[list[int]]:
return [
[int(l) for l in line.split(separator)]
for line in input.splitlines()
if line
]
def read_file(filename: str) -> str:
with open(filename, "r") as f:
return f.read()
def read_file_without_blank_lines(filename: str) -> str:
return "\n".join(
zz
for line in read_file(filename).splitlines()
if len(zz := line.strip()) > 0
)
def one_list_per_line(filename: str, separator=None) -> list[str]:
return [
[int(l) for l in line.split(separator)]
for line in read_file_without_blank_lines(filename).splitlines()
]
@total_ordering
class Vector2d:
def __init__(self, y, x):
self.x = x
self.y = y
def copy(self):
return Vector2d(self.y, self.x)
def __add__(self, other):
return Vector2d(self.y + other.y, self.x + other.x)
def __sub__(self, other):
return Vector2d(self.y - other.y, self.x - other.x)
def __str__(self):
return f"({self.y}, {self.x})"
def __repr__(self):
return f"Vector2d({self.y}, {self.x})"
def __hash__(self):
return hash(f"({self.y}, {self.x})")
def __eq__(self, other):
if isinstance(other, Vector2d):
return self.x == other.x and self.y == other.y
return False
def __le__(self, other):
return self.y < other.y or (self.y == other.y and self.x < other.x)
class Maze:
def __init__(self, maze):
self.max_y = len(maze)
self.max_x = len(maze[0])
self.orig_maze = maze
self.maze = [list(line) for line in maze]
def copy(self):
return Maze(self.orig_maze)
def valid_position(self, position: Vector2d) -> bool:
return 0 <= position.y < self.max_y and 0 <= position.x < self.max_x
def __str__(self):
return "\n".join(["".join(line) for line in self.maze])
def __setitem__(self, yx, value):
self.maze[yx[0]][yx[1]] = value
def __getitem__(self, yx):
if type(yx) is Vector2d:
return self.maze[yx.y][yx.x]
return self.maze[yx[0]][yx[1]]