Pulse Propagation

Advent of Code 2023 Day 20

Part 1

Highs and lows

Nothing exciting here. Just:

• A dictionary
• A queue
• Inputs and outputs
• Tracked state
• Conditional forwarding
• String manipulation

It probably won't be as fun as some other challenges.

But it should definitely prove...challenging.

Let's do this!

Parsing the input into a dictionary of modules

Given this input list of modules:

broadcaster -> a, b, c
%a -> b
%b -> c
%c -> inv
&inv -> a

I think I want to build a dictionary that resembles this architecture:

{
  broadcaster: {
    destinations: ['a','b','c'],
    pulse: false,
    type: null
  },
  a: {
    destinations: ['b'],
    power: false,
    type: 'flip-flop',
  },
  b: {
    destinations: ['c'],
    power: false,
    type: 'flip-flop'
  },
  c: {
    destinations: ['inv'],
    power: false,
    type: 'flip-flop'
  },
  inv: {
    destinations: ['a'],
    pulses: [false],
    type: 'conjunction'
  },
}

Writing that out made me have to re-read the rules several times.

I still don't quite understand all there is to know about pulses, remembering old pulses, and how some modules turn on and off.

But I'm sure I'll figure it out as I'm writing all the conditional logic to hopefully solve this puzzle!

Anyhoo, back to building this dictionary.

Enter: split().

First, on the ->:

broadcaster -> a, b, c

becomes:

['broadcaster', 'a, b, c']

Next, on the second element, only if there is a comma:

str.includes(',') ? str.split(', ') : str

becomes:

['broadcaster', ['a','b','c']]

And what about handling that first character?

Well, since every module except broadcaster has it, I can write a condition that, if passed, slices off and stores the first character:

let moduleType = name.slice(0,1)
name = name.slice(1)

It's time to actually write this code and programmatically craft this dictionary.

...

I coded it. It's not pretty. And I'll probably have to change parts of it as I familiarize myself with the module rules.

But my code generates a dictionary of modules with destinations, initial pulse values, and types.

Push the button!...and troubleshoot

Let's dive in by simulating a button press and debugging my way toward the expected result.

A button press is eventually going to be a single iteration of a 1000-iteration loop.

So, I'll use a for loop that runs once:

for (let i = 0; i < 1; i++) {

}

Somehow I need to make sure the program:

• Starts with broadcaster
• Touches every module that ever appears in a destination list
• Processes all modules in the current modules' destination list before proceeding to the next module

I'm envisioning a queue data structure and a while loop that runs as long as the queue isn't empty.

let todo = ['broadcaster']
while (todo.length > 0) {

}

For now, I'll track the pulse being sent:

let pulse = false

Processing the queue and adding items to it:

while (todo.length > 0) {
  let next = todo.shift()
  modules[next].destinations.forEach(d => {
    todo.push(d)
    // more important things
  })
}

First bug: not the right data type

My program kept generating an error, saying destinations doesn't exist.

Why was this?

Because sometimes I push a string to todo, and other times a push a 2-element array.

With a string, modules[next] finds a key.

With an array, modules[next] finds undefined.

One solution is to match the array data type when I craft the broadcaster key's value.

It's not great, but it gets rid of the error.

Second bug: endless loop

I assumed that queue of modules would eventually disipate.

I was wrong.

It mostly just grows.

Because every visited module has at least one destination. And each destination is being added to the list!

So, what am I missing?

Well, for staters, there's this important detail:

If a flip-flop module receives a high pulse, it is ignored and nothing happens.

That explains why the first simulated button press of the first example ends with:

inv -high-> a

At least I now have a verifiable loop termination condition.

The question is, how will I trigger it?

Nevermind that.

The above condition shouldn't even end a loop.

It just means that the receiving module triggers no further pulses.

The real terminating rule is:

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.

"...wait until all pulses have been delivered and fully handled...".

Rethinking how I track pulses

Pressing the button triggers a single low pulse with broadcaster as its destination.

So, my list of pulses is:

[
  [false, 'broadcaster']
]

I pull it from the list and apply it to broadcaster.

At this moment, the list is empty.

broadcaster has three destinations, and passes its received pulse to each of them.

So, my list of pulses after broadcaster is done looks like:

[
  [false, 'a'],
  [false, 'b'],
  [false, 'c']
]

I pull the first pulse from the list and apply it to a.

• a is a flip-flop module
• It starts as off
• It gets a low pulse
• It flips to on
• It generates a high pulse to each destination
• It only have one, b

After processing a, my pulse list looks like:

[
  [false, 'b'],
  [false, 'c'],
  [true, 'b']
]

The next two pulses act similar to the previous one.

Thus, the pulse list changes like this:

[
  [false, 'c'],
  [true, 'b'],
  [true, 'c']
]

And then:

[
  [true, 'b'],
  [true, 'c'],
  [true, 'inv']
]

Now b receives a high pulse.

As stated in the rules, nothing happens.

No new pulses are added to the list.

[
  [true, 'c'],
  [true, 'inv']
]

Now c receives a high pulse.

As stated in the rules, nothing happens.

No new pulses are added to the list.

[
  [true, 'inv']
]

Now inv receives a high pulse.

• It's a conjunction module
• It defaults to remembering a low pulse from each input module
• It updates its memory for the inputting module, c

Looks like I need to also track the originating module in my pulses list?

Anyway, since inv remembers a low pulse for c, it sends a high pulse to its destinations: a.

The pulse list - with sending module - is now:

[
  ['inv', true, 'a']
]

Now a receives a high pulse.

It does nothing.

No new pulses are generated.

And the pulse list is empty.

So this round is complete.

I think I finally understand the first example!

Better late than never!

Now how the heck am I going to re-create this programmatically??!!

Back to the code...and the endless struggle

Here's the current state of my one-iteration for loop with soon-to-be-terminating while loop:

for (let i = 0; i < 1; i++) {
  let todo = [['button', false, 'broadcaster']]
  let pulse = false
  while (todo.length > 0) {
    let [origin, bool, dest] = todo.shift()    
    modules[origin].destinations.forEach(d => {
      switch (modules[origin].type) {
        case 'broadcaster':
          todo.push([
            'broadcaster',
            pulse,
            d
          ])
          break;
        case 'flip-flop':
          if (pulse == false) {
            if (modules[origin].power) {
              todo.push([
                origin,
                false,
                dest
              ])
              modules[origin].power = false
            } else {
              todo.push([
                origin,
                true,
                dest
              ])
              modules[origin].power = true
            }
          }
          break;
        case 'conjunction':
          break;
      }
    })
  }
}

I believe I have accounted for two of the three module types.

But that third one has thrown a wrench at me.

I overlooked how complicated this detail would be:

Conjunction modules (prefix &) remember the type of the most recent pulse received from each of their connected input modules

My module-dictionary-maker only saves a module's outputs.

Not their inputs.

I need some way to store each input for each conjunction module.

I have an inkling of a strategy.

Generating all inputs to all conjunction modules

I'll add a inputs property to my conjunction modules that starts as an empty list.

I think I can do this after creating my dictionary.

Create a list of conjunction modules from the filtered dictionary keys
For each module, iterate through the dictionary's keys and values
If a key has that module as a destination
Add that key to the module's list of inputs

Time to give it a try!

...

Thankfully that wasn't too tough.

And doing it helped me clean up my dictionary generation code.

Here's the input-cataloguing code:

let conjunctions = []
for (let key in modules) {
  if (modules[key].type == 'conjunction') {
    conjunctions.push(key)
  }
}
conjunctions.forEach(c => {
  for (let key in modules) {
    if (modules[key].destinations.includes(c)) {
      modules[c].inputs[key] = false
    }
  }
})

After running on both example inputs, it seems to be making the correct architecture for both dictionaries.

And now....back to handling conjunction-type modules!

Tracking the pulses of input modules

I wrote some code that seemed to match the spec as described.

For fun, I ran one iteration.

Immediate error.

I had to re-visit my first item in todo:

['button', false, 'broadcaster']

My modules dictionary has no key for button, nor should it!

I need to manually perform the first step of sending a low signal to each of broadcaster's destination modules.

It's redundant and icky.

But it does the job.

I ran the program again for a single iteration.

It finished without errors!

I saw the same log of actions as the first example describes!

How about example 2?

I ran for a single iteration.

Another error.

This has to do with output not being a key in my dictionary.

I updated my code, wrapping almost all of the logic in a condition that checks for a key's existence in the dictionary.

I ran for a single iteration again.

It finished without errors!

I saw what seemed like the same log of steps as described after a single button push.

I ran for two iterations.

Again, it all seemed to match up.

I ran for three iterations.

Uh-oh. Mismatch detected.

A conjunction module was sending the wrong pulse to its destination module.

I'm not sure why.

After some extensive logging, I noticed that my program gets things wrong after the first iteration of the second example input.

I think I'm misunderstanding the first rule about conjunction modules:

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.

I took that to mean when a pulse is received by the input module.

But I think it means when a pulse is received by the conjunction module.

They remember the type of the most recent pulse received from each of their connected input modules.

So when a conjunction module is a destination module, it must update the pulse type in its input list for the originating module to the pulse type being passed to it.

I think...???

Honestly, I'm so confused at this point.

...

I moved and duplicated the code that updated the boolean value for any key inside a conjunction module's input object.

It now has the potential to happen any time a new todo is added to the list, since that is when a pulse is sent off.

I also fixed an unintended error where i was overriding a flip-flop module's power to null.

With all of that resolved, I can run four iterations on the second example input...

...and get what I feel is the correct result: both flip-flop modules are off.

I have very little confidence that this program will produce the correct results on my example input.

But I'm ready to move on to cataloguing and counting pulses.

Counting high and low pulses

Two pulse types.

Eventually, multiplied together.

I'll use a 2-element array.

It should be easy to update the array inside my while loop.

I also need to track when the button is pushed.

I hope that's also as easy as it seems.

...

I added the necessary increment expressions.

I ran the program on the first example a single iteration.

I saw [8, 4]. Woohoo!

Running 1000 times correctly generates [8000, 4000]. Woohoo!

Running 1000 times on the second input generates the wrong answer.

Low pulses is off by 500. High pulses is off by 1000.

Bummer.

...

Wait a second.

The sum of the pulses is 7000.

Divided by 1000 is 7.

So, 7 pulses each time?

No...there are different amounts of pulses in each four-button cycle.

...

Oh ya! The output module!

My program doesn't account for pulses sent to that module.

I bet that's what I'm missing!

If I look at the number of pulses in a single iteration, I count three low and three high.

There are eight total. Two go to output: one high and one low.

So my counts are correct...they just neglect that unprefixed module!

I'd wager my input doesn't contain any unprefixed modules.

Therefore, maybe my code already works on my puzzle input???

Worth a try!

Wrong answer.

Too low.

Bummer.

I'm so over this challenge.

My brain hurts so bad.

And I don't see how to easily update my code to account for the small task of seeing the correct pulse counts for the second example.

Sadly, I leave with no new stars earned.

This one was just too darn confusing, I guess.