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);
    }
}