2024_day23.rs

use std::env;
use std::fs;
use hashbrown::HashSet;
use hashbrown::HashMap;
use rayon::prelude::*;

fn main() {
    let graph = make_graph(read_input());
    println!("Part 1: {}", part1(&graph));
    println!("Part 2: {}", part2(&graph));
}

fn part1(graph: &HashMap<String, Vec<String>>) -> usize {
    let mut sets = HashSet::new();

    for (node, edges) in graph.iter() {
        if !node.starts_with('t') {
            continue;
        }

        for i in 0..(edges.len() - 1) {
            let ei = &edges[i];
            let ei_edges = match graph.get(ei) {
                Some(es) => es,
                None => continue,
            };
            for ej in edges.iter().skip(i+1) {
                if ei_edges.contains(ej) {
                    let mut triple: Vec<String> = vec![node.clone(), ei.clone(), ej.clone()];
                    triple.sort();
                    let triple_s = triple.join(",");
                    sets.insert(triple_s);
                }
            }
        }
    }

    sets.len()
}

fn part2(graph: &HashMap<String, Vec<String>>) -> String {
    let mut best = graph.par_iter()
        .map(|(node, _)| {
            dfs_clique(graph, vec![node.clone()], node.clone())
        })
        .max_by_key(|result| result.len())
        .unwrap();

    best.sort();
    best.join(",")
}

fn dfs_clique(
    graph: &HashMap<String, Vec<String>>,
    clique: Vec<String>,
    node: String,
) -> Vec<String> {
    graph.get(&node).unwrap().iter().filter_map(|e| {
        if e <= &node {
            return None;
        }
        if clique.contains(e) {
            return None;
        }
        if can_add_to_clique(graph, &clique, e) {
            let mut c2 = clique.clone();
            c2.push(e.clone());
            let result = dfs_clique(graph, c2, e.clone());
            if result.len() > clique.len() {
                return Some(result);
            }
        }
        None
    })
        .max_by_key(|result| result.len())
        .unwrap_or(clique)
}

fn can_add_to_clique(graph: &HashMap<String, Vec<String>>, clique: &[String], node: &String) -> bool {
    clique.iter().all(|c| {
        graph.get(c).is_some_and(|edges| edges.contains(node))
    })
}

fn read_input() -> String {
    get_content(get_arg())
}

fn get_arg() -> String {
    match env::args().nth(1) {
        Some(f) => f,
        None => "example".into(),
    }
}

fn get_content(filename: String) -> String {
    fs::read_to_string(filename).unwrap().trim().to_string()
}

fn make_graph(content: String) -> HashMap<String, Vec<String>> {
    let mut graph = HashMap::new();

    for line in content.split('\n') {
        let parts: Vec<&str> = line.split('-').collect();
        add_to_graph(&mut graph, parts[0].to_string(), parts[1].to_string());
        add_to_graph(&mut graph, parts[1].to_string(), parts[0].to_string());
    }

    graph
}

fn add_to_graph(graph: &mut HashMap<String, Vec<String>>, from: String, to: String) {
    graph.entry(from).or_default().push(to)
}