Advent of Code 2024: Day 08

Code for solutions available on GitHub.

Resonant Collinearity

Another grid puzzle today! We are given a grid of antennae, which transmit at a specific frequency (represented by a character). So in the following grid:

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

There are 6 antennae operating on 2 frequencies: 0, and A. We need to find some nefarious devices places at specific antinodes based on the antenna frequencies.

An antinode appears when two antennae are in a line, and it appears on the other side of the first antenna at the same distance as the second is to the first. The given visualization example explains it pretty well:

..........
...#......
..........
....a.....
..........
.....a....
..........
......#...
..........
..........

Two antennae in a line. Two antinodes appearing outside of them, on the same line, equally spaced.

An antinode may appear in a space where there already is an antenna. So no need to check whether the space is free or if there’s an antenna there. The task is to count how many antinodes have appeared within the bounds of the grid.

For this, I take the good old Point struct:

struct Point {
    x: i64,
    y: i64,
}

And I will implement the std::ops::Add and std::ops::Sub traits for reasons that will become clear:

impl Add<Point> for Point {
    type Output = Point;
    fn add(self, rhs: Point) -> Point {
        Point {
            x: self.x + rhs.x,
            y: self.y + rhs.y,
        }
    }
}

impl Sub<Point> for Point {
    type Output = Point;
    fn sub(self, rhs: Point) -> Point {
        Point {
            x: self.x - rhs.x,
            y: self.y - rhs.y,
        }
    }
}

And a simple in_bounds check:

impl Point {
    fn in_bounds(&self, width: i64, height: i64) -> bool {
        (0..width).contains(&self.x) && (0..height).contains(&self.y)
    }
}

I parsed the input grid into a HashMap<char, Vec<Point>>. Since all frequencies are independent and an antinode can appear where there already is an antenna, we can simply loop over the entries of this hashmap, taking all combinations of 2 antennae in each Vec and do some vector mathematics to figure out where the antinodes should end up:

let mut antinodes = Vec::new();
for (_frequency, positions) in parse_input(input) {
    for p in positions.iter().combinations(2) {
        let diff = *p[1] - *p[0];
        antinodes.push(*p[1] + diff);
        antinodes.push(*p[0] - diff);
    }
}

I am once again indebted to the itertools crate with the Itertools::combinations method. This adds all antinodes to a Vec, even invalid ones. Getting the count of valid unique antinodes is then pretty simple:

let result = antinodes
    .into_iter()
    .filter(|p| p.in_bounds(width, height))
    .unique()
    .count();

unique() is also from itertools. It does exactly what you think.

Part 2

Turns out, antinodes don’t only appear in pairs like that. They appear equally spaced, extending infinitely (within the grid) in a line. Equally spaced like before, but the position of an antenna will also generate an antinode.

The implementation is straighforwards. We just keep adding the difference vector between the antenna pair until it goes out of bounds, and add all those Points to the antinodes Vec.

for (_frequency, positions) in parse_input(input) {
    antinodes.extend_from_slice(&positions);
    for p in positions.iter().combinations(2) {
        let diff = *p[1] - *p[0];

        let mut node_1 = *p[1] + diff;
        let mut node_2 = *p[0] - diff;

        while node_1.in_bounds(width, height) {
            antinodes.push(node_1);
            node_1 = node_1 + diff;
        }

        while node_2.in_bounds(width, height) {
            antinodes.push(node_2);
            node_2 = node_2 - diff;
        }
    }
}

The rest of the code is the same. :)