Advent of Code 2024 Day 8

Parsing

We have a grid of characters, where . characters are empty spaces and alphanumeric characters are antennas. Each antenna has a frequency which is the same as the character representing the antenna.

I chose to parse this into a hashmap with the antenna frequency as the key and a list of positions as the value since we need to group antennas by frequency when solving the problem. Each position is a tuple of (row, col) coordinates.

def parse_input(inp):
    inp = inp.strip()

    antennas = {}
    row = 0
    for line in inp.splitlines():
        col = 0
        for char in line:
            if char != ".":
                if antennas.get(char) is None:
                    antennas[char] = list()
                antennas[char].append((row, col))
            col += 1
        row += 1
    width = col
    height = row
    return antennas, width, height

The parsing code goes line by line and then character by character while updating row and col indices. The width and height of the grid is found out by the last column and row indices.

Part One

For each combination of two antennas of the same frequency, two antinodes are created. Each antinode occurs on the line joining the two antennas, and each antinode is as far away from an antenna as the distance between the two antennas. In vector terms, if the two antennas are at a and b, then the two antinodes are at b + (b - a) and a - (b - a).

For part one, we need to find the number of unique positions on the grid that contain an antinode. I first define some helper functions to get the sum and difference of two positions and also to see if the antinode is contained in the grid (we don’t consider antinodes that aren’t in the grid).

def plus(a, b):
    return (a[0] + b[0], a[1] + b[1])

def minus(a, b):
    return (a[0] - b[0], a[1] - b[1])

def is_contained(point, width, height):
    return point[0] >= 0 and point[1] >= 0 and point[0] < height and point[1] < width

Then for the main code for part one, I use itertools.combinations on the list of antenna positions for each frequency to find out every combination of 2 antennas. Then I calculate the antinodes and store them in a set to get rid of duplicates.

def part1(parsed):
    antennas, width, height = parsed
    antinodes = set()
    for freq, points in antennas.items():
        for a, b in itertools.combinations(points, r=2):
            difference = minus(b, a)
            curr_antinodes = [plus(b, difference), minus(a, difference)]
            for an in curr_antinodes:
                if is_contained(an, width, height):
                    antinodes.add(an)
    return len(antinodes)

Part Two

Now, due to harmonics, there are multiple, equally spaced antinodes created by every pair of same-frequency antennas that extend out on the line joining the two antennas until the end of the grid. We now also consider the pair of antennas as antinodes themselves.

def part2(parsed):
    antennas, width, height = parsed
    antinodes = set()
    for freq, points in antennas.items():
        for a, b in itertools.combinations(points, r=2):
            difference = minus(b, a)
            an_1, an_2 = b, a
            while is_contained(an_1, width, height) or is_contained(an_2, width, height):
                if is_contained(an_1, width, height):
                    antinodes.add(an_1)
                if is_contained(an_2, width, height):
                    antinodes.add(an_2)
                an_1 = plus(an_1, difference)
                an_2 = minus(an_2, difference)
    return len(antinodes)

There are two “series” of antinodes, one along b + (n * delta) and the other along a - (n * delta) where delta is b - a and n is any positive integer. I modified my part one code to loop over these series while they are contained within the grid and add them to the antinodes set.