Another one that took a long time to reason about and even longer to get working around xmas distractions.
My part 2 runs in 100ms on my 2013 MBP so I’ve prob done something different.

Part 1 example (5.2ms): 7
Part 1 input (22.8ms): 1352
Part 2 example (0.9ms): "co,de,ka,ta"
Part 2 input (106.6ms): "dm,do,fr,gf,gh,gy,iq,jb,kt,on,rg,xf,ze"

For each node I sort all linked nodes by the number of times they are linked to each other. Then reduce the sorted list into the largest set by adding each node if it links to all existing nodes in the set.

Pretty similar solution here (at least for part 2), even without further optimizations (I use simple lists and maps) it solves part 2 sub 500ms:

defmodule Y2024.D23 do
  use Day, input: "2024/23", part1: ~c"l", part2: ~c"l"

  defp part1(input) do
    sorted_edges =
      input
      |> parse_input()
      |> Enum.sort_by(&elem(&1, 1))
      |> Enum.sort_by(&elem(&1, 0))

    sorted_edges
    |> Enum.chunk_by(&elem(&1, 0))
    |> Enum.flat_map(fn set ->
      set
      |> pairs()
      |> Enum.filter(&match?({{a1, _}, {a1, _}}, &1))
      |> Enum.filter(fn {{_, a2}, {_, b2}} -> Enum.member?(sorted_edges, {a2, b2}) end)
      |> Enum.map(fn {{a1, a2}, {a1, b2}} -> {a1, a2, b2} end)
    end)
    |> Enum.filter(fn
      {"t" <> _, _, _} -> true
      {_, "t" <> _, _} -> true
      {_, _, "t" <> _} -> true
      _ -> false
    end)
    |> Enum.count()
  end

  defp part2(input) do
    links =
      input
      |> parse_input()
      |> Enum.flat_map(fn {a, b} -> [{a, b}, {b, a}] end)
      |> Enum.group_by(&elem(&1, 0), &elem(&1, 1))

    links
    |> Enum.reduce({[], 0}, fn {from, tos}, {_, size} = acc ->
      tos
      |> combinations()
      |> Enum.sort_by(&Enum.count/1, :desc)
      |> Enum.take_while(&(Enum.count(&1) >= size))
      |> Enum.find(&full_mesh?(&1, links))
      |> case do
        nil -> acc
        set -> {[from | set], Enum.count(set) + 1}
      end
    end)
    |> elem(0)
    |> Enum.sort()
    |> Enum.join(",")
  end

  defp full_mesh?([], _), do: true

  defp full_mesh?([h | tail], links) do
    connected = Map.get(links, h)

    tail
    |> Enum.all?(&Enum.member?(connected, &1))
    |> Kernel.and(full_mesh?(tail, links))
  end

  defp pairs([]), do: []
  defp pairs([h | tail]), do: for(t <- tail, do: {h, t}) ++ pairs(tail)

  defp combinations([]), do: [[]]

  defp combinations([h | tail]) do
    tails = combinations(tail)
    for(t <- tails, do: [h | t]) ++ tails
  end

  defp parse_input(input), do: Enum.map(input, &parse_line/1)

  defp parse_line(<<node1::bytes-size(2), "-", node2::bytes-size(2)>>) do
    [node1, node2]
    |> Enum.sort()
    |> List.to_tuple()
  end
end

@bjorng I see this in your code:

    |> Enum.group_by(&elem(&1, 0))
    |> Enum.map(fn {v, reachable} ->
      {v, Enum.map(reachable, &elem(&1, 1))}
    end)
    |> Map.new

Is there any reason you do not use the third argument of Enum.group_by/3 to transform the values ?

Another fairly easy day. Decided to do part1 and part2 by just getting all valid networks first, and filter them later. It was taking about 8 seconds. Then added a filter function to pick out only the valid combinations on the fly, and that helped.

Then, taking advantage of the knowledge I gained yesterday about Atom being the fastest type of key for a Map, converted the computer names to atoms and got 3X faster. Final results are ~110ms for both parts on my M1 Mac.

I got it easily too but my solution was to build all possible networks of 3, then try to add the compatible candidates to get networks of 4, then 5, etc…

It takes 1.5 second with optimizations.

I’m trying to understand your code @bjorng but it seems that you do only one pass, there is no loop. The flat_map_reduce seems to iterate over a predefined list, which is puzzling me.

Alright ok so:

• for each computer, compute all possible combinations of all lenghts from the remaining computer
• prune the sets that would be less long than the current max+1
• try each combination to see if it’s all connected
• and just return that.

I would not have think this was the fast way haha

Thank you