Rust
Part2 works, and is fast enough, but still feels kinda gross. No idea if this is a known algorithm or not.
Edit: Having looked at the Bron-Kerbosch wiki page, I have no idea how that works, and its way too much math for me. I'm more happy with my result now :D
Edit2: Because the code is messy, i'll try summarise pt2 here:
- From pt1, I already have a list of all nodes and their peers.
- For each node, I then have the potential network.
- For each node in the potential network, count the links to the other network nodes.
- Filter network to the N nodes with at least N-1 peers
Presumably this is a known algorithm, and I just naively ran into it. I don't think it can fail, but maybe on some more exotic graphs? Might not scale well either, but given the networks are small, its probably okay here?
#[cfg(test)]
mod tests {
use std::collections::HashMap;
#[test]
fn day23_part1_test() {
let input = std::fs::read_to_string("src/input/day_23.txt").unwrap();
let links = input
.lines()
.map(|l| l.split_once('-').unwrap())
.collect::<Vec<(&str, &str)>>();
let mut peer_map = HashMap::new();
for pair in links {
peer_map.entry(pair.0).or_insert(Vec::new()).push(pair.1);
peer_map.entry(pair.1).or_insert(Vec::new()).push(pair.0);
}
let mut rings = vec![];
for (pc, peers) in &peer_map {
if !pc.starts_with('t') {
continue;
}
for (i, first) in peers.iter().enumerate() {
for second in peers[i..].iter() {
if first == second {
continue;
}
if !peer_map.get(first).unwrap().contains(second) {
continue;
}
let mut set = vec![pc, second, first];
set.sort();
if !rings.contains(&set) {
rings.push(set);
}
}
}
}
println!("{}", rings.len());
}
#[test]
fn day23_part2_test() {
let input = std::fs::read_to_string("src/input/day_23.txt").unwrap();
let links = input
.lines()
.map(|l| l.split_once('-').unwrap())
.collect::<Vec<(&str, &str)>>();
let mut peer_map = HashMap::new();
for pair in links {
let p1 = peer_map.entry(pair.0).or_insert(Vec::new());
if !p1.contains(&pair.1) {
p1.push(pair.1);
}
let p2 = peer_map.entry(pair.1).or_insert(Vec::new());
if !p2.contains(&pair.0) {
p2.push(pair.0);
}
}
let mut biggest_network = String::new();
for (pc, peers) in &peer_map {
let mut network = HashMap::new();
network.insert(pc, peers.len());
for first in peers {
let mut total = 1;
for second in peers.iter() {
if first == second {
continue;
}
if peer_map.get(first).unwrap().contains(second) {
total += 1;
}
}
network.insert(first, total);
}
let mut network_size = peers.len();
loop {
if network_size == 0 {
break;
}
let mut out = network
.iter()
.filter_map(|(k, v)| {
if v >= &network_size {
return Some(**k);
}
None
})
.collect::<Vec<_>>();
if out.len() == network_size + 1 {
out.sort();
let pw = out.join(",");
// println!("{}", pw);
if pw.len() > biggest_network.len() {
biggest_network = pw;
}
break;
}
network_size -= 1;
}
}
println!("{}", biggest_network);
}
}