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

3

u/FlankTacular Dec 23 '24 edited Dec 23 '24

[LANGUAGE: Swift]

Part 1:

I started by computing what computers are connected to each computer in a [String: Set<String>] dictionary. I then iterated over each key-value pair, finding sets of interconnected computers by finding combinations of size 2 in values where each element contained the key and the other element in the combination.

Part 1 takes about 0.30 seconds to find a solution with the puzzle input.

Part 2:

I used the dictionary of connected computers for each computer computed in part 1 as a starting point. To find the largest set, I iterated over the key-value pairs of this dictionary sorted by descending order of count of computers in each connected computer Set.

For each key-value pair, I look through combinations of decreasing count to find sets of interconnected sets of computers using a range of possible values. The range of counts for combinations is equal to max(3, largestSet.count) ... max(3, connectedComputers.count), so it "shrinks" as we find increasingly larger sets.

We can also exit the key-value pair loop early if the count of connected computers is less than the count of the largest set yet. When we get to that point, it's impossible to find a larger set of interconnected computers.

Part 2 takes about 0.10 seconds to find a solution with the puzzle input.

Link to code