Resonant Collinearity

Part 1

Another day, another grid puzzle. I’ll again be breaking out the same custom grids module I used on previous days; it represents grids as dicts mapping grid locations to tiles.

For this puzzle, however, we need to be able to associate antenna “frequencies” (i.e. all the non-dot characters in the grid) with every location of an antenna with that “frequency”. We can write a function to do this, creating a new dict mapping antenna “frequencies” to lists of antenna locations, and appending to the correct list when finding each antenna.

from collections import defaultdict

def find_antennas(grid: Grid[str]) -> dict[str, list[GridPoint]]:
    antennas: dict[str, list[GridPoint]] = defaultdict(list)
    for point, char in grid.items():
        if char != ".":
            antennas[char].append(point)
    return antennas

The first thing our solution will do is call this antenna-finding function on the input grid.

...

class Solution(StrSplitSolution):
    def part_1(self) -> int:
        grid = parse_grid(self.input)
        antennas = find_antennas(grid)
        ...

Each pair of like antennas will create two “antinodes”, one in one direction and one in the other. So I’ll be using itertools.permutations to loop through pairs of antennas, and calculating where their “antinode” would be in only one direction: towards the second antenna.

>>> from itertools import combinations, permutations
>>> list(permutations("ABC", 2))
[('A', 'B'), ('A', 'C'), ('B', 'A'), ('B', 'C'), ('C', 'A'), ('C', 'B')]
>>> list(combinations("ABC", 2))
[('A', 'B'), ('A', 'C'), ('B', 'C')]

First, I use subtract_points to calculate the row/column distance between the pair of antennas. Then I add that distance to the second antenna of the pair to find the corresponding antinode, and if it’s within the bounds of the grid, I add it to a set of antinode locations (because we want to count unique locations).

...

class Solution(StrSplitSolution):
    def part_1(self) -> int:
        ...
        antinodes: set[GridPoint] = set()
        for locations in antennas.values():
            for a, b in permutations(locations, 2):
                distance = subtract_points(b, a)

                # The antinode is just past B
                antinode = add_points(b, distance)
                if antinode in grid:
                    antinodes.add(antinode)

        return len(antinodes)

The answer is then the length of our set of antinode locations. (In my case, it’s a few hundred. Those dastardly bunnies and their chocolate-marketing tactics…)

Part 2

Looks like there are more antinodes than we thought there were. The antennas’ signals propagate much further due to “resonant harmonics”, so every grid location along the same line as two antennas¹ has an antinode. We’ll call these more abundant antinodes “strong”, and the less abundant antinodes from Part 1 “weak”.

The way we’ll find these antinodes will be similar to before; the difference is, we’ll start at the second antenna of the pair (because it has an antinode), and we’ll move in that direction until we move off of the grid.

...

class Solution(StrSplitSolution):
    def solve(self) -> tuple[int, int]:
        grid = parse_grid(self.input)
        antennas = find_antennas(grid)

        weak_antinodes: set[GridPoint] = set()
        strong_antinodes: set[GridPoint] = set()
        for locations in antennas.values():
            for a, b in permutations(locations, 2):
                distance = subtract_points(b, a)

                # The weak antinode is just past B
                antinode = add_points(b, distance)
                if antinode in grid:
                    weak_antinodes.add(antinode)

                # The strong antinodes are B and the locations past it
                antinode = b
                while antinode in grid:
                    strong_antinodes.add(antinode)
                    antinode = add_points(antinode, distance)

        return len(weak_antinodes), len(strong_antinodes)

Now the answer has grown to, in my case, over a thousand antinodes. How mediocre must the Easter Bunny’s chocolate be to require this?