Antennas & Antinodes everywhere

It's December 8th and it's snowing heavily outside: time for another challenge involving 2D grids 🥶

We have a bunch of antennas scattered across the space, each identified by a letter or digit that determines its frequency.

............
........0...
.....0......
.......0....
....0.......
......A.....
............
............
........A...
.........A..
............

Pairs of antennas having the same frequency generate antinodes. To be fair I found the explanation of these antinodes a bit confusing:

an antinode occurs at any point that is perfectly in line with two antennas of the same frequency - but only when one of the antennas is twice as far away as the other. This means that for any pair of antennas with the same frequency, there are two antinodes, one on either side of them.

However, looking at the example, it becomes clear that this means: essentially, antinodes occur on each side of the antenna-pair segment, at the same distance from each antenna.

+-----------> X
|..#.....  (2,0)
|........
|...a....  (3,2)
|........
|....a...  (4,4)
|........
|.....#..  (5,6)
|........
⌄
Y

For example, if the first antenna is on (3, 2) and the second on (4, 4), we can derive a line equation where each point we're considering increases by x + 1 and y + 2. Therefore, it's easy to derive the antinodes on each side, that is (4 + 1, 4 + 2) = (5, 6), and (3 - 1, 2 - 2) = (2, 0).

Onto my solution, first of all I created a map linking each antenna identifier (again, a lower- or uppercase letter, or a digit) to the list of coordinates where such antenna is present:

for (let [coord, cell] of grid) {
    if (cell !== '.') {
		// Get the list of coords for the current antenna, or create it if it doesn't exist yet
        const antennaCoords = antennasMap.get(cell) ?? [];
        antennaCoords.push(coord);
        antennasMap.set(cell, antennaCoords);
    }
}

Then, since antinodes are generated by pairs of antennas, but the number of antennas with the same frequency can be more than two, I generated all possible pairs from a list of N elements:

function generatePairs(array: string[], start = 0, result: string[][] = []) {
    if (start >= array.length - 1) {
        return result;
    }

    for (let i = start + 1; i < array.length; i++) {
        result.push([array[start], array[i]]);
    }

    return generatePairs(array, start + 1, result);
}

So say we have four antennas with coordinates a, b, c, d, the output of such function would be [['a', 'b'], ['a', 'c'], ['a', 'd'], ['b', 'c'], ['b', 'd'],['c', 'd']];

Next, I needed a function to actually find the antinodes on the grid: once obtained the differences between Xs and Ys for the antennas in the pair, we can simply add them to the first antenna and subtract them from the second:

function findAntinodes(antennaA: Coord, antennaB: Coord) {
    const xDelta = antennaA.x - antennaB.x;
    const yDelta = antennaA.y - antennaB.y;

    let antinodes: Coord[] = [];

    const antinodeA = new Coord(antennaA.x + xDelta, antennaA.y + yDelta);
    const antinodeB = new Coord(antennaB.x - xDelta, antennaB.y - yDelta);

	return [antinodeA, antinodeB];
}

Finally, we can loop through each antenna identifier and keep track of the unique antinode coordinates found via a set:

for (let coords of antennasMap.values()) {
    for (let pair of generatePairs(coords)) {
        const antinodes = findAntinodes(pair[0]), pair[1]);
        for (let antinode of antinodes) {
            if (grid.has(antinode)) {
                uniqueAntinodes.add(antinode);
            }
        }
    }
}

Part 2 was pretty similar, except for a couple of catches:

• pairs of antennas no longer generate just two antinodes, but as many as the grid can fit - following the same distancing rules
• antennas become antinodes themselves

Updating my findAntinodes function with the new requirements was fairly straightforward:

export function findAntinodes(antennaA: Coord, antennaB: Coord, max?: number) {
    const xDelta = antennaA.x - antennaB.x;
    const yDelta = antennaA.y - antennaB.y;

    let antinodes: Coord[] = [];

    let sourceA = antennaA;
    let sourceB = antennaB;

    while (true) {
        const antinodeA = new Coord(sourceA.x + xDelta, sourceA.y + yDelta);
        const antinodeB = new Coord(sourceB.x - xDelta, sourceB.y - yDelta);

        if (max && !isWithinRange(antinodeA, max) && !isWithinRange(antinodeB, max)) {
            break; // Stop if both antinodes are out of range
        }

        if (isWithinRange(antinodeA, max)) {
            antinodes.push(antinodeA);
            sourceA = antinodeA;
        }
        if (isWithinRange(antinodeB, max)) {
            antinodes.push(antinodeB);
            sourceB = antinodeB;
        }

        if (!max) break; // Part 1: no max range specified; exit after the first iteration
    }

    return antinodes;
}

isWithinRange simply checks that, for example on a square grid with length = 130 (the puzzle input), a coordinate is within the grid, that is with both x and y within the [0, 130) range. In the function above, we keep adding the antinodes until we reach the edge of the grid. The separate checks for the two sides of the antenna pair are obviously because antenna A might be much closer to the edge than antenna B, so the antinodes on side B would need adding even if we run out of space on side A. When both antinode candidates are out of range, we can stop checking.

Finally, regarding the clause that antennas themselves are now antinodes, I simply added them to the uniqueAntinodes list while creating the antennaMap, where max is the length of the grid.

for (let [coord, cell] of grid) {
    if (cell !== '.') {
        const antennaCoords = antennasMap.get(cell) ?? [];
        ...

        if (max) { // Part 2: add antennas as antinodes
            uniqueAntinodes.add(coord);
        }
    }
}

That's it! We're on day 8 and, apart from the Kahn algorithm on day 5, I barely broke a sweat until now :)