aoc/year2024/
day23.rs

1//! # LAN Party
2//!
3//! This is the [Clique problem](https://en.wikipedia.org/wiki/Clique_problem). For part one we
4//! find triangles (cliques of size 3) for each node by checking if there's an edge between any
5//! distinct pair of neighbouring nodes.
6//!
7//! Part two asks to find the maximum clique, for which we could use the
8//! [Bron–Kerbosch algorithm](https://en.wikipedia.org/wiki/Bron%E2%80%93Kerbosch_algorithm).
9//! However the input has a specific structure that enables a simpler approach of finding the
10//! largest *maximal* clique using a greedy algorithm. Nodes are arranged in clusters of 13 and
11//! the maximum clique is size 14. This approach will not necessarily work for any general graph,
12//! but will work for the inputs provided.
13use crate::util::hash::*;
14
15type Input = (FastMap<usize, Vec<usize>>, Vec<[bool; 676]>);
16
17/// Convert each character pair `xy` to an index from 0..676 so that we can use much faster array
18/// lookup instead of a `HashMap`.
19pub fn parse(input: &str) -> Input {
20    let mut nodes = FastMap::with_capacity(1_000);
21    let mut edges = vec![[false; 676]; 676];
22
23    let to_index = |b: &[u8]| 26 * to_usize(b[0]) + to_usize(b[1]);
24    let empty = || Vec::with_capacity(16);
25
26    for edge in input.as_bytes().chunks(6) {
27        let from = to_index(&edge[..2]);
28        let to = to_index(&edge[3..]);
29
30        // Graph is undirected so add edges to both nodes.
31        nodes.entry(from).or_insert_with(empty).push(to);
32        nodes.entry(to).or_insert_with(empty).push(from);
33
34        // https://en.wikipedia.org/wiki/Adjacency_matrix
35        edges[from][to] = true;
36        edges[to][from] = true;
37    }
38
39    (nodes, edges)
40}
41
42pub fn part1(input: &Input) -> usize {
43    let (nodes, edges) = input;
44    let mut seen = [false; 676];
45    let mut triangles = 0;
46
47    // Only consider nodes starting with `t`.
48    for n1 in 494..520 {
49        if let Some(neighbours) = nodes.get(&n1) {
50            seen[n1] = true;
51
52            for (i, &n2) in neighbours.iter().enumerate() {
53                for &n3 in neighbours.iter().skip(i) {
54                    // Skip nodes if we've already seen them.
55                    if !seen[n2] && !seen[n3] && edges[n2][n3] {
56                        triangles += 1;
57                    }
58                }
59            }
60        }
61    }
62
63    triangles
64}
65
66pub fn part2(input: &Input) -> String {
67    let (nodes, edges) = input;
68    let mut seen = [false; 676];
69    let mut clique = Vec::new();
70    let mut largest = Vec::new();
71
72    // Greedy algorithm to find *maximal* (not maximum) cliques.
73    for (&n1, neighbours) in nodes {
74        if !seen[n1] {
75            clique.clear();
76            clique.push(n1);
77
78            // Add nodes if they're connected to every node already in the clique.
79            for &n2 in neighbours {
80                if clique.iter().all(|&c| edges[n2][c]) {
81                    seen[n2] = true;
82                    clique.push(n2);
83                }
84            }
85
86            // For the specific graphs given in the input
87            // finding the largest maximal clique will work.
88            if clique.len() > largest.len() {
89                largest.clone_from(&clique);
90            }
91        }
92    }
93
94    // Convert each index back into 2 character identifiers sorted alphabetically.
95    let mut result = String::new();
96    largest.sort_unstable();
97
98    for n in largest {
99        result.push(to_char(n / 26));
100        result.push(to_char(n % 26));
101        result.push(',');
102    }
103
104    result.pop();
105    result
106}
107
108fn to_usize(b: u8) -> usize {
109    (b - b'a') as usize
110}
111
112fn to_char(u: usize) -> char {
113    ((u as u8) + b'a') as char
114}
aoc/year2024/day23.rs

aoc/year2024/
day23.rs
