Day 25: Snowverload

Megathread guidelines

  • Keep top level comments as only solutions, if you want to say something other than a solution put it in a new post. (replies to comments can be whatever)
  • You can send code in code blocks by using three backticks, the code, and then three backticks or use something such as https://topaz.github.io/paste/ if you prefer sending it through a URL

FAQ

  • Treeniks@lemmy.mlEnglish
    1·
    1 year ago

    Rust

    github codeberg gitlab

    First tried a really slow brute force, but after waiting many minutes heard others talk of Karger’s Algorithm, so I implemented that.

    use rand::prelude::*;
use std::collections::HashSet;

type Graph = (V, E);

type V = HashSet<String>;
type E = Vec<(String, String)>;

fn parse_input(input: &str) -> Graph {
    let mut vertices = HashSet::new();
    let mut edges = Vec::new();

    for line in input.trim().lines() {
        let mut it = line.split(':');

        let left = it.next().unwrap();
        vertices.insert(left.to_owned());

        for right in it.next().unwrap().trim().split_whitespace() {
            vertices.insert(right.to_owned());
            edges.push((left.to_owned(), right.to_owned()));
        }
    }

    (vertices, edges)
}

fn part1(input: &str) -> usize {
    let (vertices, edges) = parse_input(input);

    let mut rng = rand::thread_rng();

    // Karger's Algorithm
    loop {
        let mut vertices = vertices.clone();
        let mut edges = edges.clone();
        while vertices.len() > 2 {
            let i = rng.gen_range(0..edges.len());
            let (v1, v2) = edges[i].clone();

            // contract the edge
            edges.swap_remove(i);
            vertices.remove(&v1);
            vertices.remove(&v2);

            let new_v = format!("{}:{}", v1, v2);
            vertices.insert(new_v.clone());

            for (e1, e2) in edges.iter_mut() {
                if *e1 == v1 || *e1 == v2 {
                    *e1 = new_v.clone()
                }
                if *e2 == v1 || *e2 == v2 {
                    *e2 = new_v.clone()
                }
            }

            // remove loops
            let mut j = 0;
            while j < edges.len() {
                let (e1, e2) = &edges[j];
                if e1 == e2 {
                    edges.swap_remove(j);
                } else {
                    j += 1;
                }
            }
        }

        if edges.len() == 3 {
            break vertices
                .iter()
                .map(|s| s.split(':').count())
                .product::<usize>();
        }
    }
}