Advent of Code 2024 Day 8

Day 8: Resonant Collinearity

https://adventofcode.com/2024/day/8

On top of the building you are on is a radio antenna, and it is up to no good. There are many more like it across the city.

A pair of antennas broadcasting the same wavelength create two antinodes (spots where the nefarious purposes of the antenna are realised, making people buy easter bunny stuff).

An example input looks like this:

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

It’s a 2D-grid of the city. Each alphanumeric character is an antenna. Identical characters send out identical wavelengths.

Parsing

I turned the input string into a few datapoints, the bounds of the grid (rows and cols), and a mapping from each type of radiotower to a list of points where a tower of that type exists.

Helper structure

In a previous day, I said I’d start parsing data into neat data structures in order to get confused less often. I had some trouble keeping track if index 0 was a row index or a column index, and was x the variable for column again? Oh no, that was y…

So, Point! This is not necessary at all, it probably even hurts performance a tiny bit, but it’s way nicer to show and understand code.

#[derive(PartialEq, Eq, Hash, Clone, Copy)]
struct Point {
    row: i32,
    col: i32,
}

impl Point {
    fn new(row: i32, col: i32) -> Self {
        Self { row, col }
    }
}

Parsing code

For convenience, I turned all numbers here into numbers that can go negative again, because before typing this post I solved the day, and we get to do some offset calculating again!

fn parse(input: &str) -> (i32, i32, HashMap<char, Vec<Point>>) {
    let rows = input.lines().count();
    let cols = input.lines().next().unwrap().chars().count();

    let mut antennas: HashMap<char, Vec<Point>> = HashMap::new();
    for (row, line) in input.lines().enumerate() {
        for (col, c) in line.chars().enumerate() {
            if c != '.' {
                let point = Point::new(row as i32, col as i32);
                antennas.entry(c).or_default().push(point);
            }
        }
    }
    (rows as i32, cols as i32, antennas)
}

Part 1

A pair of the same antenna types create 2 antinodes, one on each side of the antennas. That happens at 2 locations directly in line with the antennas.

For a location to be an antinode, it has to be exactly twice as far away from one antenna as it is from the other.

Visualized, this pair of a antennas create 2 antinodes marked with #:

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

The question asks how many points within the bounds are an antinode.

Helpers

I expanded the Point structure with some methods.

To add 2 Points together
To calculate the distance between 2 Points
To check if a Point is within the bounds of the grid

impl Point {
    fn new(row: i32, col: i32) -> Self {
        Self { row, col }
    }

    fn is_in_bounds(&self, rows: i32, cols: i32) -> bool {
        (self.row >= 0 && self.row < rows) && (self.col >= 0 && self.col < cols)
    }

    fn dist(&self, other: &Self) -> Self {
        Point::new(self.row - other.row, self.col - other.col)
    }

    fn add(&self, other: &Self) -> Self {
        Point::new(self.row + other.row, self.col + other.col)
    }
}

Part 1 code

These helpers make the code for part 1 much simpler to read (as opposed to a bunch of loose numbers) in my opinion.

I iterate over the map of antennas, so each loop has a list of equal antennas.

I then loop over all combinations of 2 Points. The distance between the Points is added to the first Point.

If the resulting Point is within the bounds of the map, it’s an antinode and is added to a set.

So, per loop, only 1 antinode can be added to the final set, because each pair will appear twice:

once as (point1, point2)
once as (point2, point1)

At the end of the loop, the length of that set is the answer to p1!

pub fn part_1(input: &str) -> usize {
    let (rows, cols, antennas) = parse(input);
    let mut antinodes = HashSet::new();
    for points in antennas.values() {
        for p1 in points {
            for p2 in points {
                if p1 == p2 {
                    continue;
                }
                let dist = p1.dist(p2);
                let new = p1.add(&dist);
                if new.is_in_bounds(rows, cols) {
                    antinodes.insert(new);
                }
            }
        }
    }
    antinodes.len()
}

Part 2

It turns out that an antinode occurs at any grid position exactly in line with at least two antennas of the same frequency.

So there are more than 2 per pair, they keep going until they leave the bounds of the map.

This was a small change! Adding a while loop to the part 1 code, adding the distance to a point each time we loop.

fn part_2(input: &str) -> usize {
    let (rows, cols, antennas) = parse(input);
    let mut antinodes = HashSet::new();
    for points in antennas.values() {
        for p1 in points {
            for p2 in points {
                if p1 == p2 {
                    continue;
                }
                let dist = p1.dist(p2);
                let mut new = *p1;
                while new.is_in_bounds(rows, cols) {
                    antinodes.insert(new);
                    new = new.add(&dist);
                }
            }
        }
    }
    antinodes.len()
}

Final code

1
use std::collections::{HashMap, HashSet};
2

3
#[derive(PartialEq, Eq, Hash, Clone, Copy)]
4
struct Point {
5
    row: i32,
6
    col: i32,
7
}
8

9
impl Point {
10
    fn new(row: i32, col: i32) -> Self {
11
        Self { row, col }
12
    }
13

14
    fn is_in_bounds(&self, rows: i32, cols: i32) -> bool {
15
        (self.row >= 0 && self.row < rows) && (self.col >= 0 && self.col < cols)
16
    }
17

18
    fn dist(&self, other: &Self) -> Self {
19
        Point::new(self.row - other.row, self.col - other.col)
20
    }
21

22
    fn add(&self, other: &Self) -> Self {
23
        Point::new(self.row + other.row, self.col + other.col)
24
    }
25
}
26

27
fn parse(input: &str) -> (i32, i32, HashMap<char, Vec<Point>>) {
28
    let rows = input.lines().count();
29
    let cols = input.lines().next().unwrap().chars().count();
30

31
    let mut antennas: HashMap<char, Vec<Point>> = HashMap::new();
32
    for (row, line) in input.lines().enumerate() {
33
        for (col, c) in line.chars().enumerate() {
34
            if c != '.' {
35
                let point = Point::new(row as i32, col as i32);
36
                antennas.entry(c).or_default().push(point);
37
            }
38
        }
39
    }
40
    (rows as i32, cols as i32, antennas)
41
}
42

43
pub fn part_1(input: &str) -> usize {
44
    let (rows, cols, antennas) = parse(input);
45
    let mut antinodes = HashSet::new();
46
    for points in antennas.values() {
47
        for p1 in points {
48
            for p2 in points {
49
                if p1 == p2 {
50
                    continue;
51
                }
52
                let dist = p1.dist(p2);
53
                let new = p1.add(&dist);
54
                if new.is_in_bounds(rows, cols) {
55
                    antinodes.insert(new);
56
                }
57
            }
58
        }
59
    }
60
    antinodes.len()
61
}
62

63
pub fn part_2(input: &str) -> usize {
64
    let (rows, cols, antennas) = parse(input);
65
    let mut antinodes = HashSet::new();
66
    for points in antennas.values() {
67
        for p1 in points {
68
            for p2 in points {
69
                if p1 == p2 {
70
                    continue;
71
                }
72
                let dist = p1.dist(p2);
73
                let mut new = *p1;
74
                while new.is_in_bounds(rows, cols) {
75
                    antinodes.insert(new);
76
                    new = new.add(&dist);
77
                }
78
            }
79
        }
80
    }
81
    antinodes.len()
82
}

Date

Tagged

Part of series

Older post

Newer post