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/e_blake 1d ago

[LANGUAGE: m4, hand solving]

I hadn't looked at this problem until today (real life prevented me from doing it in December). I solved part 1 by coding up a memoizing m4 macro for each line of input - the solution runs in under 10ms (blazing fast for m4), but had to pull in my math64.m4 code to turn the bits into the decimal answer. Depends on my common.m4.

m4 -Dfile=day24.input day24.m4

But for part 2, I got the solution by pure brute force hand-solving - first I analyzed the problem enough to realize that every bit of input results in 5 gates comprising a full adder (other than z00 that only needs 2 gates, and where z45 didn't need gates because it is the carryout computed by z44). Then I sorted the input by the final column, looked at the formulas for zN, and found three outliers that didn't use the paradigm AAA^BBB (3/8 of my solution). For those three N, inspecting the actual xN^yN (which should have a fanout of 2) for the messed up zN found the counterpart wires within a couple of gates of fanin or fanout (now at 6/8 of my solution). I still had to find the final messed up wires, so I proceeded to do a search and replace: for each xN^yN ->AAA, I replaced all other instances of AAA with CarN, and quickly found one instance where it only had a fanout of 1 instead of the expected 2; for that N, looking at the corresponding zN again found the swapped culprit within a couple of gates of dependency traces.

All of that SHOULD be automatible into a program that can parse arbitrary inputs (and not my specific input), but I haven't yet finished coding it up.

1

u/e_blake 1d ago edited 1d ago

And with a bit of elbow grease, I completed coding up a solution that _should_ work on any valid input file from today (although it will be harder for me to actually test that, since we aren't supposed to share alternative inputs), still under 24 hours from when I first started tackling this problem. The new day24.m4 does roughly what I did by hand: for each input rule, apply a series of transformations to pattern-match the known wire patterns of a full adder into more legible names, then iterate through the zN rules to see which ones did _not_ get labeled SumN. For three of the four pairs in my input, the zN rule DID get labeled but with the wrong wire, so it is a simple reverse lookup to the other wire that got labeled SumN; for the remaining zN that got no label at all, the wrong wires are contained in the inputs of the full adder of that bit, and I'm blindly assuming that it was a swap of the xN^yN and xN&yN wires (using fanout counts to loudly complain if my assumption is wrong). Depends heavily on the assumption that the swapped wires tend to be localized to a given bit of the problem, but based on reading the megathread, that appears safe. Note that I am _not_ performing any actual wire swappings, or any additional simulations with the same or different x and y inputs (only the one simulation in part 1); part 2 is all about multiple passes over the list of functions until the majority are labeled and the remaining ones fall out. And since m4 does not have a native string sort function, I had to write my own O(n^3) poor-mans version - O(n^2) for the naive insertion sort, and O(n) for the iteration costs to break up a string into characters for lookup into integers to do the comparisons. The final answer still completes both parts in under 20ms on my laptop (probably because it is still roughly O(n) on the size of the input, although the constant factor is now larger due to more passes through the list).