Rust
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>();
}
}
}
I have night light turned on 24/7 on all my devices. If I don't I get a headache after around a day.
In fact, I couldn't consistently use linux until recently because only the latest Nvidia drivers (545) added support for night light on wayland. Those glasses could've been handy there.