Untitled

pub fn solution(test: bool) -> ((usize, Duration), (usize, Duration)) {
    let lines;
    if test {
        lines = include_str!("../../../AdventOfCodeInputs/problem_inputs_2024/day_23_test.txt");
    } else {
        lines = include_str!("../../../AdventOfCodeInputs/problem_inputs_2024/day_23.txt");
    }
    let mut graph: UnGraph<&str, ()> = UnGraph::default();
    let mut node_index: FxHashMap<&str, NodeIndex> = FxHashMap::default();
    for line in lines.lines() {
        let (node1, node2) = line.split_once("-").unwrap();
        let node1_index = *node_index
            .entry(node1)
            .or_insert_with(|| graph.add_node(node1));
        let node2_index = *node_index
            .entry(node2)
            .or_insert_with(|| graph.add_node(node2));
        graph.add_edge(node1_index, node2_index, ());
    }
    (solve01(&graph), solve02(&graph))
}

fn solve01(graph: &UnGraph<&str, ()>) -> (usize, Duration) {
    let now = Instant::now();
    let triangles = find_triangles(&graph);
    let triangles_with_t = triangles
        .iter()
        .filter(|(a, b, c)| a.starts_with('t') || b.starts_with('t') || c.starts_with('t'))
        .collect_vec();
    (triangles_with_t.len(), now.elapsed())
}
fn solve02(graph: &UnGraph<&str, ()>) -> (usize, Duration) {
    let now = Instant::now();
    let max_clique = find_max_clique(&graph);
    let max_clique_str = max_clique.join(",");
    dbg!(&max_clique_str);
    (0, now.elapsed())
}

fn find_triangles(graph: &UnGraph<&str, ()>) -> Vec<(String, String, String)> {
    let mut triangles = Vec::new();

    for edge in graph.edge_references() {
        let (u, v) = (edge.source(), edge.target());

        // Check for a common neighbor that forms a triangle
        for &neighbor in graph.neighbors(u).collect::<Vec<_>>().iter() {
            if graph.contains_edge(neighbor, v) {
                // Sort the vertices to avoid duplicates
                let mut triangle = vec![
                    graph[u].to_string(),
                    graph[v].to_string(),
                    graph[neighbor].to_string(),
                ];
                triangle.sort();
                triangles.push((
                    triangle[0].clone(),
                    triangle[1].clone(),
                    triangle[2].clone(),
                ));
            }
        }
    }

    // Remove duplicate triangles
    triangles.sort();
    triangles.dedup();

    triangles
}

fn bron_kerbosch(
    graph: &UnGraph<&str, ()>,
    r: FxHashSet<usize>,
    p: &mut FxHashSet<usize>,
    x: &mut FxHashSet<usize>,
    max_cliques: &mut Vec<FxHashSet<usize>>,
) {
    if p.is_empty() && x.is_empty() {
        max_cliques.push(r);
        return;
    }

    let p_iter = p.clone();
    for v in p_iter {
        let mut r_new = r.clone();
        r_new.insert(v);

        let neighbors: FxHashSet<_> = graph
            .neighbors(graph.from_index(v))
            .map(|n| graph.to_index(n))
            .collect();

        let mut p_new: FxHashSet<_> = p.intersection(&neighbors).cloned().collect();
        let mut x_new: FxHashSet<_> = x.intersection(&neighbors).cloned().collect();

        bron_kerbosch(graph, r_new, &mut p_new, &mut x_new, max_cliques);

        p.remove(&v);
        x.insert(v);
    }
}

fn find_max_clique(graph: &UnGraph<&str, ()>) -> Vec<String> {
    let mut max_cliques = Vec::with_capacity(512);

    let mut nodes: FxHashSet<_> = (0..graph.node_count()).collect();

    bron_kerbosch(
        graph,
        FxHashSet::default(),
        &mut nodes,
        &mut FxHashSet::default(),
        &mut max_cliques,
    );

    let largest_clique = max_cliques
        .into_iter()
        .max_by_key(|c| c.len())
        .unwrap_or_default();

    largest_clique
        .into_iter()
        .map(|i| graph.node_weight(graph.from_index(i)).unwrap().to_string())
        .sorted()
        .collect()
}