As The Historians wander around a secure area at Easter Bunny HQ, you come across posters for a LAN party scheduled for today! Maybe you can find it; you connect to a nearby datalink port and download a map of the local network (your puzzle input).

The network map provides a list of every connection between two computers. For example:

Visit the website for the full story and full puzzle description.

We tackled a graph algorithm problem today, where we had to find maximal cliques in an undirected graph. The literature provides efficient algorithms for this problem, but our graph is not too large, so we can use a straightforward "poor man's" strategy as well.

I started with the seed components, that is single element components for each node. Then, I proceeded to grow these components by adding a single node to them in all possible ways. I can put this in a loop, to get components with size 2, 3, 4, etc. Part 1 asks for the number of components that have 3 nodes and have at least one node starting with 't'. Part 2 asks for the biggest component that cannot be grown anymore.

namespace AdventOfCode.Y2024.Day23;

using System;
using System.Collections.Generic;
using System.Collections.Immutable;
using System.Linq;
using Graph = System.Collections.Generic.Dictionary<string, System.Collections.Generic.HashSet<string>>;
using Component = string;

[ProblemName("LAN Party")]
class Solution : Solver {
    public object PartOne(string input) {
        var g = GetGraph(input);
        var components = g.Keys.ToHashSet();
        components = Grow(g, components);
        components = Grow(g, components);
        return components.Count(c => Members(c).Any(m => m.StartsWith("t")));
    }

    public object PartTwo(string input) {
        var g = GetGraph(input);
        var components = g.Keys.ToHashSet();
        while (components.Count > 1) {
            components = Grow(g, components);
        }
        return components.Single();
    }
    
    HashSet<Component> Grow(Graph g, HashSet<Component> components) => (
        from c in components.AsParallel()
        let members = Members(c)
        from neighbour in members.SelectMany(m => g[m]).Distinct()
        where !members.Contains(neighbour)
        where members.All(m => g[neighbour].Contains(m))
        select Extend(c, neighbour)
    ).ToHashSet();

    IEnumerable<string> Members(Component c) => 
        c.Split(",");
    Component Extend(Component c, string item) => 
        string.Join(",", Members(c).Append(item).OrderBy(x=>x));

    Graph GetGraph(string input) {
        var edges = 
            from line in input.Split("\n")
            let nodes = line.Split("-")
            from edge in new []{(nodes[0], nodes[1]), (nodes[1], nodes[0])}
            select (From: edge.Item1, To: edge.Item2);

       return (
            from e in edges
            group e by e.From into g
            select (g.Key, g.Select(e => e.To).ToHashSet())
        ).ToDictionary();
    }
}

Please ☆ my repo if you like it!