Advent of Code 2024 - Day 08 of 25
Table of Contents
The eighth day of Advent of Code was yesterday 08/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 and Day 7.
I classified the eighth problem as easy (part 1) and easy (part 2).
Tips#
-
The problem also uses a kind of maze to represent the map.
-
If you consider each pair of antennas as points, you can imagine a line passing between them.
-
If you have the positions of two antennas as vectors, the difference between their coordinates contains the vector that represents the line.
-
You can find other points on the same line by subtracting and adding the vector to points you already know on the same line.
-
Part 1 is basically creating the list of anti-signals and counting how many are unique.
-
In part 2, you can extend the line, creating multiple points with a loop. Don’t forget to break the loop once the coordinates start exceeding the map limits.
How much Python do you need to know?#
The chapters refer to my book Introduction to Programming with Python.
- Lists, sets, dictionaries - Chapter 6
- Classes - Chapter 10
- itertools - Chapter 8
- Some linear algebra or basic vector concepts
Solution#
from itertools import combinations
from helpers import (
string_to_matrix,
Vector2d,
Maze,
read_file_without_blank_lines,
)
INPUT = """
............
........0...
.....0......
.......0....
....0.......
......A.....
............
............
........A...
.........A..
............
............
"""
class Field(Maze):
def __init__(self, maze: list[list[str]]):
super().__init__(maze)
self.anti_signals = {}
self.find_antennas()
def draw(self, path: dict[str, list[Vector2d]], character="X"):
for path in path.values():
for position in path:
if self.valid_position(position):
self[position.y, position.x] = character
def find_antennas(self):
self.antennas = {}
for y, line in enumerate(self.maze):
for x, pos in enumerate(line):
if pos != ".":
self.antennas[pos] = self.antennas.get(pos, []) + [Vector2d(y, x)]
def generate_anti_signal(self):
self.anti_signals = {}
for antenna, positions in self.antennas.items():
if len(positions) > 1:
for p1, p2 in combinations(positions, 2):
d = p2 - p1
if self.valid_position(as1 := p1 - d):
self.new_anti_signal(antenna, as1)
if self.valid_position(as2 := p2 + d):
self.new_anti_signal(antenna, as2)
def new_anti_signal(self, antenna, position: Vector2d):
self.anti_signals[antenna] = self.anti_signals.get(antenna, []) + [position]
def generate_anti_signal_with_resonance(self):
self.anti_signals = {}
for antenna, positions in self.antennas.items():
for position in self.antennas[antenna]:
self.new_anti_signal(antenna, position)
if len(positions) > 1:
for p1, p2 in combinations(positions, 2):
d = p2 - p1
while self.valid_position(as1 := p1 - d):
self.new_anti_signal(antenna, as1)
p1 = as1
while self.valid_position(as2 := p2 + d):
self.new_anti_signal(antenna, as2)
p2 = as2
def count_anti_signals(self):
unique = set()
for a in self.anti_signals.values():
for anti_signal in a:
unique.add(anti_signal)
return len(unique)
test_input = string_to_matrix(INPUT)
field = Field(test_input)
field.generate_anti_signal()
answer_part_1_test = field.count_anti_signals()
print("unique anti-signals (test - part 1):", answer_part_1_test)
assert answer_part_1_test == 14
input_part_1 = string_to_matrix(read_file_without_blank_lines("08/input.txt"))
field_part_1 = Field(input_part_1)
field_part_1.generate_anti_signal()
answer_part_1 = field_part_1.count_anti_signals()
print("unique anti-signals (part 1):", answer_part_1)
assert answer_part_1 == 276
field = Field(test_input)
field.generate_anti_signal_with_resonance()
answer_part2_test = field.count_anti_signals()
print("unique anti-signals with resonance (test - part 2):", answer_part2_test)
assert answer_part2_test == 34
field_part_2 = Field(input_part_1)
field_part_2.generate_anti_signal_with_resonance()
answer_part_2 = field_part_2.count_anti_signals()
print("unique anti-signals with resonance (part 2):", answer_part_2)
assert answer_part_2 == 991
# Output
# unique anti-signals (test - part 1): 14
# unique anti-signals (part 1): 276
# unique anti-signals with resonance (test - part 2): 34
# unique anti-signals with resonance (part 2): 991
Helper Module#
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
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):
return self.maze[yx[0]][yx[1]]
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
)