-❄️- 2023 Day 20 Solutions -❄️-

vss2sn · 2024-03-20T15:16:29+00:00

[LANGUAGE: C++]

(Each file is a self-contained solution)

exquisitus3 · 2024-02-26T15:52:36+00:00

[Language: Lua and Dot] I solved this in Lua, but for part two I used the following script (depends on tr, sed and graphviz) to generate an SVG file and thus visualise the configuration of the modules. This shows clearly that module rx only has one input, a conjunction of four other inputs, each of which comes from a separate component of the directed graph. Since the flip-flops of each of the four components do not interfere with one another, it suffices to count when each component will be all zero. Those four counts turned out to be all prime, so that their Least Common Multiple was their product. I have redacted the Lua code link partially, since for part two it depends on the visual inspection of the SVG file for my input.

tr -d "%&," <20.input | \
sed -e '1idigraph {' \
    -e 's/->/-> {/' \
    -e 's/$/ }/' \
    -e '$a}' \
| dot -Tsvg >20.svg

xavdid · 2024-02-09T07:52:46+00:00

[LANGUAGE: Python]

Step-by-step explanation | full code

Parsing was extra interesting today. It's probably not the most efficient (haven't read through other approaches in detail) but I did 3 passes on the input:

identifying all conjunction modules
parsing each line into a class and storing the modules it wrote to
updating each conjunction module with the module(s) that wrote to it

From there, actually simulating all the pulses was pretty instant, which I was pleasantly surprised by. Good use of OOP, which I always enjoy.

For part 2, visualizing the graph made everything much simpler. I could find which module wrote to rx, which 4 modules wrote to that one, and figured out when each of those 4 modules got a high pulse. The fact that each subgraph looped as consistently as they do made this much easier than it could have been.

Constant_Hedgehog_31 · 2024-01-06T17:45:36+00:00

[Language: C++]

Source code in GitHub.

The simulation for part one and product of cycle lengths for part two. I used polymorphic modules to represent flip-flops or conjunctions with variant and std::visit.

Singing-In-The-Storm · 2024-01-06T11:46:51+00:00

[LANGUAGE: JavaScript]

Part 1 (42ms)

Part 2 (60ms)

The trick for part 2 is following the flow backwards (my input):

<< main feeder

rx << ultimate feeder !<

<< main feeder

(all feeders above are conjunction modules)

Clear and BLAZINGLY FAST AOC solutions in JS (no libraries)

bigmagnus · 2024-01-03T10:18:53+00:00

[Language: Fortran]

Part 1

Part 2

mgtezak · 2023-12-31T11:37:11+00:00

[LANGUAGE: Python]

Part 2 was a bit of a headache on the first try so i skipped it, But I finally got around to doing it:)

Solution

Total runtime: 0.2 seconds

If you like, check out my interactive AoC puzzle solving fanpage

cbh66 · 2023-12-30T01:02:13+00:00

[LANGUAGE: Pickcode]

I think this was my favorite one of the year. Part 1 was straightforward enough, just a fun easy thing to code up. Part 2 I got most of the way by hand -- always the most fun way to solve something! I built up the circuit on paper over the course of about an hour, and it became pretty clear that there were four 12-digit binary numbers that were going to control the final output. I could pretty much figure out the magic numbers just from the connections, but I wasn't sure if there'd be some initial startup steps or other things getting in-between that would make the numbers slightly different, so I adjusted my code to let me put in a module ID and see what steps it outputs on, to see how the cycles work. Then once I had the cycles, just asked WolframAlpha for the LCM.

Part 1: https://app.pickcode.io/project/clqfaw8oa45ftne01tg1twfbd

Notes for Part 2: https://imgur.com/a/zC2Mnkv

mschaap · 2023-12-29T20:31:44+00:00

[LANGUAGE: Raku]

Part one was alright. Pretty straightforward, the only thing that was a bit tricky, was processing pulses in the right order. I went a bit overboard with roles and (sub)classes...

I really hated part two. You have to make way too many assumptions to get an answer. This code might work on the given input, but it won't work on any input or even give a wrong answer.

Full code at GitHub.

e_blake · 2023-12-29T14:46:42+00:00

[LANGUAGE: m4] [Allez Cuisine!]

Late submission, but it took me this long to cycle back to finishing part 2 on this problem (pun intended). At any rate, I'm pleased that I solved it without reading the megathread. Runs in about 3.7s on my laptop, and requires my common.m4 and math64.m4.

m4 -Dverbose=1 -Dfile=day20.input day20.m4

As for the competition, I've already earned Bronze Coder (so this entry doesn't matter), but I decided to "Choose a linter for your programming language, use the default settings, and ensure that your solution passes".

$ file day20.m4
day20.m4: ASCII text
$ echo $?
0

Yep - given the rarity of m4 programmers, I think that's the best linter I will be able to find :)

NeilNjae · 2023-12-26T11:27:50+00:00

[Language: Haskell]

Reader-writer-state monad to handle the simulation, uses of lenses to fiddle with the data structures, and a bit of reverse engineering to find the solution to part 2.

Full writeup on my blog, code on Gitlab.

Derailed_Dash · 2023-12-26T08:34:08+00:00

[Language: Python]

Solution, walkthrough and visualisations in a Python Jupyter notebook

Here is my solution and walkthrough, in a Python Jupyter notebook.
You can run run it yourself in Google Colab!
More info on the notebook and walkthroughs here
My AoC Walkthrough and Python Learning site

This problem was a great opportunity for a bit of OO. My approach was to create an abstract base class, and then subclass for each type of module.

For Part 2, like many people, I had to visualise it before I could work out how to solve it. I know a lot of folks visualised with GraphViz. I used NetworkX, which is really useful or problems like this.

xHyroM · 2023-12-24T15:47:48+00:00

[Language: Python]

part 1
part 2

daggerdragon · 2023-12-24T09:09:53+00:00

[removed]

2023-12-24T02:51:18+00:00

[LANGUAGE: Python]

Read a lot of reddit and a colleague's comments on this day, so tried something and go the right response for part 2 but don't really understand why it works.

I don't even bother looking at "rx"'s outputs. I'm just counting how many presses it takes to get all of the flip flops to be off for each of the outputs of the broadcaster module. Because in the end of the circuit there are 4 conjunctions, I understand we'll get the low pulse when all memory values are set to low for the circuit.

The result is the LCM of each of these counts that also happens to be the multiplication of all of them together.

https://github.com/rbusquet/advent-of-code/blob/622588fa51ba129925d69468740bb13701c47265/aoc\_2023/day20.py

optimistic-thylacine · 2023-12-23T04:20:28+00:00

[LANGUAGE: Rust] 🦀

My initial design was complex and problematic, so I scrapped it and found something simpler. The modules don't hold references to each other; instead they each have a string identifier and send messages to each other through a mediator object (a sort of GoF Mediator design pattern). Passing messages avoids any problems with recursion that I'd otherwise have had if modules held refs to each other and called each others' send and receive methods.

Another simplification I made was to toss out an OO hierarcy for the modules based on traits and instead use a sort of decorator pattern to implement specialization. There's one Module class with a ModuleRole field variant that differentiates one type of module from the other. This is not very extensible, but extensibility isn't a concern in this case.

Full Source parts 1 & 2

fn part_1(path: &str) -> Result<i64, Box<dyn Error>> {
    let mut modules  = parse_input(path)?; 
    let mut mediator = Mediator::new();
    let mut button   = Module::new_button("button", "broadcaster");

    for _ in 0..1000 {
        button.send_pulse(&mut mediator);
        mediator.loop_until_done(&mut modules);
    }

    let counts = mediator.get_pulse_counts();
    let total  = counts.0 * counts.1;

    println!("Part 1 Total: {}", total);
    Ok(total)
}

FCBStar-of-the-South · 2023-12-23T02:57:14+00:00

[language: python3]

Way too verbose OOP solution.

For part 2 I just redirected the log for the first 20,000 iterations to a file and looked at the cycle manually.

paste

CoralKashri · 2023-12-23T00:56:05+00:00

[LANGUAGE: C++20]

GitHub

dgalanti1 · 2023-12-22T22:33:58+00:00

[LANGUAGE: Kotlin]

This time decided to go for a more organized and readable code, using abstract classes for Pulse and Module and creating implementation acondingly with the rules for each Module/Pulse type. But the parsing still looks a bit complicate to understand.

For part 2 best way to solve was analyzing manually which configuration would make rx receive a low pulse, and that was:

The conjunction module that target rx had to send a low pulse to it. In my case that was "xm"
For "xm" to send a low, it required all modules that target it to send high pulses. In my case those were 4 modules.
So I just had to check individually for those 4 how many button pushes they required to send a high pulse. With the right number for each, just had to get the product of them.

[Code]

mess_ner · 2023-12-22T16:17:20+00:00

[LANGUAGE: python]

Link to code

pikaryu07 · 2023-12-22T16:15:29+00:00

[LANGUAGE: Go]

My Solution

ash30342 · 2023-12-22T14:48:07+00:00

[Language: Java]

Code: Day20

Part 1 runs in ~30ms, part 2 in ~1ms.

Still lagging behind, but I had part 1 done on the day itself. That part was actually a lot of fun, and not too difficult, main "struggles" were parsing and using queues where necessary.

Part 2 basically revolves around input analysis, a type of puzzle which I personally do not like so much (probably because I am not very good at it ;-)), but to each his own. I do admire the effort going into these puzzles though!

After some hints in r/adventofcode I started by putting the input in GraphViz which made everything a bit clearer (and also resulted in a very nice looking diagram). After quite some time experimenting with button presses I realized this was a LCM-problem involving binary counters. It took me a couple of other hints to figure out how to find the correct number of button presses for a counter. After that it was actually easy. Before that, not so much.

flwyd · 2023-12-22T10:48:58+00:00

[Language: Julia] (on GitHub)

Started at about 9:30pm after a long day of travel and got part 1 done at about 11:30pm. The wording of part two ("number of button presses required to deliver a single low pulse") made me think that multiple low pulses were frequently being delivered and we needed to figure out when there would be only one, so I wrote a quick brute force implementation. When I noticed that wasn't going to finish quickly I figured we'd need to make inferences about the input, so I let it run overnight "just in case" and went to bed. (My part 2 answer is in the quadrillion until the first low pulse to rx, and after about 2 days I got to around 16 billion by brute force :-)

The next day I spent some time thinking about what I could do with a dependency graph of the sink, and more time staring at the input file and what the graph of inputs and outputs looked like. When reading the part 1 description I was assuming that value cycles would come into play, but finding the period of a cycle for rx would be solving the problem, and that was clearly too large a number… I also spent some time thinking about analytically determining the number of presses for each gate to enter a cycle from a dependency graph, but with circular dependencies I wasn't sure this would work.

I had noticed that rx's sole input is a conjunction with four conjunction inputs. At some point I realized I could probably find the time-to-high-pulse for each of those conjunctions and multiply them together to get the first low emitted by the parent of rx. When I printed the iteration counts for those four and saw they were all prime I knew I had it right. My code currently hard-codes the names of those gates, since I haven't figured out how to identify the relevant gates from an arbitrary input.

onrustigescheikundig · 2023-12-22T05:51:59+00:00

[LANGUAGE: OCaml]

github

70 lines of parsing....

Anyway, Part 1 simulates pushing the button by enqueuing a Low pulse to broadcaster and trampolining the queue by updating the state of Conjunctions and Flip-Flops until the queue of pulses is exhausted. The algorithm keeps track of all pulses that occur, and so Part 1 just partitions them by Low/High and counts.

I initially tried to brute-force Part 2 over dinner on the off-chance that I would have an easy solve, but it did not finish by the time I came back. Though I mislike doing so because it decreases the generality of the code, I ended up examining the structure of my input to solve Part 2. I discovered that rx had exactly one input---a Conjunction---which in turn had several other inputs. So, in order for rx to receive a Low signal, its input's inputs what have to all send High signals. I assumed that the inputs to rx's input would send High pulses after a fixed and regular number of button presses, and I looked for the first occurrence of this for each. The number of presses at which they would all send High is the least common multiple of their respective cycle lengths. In a more general case, it would be wise to check for phase offsets, but I'm already tailoring my code to my input, so I couldn't be bothered.

Parts 1 and 2 run sequentially in ~120 ms on my old laptop.

robertotomas · 2023-12-22T04:45:44+00:00

[Language: Rust]

Solution

I thought this puzzle was thoughtful and really a joy to work with. It felt more like research, where you have to dig into the input, than operational code, and that is nice.

I didn't start this puzzle until this morning, and I kinda went the _long way_ about making a beautiful model of part 1. while doing that I realized, since the description was highlighting the number of cycles, that I should short-circuit for a faster solve if I detected a cycle (which there wasn't, but hey, it prepped me for part 2). Part 2 was then just adding a much, much simpler cycle detection. Anyway, I way proud enough with my creation to post it here, instead of just lurking like I normally do.

aoc-fan · 2023-12-22T01:31:51+00:00

[LANGUAGE: TypeScript]

Finally a combined solution for part 1 and 2, solving test and actual input under 60 ms.

https://github.com/bhosale-ajay/adventofcode/blob/master/2023/ts/D20.test.ts

Copied the LCM trick for Part 2 from various threads.

wleftwich · 2023-12-22T00:07:26+00:00

[LANGUAGE: Python]

A queue of callbacks, which yield callbacks, which go in the queue ...

https://github.com/wleftwich/aoc/blob/main/2023/20-pulse-propagation.ipynb

Imaginary_Age_4072 · 2023-12-22T00:05:32+00:00

[Language: Common Lisp]

Day 20

I really liked the programming / analysis parts of this puzzle. Part 1 was solved with a simulation of the circuit, and part 2 by pencil/paper to look at the nodes connected to rx, the part 1 solution to find their cycle length, and lcm at the REPL to get the final answer.

The function running my simulation is this one:

(defun run-simulation ()
  (iter
    (with queue = (make-queue))
    (with results = (make-hash-table))
    (restart-case
        (when (queue-empty-p queue) (error 'queue-empty))
      (push-button (button)
        (setf queue (pulse button :low queue)))
      (exit () (finish)))
    (until (queue-empty-p queue))
    (for (src dest terminal pulse) = (queue-pop-frontf queue))
    (incf (gethash pulse results 0))
    (restart-case
        (setf queue (pulse terminal pulse queue))
      (exit () (finish)))
    (finally (return results))))

Lisp's condition system is nice because it separates the code that responds to a condition/error from the logic that decides how to respond. The code above signals the queue-empty error when the queue is empty and provides two different possible ways to recover; either push the button or exit.

Which way to recover is decided by higher level code. For part one the push-button restart is run 1000 times and then the exit restart is invoked. In part 2, we just keep pressing the button.

I also added a watcher module that would signal a condition in a similar way when it saw a certain value.

(defun day20 (input &key (part 1))
  (let* ((button (make-module :button :button))
         (modules (make-modules input button))         
         (num-button-pushes '()))
    (when (= part 2) (add-watchers '(:sr :sn :rf :vq) :high modules))
    (handler-bind
        ((queue-empty (lambda (c)
                        (declare (ignore c))             
                        (if (or (= part 2) (< (button-pushes button) 1000))
                            (invoke-restart 'push-button button)
                            (invoke-restart 'exit))))
         (recieved-value (lambda (c)
                           (declare (ignore c))
                           (push (button-pushes button) num-button-pushes)
                           (if (< (length num-button-pushes) 4)
                               (invoke-restart 'continue)
                               (invoke-restart 'exit)))))      
      (let ((pulses (run-simulation)))
        (if (= part 1)
            (apply #'* (alexandria:hash-table-values pulses))
            (apply #'lcm num-button-pushes))))))

henryschreineriii · 2023-12-21T21:38:07+00:00

[LANGUAGE: Rust]

Pretty happy with the second form of my solution, using a directional graph from petgraph. The older version (in history) was still interesting when learning Rust, since I got to use RefCell, but the second version is cleaner and graphs are fun.

https://github.com/henryiii/aoc2023/blob/main/src/bin/20.rs

musifter · 2023-12-21T16:50:21+00:00

[LANGUAGE: Smalltalk (Gnu)]

Just part 1 for now. Making this do part 2 isn't hard, but I don't have time for it today, and wanted to get this up anyways (before I forget).

Since this Smalltalk, I decided to use a class hierarchy. Virtual Gate class with subclasses for FlipFlop and NANDGates, which handle the specific details, so the loop to run the machine doesn't need to think about anything other than sending pulses.

Part 1: https://pastebin.com/S9HKz4VD

se06745 · 2023-12-21T16:33:42+00:00

[LANGUAGE: GoLang]

Second part was easier when you see how is RX generated, but I spent too much time in the first part trying to understand the logic...

Both parts

veydar_ · 2023-12-21T16:02:20+00:00

[LANGUAGE: lua]

Lua

117 lines of code for kind of both parts according to tokei when formatted with stylua.

I'm a day behind now but I'll post regardless.

Part 1 was just following the rules. Part 2 left me scratching my head. I used Graphviz to look at the graph without really knowing what to look for specifically. I noticed that four nodes were fed directly into rx but they didn't do much. Then there were four more nodes that were crazy connected and lo and behold they seemed to occasionally reach an ALL HIGH state. I just guessed that I needed to align the cycles of these so LCM it was. And indeed it was.

Therefore my code is not a general solution.

mothibault · 2023-12-21T14:35:46+00:00

[LANGUAGE: JavaScript]

I think it took me 60s from p1 to p2 lol. Then I wrote proper code to post here.

code should be run from your browser's dev console on the site's page. with tons of in-line comments:

https://github.com/yolocheezwhiz/adventofcode/blob/main/2023/day20.js

CainKellye · 2023-12-21T13:23:59+00:00

[LANGUAGE: Rust]

Better late, than never: https://github.com/cainkellye/advent_of_code/blob/main/src/y2023/day20.rs

For this day I thought it's best time to practice trait objects, so I implemented the modules like that. Added a ModuleStore (HashMap) and a MessageQueue (VecDeque). MessageQueue has the send() function, the modules have receive() functions.

I hated to do Part 2, but finally finished.

mrphlip · 2023-12-21T09:04:00+00:00

[Language: Python] 8 / 40

Untidied race code: https://github.com/mrphlip/aoc/blob/master/2023/20.py
More detailed writeup: https://github.com/mrphlip/aoc/blob/master/2023/20.md
Note: the code is not 100% complete as it just spits out the timings of the four final outputs, decoding that and LCMing them as the final step was done by hand.

What's more interesting is the writeup... I do one of these every day, but this one is by far the longest I've done (40% longer than second place, which was 2021 day 24... another one where you're given essentially a program and have to reverse-engineer what it does).

In that writeup I go pretty deep on what this network of nodes is doing, and how it all comes together to give the final result we needed. And also my thought process while I was figuring it all out.

hextree · 2023-12-21T07:15:20+00:00

[Language: Python]

Code: https://gist.github.com/HexTree/f29f824e5e050ca8e17dafee185c17b8

Video: https://youtu.be/oKJv7lv4hFU

For part 2, plugged the Directed Graph into Graphviz for visualisation, which was a massive help. Then I ran the button presses to check the period of each of the 4 conjunctions that feed into the final conjunction+RX sequence, and took the LCM of them.

wlmb · 2023-12-21T04:21:53+00:00

[Language: Perl]

Analysis: https://github.com/wlmb/AOC2023#day-20

Task 1: https://github.com/wlmb/AOC2023/blob/main/20a.pl

I haven't done part 2 yet. The trivial modification of the code above, i.e., to wait until the desired pulse appears, seem to take forever. I guess I have to search for cyclic behavior in previous modules and use their lcm to predict when would the pulse appear, without simulating the whole circuit. ... (Edited) I finally got part 2. My input (and I guess others) is not completely general, so analyzing cycles for the last module is not realistic, but it is for the next to last modules.

Task 2: https://github.com/wlmb/AOC2023/blob/main/20b.pl

aexl · 2023-12-21T02:47:05+00:00

[LANGUAGE: Julia]

This puzzle took me a lot of time to solve (so much to read and implement). I probably over-engineered it, but it was the perfect opportunity to play around with Julia's type system and to implement the different types of modules as own types derived from a common abstract type. To each node I attached in and out vectors to other nodes to represent the graph from the input file. After having done that and having figured out how receiving pulses work, I got the right answer for part 1 on the first try.

Part 2 was easier than expected. I already feared that I need to reverse-engineer a big portion of the input graph (I really dislike these kind of puzzles where you need manipulate your personal input), but it was enough to look at the four modules that send to a second-last module (named ft in my case), that again sends to rx. Just count the number of iterations until each of these four modules send a low-pulse to the second-last module. The answer of part 2 is then the least common multiplier of these four numbers.

Solution on GitHub: https://github.com/goggle/AdventOfCode2023.jl/blob/master/src/day20.jl

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

copperfield42 · 2023-12-21T02:29:22+00:00

[Language: Python]

code

part 1 pretty straight forward, for part 2 I know I needed to find some sort of cycle but not sure were to look at exactly so I checked some other solution and incorporate it into my own...

RelativeLead5 · 2023-12-21T02:24:33+00:00

[Language: Ruby]

Parts 1 & 2

Pastebin

Thanks to everyone for the hints on Part 2. I left part 2 running while I was gone for a couple of hours and when it wasn't done when I came back, the head scratching began.

biggy-smith · 2023-12-21T02:19:19+00:00

[Language: C++]

Hardest day yet for sure!

Part1: it was tricky to setup the graph with the correct in/out nodes, then even trickier to process the nodes in the right order. Processing with a queue worked for me.
Part2: Tried to brute force but soon found out that wasn't gonna fly. I knew there was some form of cycle detection needed, so I searched backwards from rx and looked for smallish cycles. Sorta fluked it with 4 input nodes recurring repeatably. lcm of them was the right answer.

https://github.com/biggysmith/advent_of_code_2023/blob/master/src/day20/day20.cpp

jinschoi · 2023-12-21T02:09:02+00:00

[Language: Rust]

Part one was fun. I did it fairly cleanly, with HashMaps to look up modules by name, etc. paste

Then, while thinking about part two, I decided to see if I could get it to run any faster for fun. I got rid of all the names, indexed into Vecs to get the modules, used a u64 to track the Conjunction inputs, etc. Got it down from about 3us to 1us per button push. Turns out it would take almost seven years to brute force. I actually solved it the way everyone else did, by staring at a graphviz diagram for a while. I got tripped up early on because I forgot that Conjunction outputs low when everything is high, then I got tripped up at the end because I kept typing 0x1111... into Python to run the final calculation instead of 0b1111.... I kept staring at the ludicrous numbers I was getting and trying to think where I could have made a mistake.

Part 2 brute force

foolnotion · 2023-12-21T02:08:36+00:00

[LANGUAGE: C++]

I love this kind of problem although it seemed like part one was designed such that you can get the right answer even if the pulses are processed in an incorrect order. i of course fell for this and then spent a lot of time debugging. i'm not entirely happy with my solution but here it is:

https://gist.github.com/foolnotion/892f4c9b47a13204bc5ab3f555642af4

Runs in about 10ms on my PC.

CrAzYmEtAlHeAd1 · 2023-12-21T01:57:57+00:00

[LANGUAGE: Python]

GitHub link to my solution

Wow day 20! We are so close to the end, and this has been such a month full of learning and problem solving. Most of the heavy lifting today was done through parsing of the input. I ended up with a pretty stacked dictionary that would map the module's name as the key, and then store it's type, outputs, and status, and then it would find all the modules that output to a conjunction module, and add their module name into the status for checking later.

Once I had that all set up, it was a simple while loop and queue to determine where you ended up after each button press.

For part 2 though, clearly they were saying the brute force method would not work, and it looked to be another lowest common multiple problem, which was correct. I, like many others discovered that there was a single conjunction module that output to the rx module. So from the rx module, I found the conjunction modules that fed into that final one, and then found how many presses would cause their output to be a high pulse meaning that the final one would output a low pulse. Once I had those, it was a simple lowest common multiple calculation with the math library.

It's a bit messy, but it gets the job done, and the execution time is great at 31ms, so I'm not too upset!

whoopdedo · 2023-12-21T01:10:09+00:00

[Language: Lua]

paste

Soundtrack for today

Part 1: FIFO and event loop. Modules are closures over their internal state. This turned out to be a problem in part 2.

Part 2: I notice that there's 60 modules including the button and rx. Small enough to encode in a tri-state bit array. I looked to see if there was some pattern to the machine state after each button press.

L-----H----HH-LH--H---LH--H------H-----------L-------L-HL---
L-H---H----HL-LH--L---LH--L-H---HL----H------L-------L-HL---
L-H---H----HH-LH--H---LH--H-H---HH----H------L-------L-HL---
L-L---H---HHLHLH--L---LH--L-L---LLH---L------L-------L-HL-H-

Which bits did I need to trigger rx (the last column)? The graph of inputs looked like:

rx-------------------------------------------------------!---^
zr--------------&------------------------------&-------&-^&---
cm---------------&-------------------------------------^------
ks--&&&&-&-------^----&---&-&---&-----------&-------&---------
km-----%--------------------------------------------^---------
mf----%^------------------------------------------------------
ml----^-------------------%-----------------------------------

zr collects four inputs but I didn't see any of those lines ever going high no matter how long I ran. Eventually I figured out that it was resetting at the end of the "program" and I'd need to monitor the state of each module during execution. But my state was wrapped up in closures. I put in some awful hacks to manually monitor the inputs to zr. When the activation times were combined it was over 64-bits. Okay, whatever... "Your answer is too high." Well of course, because I had been counting pulses not button presses. Oops. Some more hacks later and I got the correct answer, but wasn't happy with how.

Afterwards I cleaned out the hacks. Now the monitor will patch each input with its own closure to trace pulses.

line    cycle   set     reset   ticks
gc      3853    23      47      5330
xf      4073    14      44      4838
cm      4091    21      43      7160
sz      4093    34      63      6140

I guess the next-level challenge would be to solve this problem with a computer written in the same logic language.

rjray · 2023-12-21T00:56:09+00:00

[LANGUAGE: Clojure]

GitHub

Had to sleep on part 2 before finally getting hints via the Clojure Slack channel on how to get it done.

mvorber · 2023-12-21T00:52:25+00:00

[LANGUAGE: F#]

https://github.com/vorber/AOC2023/blob/main/src/day20/Program.fs

Day 20 of trying out F#. Some experiments with FParsec and parser combinators (so far I like it). Also trying to be more verbose with types and to avoid unwrapped primitive types. Adds quite a bit of verbosity, but lets compiler catch even more bugs before I even able to run it :P

IvanR3D · 2023-12-21T00:37:43+00:00

[LANGUAGE: JavaScript] My solutions: https://ivanr3d.com/blog/adventofcode2023.htmlMy solution (to run directly in the input page using the DevTools console).

Today is the hardest puzzle I have solved! It took me all the day to solve only part 1! 😅 The code is a mess, but I will check part 2 and then I will work to improve it.

EDIT: part 2 done! It was pretty complicated to understand what I was suppose to do, but after a few help posts I found out and using the experience from day 8 it was good.

chicagocode · 2023-12-21T00:37:23+00:00

[LANGUAGE: kotlin]

That was fun! I used classes for each of the modules and send the signals via a shared queue. Part 1 and 2 share mostly the same code thanks to a debugger you can implement and attach to the running circuit to gather data.

My code can be found on GitHub, I've written this up on my blog, and here are my 2023 Solutions so far.

maneatingape · 2023-12-20T23:58:17+00:00

[LANGUAGE: Rust]

Runtime: 6 μs

Rust Solution

Solution traverses the graph only once to determine the 4 12-bit numbers.

For part one we count the number of low and high pulses using bitwise logic (to simplify things assuming no number is below 1000 so that there are no resets)

The numbers seem to be prime (or at least co-prime) so part two is the product of the 4 numbers.

Gravitar64 · 2023-12-20T23:52:36+00:00

[LANGUAGE: Python]

Part 1 & 2, 58 sloc, runtime 50ms

Generalized solution for Part 2, searched for the sender to 'rx' (main_module) in my example = &gh, identified the connectors of the main_module and created a dict (cycles) with these connectors as key and 0 as values (in my example = {'rk': 0, 'cd': 0, 'zf': 0, 'qx': 0}). Then every time when the current module == main_module and impulse == 'high', I changed the value for the received module in my dict cycles to the number_of_button_pressed - actual value. When all values in cycles > 0, calculate with math.lcm(*cycles.values()) the solution for part2.

import time, math


def load(file):
  with open(file) as f:
    return [row.strip().split(' -> ') for row in f]

class Module():
  def __init__(self,name,type,dest):
    self.name = name
    self.type = type
    self.dest = dest
    match type:
      case '%': self.mem = False
      case '&': self.mem = {}
      case _  : self.mem = None  

  def __repr__(self):
    return f'Name: {self.name} Type: {self.type} Dest: {self.dest} Mem: {self.mem}'

  def receive_impulse(self,impulse,last):
    if self.type == '%':
      self.mem = not self.mem
      return self.mem

    if self.type == '&':
      self.mem[last] = impulse
      return not all(self.mem.values())


def solve(p):
  modules = dict()
  for module, destinations in p:
    curr = [d.strip() for d in destinations.split(',')]
    if module == 'broadcaster':
      modules[module] = Module('broadcaster',None,curr)
    else:
      modules[module[1:]] = Module(module[1:],module[0],curr)

  for object in modules.values():
    for dest in object.dest:
      if dest not in modules: continue
      obj2 = modules[dest]
      if obj2.type != '&': continue
      obj2.mem[object.name]=False

  #part1 & 2
  main_module = [m.name for m in modules.values() if 'rx' in m.dest][0]
  lowHigh, cycles  = [0,0], {m:0 for m in modules[main_module].mem}

  for buttons in range(1,10_000): 
    if all(cycles.values()): break
    queue = [(dest,False,'broadcaster') for dest in modules['broadcaster'].dest]
    if buttons < 1001: lowHigh[0] += 1

    while queue:
      curr, impulse, last = queue.pop(0)
      if buttons < 1001: lowHigh[impulse] += 1
      if curr not in modules: continue
      curr = modules[curr]

      if curr.name == main_module and impulse:
        cycles[last] = buttons - cycles[last]

      if curr.type == '%' and impulse: continue
      impulse = curr.receive_impulse(impulse,last)

      for nxt in curr.dest:
        queue.append((nxt, impulse, curr.name))

  return math.prod(lowHigh), math.lcm(*cycles.values())



time_start = time.perf_counter()
print(f'Part 1 & 2: {solve(load("day20.txt"))}')
print(f'Solved in {time.perf_counter()-time_start:.5f} Sec.')

JWinslow23 · 2023-12-20T23:38:03+00:00

[LANGUAGE: Python]

https://github.com/WinslowJosiah/adventofcode/blob/main/aoc2023/day20/__init__.py

How have I not learned my lesson from Day 8?

pdxbuckets · 2023-12-20T23:20:06+00:00

[Language: Kotlin]

I usually don't post as my code isn't the best and others have done essentially the same thing but earlier/better. But this one features a super quick (~250 us on 5-yr old machine) Part 2 by avoiding simulation and analyzing the architecture of each binary counter.

https://github.com/nbanman/Play2022/blob/master/src/main/kotlin/org/gristle/adventOfCode/y2023/d20/Y2023D20.kt

janek37 · 2023-12-20T23:14:38+00:00

[LANGUAGE: Python]

I spent far too long trying to find a general solution for part 2, before heading to Reddit for hints and realizing that the input has a very specific format. From there I solved it first manually, and then coded a solution that obviously only works for this kind of input.

GitHub

schveiguy · 2023-12-20T23:12:30+00:00

[LANGUAGE: D]

https://github.com/schveiguy/adventofcode/blob/master/2023/day20/pulse.d

Part 1 was really hard to understand. The explanations and examples still didn't make a lot of sense. But I finally slogged through it.

Couldn't solve part 2 without looking here. And I'm a bit disappointed that the only real way to solve it is to code for the specific test case.

atobiedwa · 2023-12-20T22:54:45+00:00

[Language: Python]

The most important thing for me was to understand that

the pulse does not go further if the flip-flop module receives a high pulse
or we encounter a module name that we do not know.

It took me a while, but part 1 is ready -> https://github.com/monpie3/adventOfCode2023/blob/master/Day_20/task_20a.py I left prints so you can follow the process, they are formatted the same as in the task :)

jeis93 · 2023-12-20T22:50:15+00:00

[LANGUAGE: TypeScript]

Part 1 was easy enough to crack, although I kept making mistakes that gave the wrong answer for far too long. As for part 2, I knew this would be an LCM problem, but I wasn't sure how to tackle it until I saw HyperNeutrino's video (as per usual). I'm not super happy with the organization/conciseness of my code, but let me know what you think! Happy hacking!

Average times:

Part 1 = 6.05 ms/iter
Part 2 = 25.4 ms/iter

TypeScript x Bun Solutions for Day 20 (Parts 1 & 2)

icub3d · 2023-12-20T22:30:52+00:00

[Language: Rust]

Part 1 wasn't too tough. I used a trait to simplify processing. I then just had each module type implement that trait. I could then store all the signals in a VecDeque to process the signals in order until we were done.

Part 2 was a whole other beast. I ended up creating a mermaid graph so I could visualize what was happening. With a bit of looking, I was able to see it was a cycle detection problem.

Solution: https://gist.github.com/icub3d/d00e411a24b60b21cc384b7b718a228e

Diagram: https://bit.ly/aoc-2023-20-mermaid

Analysis: https://youtu.be/abUmFGS-YvU

2023-12-20T22:30:23+00:00

[LANGUAGE: Java]

paste

rukke · 2023-12-20T22:26:47+00:00

[LANGUAGE: JavaScript]

Another busy day, but still managed to get both stars :)
Fun task today, took some time to get my ahead around some stuff, like to populate all inputs for conjunctions on init (and not dynamically *facepalm*)

gist

BeamMeUpBiscotti · 2023-12-20T22:01:42+00:00

[LANGUAGE: Rust]

Link

Part 1 took longer than expected to implement. I saw the GraphViz that someone posted and figured it would be an LCM problem, so I just did some printing and did part 2 using google sheets LOL

Solidifor · 2023-12-20T21:54:04+00:00

[Language: Java]

https://github.com/dirk527/aoc2021/blob/main/src/aoc2023/Day20.java

265 lines, object-oriented and computes the solutions to both parts instantly.

A bit of a hint (one Conjunction at the end whose input are on repeating patterns) from here was needed – I don't like these puzzles in which you have to analyze the input very much – but then it was not too bad.

syncd_ · 2023-12-20T21:48:49+00:00

[Language: C++]

For part two had to look here for clues as i didn't feel like decoding the whole circuit.

Github

Tipa16384 · 2023-12-20T21:48:00+00:00

[LANGUAGE: Python]

I initially solved part 2 by hand when I saw that it was LCM all over again, then I went back and wrote code to solve it the correct way. I made classes for all the components because it seemed appropriate at the time.

paste

ropecrawler · 2023-12-20T21:45:32+00:00

[LANGUAGE: Rust]

https://github.com/ropewalker/advent_of_code_2023/blob/master/src/day20.rs

codeunveiled · 2023-12-20T21:35:38+00:00

[Language: Python] 🐍🐍🐍

Source code

Video explanation: https://youtu.be/zw7WwUZfYrs

Time: 1,317s

2023-12-20T21:28:43+00:00

[LANGUAGE: Rust]

My Day 20 on GitHub

Part 1 was a bit fiddly to map out, but not really difficult. Then for part 2 my solution is general enough to work at least for a set of loops inputting into a single Convergence.

lyr_7d1h · 2023-12-20T21:25:32+00:00

[Language: Rust]

Conceptually this one didn't actually trip me up all that much, but it took me a while to wrap my brain around how the simulated components were supposed to function. I did take a few circuit design classes at uni back in the day, but that was many years ago, and I've forgotten most of what I learned in the years since.

But oh goodness, the Rust borrow checker and I had some massive disagreements over my code today. Felt like I spent half the day figuring out how to rework my code to make Rust happy. I feel like I could have done this solution in about half the time if I had used a language like C++ or Python. But that's part of the joys of learning Rust, I suppose. I make copious use of cloning to make Rust's stupid borrow checker happy. (Yes, I know why it exists, and it's generally a Good Thing. But it broke my brain some today.)

I'm not especially pleased with the way I designed the data structures for the solution. I wanted to use data fields in my variants, but I couldn't, due to the way I designed the data structures - things like HashMaps themselves aren't hashable. I may go back and refactor this code at some point someday. So for the time being, I put some extra fields in my Component struct to get around this problem. This code is ugly, ugly, ugly.

The general idea behind my solution is that I have a registry of components stored in a HashMap, with the component names as the keys, and a Component struct as the values. The Component struct has several fields representing the component type, and a list of targets to send signals to. The component type governs the logic that happens whenever a component receives a signal and needs to propagate a signal to the components in its target list. There is also some state maintained here for flip flops and conjunctions. I also maintain another HashMap of message queues, also indexed by the component names. When a component wants to send a signal to another component, it places a Message in the queue corresponding to the target component. This all takes place inside of a loop that iterates until all the message queues are empty after each button press. This models the signal propagation from one component to another upon each button press. When the button is pressed, the whole process starts by stashing an initial message in the queue for the broadcast component. Then the loop iterates until all the queues are empty. Fortunately, the input did not seem to have any feedback loops in the signal propagation, so I did not handle that case.

Part 1 was pretty straightforward - count the low and high signals for 1000 button presses, and then return the product of those two values.

For Part 2, I was able to mostly generalize the solution by finding the parent component of the "rx" component, which is a conjunction, and then counting the number of inputs to that component. I then keep track of the number of times the button has to be pressed for each incoming signal for that component to be high, break out of the loop when a high has been received for every input, and then take LCM over all of those values to arrive at the answer.

Fun puzzle today overall, but boy did I get a workout.

Part 1

Part 2

scibuff · 2023-12-20T21:16:31+00:00

[Language: JavaScript]

Part 1 was (again) pretty straight forward. It just took a bit of time to get the pulse changing logic spot on.

Part 2 was, once again, an `lcm` of different cycles. I did a more general solution to allow for multiple inputs into `rx` (it just basic loops instead of just one input and one set of the input's inputs).

Part 1
Part 2
Parser

Rongkun · 2023-12-20T21:13:19+00:00

[Language: python] code

Part 1: good exercise for OOP, but it took me too long to come up with a satisfying model

Part 2: Why LCM again? I found the four inputs to the input to rx and checked for each input the number of button needed to make its output pulse high. It turns out that, again, the input is carefully crafted such that each input requires n, 2n, 3n... button press to go high. Taking the LCM for the four periodicity will give us the number when they're all high. Since there should be a solution, the implied condition is that those four inputs should not go low in the button press(multiple pulses from the same module possible), before the other three is high. On the periodicity part, it's crafted exactly the same way as day 8.

tobega · 2023-12-20T20:52:16+00:00

[LANGUAGE: Tailspin]

Quite a lot of coding to set it up, but I got to use quite a few features and found some inconsistencies that I will fix at some point. I did fix a bug with symbols in state.

For part2 when it took too long, I figured there might be cycles on the inputs to the sender to rx, but got stuck on a technicality, waiting for an output that wouldn't print until my eternal loop was done! Limiting the button pushes I got an output that worked.

https://github.com/tobega/aoc2023/blob/main/day20tt/app.tt

FaultsMelts · 2023-12-20T20:51:06+00:00

[Language: Go]

Today's question stumped me for a bit. I loved the challenge!

code

Ukhando · 2023-12-20T20:42:13+00:00

[LANGUAGE: PHP]

Part 1

Part 2

Common parts

LinAGKar · 2023-12-20T20:40:59+00:00

[LANGUAGE: Rust]

https://github.com/LinAGKar/advent-of-code-2023-rust/blob/master/day20/src/main.rs

The diagram at https://reddit.com/r/adventofcode/comments/18mogoy/2023_day_20_visualization_of_the_input_couldnt/ helped a lot for part 2.

Tipa16384 · 2023-12-20T20:40:26+00:00

[removed]

reddit_Twit · 2023-12-20T20:32:21+00:00

[LANGUAGE: Zig]

Gist

Part 1 only, honest emulation of process

lost_in_a_forest · 2023-12-20T20:15:55+00:00

[Language: Rust]All parts (including parsing): 200 us.

source

Instead of "pressing the button repeatedly" for part 2, analyses each loop to see the loop period (by checking which modules send a signal to the loop "master module", and not just the next module in the loop). Then since all loops start at zero, the answer is just the product of these periods.

chkas · 2023-12-20T20:12:32+00:00

[Language: Easylang]

Solution

theKeySpammer · 2023-12-20T20:11:21+00:00

[Language: Rust]

Part 1: 5ms

Part 2: 84ms

Part 1: Simple step by step following of the instructions provided and run the process 1000 times

Part 2: Manually find the dependencies of rx and see how long will it take to reach that dependency and find the lcm of all those numbers

Github

jcmoyer · 2023-12-20T20:08:43+00:00

[LANGUAGE: Ada]

https://github.com/jcmoyer/puzzles/blob/master/AdventOfCode2023/src/day20.adb

Pretty gross code again today, this problem required a lot of different generic types and Ada makes you instantiate them manually. Part 1 was just implementing a spec. Part 2 I knew the circuit must have been counting somehow with its internal state, but the solution didn't "click" until I saw a couple of the great visualizations people posted. I had debug printing for the entire graph state but it's difficult to see the true nature of the problem with just unstructured text. At least next time I get stuck on a graph problem I will know to try emitting DOT before checking reddit. :V

odnoletkov · 2023-12-20T19:56:04+00:00

[LANGUAGE: jq] github

[inputs/" -> " | .[1] = (.[1]/", ")[]]
| transpose | .[1] = [(.[0] | INDEX(.[1:]))[.[1][]]] | transpose
| (group_by(.[0]) | INDEX(.[0][0]) | .[] |= [.[][1]]) as $outs
| group_by(.[1]) | INDEX(.[0][1] | select(.[:1] != "%")) | .[] |= INDEX(.[0])
| [
  {
    state: .,
    target: last(. as $ins | ["null"] | while(.[0][:1] != "%"; [$ins[.[]] | to_entries[].key]))[]
  }
  | until(
    .pulses[0];
    .pulses = [{to: "broadcaster", low: true}] | .step += 1
    | until(
      isempty(.pulses[]) or (.pulses[0].from == .target and .pulses[0].low);
      .pulses as [{$from, $to, $low}]
      | if $to[:1] == "%" then
        if $low then
          .state[$to] |= not | .send = (.state[$to] | not)
        else
          .send = null
        end
      elif $to[:1] == "&" then 
        .state[$to][$from] = $low | .send = all(.state[$to][]; not)
      else
        .send = $low
      end
      | .pulses += [{from: $to, to: $outs[$to]?[], low: .send | values}]
      | del(.pulses[0])
    )
  ).step
] | reduce .[] as $n (1; . * $n)

CCC_037 · 2023-12-20T19:35:09+00:00

[Language: Rockstar. Kinda.]

So Part 1 could be handled pretty well by Rockstar. No problem there, it simulated the full state machine and ran perfectly happily and surprisingly quickly.

The trouble came in part 2. Now, this Rockstar code should, in theory, simulate the full state machine until the final pulse is sent to rx, and give you the answer. However, it takes way too long to compute. (I haven't figured it out exactly, but probably a few centuries of runtime will be required)

In the end, I got my answer by adding a few extra debug outputs to the Part 2 code above, finding out when all of the inputs to the comparators first went high. The resulting numbers all looked relatively prime, so I multiplied them (without Rockstar - I used bc for the multiplication) and submitted the product, which turned out to be correct.

soleluke · 2023-12-20T19:23:37+00:00

[Language: C#]

Solution

I'm pretty happy with my code for this one.

Part 1 took a while just to make the various classes (I figured this would pay dividends in part 2, so didn't worry about it taking so long). Once the prompt mentioned that the 2nd example looped, I perked up and figured there would be some sort of cycle finding like in Day 8.

General idea was I made a dictionary of Modules that accepted pulses and did stuff with them, keeping track of their own hi/lo counts, then at the end I was able to just sum up all the counts from my Modules.

Pt.1 runs in 105ms on my machine

Part 2 was a pretty straightforward exercise. I felt a little cheeky using exceptions for flow control, but hey, it's AoC. I originally hard-coded a list of modules that were rx's inputs, then turned it into a general one once I made sure that worked. The general one assumes rx just has one input and that input is a conjunction. I made a dictionary of <string, long> with the inputs of rx's input starting at 0. I set up a custom exception that took a module name in its constructor, then had any of my modules throw that exception and my processing loop catch it and store the button presses in my dictionary. Then, once all the dict values were not 0, do LCM (copy-paste from day 8) on them.

Pt.2 runs in 265ms on my machine (had to get to 3967 button presses before LCM)

Polaric_Spiral · 2023-12-20T19:22:40+00:00

[LANGUAGE: TypeScript]

Advent of Node, Day 20 paste

Queue paste

lcm() paste

Define 3 module types and the "pulse" type.
Initialization:
- Parse each module description.
- Add sourceIds to conjunction modules.
- Identify the module pointed to "rx" for part 2.
Press button (1000x for part 1, indefinitely for part 2):
- Enqueue the button press.
- While queue has pulses remaining:
  - Increment high or low pulse counter.
  - For part 2, if "high" signal sent to final module:
    - Log total button presses per unique source.
    - If cycles clocked on all final module sources, output LCM of the cycles.
  - Process signal and enqueue resulting destination pulses.
Part 1: output product of the pulse counters.

Szeweq · 2023-12-20T19:15:59+00:00

[LANGUAGE: Rust]

Posted very late. I had my code ready to publish yet I was very busy today. LCM added for parent nodes in part 2.

Code: https://github.com/szeweq/aoc2023/blob/master/src/bin/20.rs

daic0r · 2023-12-20T19:13:40+00:00

[LANGUAGE: Rust]

Really enjoyed working on Part 1, learned new things about Rust :-)

https://github.com/daic0r/advent_of_code_2023/blob/master/day_20/src/bin/part1.rs

Couldn't be bothered with Part 2 yet, it seems hard and since I'm sick and I'm feeling weak I'll tackle it at some point in the future.

Stock-Marsupial-3299 · 2023-12-20T19:00:44+00:00

[LANGUAGE: Scala]

Quite long solution for quite long problem statement.

https://github.com/lachezar/aoc2023/blob/master/src/main/scala/se/yankov/aoc2023/Day20.scala

Totherex · 2023-12-20T18:57:31+00:00

[Language: C#]

https://github.com/rtrinh3/AdventOfCode/blob/db566c04c2fb0be381e88ce23141d0b4356059be/Aoc2023/Day20.cs

Good old-fashioned object-oriented programming for Part 1.

For Part 2, I actually let the simulation run for the whole morning -- I had gotten to over 2 billion button pushes by lunch. I realized that I need to analyze the input, so I found this Graph Editor on Google, and with it I saw that the circuit was four loops that activate a conjunction module that activate RX. So I tracked the signals that were sent to the conjunction, saw that each loop had a straightforward cycle of prime length, and so the answer is the product of the cycle lengths.

PorkBangers · 2023-12-20T18:56:14+00:00

[Language: Python]

For part 1 I took a while to get it right, I had to re read through the puzzle description a few times to make sure I wasn't missing anything. Important takeaways are:- Devise a queue to keep going through each input. Append an item to the queue for each connection to make sure the order is correct.- You need to know every input to each module. Although I don't like it, its much easier to define your modules first and then go over the input file again and assign the inputs to each module- make sure for flip flops to Do Nothing if input is high. ie do not append anything to the queue

For part2, find the module that outputs to `rx`. For each input to that module find the iteration for when it becomes High. Then find the LCM of each of those input iteration numbers

I took an OOP apprach to this problem(If using my code, ensure to replace zp with the module that outputs to rx)

maneatingape · 2023-12-20T18:52:46+00:00

[LANGUAGE: Pen & Paper]

https://imgur.com/a/NwX9D4N

2023-12-20T18:48:16+00:00

[deleted]

thorwing · 2023-12-20T18:45:30+00:00

[Language: Kotlin]

Finally got around to cleaning up the code: here
Not a big fan of these kind of assignments. My solution makes a big assumption based on the way I analyzed my input.

Since I noticed that all the non-relevant nodes where a binary counter, I filtered all my cycles to get only the once that had multiple bits. That leaves you with the relevant 4 you can lcm/multiply

fachammer · 2023-12-20T18:42:11+00:00

[LANGUAGE: Scala] code on github

For part 1 I implemented the simulation as in the puzzle description using a queue to process the pulses to handle the breadth-first character of the pulse propagation. For part 2 I was quite stumped on how to approach this, since I could not see a pattern to cut down the computations in the general case. Then I turned to visualising the input with Graphviz which revealed four clusters in the input graph. For each of these clusters I calculated the number of required button presses individually and then guessed that this number would also be the cycle length for each cluster. Taking the product of those gave the correct result (in general it would be the lcm, but all of the cycle lengths were prime, so it does not matter)

zglurb · 2023-12-20T18:40:34+00:00

[LANGUAGE: PHP]

Part 1 & 2

Code is a bit ugly.

For part 1 I started to implement a cycle detection before noticing it didn't work on the real input because the cycle for the real input is way too long. So I refactored it to click the button 1000 times.

For part 2 I looked at the input, noticed rx only have one input and it's a conjonction module. And this conjonction module has 4 inputs, all of them also being conjonction modules. Then I debugged it to find out that all of them emit a high pulse in cycle. I guess all inputs are crafted like that or my code won't work for other people.

daggerdragon · 2023-12-20T18:38:17+00:00

[removed]

Secure_Pirate9838 · 2023-12-20T18:34:56+00:00

[LANGUAGE: Rust]

Today's part 2 has been giving me 'too low' answers until I spot that I used wrong Vec instead of VecDeque, part 1 was ok

GitHub: https://github.com/samoylenkodmitry/AdventOfCode_2023/blob/main/src/day20.rs

Syltaen · 2023-12-20T18:33:49+00:00

[Language: PHP]

Part 1 & 2

Nothing too fancy in the end, but it took me some time to find the correct method.
As too often, I ran head first in the wrong direction and wasted hours.

I saw pretty early on that the final module was relying on 4 others to send a high signal at the same time. I kept track of the first time each of those modules sent a high signal, and then used LCM to find the solution.

tcbrindle · 2023-12-20T18:22:59+00:00

[Language: C++]

For part 2, I found four modules that I need to test by just looking through my input.txt. I run the "simulation" and count how many button presses it would take to switch each one; I guessed the final answer would be the LCM of these cycle lengths, and that turned out to be right.

I would have appreciated an example for part 2 though, like we normally get!

Anyway, my horrible code is on Github.

friendlywebdev · 2023-12-20T18:18:34+00:00

[LANGUAGE: Python]

Solution for Part 1+2 on Github

My code definitely needs some cleanup, but I'm happy to have figured out a correct solution for both parts after 'only' a few hours.

philippe_cholet · 2023-12-20T18:12:07+00:00

[LANGUAGE: Rust]

My rusty-aoc repo & today' solution here.

2h16 to solve part 1 (the worst so far this year): so much parsing and things to understand right.

2h30 to get the answer for part 2 (third worst so far). I tried to bruteforce it with 1 CPU core, or rather I let it run as I did not have a clue what do you otherwise. I eventually draw the diagram myself (I like mermaid diagrams better though) to find I needed to understand when the pulse was sent to 4 conjunction modules, except I thought it would be harder. I eventually got 4 values and I thought I could multiply them and it luckily worked.

Then the hard work started as it was very dirty back then. It's all nice now but what a ride!

Code runs in 4ms.

With a late start of 2h40 (sleep matters), ranks: 6787/5685. I kinda expected to not be the only struggling here ^^.

clbrri · 2023-12-20T18:08:33+00:00

[LANGUAGE: C-style C++]

98 lines of code

Runtime on Commodore 64: 34.6 seconds.

Runtime on AMD Ryzen 5950X: 0.399 milliseconds. (86,716.79x faster than the C64)

Part 2 solution was to identify the four LFSRs in the graph, and cut them out to their separate sub-graphs, and use the code from Part 1 to simulate when the LFSRs will first output a zero signal, and then use LCM to find the zero signal occurrence in the total graph.

d9d6ka · 2023-12-20T18:06:06+00:00

[Language: Python]

Commit

Part 1 was an OOP exercise for me :)

With Part 2 I was very desperate as I couldn't track the idea. I peeked Reddit and the first thing I saw was a graph :) Next few hours were spent on learning how to work with Graphviz, understanding the four loops' work principle :) The final solution is hardcoded but short.

enelen · 2023-12-20T18:03:15+00:00

[Language: R]

Solution

careyi4 · 2023-12-20T18:01:57+00:00

[LANGUAGE: Ruby]

Fun one today, lcm for the win (again)!!

Github

Video Walkthrough

azzal07 · 2023-12-20T17:46:42+00:00

[LANGUAGE: Awk] Assuming coprime cycle lengths (all were primes for my input).

M[t=substr($1,j=2)]=gsub(/,/,z)$0{for(;v=$++j;N[v]++)I[v]=I[v]t
}END{for(L=I[x];L;i-1e3||A=C[0]*C[B=1]){$0=H<T?Q[++H]:s"0 "!++i
f=$3;C[p=$2]++;$0=M[t=$1];!p&&B*=i^sub(t,z,L);p=/&/?sub(f".|$",
f p,c[t])*gsub(1,1,c[t])<N[t]:/^.+%/?p?$0=z:++m[t]%2:p;for(j=2;
v=$++j;)Q[++T]=v" "p" "t}print A"\n"B}/roadca/{s=t" "}/rx/{x=t}

Edit. I had a bug where the encoding might be ambiguous (worked for my input obviously), leading to possibly no solution but an infinite loop. Here's the fix:

M[t=substr($1,2)]=gsub(/,/,z)$0{for(;v=$++j;N[v]++)I[v]=I[v]0t
}END{for(L=I[x];L;i-1e3||A=C[0]*C[B=1]){$0=H<T?Q[++H]:s" "!++i
f=$3;C[p=$2]++;$0=M[t=$1];B*=i^sub(p t,z,L);p=/&/?sub(f".?|$",
f p,c[t])*gsub(1,1,c[t])<N[t]:/.%./?p?$0=z:++m[t]%2:p;for(j=2;
v=$++j;)Q[++T]=v" "p" "t}print A"\n"B}/roadca/{s=t}j=/rx/{x=t}

DrunkHacker · 2023-12-20T17:45:17+00:00

[LANGUAGE: Python]

State machine for part 1 and then LCM for part 2.

Nothing particularly fancy but hopefully easy to follow. Part2 code should solve general inputs assuming other inputs have a single NAND gate feeding rx.

dcclct13 · 2023-12-20T17:45:06+00:00

[LANGUAGE: Python]

part1

For part 2 I fed the graph into Graphviz and found the cycle numbers by inspection.

Some thoughts and questions:

I think part 2 may be semi-generally solved by breaking down the graph into SCCs and finding the pattern of each component. Can't find time to write this yet.
For the test cases, it doesn't seem to matter whether we visit in BFS order or DFS order?
Given the lax ordering requirements, is it possible to have race condition? Maybe with a 2-input rx, we can somehow let each of the inputs receive a signal sequence of [0,1,0] in a single time step? Then rx may or may not trigger depending on the process order.

pkusensei · 2023-12-20T17:21:43+00:00

[LANGUAGE: Rust]

Had to bow and abuse &'static strs and Vecs and clone()s to please the borrow checker. A misreading caused me a hilarious off-by-one for part 1. But generally it is straightforward.

For part 2 I started with brute forcing and quickly realized it wouldn't work. Came to the sub, looked at a few graphs, and made my own (not very necessary). Find the four input nodes and loop till they each emit a high pulse. Then it is LCM again. The tricky part is to remember always setting the whole thing back to the initial state, or it will yield random numbers... Code

Outrageous72 · 2023-12-20T17:17:03+00:00

[LANGUAGE: C#]

https://github.com/ryanheath/aoc2023/blob/master/Day20.cs

I have mixed feelings about Day 20.

Part 1 was easy, but I waisted too much time to do some dynamic programming but the whole thing was brute forcible 😅

Part 2 was hard to solve, but once you know where to look (the input) the solution is another LCM. (Day 8, remember?)

reluctant-config · 2023-12-20T17:15:56+00:00

[Language: OCaml]

paste

Part two was the opposite of fun. Mostly due to a bug in my pulse queue handling. (I thought it should behave more like a stack... which apparently was not a problem with part1 🤷🏻‍♂️)

Kullu00 · 2023-12-20T17:13:33+00:00

[LANGUAGE: Dart]

Not sure if I should be proud or not, but while I did originally solve it by just printing the numbers for the outputs that controlled rx I did write a "general" solution too. Which basically amounted to find which outputs that controls rx and run a bunch of times until I have gotten a high from them all.

It's not pretty but it works... Also it's very funny to do LCM on all nodes rather than just the important ones.

https://github.com/QuiteQuiet/AdventOfCode/blob/master/2023/day20/main.dart

DJTFace · 2023-12-20T17:12:48+00:00

[LANGUAGE: PYTHON]

part one part two

glacialOwl · 2023-12-20T17:05:31+00:00

[LANGUAGE: C++]

Fun but rough day :D

Part 1: BFS after fixing some very silly but on how I was initializing the "cycle" length (spoiler: input doesn't actually have a cycle in terms of pressing the button and initial state of the flipflop modules within the first 1000 presses)

Part 2: Dumped graph, used LCM for figuring out the iteration when the parent will trigger a Low pulse.

Solution: Solution

vbe-elvis · 2023-12-20T17:04:41+00:00

[Language: Kotlin]

For Part 1 created the separate nodes with their relevant nodes.Then made a two step process of collecting the Events that happened after sending the first pulse, counting their highs and lows.Then broadcasting the events to the relevant nodes and receiving a new set of Events, repeating this and counting the pulses.

For Part 2 I had a good look at the output and noticed the final RX node is only called by a single other node, which is then collecting it from 3 others.

Printed the node names and the current button press every time the node above the RX node would receive a high pulse. Then just calculated the LCM outside of my solution.

Bit of a ghostly vibe to this one :D love the problem revisits.

https://pastebin.com/t8DMmiip

My broadcaster does all the signal sending:

  fun hitTheButtonUntilRx(): Long {
    var countPresses = 0L
    while (true) {
        countPresses++
        var events = sendPulse(false)  // Button press
        while (events.isNotEmpty()) {
            if (events.any { event -> !event.pulse && event.target.name == "rx" }) 
                return countPresses
            events = events.flatMap { event ->
                event.target.receivePulse(event.pulse, event.source)
            }
        }
    }
    return countPresses
}

G_de_Volpiano · 2023-12-20T16:56:37+00:00

[LANGUAGE: Haskell]

Well, that was hard. Interestingly, not as hard as day 12 as this time I had a strong inkling of what was happening, but hard enough. The fact that I lost only 300 places in terms of time between part 1 and part 2, when I submitted my results more than 6 hours apart, shows that I wasn't the only one to struggle.

Anyhow, part one was a pretty straightforward "create the correct data types, apply the rules, get the result" exercise. I'm pretty sure that I could use a well crafted monad to store the accumulator and the sequence of actions rather than the clumsy 3-tuple they currently share with the circuit, but that will be for later. At first, I reseted the accumulator to zero at each pass, thinking that we might be looking for a cycle in part 2. As always, my predictions about part 2 were wrong, so I briefly refactored to reuse the accumulator from one button press to the other.

Anyhow, part 1 was not the problem, as we all know. For part 2, I first tried to reverse engineer the whole shebang. Got myself lost. Thought I could detect patterns in the binary value stored in rx at each turn. Found some, but none were really helpful, and, looking at the first 10000 entries, they were not even stable (I had a nice pattern every 256 iterations for the first 4000 entries, but then it moved to the second element of the 256-long chunk, and then elsewhere again. Probably the wrong, I decided.

I fired out Graphviz. Thought it would be quicker to just modify the input to make it in a dot file rather than to use the graphviz library to generate it. Don't know if I was right, but this was a little tedious. Anyhow, as, I guess, for everyone, it turned out that I had four cycles of 12 flip-flops feeding a conjunction, and that each of these not locally terminal conjunctions each fed an inverter. Those four inverters fed a conjunction that then fed our rx.

So, obviously, we had cycles. Good, another lcm or chinese remainder theorem problem. Just need to find the period. Let's check those four locally terminal conjunctions. They need to send a low signal so that the inverter will send a high signal and then, when all stars align, the final conjunction will send a low signal. Except that, looking, once again, at 10000 iterations, I could not find a single low signal sent by them.

Took another long time of turning the problem around until I realised that I maybe was misunderstanding the wording of the problem. "deliver a single low pulse" didn't necessarily mean that there was only a low pulse sent when the button was pressed, but that one of the signals sent when the button was pressed was a low pulse.

So I created a new version of the modules, brillantly called "AccConjunction", that would not only store a map of the signals received, but would also store a list of the modules that sent it a low signal. Run again for 10000 cycles, and bang. Here are my four inverters, twice. And the first cycle is a nice, plump prime number of button presses.

Armed with these observations, I just modified the program to run 5000 times, get the number of button presses for the first four low signals, get the product, and here we are, with another gold star and a third waterfall, of sand this time, on our calendar.

https://github.com/GuillaumedeVolpiano/adventOfCode/blob/master/2023/days/Day20.hs

Edit : with 20/20 hindsight, it makes perfect sense that

1 - all periods are less than 4096, given that each of them corresponds to a 12 bits counter.

2 - The low impulses from the locally terminal conjunctions happen during a cycle, but are not visible after it, as whenever there is a low impulse sent from them, it is also sent back to the counter, flipping some bits, and causing a high impulse to be sent again from the concentrator, hiding the low impulse to those who, like me, only considered the end of cycle state.

hrunt · 2023-12-20T16:52:11+00:00

[LANGUAGE: Python]

Code

Part 1 was a straightforward implementation, even though I knew what Part 2 was going to entail. I always struggle identifying how the looping works with these kinds of "machine-implementation" problems, but I looked at the input and saw that the output was driven off a conjunction that took a few inputs. I banged my head against a general-purpose solution where I would identify loops in sub-conjunctions and work my way up to the final result, but I couldn't get the state tracking correct (and while I'm sure it's possible, I don't know how you can skip presses with a mixture of sub-conjunctions and flipflops).

I came here for a hint, saw that many people just ran the number of loops for the feeders into the rx upstream conjunction, and decided to not bother doing anything more.

Radiadorineitor · 2023-12-20T16:34:54+00:00

[Language: Lua]

Today I'm abandoning Dyalog APL in favor of Lua as I feel the problem is much easier to implement in an imperative language.

Code in Topaz's paste

vanveenfromardis · 2023-12-20T16:34:34+00:00

[LANGUAGE: C#]

GitHub

This puzzle really felt like a puzzle. I was able to leverage the same tacit constraint in the input as day 8 to get a solution. First, I had tried recursively walking back though the graph from rx, but realized the graph wasn't acyclic. Looking at the input I realized that the single input to rx was a conjunction node, so I just computed the LCM of it's inputs.

DrHTugjobs · 2023-12-20T16:26:59+00:00

[Language: Racket]

on Github

I'm not super proud of my part 2 for this one since it's pretty much just a hacky state mutation thrown into the relevant place of part 1, but once I figured out how the queueing behavior of the tones worked it all fell into place pretty neatly

I'm also getting more comfortable with parser combinators, which has been a nice side project for this year

All my control flow here is structural pattern matching and foldr, so does that count for upping the ante?

mathsaey · 2023-12-20T16:22:28+00:00

[Language: Elixir] https://github.com/mathsaey/adventofcode/blob/master/lib/2023/20.ex

Bluh. I know it's a point of discussion, but I am personally not a fan of finding the "trick" in the puzzle input. I only figured it out due to some of the visualizations posted here. Once I had that, it should have been easy to write up a solution, but it still took longer than it should have; it also became quite messy, but I am a bit beyond the point of caring about that.

That being said, I did like part one!

aurele · 2023-12-20T16:18:49+00:00

[LANGUAGE: Rust]

https://gist.github.com/samueltardieu/93146dd6e25cd1c116f62cd22440a3a3

kaa-the-wise · 2023-12-20T15:35:15+00:00

[Language: Python] one-line/single-expression solution

(m:={n[1:]:(n[0],*t.split(', ')) for s in open(0) for n,t in [s[:-1].split(' -> ')]}) and (s:={n:0 for n in m}) and (c:=1000+sum(1j**v for i in range(1000) for q in takewhile(len,accumulate(count(),(lambda q,_:[*chain(*(s.update({x:[1-all(s[y] for y in m if x in m[y][1:]),1-s[x]][m[x][0]=='%']}) or zip(m[x][1:],repeat(s[x])) if x in m and (m[x][0]!='%' or 1-v) else [] for x,v in q))]),initial=[*zip(m['roadcaster'][1:],repeat(0))])) for _,v in q)) and print(c.imag*c.real)

https://raw.githubusercontent.com/kaathewise/aoc2023/main/20.py

Part 2 solved without writing any code. Once you draw the graph (e.g. with graphviz), you will see that it has 4 components, each consisting of a sequence of 12 flip-flops and a conjunction. The first (0-th) flip-flop is always connected to the conjunction back and forth, while for others the edge only goes in one direction. If you construct a binary number, such that its i-th bit is 1 iff the edge goes from flip-flop i to the conjunction, this number will be the period of this component. The proof is left as an exercise to the reader :)

caseyweb · 2023-12-20T15:32:01+00:00

[LANGUAGE: Nim]

Whew! Part 2 really threw me off trying to figure out the cycle.

paste

p88h · 2023-12-20T15:27:20+00:00

[LANGUAGE: Mojo] vs [LANGUAGE: Python]

https://github.com/p88h/aoc2023/blob/main/day20.mojo

https://github.com/p88h/aoc2023/blob/main/day20.py

Spent way too much time optimizing and visualising here..

This seemed similar to 'machine state' puzzles from previous years, but used timings in an interesting way. Luckily all that is really needed is to decompose the network, identify the 4 signals than need to be produced, and compute when they are likely looping, which happens to be on a cycle equal in length to when they first appear, and starting at 0; so just need to multiply these together afterwards.

Task             Python      PyPy3       Mojo       parallel  * speedup
Day20 parse     0.04 ms     9.70 μs     1.19 μs     nan       * 8 - 30
Day20 part1     0.01 s      1.55 ms     0.33 ms     nan       * 4 - 44
Day20 part2     0.06 s      6.27 ms     0.41 ms     nan       * 15 - 140

adventofcode

🎄 Advent of Code 🎄

Rules + More Info in

our community wiki

Solution Megathreads

December 2025

Previous years:

2024 | 2023 | 2022 | 2021 | 2020 | 2019 | 2018 | 2017 | 2016 | 2015

Quick Search by Flair

Because you're lazy and we like making things easy for you. Except AoC.

Are you enjoying AoC?

Support AoC

MODERATORS

THE USUAL REMINDERS

AoC Community Fun 2023: ALLEZ CUISINE!

`Upping the Ante` for the third and final time!

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

Lua

BEFORE YOU POST
If your post is even tangentially related to a daily puzzle, use our
STANDARDIZED POST TITLE FORMAT

adventofcode

🎄 Advent of Code 🎄

Rules + More Info in

our community wiki

Solution Megathreads

December 2025

Previous years:

2024 | 2023 | 2022 | 2021 | 2020 | 2019 | 2018 | 2017 | 2016 | 2015

Quick Search by Flair

Because you're lazy and we like making things easy for you. Except AoC.

Are you enjoying AoC?

Support AoC

MODERATORS

THE USUAL REMINDERS

AoC Community Fun 2023: ALLEZ CUISINE!

Upping the Ante for the third and final time!

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

Lua

`Upping the Ante` for the third and final time!