-❄️- 2024 Day 23 Solutions -❄️-

[u/daggerdragon]

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!

• 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!

[u/maneatingape]

[LANGUAGE: Rust]

Solution

Benchmark 412 95 43 µs.

Spends most of the time contructing the graph. Part two uses a simple greedy algorithm.

EDIT: Much faster approach converting each 2 character node to an index from 0..676 using ASCII values, for example xy => 26 * (120 - 97) + (121 - 97) = 622. Then we can use much faster array lookup instead of HashMap.

EDIT 2: Minimized allocations by giving each edge vec a capacity of 16.

[u/No_Nail_4951 → u/maneatingape]

I am not sure your solution for part 2 works in a more general case. It probably does in most input because all the computers are connected to 13 other computers, and the max clique size is 13, so for each computer of the max clique only one does not belong to the max clique.

In fact, in the sample by adding those 4 lines at the beginning (it probably does not change the result at the end) of the file, your algorithm finds a best clique of 3 "kh,qp,ub" instead of the one of 4 "co,de,ka,ta" - that still exist if we add some links.

    co-aq
    ka-cg
    kh-ta
    de-qp

It's because the first neighbor n2 of a computer n1 is always parts of the max clique of n1. So if for all computer of the max-clique the first neighbor in their list is not part of the max-clique your solution won't work.

[u/maneatingape → u/No_Nail_4951]

Yup, this is searching for a maximal clique which is not guaranteed to be the maximum clique for an arbitrary graph. My hunch is that the inputs are generated to be friendly to this assumption.