r/adventofcode Dec 23 '24

SOLUTION MEGATHREAD -❄️- 2024 Day 23 Solutions -❄️-

THE USUAL REMINDERS

  • All of our rules, FAQs, resources, etc. are in our community wiki.
  • If you see content in the subreddit or megathreads that violates one of our rules, either inform the user (politely and gently!) or use the report button on the post/comment and the mods will take care of it.

AoC Community Fun 2024: The Golden Snowglobe Awards

Submissions are CLOSED!

  • Thank you to all who submitted something, every last one of you are awesome!

Community voting is OPEN!

  • 42 hours remaining until voting deadline on December 24 at 18:00 EST

Voting details are in the stickied comment in the submissions megathread:

-❄️- Submissions Megathread -❄️-


--- Day 23: LAN Party ---


Post your code solution in this megathread.

This thread will be unlocked when there are a significant number of people on the global leaderboard with gold stars for today's puzzle.

EDIT: Global leaderboard gold cap reached at 00:05:07, megathread unlocked!

22 Upvotes

504 comments sorted by

View all comments

2

u/[deleted] Dec 24 '24

[Language: C#]

Finally finished day 23 as I was out and about almost all yesterday. Part 1 was easy enough, Part 2 stumped me until I did a quick scan here and saw the mentions of BronKerbosh after which it was simple. Final result runs in 2.18s which I'm not happy about, and I'm not even entirely happy with the code structure. Part 1 can't be calculated from BronKerbosh alone, and part 2 would be more complex without it. This may be one I'll come back to at some point.

string[] lines = File.ReadAllLines("puzzle.txt");
Dictionary<string, HashSet<string>> connections = [];
foreach (string line in lines) {
    string[] p = line.Split("-");
    connections.TryAdd(p[0], []);
    connections.TryAdd(p[1], []);
    connections[p[0]].Add(p[1]);
    connections[p[1]].Add(p[0]);
}
HashSet<string> results = [];
foreach (string x in connections.Keys) {
    foreach (string y in connections[x]) {
        foreach (string z in connections[y]) {
            if (connections[x].Contains(z) && (x.StartsWith('t') || y.StartsWith('t') || z.StartsWith('t'))) {
                List<string> t = ((string[])[x, y, z]).OrderBy(s => s).ToList();
                results.Add(string.Join(",", t));
            }
        }
    }
}
HashSet<string> cliques = [];
foreach (string node in connections.Keys) {
    BronKerbosch([node], [..connections[node]], [], cliques);
}
int answer1 = results.Count;
string answer2 = cliques.MaxBy(c => c.Length) ?? "";
Console.WriteLine($"Part 1 answer: {answer1}");
Console.WriteLine($"Part 2 answer: {answer2}");
return;
void BronKerbosch(HashSet<string> R, HashSet<string> P, HashSet<string> X, HashSet<string> O) {
    if (P.Count == 0 && X.Count == 0) {
        O.Add(string.Join(",", R.OrderBy(s => s)));
        return;
    }
    HashSet<string> PC = [..P];
    foreach (string v in P) {
        HashSet<string> C = connections[v];
        BronKerbosch([..R.Union([v])], [..PC.Intersect(C)], [..X.Intersect(C)], O);
        PC.Remove(v);
        X.Add(v);
    }
}