Advent of Code 2023's Day 20 problem: Pulse Propagation is
one of my favourite problems. I took quite some time to solve it, and looking
back, it's a great way to showcase almost all the things I love about Elixir.
Here's my approach of solving this problem, accompanied by how Elixir's
(mental) model helped me. I skip over some things which are "basic" to Elixir,
so you can refer to the official docs if something
doesn't quite make sense. In a gist:
Elixir is a dynamic and functional language
|> is the pipe operator,
pretty central to the language; passes result of the left operation as the
first argument for the right operation
There is no return keyword, the value returned by a function is the value
returned by its last expression
Modules communicate using pulses. Each pulse is either a high pulse
or a low pulse. When a module sends a pulse, it sends that type of pulse
to each module in its list of destination modules.
There are several different types of modules:
Flip-flop modules (prefix %) are either on or off; they are
initially off. If a flip-flop module receives a high pulse, it is ignored
and nothing happens. However, if a flip-flop module receives a low pulse, it
flips between on and off. If it was off, it turns on and sends a high
pulse. If it was on, it turns off and sends a low pulse.
Conjunction modules (prefix &) remember the type of the most recent
pulse received from each of their connected input modules; they initially
default to remembering a low pulse for each input. When a pulse is
received, the conjunction module first updates its memory for that input.
Then, if it remembers high pulses for all inputs, it sends a low pulse;
otherwise, it sends a high pulse.
There is a single broadcast module (named broadcaster). When it receives
a pulse, it sends the same pulse to all of its destination modules.
Here at Desert Machine Headquarters, there is a module with a
single button on it called, aptly, the button module. When you push the
button, a single low pulse is sent directly to the broadcaster module.
After pushing the button, you must wait until all pulses have been delivered
and fully handled before pushing it again. Never push the button if modules
are still processing pulses.
Pulses are always processed in the order they are sent. So, if a pulse is
sent to modules a, b, and c, and then module a processes its pulse and sends
more pulses, the pulses sent to modules b and c would have to be handled first.
[...]
To get the cables warmed up, the Elves have pushed the button 1000 times. How
many pulses got sent as a result (including the pulses sent by the button itself)?
In the first example, the same thing happens every time the button is pushed:
8 low pulses and 4 high pulses are sent. So, after pushing the button 1000
times, 8000 low pulses and 4000 high pulses are sent. Multiplying these
together gives 32000000.
In the second example, after pushing the button 1000 times, 4250 low pulses
and 2750 high pulses are sent. Multiplying these together gives 11687500.
Consult your module configuration; determine the number of low pulses and high
pulses that would be sent after pushing the button 1000 times, waiting for all
pulses to be fully handled after each push of the button. What do you get if
you multiply the total number of low pulses sent by the total number of high
pulses sent?
There's a lot of words to make the problem more thematic, but the takeaways are:
There's one input, broadcaster module
Modules can be of two types, flip-flop modules, denoted by %, and
conjunction modules denoted by &.
Flip-flop modules switch between on and off, are initially off, but flip
only when they receive a low pulse. high pulses are ignored.
Conjunctions modules will store the type of most recent pulse received from
each of its inputs, initially low for each.
When it receives a pulse, it checks if it "remembers" high pulses from all
its inputs, and forwards a low pulse if so, high otherwise.
With this in mind, we're ready to begin.
Parsing input
Here's the sample input:
We'll need to parse this and create a Map
to store our module connections. Looking at our sample input, here's some pseudocode:
Anonymous functions, pattern matching and atoms
A couple of handy Elixir-isms will help us out here:
And processing the given input thus far gives us:
...but there's a problem: we don't have the inputs mapped for the conj modules.
We'll need to iterate over the modules and create a map of conj modules and
their inputs, and then merge them.
All together now:
Parsing our example input now gives us an accurate map:
Processing pulses
We need to process a button press, sending a :low pulse from our broadcast
module to its destination modules.
We'll extract the broadcast key from the parsed_input:
...and then loop over the destination modules where we'll send the :low pulse.
Since we'll need to update our :conj modules' inputs later, let's add in the
sender module in the pulse_details as well.
With all that setup done, it's time to think about how to actually process the pulses.
Something important to keep in mind is that there is no class in Elixir, no
objects/instances — so anytime we need to keep track of certain changes, you'll
need to pass around a variable.
Here's some pseudocode:
Guards
At this stage, we'll need to do some more complex checks in our pattern amtching,
for which we'll use guards.
With that, we've handled all the "scenarios" where we need to make/handle a
change in our modules_map and/or send pulses onwards. But there's still some
cases left to handle:
:output module which is only mentioned as a destination module, and would
thus be missing from the parsed input map
"If a :flip module receives a :high pulse, it is ignored and nothing happens"
We can handle both of these by returning an empty list of "next pulses", and
leaving the modules_map unchanged.
Additionally, we also need to handle:
rest_pulses, by calling process_pulses recursively
base case for when we're done handling all pulses
Keep track of :low and :high pulse count
Here's what our overall module looks like now:
Running part 1
For the first part of the puzzle, we need to perform 1000 "button presses".
This translates to processing 1000 :low pulses sent from the broadcast module
and counting the number of :low and :high pulses.