# Advent of Code 2023 - Day 25

I came up with a solution myself, but it is not fast.

My first brute-force solution simply tried removing all combinations of three edges and check if the resulting graph had two components. That algorithm had quartic complexity and would probably have taken weeks to finish.

My second solution was to remove all combinations of two edges. The third edge to remove can then be found in linear time with a simple algorithm based on DFS. That algorithm has “only” cubic complexity, which allowed it to finish in “only” one hour and twenty minutes.

2 Likes

I implemented Karger’s algorithm for finding the min-cut and then applied it repeatedly until the cut size was 3:

Part 1
``````defmodule Part1 do
def parse(input) do
for line <- String.split(input, "\n", trim: true),
reduce: %{} do
acc ->
[a | rest] = String.split(line, [":", " "], trim: true)

for b <- rest,
reduce: acc do
acc ->
acc
|> Map.update(a, MapSet.new([b]), &MapSet.put(&1, b))
|> Map.update(b, MapSet.new([a]), &MapSet.put(&1, a))
end
end
end

def group_product(graph) do
Map.keys(graph)
|> Enum.map(&String.length/1)
|> Enum.map(&div(&1, 3))
|> Enum.product()
end

def cut_size(g1, g0) do
[as, bs] =
for key <- Map.keys(g1) do
key
|> String.to_charlist()
|> Enum.chunk_every(3)
|> Enum.map(&to_string/1)
end

bs = MapSet.new(bs)

for a <- as,
_ <- MapSet.intersection(g0[a], bs),
reduce: 0 do
acc -> acc + 1
end
end

def contract(graph) when map_size(graph) == 2, do: graph

def contract(graph) do
{a, ea} = Enum.random(graph)
b = Enum.random(ea)
eb = graph[b]

ab = a <> b

ea = MapSet.delete(ea, b)
eb = MapSet.delete(eb, a)

eab = MapSet.union(ea, eb)

graph =
Enum.reduce(ea, graph, fn c, graph ->
Map.update!(graph, c, fn ec ->
ec
|> MapSet.delete(a)
|> MapSet.put(ab)
end)
end)

graph =
Enum.reduce(eb, graph, fn c, graph ->
Map.update!(graph, c, fn ec ->
ec
|> MapSet.delete(b)
|> MapSet.put(ab)
end)
end)

graph =
graph
|> Map.delete(a)
|> Map.delete(b)
|> Map.put(ab, eab)

contract(graph)
end
end

g0 = Part1.parse(input)

Stream.repeatedly(fn -> Part1.contract(g0) end)
|> Enum.find(fn g1 -> Part1.cut_size(g1, g0) == 3 end)
|> Part1.group_product()
``````

Now I just need to finish the other puzzles so that I can complete part 2!

3 Likes

Part 1 solution: Find the most used wires by counting the used wires between two random components. Repeat until removing the top three used wires divides the components in two groups.