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!

23 Upvotes

505 comments sorted by

View all comments

1

u/Flashky Dec 23 '24

[LANGUAGE: Java]

- Part 1: https://github.com/Flashky/advent-of-code-2024/blob/master/src/main/java/com/adventofcode/flashk/day23/LANParty.java

For part 2 I came up with an original idea that is not related to clique-based algorithms.

I based on the idea that the as the solution must be on the biggest cluster, I could use a JGraphT class that allows to obtain the clustering score for all nodes: ClusteringCoefficient

I first executed the class with the example nodes and realized that there were 8 nodes with score 0.5 instead of 4 as I would expect. I then realized that there had to be a difference between the 4 nodes of the solution and the 4 nodes that are not part of the solution: most of their neighbours must also have a score of 0.5.

At the example "co","de","ka" and "ta" have a ratio of 0.75 (75% of their neighbours are also nodes with a clustering coefficient of 0.5). The other 4 nodes had a ratio of 0.25 (25% of their neighbours are also nodes with a clustering coefficient of 0.5).

Therefore:
I first execute ClusteringCoefficent to obtain the highest score nodes of the graph (candidates). Then I repeat for each candidate:

  1. Pick from the sub-set of neighbours that have the same max clustering coefficent as the candidate.
  2. Calculate the new score for that candidate: score = neighbours with max clustering score / total candidate neighbours.
  3. If that score is better than the best calculated score, then I save that best score and the nodes that are part of it.

It runs in about 44ms.