bjorng
December 26, 2023, 7:07pm
1
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.

```
#
# A brute-force solution that find the three edges in about 78 minutes
# on my computer.
#
# The idea is to try all combinations of removing two edges. With two
# edges removed, the last edge to cut (the bridge edge) can be found
# using a simple algorithm based on DFS.
#
defmodule Day25 do
def part1(input) do
g = parse(input)
solve(g)
end
defp solve(g) do
edges = :digraph.edges(g)
do_solve(g, edges, 0)
end
```

This file has been truncated. show original

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.

```
<!-- livebook:{"file_entries":[{"name":"04.txt","type":"attachment"}]} -->
# Advent of Code 2023 - Day 25
```elixir
Mix.install([
{:req, "~> 0.4.0"},
{:libgraph, "~> 0.16.0"}
])
```
## Input
```elixir
opts = [headers: [{"cookie", "session=#{System.fetch_env!("LB_AOC_SESSION")}"}]]
puzzle_input = Req.get!("https://adventofcode.com/2023/day/25/input", opts).body
```
```elixir
input =
```

This file has been truncated. show original