Those who need a refresh can read the problem here.

This is our last day and these are historically not very hard. The puzzle is asking us to cut an undirected graph into two components by removing only three edges. I had absolutely no idea how to do that in an effective way, so it was time to consult the literature. Soon enough I found Karger's algorithm on Wikipedia.

It's a randomized algorithm that works on non-weighted, undirected graphs like ours. It finds some cut which is not necessarily minimal, but there is a good chance that it finds the minimal one in a few tries. This is the Elf way!

Karger's is not hard to implement, but I'm not used to do this kind of things lately, so I spent quite a lot of time getting it right. One mistake was that I didn't add the edges in the reverse direction: the input contains them only in one way. Then it was not obvious what to do with multiple edges between two nodes, because the algorithm needs to create these. But it has started to work and I just let it do its thing in a loop and it really found a cut with 3 edges in a few milliseconds.

It was easy to extend the algorithm to return the sizes of the two components as well. Part 1 asks for the product of these. Part 2 is a meta puzzle, it requires to complete all other challenges from the previous days, but I already finished those, so I can conclude season today (Dec 25th).

Thanks for joining me! If you find this work useful or want to get in touch (even just saying hello), find me on Github or Twitter.

Psst! There is game hidden in this site.

namespace AdventOfCode.Y2023.Day25;

using System;
using System.Collections.Generic;
using System.Linq;

[ProblemName("Snowverload")]
class Solution : Solver {

    public object PartOne(string input) {
        Random r = new Random(25);

        // run Karger's algorithm until it finds a cut with 3 edges
        var (cutSize, c1, c2) = FindCut(input, r);
        while (cutSize != 3) {
            (cutSize, c1, c2) = FindCut(input, r);
        }
        return c1 * c2;
    }

    // https://en.wikipedia.org/wiki/Karger%27s_algorithm
    // Karger's algorithm finds a cut of a graph and returns its size. 
    // It's not necessarily the minimal cut, because it's a randomized algorithm 
    // but it's 'likely' to find the minimal cut in reasonable time. 
    // The algorithm is extended to return the sizes of the two components 
    // separated by the cut as well.
    (int size, int c1, int c2) FindCut(string input, Random r) {
        var graph = Parse(input);
        var componentSize = graph.Keys.ToDictionary(k => k, _ => 1);

        // updates backreferences of oldNode to point to newNode
        var rebind = (string oldNode, string newNode) => {
            foreach (var n in graph[oldNode]) {
                while (graph[n].Remove(oldNode)) {
                    graph[n].Add(newNode);
                }
            }
        };

        for (var id = 0; graph.Count > 2; id++) {
            // decrease the the number of nodes by one. First select two nodes u 
            // and v connected with an edge. Introduce a new node that inherits 
            // every edge going out of these (excluding the edges between them). 
            // Set the new nodes' component size to the sum of the component 
            // sizes of u and v. Remove u and v from the graph.
            var u = graph.Keys.ElementAt(r.Next(graph.Count));
            var v = graph[u][r.Next(graph[u].Count)];

            var merged = "merge-" + id;
            graph[merged] = [
                ..from n in graph[u] where n != v select n,
                ..from n in graph[v] where n != u select n
            ];
            rebind(u, merged);
            rebind(v, merged);

            componentSize[merged] = componentSize[u] + componentSize[v];

            graph.Remove(u);
            graph.Remove(v);
        }

        // two nodes remain with some edges between them, the number of those 
        // edges equals to the size of the cut. Component size tells the number 
        // of nodes in the two sides created by the cut.
        var nodeA = graph.Keys.First();
        var nodeB = graph.Keys.Last();
        return (graph[nodeA].Count(), componentSize[nodeA], componentSize[nodeB]);
    }

    // returns an adjacency list representation of the input. Edges are recorded 
    // both ways, unlike in the input which contains them in one direction only.
    Dictionary<string, List<string>> Parse(string input) {
        var graph = new Dictionary<string, List<string>>();

        var registerEdge = (string u, string v) => {
            if (!graph.ContainsKey(u)) {
                graph[u] = new();
            }
            graph[u].Add(v);
        };

        foreach (var line in input.Split('\n')) {
            var parts = line.Split(": ");
            var u = parts[0];
            var nodes = parts[1].Split(' ');
            foreach (var v in nodes) {
                registerEdge(u, v);
                registerEdge(v, u);
            }
        }
        return graph;
    }
}

Please ☆ my repo if you like it!