year2024/
day08.rs

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

year2024/
day08.rs
