Haskell

The solution for part two could now be used for part one as well but then I would have to rewrite part 1 .-.

import Control.Arrow

import Data.Ord (comparing)

import qualified Data.List as List
import qualified Data.Map as Map
import qualified Data.Set as Set

parse = Map.fromListWith Set.union . List.map (second Set.singleton) . uncurry (++) . (id &&& List.map (uncurry (flip (,)))) . map (break (== '-') >>> second (drop 1)) . takeWhile (/= "") . lines

depthSearch connections ps
        | length ps == 4 && head ps == last ps = [ps]
        | length ps == 4 = []
        | otherwise  = head
                >>> (connections Map.!)
                >>> Set.toList
                >>> List.map (:ps)
                >>> List.concatMap (depthSearch connections)
                $ ps

interconnections (computer, connections) = depthSearch connections [computer]

part1 = (Map.assocs &&& repeat)
        >>> first (List.map (uncurry Set.insert))
        >>> first (Set.toList . Set.unions)
        >>> uncurry zip
        >>> List.concatMap interconnections
        >>> List.map (Set.fromList . take 3)
        >>> List.filter (Set.fold (List.head >>> (== 't') >>> (||)) False)
        >>> Set.fromList
        >>> Set.size

getLANParty computer connections = (connections Map.!)
        >>> findLanPartyComponent connections [computer]
        $ computer

filterCandidates connections participants candidates = List.map (connections Map.!)
        >>> List.foldl Set.intersection candidates
        >>> Set.filter ((connections Map.!) >>> \ s -> List.all (flip Set.member s) participants)
        $ participants

findLanPartyComponent connections participants candidates
        | Set.null validParticipants = participants
        | otherwise = findLanPartyComponent connections (nextParticipant : participants) (Set.delete nextParticipant candidates)
        where
                nextParticipant = Set.findMin validParticipants
                validParticipants = filterCandidates connections participants candidates

part2 = (Map.keys &&& repeat)
        >>> uncurry zip
        >>> List.map ((uncurry getLANParty) >>> List.sort)
        >>> List.nub
        >>> List.maximumBy (comparing List.length)
        >>> List.intercalate ","

main = getContents
        >>= print
        . (part1 &&& part2)
        . parse

Rust

Finding cliques in a graph, which is actually NP-comlete. For part two I did look up how to do it and implemented the Bron-Kerbosch algorithm. Adding the pivoting optimization improved the runtime from 134ms to 7.4ms, so that is definitely worth it (in some sense, of course I already had the correct answer without pivoting).

use rustc_hash::{FxHashMap, FxHashSet};

fn parse(input: &str) -> (Vec<Vec<usize>>, FxHashMap<&str, usize>) {
    let mut graph = Vec::new();
    let mut names: FxHashMap<&str, usize> = FxHashMap::default();
    for l in input.lines() {
        let (vs, ws) = l.split_once('-').unwrap();
        let v = *names.entry(vs).or_insert_with(|| {
            graph.push(vec![]);
            graph.len() - 1
        });
        let w = *names.entry(ws).or_insert_with(|| {
            graph.push(vec![]);
            graph.len() - 1
        });
        graph[v].push(w);
        graph[w].push(v);
    }
    (graph, names)
}

fn part1(input: String) {
    let (graph, names) = parse(&input);
    let mut triples: FxHashSet<[usize; 3]> = FxHashSet::default();
    for (_, &v) in names.iter().filter(|(name, _)| name.starts_with('t')) {
        for (i, &u) in graph[v].iter().enumerate().skip(1) {
            for w in graph[v].iter().take(i) {
                if graph[u].contains(w) {
                    let mut triple = [u, v, *w];
                    triple.sort();
                    triples.insert(triple);
                }
            }
        }
    }
    println!("{}", triples.len());
}

// Bron-Kerbosch algorithm for finding all maximal cliques in a graph
fn bron_kerbosch(
    graph: &[Vec<usize>],
    r: &mut Vec<usize>,
    mut p: FxHashSet<usize>,
    mut x: FxHashSet<usize>,
) -> Vec<Vec<usize>> {
    if p.is_empty() && x.is_empty() {
        return vec![r.to_vec()];
    }
    let mut maximal_cliques = Vec::new();
    let Some(&u) = p.iter().next() else {
        return maximal_cliques;
    };
    let mut p_pivot = p.clone();
    for w in &graph[u] {
        p_pivot.remove(w);
    }
    for v in p_pivot {
        let pn = graph[v].iter().filter(|w| p.contains(w)).copied().collect();
        let xn = graph[v].iter().filter(|w| x.contains(w)).copied().collect();
        r.push(v);
        let new_cliques = bron_kerbosch(graph, r, pn, xn);
        r.pop();
        maximal_cliques.extend(new_cliques);
        p.remove(&v);
        x.insert(v);
    }
    maximal_cliques
}

fn part2(input: String) {
    let (graph, names) = parse(&input);
    let p = (0..graph.len()).collect();
    let mut r = Vec::new();
    let maximal_cliques = bron_kerbosch(&graph, &mut r, p, FxHashSet::default());
    let maximum_clique = maximal_cliques
        .iter()
        .max_by_key(|clique| clique.len())
        .unwrap();
    let mut lan_names: Vec<&str> = names
        .iter()
        .filter(|(_, v)| maximum_clique.contains(v))
        .map(|(name, _)| *name)
        .collect();
    lan_names.sort_unstable();
    println!("{}", lan_names.join(","));
}

util::aoc_main!();

Also on github

Haskell

I was expecting a very difficult graph theory problem at first glance, but this one was actually pretty easy too!

import Data.Bifunctor
import Data.List
import Data.Ord
import Data.Set qualified as Set

views :: [a] -> [(a, [a])]
views [] = []
views (x : xs) = (x, xs) : (second (x :) <$> views xs)

choose :: Int -> [a] -> [[a]]
choose 0 _ = [[]]
choose _ [] = []
choose n (x : xs) = ((x :) <$> choose (n - 1) xs) ++ choose n xs

removeConnectedGroup connected = fmap (uncurry go . first Set.singleton) . Set.minView
  where
    go group hosts =
      maybe
        (group, hosts)
        (\h -> go (Set.insert h group) (Set.delete h hosts))
        $ find (flip all group . connected) hosts

main = do
  net <- Set.fromList . map (second tail . break (== '-')) . lines <$> readFile "input23"
  let hosts = Set.fromList $ [fst, snd] <*> Set.elems net
      connected a b = any (`Set.member` net) [(a, b), (b, a)]
      complete = all (uncurry $ all . connected) . views
  print
    . length
    . filter complete
    . filter (any ((== 't') . head))
    $ choose 3 (Set.elems hosts)
  putStrLn
    . (intercalate "," . Set.toAscList)
    . maximumBy (comparing Set.size)
    . unfoldr (removeConnectedGroup connected)
    $ hosts
``