year2024/
day08.rs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
use utils::array::ArrayVec;
use utils::prelude::*;

/// Plotting lines between nodes of the same frequency.
#[derive(Clone, Debug)]
pub struct Day08 {
    cols: usize,
    len: usize,
    antennas: [ArrayVec<usize, MAX_ANTENNA>; FREQUENCY_COUNT],
}

const MAX_ANTENNA: usize = 4;
const FREQUENCY_COUNT: usize = 62;

impl Day08 {
    pub fn new(input: &str, _: InputType) -> Result<Self, InputError> {
        let mut lines = input.lines().peekable();
        let Some(cols) = lines.peek().map(|s| s.len()) else {
            return Err(InputError::new(input, 0, "expected grid"));
        };
        if cols == 0 {
            return Err(InputError::new(input, 0, "expected at least one column"));
        }

        let mut antennas = std::array::from_fn(|_| ArrayVec::default());
        let mut index = 0;
        for line in lines {
            if line.len() != cols {
                return Err(InputError::new(
                    input,
                    &line[cols.min(line.len())..],
                    format!("expected {cols} columns"),
                ));
            }
            for b in line.bytes() {
                let freq = if b.is_ascii_lowercase() {
                    b - b'a'
                } else if b.is_ascii_uppercase() {
                    b - b'A' + 26
                } else if b.is_ascii_digit() {
                    b - b'0' + 52
                } else if b == b'.' {
                    index += 1;
                    continue;
                } else {
                    return Err(InputError::new(input, b as char, "expected . or frequency"));
                };

                if antennas[freq as usize].push(index).is_err() {
                    return Err(InputError::new(
                        input,
                        line,
                        format!("expected at most {MAX_ANTENNA} '{}' antennas", b as char),
                    ));
                }
                index += 1;
            }
        }

        Ok(Self {
            cols,
            len: index,
            antennas,
        })
    }

    #[must_use]
    pub fn part1(&self) -> usize {
        self.count_antinode_locations(false)
    }

    #[must_use]
    pub fn part2(&self) -> usize {
        self.count_antinode_locations(true)
    }

    #[inline]
    fn count_antinode_locations(&self, part2: bool) -> usize {
        let mut antinodes = vec![false; self.len];
        for indexes in &self.antennas {
            for (i, &index1) in indexes.iter().enumerate() {
                for &index2 in &indexes[i + 1..] {
                    let offset = index2 - index1;
                    // Whether adding offset should move to the right/increase the column number.
                    // Used to prevent wrapping around onto the next/previous row when
                    // adding/subtracting the offset from the previous index.
                    let right = index1 % self.cols < index2 % self.cols;

                    let mut prev = index1;
                    while let Some(index) = prev.checked_sub(offset) {
                        if (index % self.cols < prev % self.cols) == right {
                            antinodes[index] = true;
                            prev = index;
                            if part2 {
                                continue;
                            }
                        }
                        break;
                    }

                    let mut prev = index2;
                    while let Some(index) = prev.checked_add(offset) {
                        if index < self.len && ((prev % self.cols < index % self.cols) == right) {
                            antinodes[index] = true;
                            prev = index;
                            if part2 {
                                continue;
                            }
                        }
                        break;
                    }
                }

                antinodes[index1] |= part2;
            }
        }
        antinodes.iter().filter(|&&x| x).count()
    }
}

examples!(Day08 -> (usize, usize) [
    {file: "day08_example0.txt", part1: 14, part2: 34},
    {file: "day08_example1.txt", part1: 2},
    {file: "day08_example2.txt", part1: 4},
    {file: "day08_example3.txt", part1: 4},
    {file: "day08_example4.txt", part2: 9},
]);