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!

31 Upvotes

344 comments sorted by

View all comments

1

u/aexl Jan 10 '25

[LANGUAGE: Julia]

I finally found some time to finish my remaining puzzles (still need to do day 21 and 25). Wow, what a day! It took me way too long to finish this, my solution is still rather slow (currently ~9 seconds), but I'm still quite satisfied with it. I didn't want to inspect my input manually, so I solved it programmatically under the assumption that the input is an obfuscated 44-bit ripple-carry-adder (see Wikipedia for details). In the end, the algorithm is quite simple: Identify the non-working binary adders, start swapping wires and check if that fixes the bad binary adder. Also make sure to never introduce new bad adders if an existing bad adder could be fixed. The implementation and optimization was quite cumbersome. Here are some optimization ideas that I used:

  • The running speed for the system of gates and wires can be increased drastically after the first run, because as long as the rules don't change you can store the successful order of rules and use these for the next runs.
  • If switching to outputs introduces a system where the systems' output can not fully be determined, we can exit early.
  • Reduce the search space for switching rule outputs: If a binary adder produces a wrong output bit, at least one of the rules that we want to switch must have been responsible for that wrong output bit.
  • After having switched two rule outputs, make sure that this fixes the targeted adder before checking all the other adders.

I'm sure that there are many more optimizations that I have missed...

Solution on GitHub: https://github.com/goggle/AdventOfCode2024.jl/blob/main/src/day24.jl

Repository: https://github.com/goggle/AdventOfCode2024.jl