AoC Day 8 has us mapping interactions between items on a grid. The input is a large grid filled with mostly blank (“.”) spaces. However, across the grid are multiple “antennas” identified by the frequency that they are broadcasting (frequency is identified by an arbitrary letter or number). The challenge is to find interactions between the various antennas that are broadcasting on the same frequency.
The interactions occur to produce an “antinode”. An antinode occurs at a location that is equal to the distance between the two antennas in the interaction, on the opposite side of the antenna. For example, if I have two antennas on the same frequency with one located at grid 3, 3 and the other at 5,5, I would have antinodes located at 1,1 and 7,7.
The basic answer to finding this is simply finding the rise/run (aka the Slope) of the line produced between the two antennas, and then adding antinodes at the next spot within that slope on either side of the antennas.
The one trick to this, is the challenge is only looking for antinodes that would occur within the provided grid, so we’re space confined.
I started to tackle this right from the start with reading in the data. Really, the only thing I cared about was the grid locations of each antenna, and the frequency it was transmitting on. Also the maximum size of the grid. To do this, I updated my standard get_data function to parse only that information.
def get_data():
from os import path
from collections import defaultdict
data = defaultdict(list)
with open(path.join(path.dirname(__file__), 'input.txt'), 'r') as f:
for y, line in enumerate(f):
line = list(line.strip())
for x, i in enumerate(line):
if i != ".":
data[i].append((x,y))
return data, (len(line), y)
You’ll notice that the primary data I am getting back is a default dictionary that uses the frequency as the key, and has a list of the antenna locations as the value. To find all of the interactions, I loop through the various keys (frequencies) in the data and pass it, and the list of locations to another function.
For finding the antinodes, I use the combinations function provided by the itertools library to find the various combinations of antennas (order doesn’t matter, just pairings). I calculate the rise and run for between the two antenna, and then see if they are within my grid area. I would show how I do it, but I ended up modifying my function a little bit for part 2, so keep reading.
Part 2
For part 2, the rule changes very slightly. Instead of a single antinode being produced by each antenna, it is a series the runs to infinity. This means I have to calculate a series of antinodes instead of just a single one. To do this, I modified my function and broke it out. I used one function to get the combinations of antennas and then figure out the rise/run for that pairing. It then turns over the location of the antenna and the rise/run to a second function that either fills it (for part 2) or does just a single iteration (for part 1) and checks to see if it is within the grid. It then does that same thing again for the other antenna in reverse.
def fill_antinodes(cordinate, slope, direction, grid_size, fill=False):
antinodes = []
x, y = cordinate
run, rise = slope
if direction == "-":
rise *= -1
run *= -1
x += run
y += rise
if fill:
antinodes.append(cordinate)
while (0 <= (x) < grid_size[0]) and (0 <= (y) <= grid_size[1]):
antinodes.append((x, y))
x += run
y += rise
else:
if (0 <= (x) < grid_size[0]) and (0 <= (y) <= grid_size[1]):
antinodes.append((x, y))
return antinodes
def calculate_antinodes(locations, grid_size, fill=False):
from itertools import combinations
antinodes = []
pairs = combinations(locations, 2)
for pair in pairs:
rise = pair[1][1] - pair[0][1]
run = pair[1][0] - pair[0][0]
antinodes += (fill_antinodes(pair[0], (run, rise), "-", grid_size, fill))
antinodes += (fill_antinodes(pair[1], (run, rise), "+", grid_size, fill))
return antinodes
You can see my complete code on Github.