year2024/
day23.rs

1use utils::bit::BitIterator;
2use utils::prelude::*;
3
4/// Finding the largest clique in a graph.
5///
6/// Assumes each node has the same degree N, and the largest clique contains N nodes.
7#[derive(Clone, Debug)]
8pub struct Day23 {
9    nodes: [[u64; (26usize * 26).div_ceil(64)]; 26 * 26],
10    degree: u32,
11}
12
13impl Day23 {
14    pub fn new(input: &str, _: InputType) -> Result<Self, InputError> {
15        let mut nodes = [[0u64; 11]; 676];
16
17        for item in parser::byte_range(b'a'..=b'z')
18            .repeat_n::<2, _>(parser::noop())
19            .repeat_n::<2, _>(b'-')
20            .with_suffix(parser::eol())
21            .parse_iterator(input)
22        {
23            let [n1, n2] = item?;
24
25            let index1 = 26 * (n1[0] - b'a') as usize + (n1[1] - b'a') as usize;
26            let index2 = 26 * (n2[0] - b'a') as usize + (n2[1] - b'a') as usize;
27
28            nodes[index1][index2 / 64] |= 1 << (index2 % 64);
29            nodes[index2][index1 / 64] |= 1 << (index1 % 64);
30        }
31
32        let Some(first_node) = nodes.iter().find(|&b| b.iter().any(|&n| n != 0)) else {
33            return Err(InputError::new(input, 0, "expected non-empty graph"));
34        };
35
36        let degree = first_node.iter().map(|&n| n.count_ones()).sum::<u32>();
37        if nodes.iter().any(|&b| {
38            let d = b.iter().map(|&n| n.count_ones()).sum::<u32>();
39            d != 0 && d != degree
40        }) {
41            return Err(InputError::new(
42                input,
43                0,
44                "expected all nodes to have same degree",
45            ));
46        }
47
48        Ok(Self { nodes, degree })
49    }
50
51    #[must_use]
52    pub fn part1(&self) -> u32 {
53        let mut count = 0;
54
55        // 19 = b't' - b'a'
56        for n1 in 19 * 26..20 * 26 {
57            for n2 in self.neighbors(n1) {
58                // Ensure the combination is only counted once if the second node also starts with t
59                if n2 / 26 == 19 && n2 >= n1 {
60                    continue;
61                }
62
63                for n3 in Self::iter(Self::intersect(self.nodes[n1], self.nodes[n2])) {
64                    if n3 >= n2 {
65                        break;
66                    }
67                    if n3 / 26 == 19 && n3 >= n1 {
68                        continue;
69                    }
70
71                    count += 1;
72                }
73            }
74        }
75
76        count
77    }
78
79    #[must_use]
80    pub fn part2(&self) -> String {
81        for i in 0..self.nodes.len() {
82            'sets: for skip in self.neighbors(i) {
83                if skip > i {
84                    break;
85                }
86
87                // Set of N nodes is (neighbours + starting node - skipped neighbour)
88                let mut connected = self.nodes[i];
89                connected[i / 64] |= 1 << (i % 64);
90                connected[skip / 64] &= !(1 << (skip % 64));
91
92                for n in self.neighbors(i).filter(|&n| n != skip) {
93                    connected = Self::intersect(connected, self.nodes[n]);
94                    connected[n / 64] |= 1 << (n % 64);
95
96                    if connected.iter().map(|&n| n.count_ones()).sum::<u32>() != self.degree {
97                        continue 'sets;
98                    }
99                }
100
101                return Self::iter(connected).fold(String::new(), |mut acc, i| {
102                    if !acc.is_empty() {
103                        acc.push(',');
104                    }
105                    let name = [b'a' + (i / 26) as u8, b'a' + (i % 26) as u8];
106                    acc.push(name[0] as char);
107                    acc.push(name[1] as char);
108                    acc
109                });
110            }
111        }
112
113        panic!("no solution found")
114    }
115
116    #[inline]
117    fn neighbors(&self, n: usize) -> impl Iterator<Item = usize> {
118        Self::iter(self.nodes[n])
119    }
120
121    #[inline]
122    fn iter(bitset: [u64; 11]) -> impl Iterator<Item = usize> {
123        bitset.into_iter().enumerate().flat_map(|(element, b)| {
124            BitIterator::ones(b).map(move |(bit, _)| element * 64 + bit as usize)
125        })
126    }
127
128    #[inline]
129    fn intersect(mut bitset1: [u64; 11], bitset2: [u64; 11]) -> [u64; 11] {
130        for (a, &b) in bitset1.iter_mut().zip(bitset2.iter()) {
131            *a &= b;
132        }
133        bitset1
134    }
135}
136
137examples!(Day23 -> (u32, &'static str) [
138    {file: "day23_example0.txt", part1: 7, part2: "co,de,ka,ta"},
139]);
year2024/day23.rs

year2024/
day23.rs
