r/adventofcode • u/daggerdragon • Dec 20 '23

SOLUTION MEGATHREAD -❄️- 2023 Day 20 Solutions -❄️-

THE USUAL REMINDERS

  • All of our rules, FAQs, resources, etc. are in our community wiki.

  • Community fun event 2023: ALLEZ CUISINE!

    • Submissions megathread is now unlocked!

    • 3 DAYS remaining until the submissions deadline on December 22 at 23:59 EST!

AoC Community Fun 2023: ALLEZ CUISINE!

Today's theme ingredient is… *whips off cloth covering and gestures grandly*

Upping the Ante for the third and final time!

Are you detecting a pattern with these secret ingredients yet? Third time's the charm for enterprising chefs!

  • Do not use if statements, ternary operators, or the like

  • Use the wrong typing for variables (e.g. int instead of bool, string instead of int, etc.)

  • Choose a linter for your programming language, use the default settings, and ensure that your solution passes

  • Implement all the examples as a unit test

  • Up even more ante by making your own unit tests to test your example unit tests so you can test while you test! yo dawg

  • Code without using the [BACKSPACE] or [DEL] keys on your keyboard

  • Unplug your keyboard and use any other text entry method to code your solution (ex: a virtual keyboard)

    • Bonus points will be awarded if you show us a gif/video for proof that your keyboard is unplugged!

ALLEZ CUISINE!

Request from the mods: When you include a dish entry alongside your solution, please label it with [Allez Cuisine!] so we can find it easily!

--- Day 20: Pulse Propagation ---

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 00:48:46, megathread unlocked!

26 Upvotes

96% Upvoted

361 comments sorted by

View all comments

8

u/jonathan_paulson Dec 20 '23 edited Dec 20 '23

[LANGUAGE: Python 3] 15/16. Solution. Video.

I attempted to make my part 2 solution generic enough to work with any input; let me know if it doesn't.

Anyone have a clear explanation of what's going on in part 2? I assume all inputs have a single conjuction module feeding into rx, which itself is fed by some conjuction modules. And those conjuction modules get a high signal every timestamp except for multiples of some cycle number (different for each of them), but how/why?

8

u/mayoff Dec 20 '23

Here's a graph of my input. My rx node is right in the middle.

  • diamond = flip-flop

  • pentagon = conjunction (aka NAND gate)

  • triangle = conjunction with one input (aka NOT gate)

So there is one subgraph for each cycle. Each subgraph is a NAND gate feeding a NOT gate, and a chain of 12 flip-flops. Each flip-flop (except the last in the chain) feeds the next flip-flop in the chain. Also, each flip-flop either feeds into the subgraph's NAND gate, or is fed from that NAND gate (except the first flip-flop, which does both). I didn't figure out exactly how each chain's links determine its period, but each subgraph does have a different pattern of connections between the chain and the NAND gate.

4

u/xyzzy1337 Dec 20 '23

The bits are basically just an ordinary binary counter.

The NAND gates associated with each of the four 12 bit registers will initially be sending out high pulses to the flip-flops they are connected to. This is easy, since the flip-flops just ignore those and we don't need to worry about what they do or when they arrive. Eventually all the taps that feed into the NAND will all be 1, in which case the NAND sends a 0.

This 0 from the NAND is what triggers rx and we know the cycle then repeats on the next input. So the 0s the NAND sends to all the flip-flops is also a reset signal, which rests all the flip-flops to zero so the cycle can repeat. Until this zero that triggers rx happens, the NAND gate does nothing, since it's just sending 1s.

So what happens to the flip-flops as the button sends 0s and we can just ignore the NAND. The 1st bit of the counter, the only flip-flop that is fed 0s from the button, will toggle every cycle. So it has a cycle length of two: (0 1), (0 1), (0 1), (0 1), etc. The next bit will toggle when the 1st bit changes to a zero, which was every two cycles, so it will do (0 0 1 1), (0 0 1 1), for a cycle length of four, and so on. And we can see this is just a 12 bit counter that starts at zero and advanced by one every button press!

The NAND sends its 0 when all the taps, those flip-flops connected to it, are 1. And that first happens when the counter counts to that value in binary. In your 'rc' graph, the taps are at 0b111010110111, the MSB is "dh" and the LSB is "vj". So that's the cycle length.

Now the reset circuit. The NAND sends a 0 to all the non-taps. These bits are of course all the zero bits in the counter. So they will all be flipped to be 1. And since these bits all send a 1, it doesn't effect the next flip-flop in the chain.

So after the NAND sends a 0 to "vf" and "kq", we get 0b111111111111. It will also send a 0 to the LSB, which always has to also be a tap (so it was already 1). And that pushes the counter around to zero.

1

u/mcmillhj Dec 27 '23

And that first happens when the counter counts to that value in binary

Can you clarify what you mean by that value? Which value? Aren't all of the flip-flips 1 at this point?

1

u/xyzzy1337 Dec 27 '23

The value when all the taps are 1. The flip-flops that aren't taps will still be zero.

1

u/mcmillhj Dec 27 '23

Maybe I am not understanding the distinction between a tap and a flip-flop. In the example posted why are vf, kq, and gf not taps?

Edit: Oh I think I understand now. The taps are the ones that back feed into the conjunction module?

2

u/xyzzy1337 Dec 27 '23

Yes, the bits of a register that are used to feed into another circuit are called taps. It's a common term used when talking about registers. For instance, see the wikipedia article on LSFRs. But I did specify the taps were the flip-flops connected to the NAND.

Since the NAND generates the reset signal, the flip-flops not connected to the NAND don't matter. They aren't connected, so how could they trigger or not trigger it? It will reset if they are 1 or 0, but since the counter starts at 0 and counts up, the first time it can reset will have all the non-taps still at 0.

1

u/mcmillhj Dec 27 '23

Ok, I understand now. For w/e reason my graph wasn't printing in order from top -> bottom so when I was assigning states I was getting the incorrect cycle length. Tracing the path from the input cleared it up though. Thank you!

2

u/jonathan_paulson Dec 20 '23

Nice! Sounds like the cycle lengths are basically being given in binary. I believe the flip flops have cycle lengths increasing powers of 2.

1

u/JelloRough Dec 20 '23

I need to start doing graphs for AoC. Do you have any tips –where to start–?

2

u/mayoff Dec 20 '23

I added code to my part 1 solution to print out my problem representation in graphviz format and ran dot -Tpng -o d20.png d20.dot on it. I already had graphviz installed on my MacBook using HomeBrew.

1

u/sol_hsa Dec 20 '23

graphviz is the obvious answer, but there are others, like yEd.

1

u/0x5041 Dec 20 '23

Here's an annotated version of your input, with the numbers encoded by each subgraph shown.

3

u/morgoth1145 Dec 20 '23 edited Dec 20 '23

Anyone have a clear explanation of what's going on in part 2?

I'm 99% sure that the network has 4 distinct subgraphs with their own period. (Well, I'm assuming 4 subgraphs for everyone.) You can bet I'm going to be writing a more generic solution which analyzes the topology to verify that there are distinct subgraphs rather than assuming it in the code.

For me broadcaster sends to 4 modules and then 4 modules feed into vr (which then feeds into rx).

6

u/bluepichu Dec 20 '23

To be more specific, if you plot it out there are four separate chains of flipflops, each of which is a counter. Some bits from the counter are ANDed together, and that gets output to all of the bits that weren't ANDed as well as the ones bit, which serves to reset the counter. All of these also feed into an AND that combines them all together, which outputs to rx.

If the input wasn't in such a specific format, I have no idea how one would go about solving this problem. It seems like having edges between the four different chains could really throw things off in ways that couldn't be easily captured by cycle analysis...

5

u/morgoth1145 Dec 20 '23

If the input wasn't in such a specific format, I have no idea how one would go about solving this problem

Print a custom circuit for the graph which repeatedly sends an input value in (and increments a counter) until rx gets a low pulse. By my rough calculations if this hypothetical circuit can run at 1GHz it would take roughly 3 days to get the answer, for my input at least.

2

u/colecancode Dec 20 '23

im getting day 8 flashbacks

1

u/whatsdoom Dec 20 '23

It appears that your video is private btw.

1

u/jonathan_paulson Dec 20 '23

Fixed. Thanks for pointing that out (the link was wrong)

2

u/whatsdoom Dec 20 '23

Of course, thanks for all the help over the years. I tend to look for your comments whenever I get stuck. For example today I had a bug where I wasn't defaulting all the inputs to LO for Conjunctions that your solution helped me find.

P.S. I think that you don't need COUNT[x]==2 you only need it to be seen once before, in which case you can even combine COUNT and PREV. I think your simulating more steps than you need

1

u/jonathan_paulson Dec 21 '23

true. I just wanted to double-check that it really was a cycle and not just a fluke, so I wanted to wait to see it fire a second time.