My first reaction today when I read that there are antennas involved:
Oh damn, a geometry puzzle.
I’m generally rubbish at them. There was a 3D geometry puzzle a few years back that absolutely broke me and I’m still not fully recovered.
Today turned out to be not that bad though so let’s crack on.
Read input
First of all, we’re once again dealing with grids so let’s start with a Coordinate tuple:
from collections import namedtuple
Coordinate = namedtuple("Coordinate", ["x", "y"])I wrote about the benefits of sparse grids earlier and today is a special case of that. Since we don’t care about the empty spots, we don’t have to read any of them into any kind of data structure.
def create_map(inputs):
antennas = defaultdict(set)
for y, row in enumerate(inputs):
for x, cell in enumerate(row):
if cell != ".":
antennas[cell].add(Coordinate(x, y))
grid_size = len(inputs)
return antennas, grid_sizeWe create a dictionary of sets where the key is the frequency and the set is all the coordinates that frequency antenna appears. We also calculate the grid size (if we’d deal with non-square grids, we’d need to calculate maximum x and y separately) so we can ignore all antinodes that fall outside the grid.
Part 1
In the first part, we get an input like this:
............
........0...
.....0......
.......0....
....0.......
......A.....
............
............
........A...
.........A..
............
............and need to figure out where antinodes are located based on the antennas.
For a more simplified example, let’s look at a map like this:
...#......
..........
....a.....
..........
.....a....
..........
......#...For each pair of antennas (here marked as a), two antinodes (#) are created at locations which are on the same line as the antennas and their distance from the two antennas is the same as the distance between the antennas themselves.
I have a feeling that my calculations for the antinode positions are bit convoluted so don’t take math advice from me, m’kay.
def sign(a, b):
return (a - b) // (abs(a - b))
def calculate_antinodes(pos1, pos2, grid_size):
diff = abs(pos1.x - pos2.x), abs(pos1.y - pos2.y)
pos1_signs = sign(pos1.x, pos2.x), sign(pos1.y, pos2.y)
pos2_signs = sign(pos2.x, pos1.x), sign(pos2.y, pos1.y)
antinode_1 = Coordinate(
pos1.x + pos1_signs[0] * diff[0], pos1.y + pos1_signs[1] * diff[1]
)
antinode_2 = Coordinate(
pos2.x + pos2_signs[0] * diff[0], pos2.y + pos2_signs[1] * diff[1]
)
antinodes = set()
if (
antinode_1.x >= 0
and antinode_1.y >= 0
and antinode_1.x < grid_size
and antinode_1.y < grid_size
):
antinodes.add(antinode_1)
if (
antinode_2.x >= 0
and antinode_2.y >= 0
and antinode_2.x < grid_size
and antinode_2.y < grid_size
):
antinodes.add(antinode_2)
return antinodesWe calculate the change vector (diff) and then calculate the signs for each x and y of both antenna locations so we know which direction the new node will be at. Then we calculate the antinode positions by adding or subtracting the change vector and finally check if the created antinodes are inside the grid.
To find all antinode positions, I go through all antennas by their frequency and using itertools.combinations generate all pairs. Then for each pair, I calculate all antinode positions.
Using a set here is handy because we never have to worry about duplicate positions.
def part_1():
inputs = read_input(8, str)
antennas, grid_size = create_map(inputs)
antinodes = set()
for positions in antennas.values():
for pos1, pos2 in combinations(positions, 2):
antinode_positions = calculate_antinodes(pos1, pos2, grid_size)
antinodes.update(antinode_positions)
result = len(antinodes)
print(f"Part 1: {result}")Originally, I had missed the part of the description that stated that antinodes can be in same locations as antennas and I did extra work to remove all antenna locations from the final result. This proves that at least 50% of Advent of Code puzzle solving is reading comprehension.
Part 2
Speaking of reading comprehension, I had such a hard time to understand the second part.
Here, instead of generating two antinodes, the antennas generate infinite amount of antinodes as long as they follow the rules from number one: they are in the same line as antennas and follow the same distancing from each other.
Although, in the puzzle, it said (emphasis mine):
After updating your model, it turns out that an antinode occurs at any grid position exactly in line with at least two antennas of the same frequency, regardless of distance.
To me, that reads that it should be any position that is on the same line. Luckily, the examples provided extra information and allowed me to cook up this change:
def calculate_all_antinodes(pos1, pos2, grid_size):
diff = abs(pos1.x - pos2.x), abs(pos1.y - pos2.y)
pos1_signs = sign(pos1.x, pos2.x), sign(pos1.y, pos2.y)
pos2_signs = sign(pos2.x, pos1.x), sign(pos2.y, pos1.y)
node = Coordinate(
pos1.x + pos1_signs[0] * diff[0], pos1.y + pos1_signs[1] * diff[1]
)
antinodes = set([pos1, pos2])
while node.x >= 0 and node.y >= 0 and node.x < grid_size and node.y < grid_size:
antinodes.add(node)
node = Coordinate(
node.x + pos1_signs[0] * diff[0], node.y + pos1_signs[1] * diff[1]
)
node = Coordinate(
pos2.x + pos2_signs[0] * diff[0], pos2.y + pos2_signs[1] * diff[1]
)
while node.x >= 0 and node.y >= 0 and node.x < grid_size and node.y < grid_size:
antinodes.add(node)
node = Coordinate(
node.x + pos2_signs[0] * diff[0], node.y + pos2_signs[1] * diff[1]
)
return antinodesHere, we do basically the same as we did in part 2 but we add a while loop to continue adding the antinodes until we run out of the grid into one direction and then do the same into another direction.
Since in this new model, every antenna location is an antinode location, we also add the antenna positions into the mix as well.
Part 2’s wrapper code is basically the same as 1, just calling this new function:
def part_2():
inputs = read_input(8, str)
antennas, grid_size = create_map(inputs)
antinodes = set()
for positions in antennas.values():
for pos1, pos2 in combinations(positions, 2):
antinode_positions = calculate_all_antinodes(pos1, pos2, grid_size)
antinodes.update(antinode_positions)
result = len(antinodes)
print(f"Part 2: {result}")Today’s puzzle took me about an hour. I drew many many small grids on index cards and had to debug my math quite a lot. For example, turns out that forgetting the parentheses around the first subtraction in a - b // (abs(a - b)) leads to wildly incorrect results.