Day 23

prelude

https://adventofcode.com/2024/day/23

import { inputDay } from "./lib/utilities.js"

const parser = inp =>
  inp
    .trim()
    .split("\n")
    .map(x => x.split("-"))
const test = parser(
  "kh-tc\nqp-kh\nde-cg\nka-co\nyn-aq\nqp-ub\ncg-tb\nvc-aq\ntb-ka\nwh-tc\nyn-cg\nkh-ub\nta-co\nde-co\ntc-td\ntb-wq\nwh-td\nta-ka\ntd-qp\naq-cg\nwq-ub\nub-vc\nde-ta\nwq-aq\nwq-vc\nwh-yn\nka-de\nkh-ta\nco-tc\nwh-qp\ntb-vc\ntd-yn\n",
)
display(test)

const input = await inputDay(23, { parser })
display(input)

part 1

// gather the network into a map of node -> set of connections
function gather(network) {
  const m = new Map()
  for (const [a, b] of network) {
    if (!m.get(a)) m.set(a, new Set())
    if (!m.get(b)) m.set(b, new Set())
    m.get(a).add(b)
    m.get(b).add(a)
  }
  return m
}
display(gather(test))

// find and return connections a -> b -> c -> a
function run(network) {
  const net = gather(network)
  const triples = new Set()
  for (const key of net.keys().filter(x => x.startsWith("t"))) {
    for (const conn of net.get(key)) {
      for (const conn_ of net.get(conn)) {
        if (conn_ == key || conn_ == conn) continue
        if (net.get(conn_)?.has(key))
          triples.add([key, conn, conn_].sort().join("->"))
      }
    }
  }
  return triples
}

display(run(test))
display(run(input))

part 2

A function to get the complete subgroups for a given key:

function subgroup(network, key) {
  // start with the pairs of each node with its connections
  let groups = [
    ...network
      .get(key)
      .values()
      .map(c => [key, c]),
  ]
  let found = true
  while (found) {
    // quit the loop when we haven't added any connections
    found = false
    for (const group of groups) {
      // check the last node of every group
      let node = group[group.length - 1]

      // for each of its connections
      for (const conn of network.get(node)) {
        // if the node has a connection to every item in the group, add it
        if (group.every(n => network.get(n).has(conn))) {
          group.push(conn)
          found = true
        }
      }
    }
  }
  return groups
}
display(subgroup(gather(test), "co"))

Now we can iterate each node, get the largest subgroup for it, and return the largest of these

function largestSubgroup(network) {
  const net = gather(network)
  let max = ""
  for (const key of net.keys()) {
    const maxSubgroup = subgroup(net, key)
      .sort(x => -x.length)[0]
      .sort()
      .join(",")
    if (maxSubgroup.length > max.length) {
      max = maxSubgroup
    }
  }
  return max
}

display(largestSubgroup(test))
display(largestSubgroup(input))