How to solve Advent of Code 2024 - Day 8 with Python
Back to grids with our first "radius"-related puzzle of the year.
But before we get right into the day and my solution for this day's puzzle, here is the info on how I approach this whole event (where my code is, what editor I use, etc):
Sarah Glasmacher
🎄❄️💻
Day 8 Puzzle
On my blog here, I will go through the puzzle and my way of solving it. If you want, you can jump directly to the code solution here:
GitHub .py script
Here is the challenge, if you want to read the full puzzle:
Advent of Code 2024 - Day 8
This day we are visiting a location from Advent of Code 2016, Day 25 - the... checks notes ... top-secret Easter Bunny installation. Alright then. 🐰
We are investigating mind-control, which is done here in the very traditional way of antennas. Our task is to find out how bad exactly the situation is by counting the number of unique locations of so-called "antinodes" - locations where the signal is the strongest, given some rules about distances to antennas.
Part 1
Day 8 gives us a grid input, where '.' are empty positions and any letter/number is an antenna with that frequency.
# Example input
............
........0...
.....0......
.......0....
....0.......
......A.....
............
............
........A...
.........A..
............
............
Solution Approach:
- read all the antenna positions in a grid/
numpyarray - calculate all antenna pairs (if there are 3 "0" antennas, each pair of those creates two antinodes)
- calculate the two antinodes per pair, enter them into an antinode grid (same size as the original antenna grid, but empty, so we don't run into collisions with the antennas)
- count the entries in the antinode grid
Key Code Snippets:
Help-functions for finding all antennas in the input: Note: the antennas are separated by their character/frequency. Each frequency is a key in the dictionary and has a list of antennas. Antennas of different frequencies don't mix.
def find_antenna_positions(
antenna_grid: np.ndarray,
) -> dict[str, list[tuple[int, int]]]:
antenna_positions = {}
for i, row in enumerate(antenna_grid):
for j, cell in enumerate(row):
if cell != ".":
if cell not in antenna_positions:
antenna_positions[cell] = []
antenna_positions[cell].append((i, j))
return antenna_positions
Fill the antinode grid:
def calculate_antinode_grid(
antenna_grid: np.ndarray,
antenna_positions: dict[str, list[tuple[int, int]]],
part2: bool = False,
) -> np.ndarray:
antinode_grid = np.zeros(antenna_grid.shape)
for _, positions in antenna_positions.items():
antenna_pairs = (
(pos1, pos2)
for i, pos1 in enumerate(positions)
for pos2 in positions[i + 1 :]
)
for antenna_1, antenna_2 in antenna_pairs:
if part2:
# different algorithm for computing positions in part 2
antinode_positions = (
calculate_antinode_positions_for_antenna_pair_part2(
antenna_1, antenna_2, antenna_grid
)
)
else:
antinode_positions = calculate_antinode_positions_for_antenna_pair(
antenna_1, antenna_2
)
for antinode_position in antinode_positions:
if check_if_position_still_on_grid(antinode_grid, antinode_position):
antinode_grid[antinode_position] = 1
return antinode_grid
Get the antinode position for one pair of antennas:
- calculate the difference ("vector" of line through the two positions with the length between those two points)
- add that to
antenna_2for one direction, subtract that fromantenna_1for the other direction of the line
def calculate_antinode_positions_for_antenna_pair(
antenna_1: tuple[int, int], antenna_2: tuple[int, int]
) -> list[tuple[int, int]]:
difference = (antenna_2[0] - antenna_1[0], antenna_2[1] - antenna_1[1])
first_antinode = (antenna_2[0] + difference[0], antenna_2[1] + difference[1])
second_antinode = (antenna_1[0] - difference[0], antenna_1[1] - difference[1])
return [first_antinode, second_antinode]
Full Solution for Part 1:
def solve_part_1(mode: str = "example"):
file_lines = read_input_file(day=8, mode=mode)
antenna_grid = read_letter_grid_from_lines(file_lines)
antenna_positions = find_antenna_positions(antenna_grid)
antinode_grid = calculate_antinode_grid(antenna_grid, antenna_positions)
nr_of_antinodes = np.sum(antinode_grid)
return nr_of_antinodes
Part 2
We get more antinodes now - at every position on the line drawn through the two antennas.
What you need to consider is that on a grid-less field that would mean infinite antennas along a line. However we can only place antinodes on full grid tiles, so we can't have positions with less than full integers as coordinates.
For this I shorten the difference-vector to the shortest integers by dividing it by the greatest common divisor between the two entries:
def calculate_antinode_positions_for_antenna_pair_part2(
antenna_1: tuple[int, int], antenna_2: tuple[int, int], antenna_grid: np.ndarray
) -> list[tuple[int, int]]:
difference = (antenna_2[0] - antenna_1[0], antenna_2[1] - antenna_1[1])
# shorten distance by dividing by the greatest common divisor
divisor = gcd(abs(difference[0]), abs(difference[1]))
difference = (difference[0] // divisor, difference[1] // divisor)
antinode_positions = [antenna_2, antenna_1]
# one direction of antinodes (beyond antenna_2)
possible_antinode_position = (
antenna_2[0] + difference[0],
antenna_2[1] + difference[1],
)
while check_if_position_still_on_grid(antenna_grid, possible_antinode_position):
antinode_positions.append(possible_antinode_position)
antenna_2 = possible_antinode_position
possible_antinode_position = (
antenna_2[0] + difference[0],
antenna_2[1] + difference[1],
)
# other direction of antinodes (beyond antenna_1)
possible_antinode_position = (
antenna_1[0] - difference[0],
antenna_1[1] - difference[1],
)
while check_if_position_still_on_grid(antenna_grid, possible_antinode_position):
antinode_positions.append(possible_antinode_position)
antenna_1 = possible_antinode_position
possible_antinode_position = (
antenna_1[0] - difference[0],
antenna_1[1] - difference[1],
)
return antinode_positions
After shortening the step-size, just step farther and farther from antenna_2 and antenna_ respectively until you hit the edge of the grid. Due to the non-existing ability to properly add and subtract tuples in python, this looks gnarly. If you would use numpy arrays for every single position, you could add them like vectors, which would make it slightly prettier.
Conclusion
Vector calculations. This year has been really kind to math majors so far 😄