Table of content

What is this :grey_question:

The rules of the game are explained in my original.

99th Challenge

Challenge

Today’s challenge is day 23 of advent of code 2024.

Solution

Today’s challenge was graph theory relatedday 23 of advent of code 2024. I looked for a crate that could help and found graphrs crate. The crate counts traingles. So I counted traingles with and without ‘t’ at the beginning of the name (first I just checked any where in the name) and then subtracted the two. Note, because each node counts traingles for its self and the other nodes, I had to divide by 3.

For the second part I’m not exactly sure what I did yet. I didn’t find functions that count maximum cliques so I looked ath other functions in graphrs. I found the function generalized_degree and I found a condition for its output that matches maximum clique size of the graph. I’m not sure why though, and I’m not sure if it works on other inputs as well.

use graphrs::{algorithms::cluster, Edge, Graph, GraphSpecs};

fn main() {
    let input = include_str!("input.txt");

    let mut graph_with_t: Graph<&str, ()> = Graph::new(GraphSpecs::undirected_create_missing());
    let mut graph_without_t: Graph<&str, ()> = Graph::new(GraphSpecs::undirected_create_missing());

    input.lines().for_each(|line| {
        let mut parts = line.split("-");
        let n1 = parts.next().unwrap();
        let n2 = parts.next().unwrap();

        let edge = Edge::new(n1, n2);
        graph_with_t.add_edge(edge.clone()).unwrap();

        if !n1.starts_with("t") && !n2.starts_with("t") {
            graph_without_t.add_edge(edge).unwrap();
        }
    });

    let triangles_with_t = cluster::triangles(&graph_with_t, None);
    let triangles_without_t = cluster::triangles(&graph_without_t, None);

    if let (Ok(with_t), Ok(without_t)) = (triangles_with_t, triangles_without_t) {
        println!(
            "result part1: {:?}",
            with_t.values().sum::<usize>() / 3 - without_t.values().sum::<usize>() / 3
        );
    }

    let g = graph_with_t;

    let c = cluster::generalized_degree(&g, None);

    let mut pass = vec![];
    if let Ok(clustering) = c {
        let max = clustering
            .iter()
            .map(|(_node, cluster_map)| {
                cluster_map
                    .iter()
                    .filter(|(key, value)| **key as i32 - 1 == **value as i32)
                    .map(|(key, _value)| key)
                    .max()
                    .unwrap_or(&0)
            })
            .max()
            .unwrap();

        println!("max: {:?}", max);

        for (node, cluster_map) in clustering.iter() {
            for (key, value) in cluster_map.iter() {
                // key and value are values for clustring hashmap where key is max and value is 1+max
                if key == max && value == &(max + 1) {
                    pass.push(node.clone());
                    break;
                }
            }
        }
    }

    pass.sort();
    println!("result part2: {:?}", pass.join(","));
}