year2024/
day08.rs

1use utils::array::ArrayVec;
2use utils::grid;
3use utils::prelude::*;
4
5/// Plotting lines between nodes of the same frequency.
6#[derive(Clone, Debug)]
7pub struct Day08 {
8    cols: usize,
9    len: usize,
10    antennas: [ArrayVec<usize, MAX_ANTENNA>; FREQUENCY_COUNT],
11}
12
13const MAX_ANTENNA: usize = 4;
14const FREQUENCY_COUNT: usize = 62;
15
16impl Day08 {
17    pub fn new(input: &str, _: InputType) -> Result<Self, InputError> {
18        let mut antennas = std::array::from_fn(|_| ArrayVec::default());
19        let (rows, cols) = grid::for_each_row(
20            input,
21            |b| b == b'.' || b.is_ascii_alphanumeric(),
22            || "expected '.' or frequency",
23            |row, cols, line| {
24                for (col, &b) in line.iter().enumerate() {
25                    let freq = match b {
26                        b'a'..=b'z' => b - b'a',
27                        b'A'..=b'Z' => b - b'A' + 26,
28                        b'0'..=b'9' => b - b'0' + 52,
29                        b'.' => continue,
30                        _ => unreachable!("input already validated"),
31                    };
32
33                    if antennas[freq as usize].push(row * cols + col).is_err() {
34                        return Err(InputError::new(
35                            input,
36                            line,
37                            format!("expected at most {MAX_ANTENNA} '{}' antennas", b as char),
38                        ));
39                    }
40                }
41                Ok(())
42            },
43        )?;
44
45        Ok(Self {
46            cols,
47            len: rows * cols,
48            antennas,
49        })
50    }
51
52    #[must_use]
53    pub fn part1(&self) -> usize {
54        self.count_antinode_locations(false)
55    }
56
57    #[must_use]
58    pub fn part2(&self) -> usize {
59        self.count_antinode_locations(true)
60    }
61
62    #[inline]
63    fn count_antinode_locations(&self, part2: bool) -> usize {
64        let mut antinodes = vec![false; self.len];
65        for indexes in &self.antennas {
66            for (i, &index1) in indexes.iter().enumerate() {
67                for &index2 in &indexes[i + 1..] {
68                    let offset = index2 - index1;
69                    // Whether adding offset should move to the right/increase the column number.
70                    // Used to prevent wrapping around onto the next/previous row when
71                    // adding/subtracting the offset from the previous index.
72                    let right = index1 % self.cols < index2 % self.cols;
73
74                    let mut prev = index1;
75                    while let Some(index) = prev.checked_sub(offset) {
76                        if (index % self.cols < prev % self.cols) == right {
77                            antinodes[index] = true;
78                            prev = index;
79                            if part2 {
80                                continue;
81                            }
82                        }
83                        break;
84                    }
85
86                    let mut prev = index2;
87                    while let Some(index) = prev.checked_add(offset) {
88                        if index < self.len && ((prev % self.cols < index % self.cols) == right) {
89                            antinodes[index] = true;
90                            prev = index;
91                            if part2 {
92                                continue;
93                            }
94                        }
95                        break;
96                    }
97                }
98
99                antinodes[index1] |= part2;
100            }
101        }
102        antinodes.iter().filter(|&&x| x).count()
103    }
104}
105
106examples!(Day08 -> (usize, usize) [
107    {file: "day08_example0.txt", part1: 14, part2: 34},
108    {file: "day08_example1.txt", part1: 2},
109    {file: "day08_example2.txt", part1: 4},
110    {file: "day08_example3.txt", part1: 4},
111    {file: "day08_example4.txt", part2: 9},
112]);
year2024/day08.rs

year2024/
day08.rs
