# HG changeset patch
# User IBBoard <dev@ibboard.co.uk>
# Date 1713466583 -3600
# Node ID 7197f31970ff3cc68515ecb4096302caea6daa47
# Parent  ca54f9702892664b22ecf4e4d220577fe6662f0d
Day 25 part 1 instructions and partial solution

diff -r ca54f9702892 -r 7197f31970ff day25.rb
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/day25.rb	Thu Apr 18 19:56:23 2024 +0100
@@ -0,0 +1,85 @@
+#! /usr/bin/env ruby
+
+require 'set'
+
+if ARGV.length != 1
+    abort("Incorrect arguments - needs input file")
+elsif not File.exist? (ARGV[0])
+abort("File #{ARGV[0]} did not exist")
+end
+
+file = ARGV[0]
+
+
+connections = File.open(file, "r").each_line(chomp: true).flat_map do |line|
+    node1, rest = line.split(": ")
+    rest.split(" ").flat_map {|node| [[node1,node], [node,node1]]}
+end.group_by {|key, value| key}.transform_values {|vals| vals.map {|val| [val[1], 1]}.to_h}
+
+puts "#{connections}"
+
+# From https://en.wikipedia.org/wiki/Stoer%E2%80%93Wagner_algorithm
+# and https://tjkendev.github.io/procon-library/python/graph/stoer-wagner-algorithm.html
+
+def global_minimum_cut(graph, u0)
+    N = graph.size
+    res = 10**18
+
+    # groups = [{i} for i in range(N)]
+
+    merged = [0]*N
+    for s in range(N-1):
+        # minimum cut phase
+        used = [0]*N
+        used[u0] = 1
+        costs = [0]*N
+        for v in range(N):
+            if E[u0][v] != -1:
+                costs[v] = E[u0][v]
+        order = []
+        for _ in range(N-1-s):
+            v = mc = -1
+            for i in range(N):
+                if used[i] or merged[i]:
+                    continue
+                if mc < costs[i]:
+                    mc = costs[i]
+                    v = i
+            # assert v != -1
+
+            # v: the most tightly connected vertex
+            for w in range(N):
+                if used[w] or E[v][w] == -1:
+                    continue
+                costs[w] += E[v][w]
+            used[v] = 1
+            order.append(v)
+
+        v = order[-1]
+        ws = 0
+        for w in range(N):
+            if E[v][w] != -1:
+                ws += E[v][w]
+        # - the current min-cut is (groups[v], V - groups[v])
+        # - the weight of the cut is ws
+        res = min(res, ws)
+
+        if len(order) > 1:
+            u = order[-2]
+            # groups[u].update(groups[v])
+            # groups[v] = None
+
+            # merge u and v
+            merged[v] = 1
+            for w in range(N):
+                if w != u:
+                    if E[v][w] == -1:
+                        continue
+                    if E[u][w] != -1:
+                        E[u][w] = E[w][u] = E[u][w] + E[v][w]
+                    else:
+                        E[u][w] = E[w][u] = E[v][w]
+                E[v][w] = E[w][v] = -1
+    return res
+
+puts global_minimum_cut(connections, 1)
\ No newline at end of file
diff -r ca54f9702892 -r 7197f31970ff day25.txt
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/day25.txt	Thu Apr 18 19:56:23 2024 +0100
@@ -0,0 +1,7 @@
+--- Day 25: Snowverload ---
+
+You have a set of connected components. Connections are undirected, but are written as `a: b c d` to show that
+a is connected to b, c and d.
+
+You can cut three connections to split the system in half. What is the product of the number of nodes in each group
+when you do that?
\ No newline at end of file