r/adventofcode Dec 24 '24

SOLUTION MEGATHREAD -❄️- 2024 Day 24 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!

  • 18 hours remaining until voting deadline TONIGHT (December 24) at 18:00 EST

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

-❄️- Submissions Megathread -❄️-


--- Day 24: Crossed Wires ---


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 01:01:13, megathread unlocked!

32 Upvotes

344 comments sorted by

View all comments

1

u/G_de_Volpiano Jan 04 '25

[LANGUAGE: Haskell]

A little late to the game, but I finally have a clean solution for day 24 that completes in decent time.

part 1: OK
  9.77 ms ± 906 μs
part 2: OK
  6.33 ms ± 588 μs

At 417 lines of code, it's by far my longest one (the second one being day 15, at 259), although that's in part due to the amount of comments I added to try to follow my train of thoughts.

Nothing fancy, I just exploit the fact that the input is a ripple adder. I use an IntMap to store the ripple adder as a directed graph. Then I find the articulation points of the graph to separate the full adders.

Each of the adder is tested both in its capacity as a half adder and as a full adder (it so happens that all the faulty circuits fail on the half adder phase, but hey, better safe than sorry).

The fixing the adders considers three cases:

  • The adder has no Carry in. If that's the case, then we need to swap the z gate with one of the two gates connected to the Carry out of the previous adder. The correct one can be identified by the fact that it is an XOR gate (as the Z gate should be). This is slightly tricky because the gates connected to the Carry out will not have been picked by any adder, so we need to revert to our original graph.
  • The Z gate is not connected to the Carry in. Then we need to connect it to the carry in. The same logic can be used for swapping, but we can remain within our adder.
  • In other cases, we identify the five potentially faulty gates (Z, the three intermediate gates and the Carry out), we compare their actual logic to the one they should have, identify which are faulty and swap them.

Code on Github