Advent of Code 2023 - Day 25

Learning Questions & Discussions Coding Challenges
,
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.

2 Likes
2

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
3

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.