Advent of Code 2024 - Day 23

Learning Questions & Discussions Coding Challenges
,
1

This was surprisingly easy.

After a quick attempt to use digraph, I implemented by own straightforward algorithm to find the groups. To my surprise, I didn’t need to do any optimizations to solve both parts. The combined runtime for solving both parts was 2.5 seconds.

I then added an optimization to keep track of the size of largest set seen so far and quickly discard any sets smaller than that number before checking for connectedness.

That reduced the runtime to 0.2 seconds.

2

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 ?

1 Like
3

Not really. I just didn’t think of doing that.

4

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.

1 Like
5

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.

1 Like
6

The flat_map_reduce iterates over the map of all connections for each computer. For the example it looks this:

%{
  co: [:ka, :ta, :de, :tc],
  cg: [:de, :tb, :yn, :aq],
  tc: [:kh, :wh, :td, :co],
  kh: [:tc, :qp, :ub, :ta],
  qp: [:kh, :ub, :td, :wh],
  de: [:cg, :co, :ta, :ka],
  ka: [:co, :tb, :ta, :de],
  yn: [:aq, :cg, :wh, :td],
  aq: [:yn, :vc, :cg, :wq],
  ub: [:qp, :kh, :wq, :vc],
  tb: [:cg, :ka, :wq, :vc],
  vc: [:aq, :ub, :wq, :tb],
  wh: [:tc, :td, :yn, :qp],
  ta: [:co, :ka, :de, :kh],
  td: [:tc, :wh, :qp, :yn],
  wq: [:tb, :ub, :aq, :vc]
}

For each computer, all possible sets that the computer is part of is constructed. There will be a lot of duplicate sets in the combined list, but Enum.uniq gets rid of them. That approach was my first stab at solving the problem. All I aimed for was a correct solution that I then could optimize. It surprised me that it was that fast. For once, a pleasant surprise!

7

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 :slight_smile:

1 Like
8

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.

2 Likes
9

Nice. I wondered if building up the sets rather than staring w/ all combinations and filtering them down would work faster.