Advent of Code 2024 - Day 23

Oh, true. Thanks!

For part 1, the instructions say to only count groups of 3.

Find all the sets of three inter-connected computers.

I don’t see in your code a filter for sets larger or smaller than that. Is it possible the full dataset has such groups?

Ignore me I didn’t read carefully

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.

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

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

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

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!

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.

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.