Advent of Code 2024 - Day 23

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 ?

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

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.

https://github.com/rvnash/aoc2024/blob/main/lib/d23.ex#L63

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.

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!

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

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.
https://github.com/liamcmitchell/advent-of-code/blob/6227b6dd61e22568ad110332b85d8ec03561ebad/2024/23/1.exs#L45-L68

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

Can somebody help me figure out why my naive attempt is wrong.
I create a map where key is each computer and value is a map set of other computers connected to that computer.
Then for each element of value for a key value pair I get the values by using that value as key, and I filter under condition key in other_values and other_value in values which would mean they are connected; or so I thought.

defmodule Aoc2024.Solutions.Y24.Day23 do
  alias AoC.Input

  def parse(input, _part) do
    input
    |> Input.stream!(trim: true)
    |> Enum.map(fn line -> line |> String.split("-") |> List.to_tuple() end)
  end

  def part_one(problem) do
    map =
      problem
      |> Enum.reduce(%{}, fn {a, b}, map ->
        map
        |> Map.update(a, MapSet.new([b]), fn set -> MapSet.put(set, b) end)
        |> Map.update(b, MapSet.new([a]), fn set -> MapSet.put(set, a) end)
      end)

    Enum.reduce(map, MapSet.new(), fn {key, values}, acc ->
      values
      |> Enum.reduce(MapSet.new(), fn value, acc ->
        map
        |> Map.get(value)
        |> then(fn other_values ->
          other_values
          |> Enum.filter(&(key in other_values and &1 in values))
          |> Enum.reduce(acc, &MapSet.put(&2, Enum.sort([key, value, &1])))
        end)
      end)
      |> MapSet.union(acc)
    end)
    |> dbg()
    |> Enum.filter(&Enum.any?(&1, fn e -> String.contains?(e, "t") end))
    |> Enum.count()
  end
end

For test example I get same result as instructed:

 MapSet.new([
  ["aq", "cg", "yn"],
  ["aq", "vc", "wq"],
  ["co", "de", "ka"],
  ["co", "de", "ta"],
  ["co", "ka", "ta"],
  ["de", "ka", "ta"],
  ["kh", "qp", "ub"],
  ["qp", "td", "wh"],
  ["tb", "vc", "wq"],
  ["tc", "td", "wh"],
  ["td", "wh", "yn"],
  ["ub", "vc", "wq"]
]

and the filter/count returns 7.
But for real input it’s wrong. I would like to now why is my approach wrong. I’m missing something but I can’t figure out what.

Ignore me I didn’t read carefully