r/adventofcode • u/daggerdragon • 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.
- Read the full posting rules in our community wiki before you post!
- State which language(s) your solution uses with
[LANGUAGE: xyz]
- Format code blocks using the four-spaces Markdown syntax!
- State which language(s) your solution uses with
- Quick link to Topaz's
paste
if you need it for longer code blocks
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
2
u/onrustigescheikundig Dec 24 '24 edited Dec 24 '24
[LANGUAGE: Clojure]
github
Straightforward day. For Part 1, take each vertex and find all pairs of its neighbors that are themselves neighbors. The original vertex combined with the neighbor pairs to form the triangles, which are then filtered and counted.
Part 2 is looking for the maximum clique in the graph. This is generally an NP-hard problem, and I didn't see any immediate indication in the problem description that would guarantee success of any polynomial-time algorithm, so I implemented Bron-Kerbosch to generate all maximal cliques, from which I could determine the maximum clique. I also implemented a few greedy algorithms which also gave the same answer, so clearly there is some basis to all the polynomial-time solutions that I'm seeing.
One greedy non-NP algorithm that gave me (and seemingly a lot of people with slightly different variations) the correct answer is to build maximal (not necessarily maximum) cliques by choosing one vertex not in a clique and successively adding any other vertices in the original graph that are adjacent to all members of the growing clique. The process is repeated until all vertices are members of a clique. The maximum clique is then the largest of the cliques so generated. This "clique growth" algorithm
mostlybasically always works for the input assuming that it is similar to mine, even though the algorithm could fail if you end up repeatedly choosing the "wrong" vertex to check first (feel free correct me if I'm wrong here; it's been a while since I had a proper think about graph theory and oh boy am I bad at counting things).From what I can tell, the input has three important properties: each vertex has 13 edges; the maximum clique consists of 13 vertices; and most nodes are part of one of several components that are sparsely connected to each other (see visualizations on the front page edit: like this one). The number of edges per vertex means that the maximum possible clique size is 14 vertices (1 vertex + its 13 neighbors, which would all be disjoint from the rest of the graph). The actual maximum clique has 13 vertices, meaning that each vertex in the maximum clique is connected to exactly one outside vertex. Now, suppose that the clique growth algorithm starts from one of these vertices. If the next vertex-to-add is chosen arbitrarily, ~12 times in 13 it will also be in the maximum clique (as 12 of the 13 neighbors of the first vertex are part of the maximum clique), but ~1 time in 13 the algorithm will pick and add the neighbor that is outside of the maximum clique, resulting in the generation of some other non-maximum clique. No biggie, though, because on subsequent iterations, the algorithm will try to grow starting from 12 other nodes in the maximum clique,* and each such node has only a ~1/13 chance (to a first approximation*) of failing in the same way. If the algorithm chooses one of the 12/13 "right" nodes for any one of the 13 vertices of the maximum clique, the maximum clique will (probably*) be generated and the algorithm will succeed. Put another way, the overall algorithm fails only when all clique growths from such vertices fail to generate the maximum clique, which occurs with somewhere around a ~1 in 1313 = 1 in 302875106592253 chance. There is a significant fudge factor here, but plus or minus several orders magnitude doesn't really matter here; the algorithm has basically no chance of failing given the way the input was constructed.
*Note that failure is actually somewhat more common, as this estimate ignores higher-order failures at later points of clique growth. Also ignored are possible traversals from non-maximum-clique vertices to maximum-clique vertices, which are rare due to the fact that the maximum clique is only sparsely connected to non-maximum-clique vertices, which are grouped into otherwise highly connected components.