Duet

Advent of Code 2017 Day 18

Why out of order?

• Day 23 referenced Day 18
• I couldn't faithfully attempt Part 1 of Day 23 without building an algorithm that solved at least Part 1 of Day 18

A malfunctioning - but stimulating - simulator

• I built a simulator
• It doesn't generate the correct answer for me for Part 2
• But it does show how each program runs, albeit likely incorrectly at parts

Part 1

1. Solve for X where X =...
2. Recovered frequency? rcv instruction?
3. This all feels very familiar
4. Here we go again: building a registry-based instruction-processing computer
5. Writing a working algorithm

Solve for X where X =...

The value of the recovered frequency (the value of the most recently played sound) the first time a rcv instruction is executed with a non-zero value

Recovered frequency? rcv instruction?

• rcv is one of eight instruction types
• It recovers the frequency of the last sound played
• But only when the value of X is not zero
• What does X refer to?

The eight instructions follow a blueprint:

instruction X Y?

• The three-letter name of the instruction
• At least one operand, indicated by X
• Almost always a second operand, indicated by Y

rcv is one of two instructions that work with one operand.

This all feels very familiar

• 2019 was filled with puzzles that had me constructing a computer that ran Intcode programs
• Those puzzles also featured instructions - although they used integers 0-9 as designates for instructions, whereas here the instructions have 3-letter names
• Those puzzles also ran until being halted, usually when an address tracker attempted to access an instruction beyond the size of the list

In summary, I'm confident I can solve this puzzle...

...assuming there's not secret trick to bypass a nearly-infinite loop that would otherwise cause the program to run too long.

Here we go again: building a registry-based instruction-processing computer

Ingredients:

• A set of registers that are each named with a single letter and that can each hold a single integer
• Each register should start with a value of 0
• 7 instructions: snd, set, add, mul, mod, rcv, jgz
• Each instruction expects either one or two arguments
• Each instruction always updates the address for which instruction to process next
• Each instruction also either does nothing, sets a value to a register, or reads a value from a register
• An ordered list of recently played sounds

Writing a working algorithm

Setup:

Split the input at each newline character into an array of strings
For each string
  Split the string at each space character into an array of two or three strings
  Check whether there is a third value
    If there is
      Return a three-element array where the elements are:
        1. A three-letter string
        2. A single-letter string
        3. Either a single-letter string or a number
    If there is no third value
      Return a two-element array where the elements are:
        1. A three-letter string
        2. A single-letter string
Create an empty object to store each register and its current number value
Create an address tracker, starting at 0
Create an empty array to store each played sound

Next, the object storing each instruction function.

I struggled the most with this because I ignorantly overlooked a bunch of small edge cases, like:

• Each function must increment the address tracker by 1, or in the case of jgz by a specific amount, or in the case of rcv to any address outside of the list (specifically, -1)
• Any functions that attempt to update a register's value should first ensure that register exists and is set to 0
• I need to check the value stored in the register key, not check the register key itself (which results in NaN)
• The second argument for most functions may be one of three things: 1) undefined, 2) number, 3) string

Six of the functions had this blueprint:

rule(X,Y?) {
  if X is not a key in registers
    create it and set its value to 0
  update the value associated with X
    based on the proper operation and the value of Y
  increment address by 1
}

rcv and jgz had this blueprint:

rule(X,Y?) {
  check registers[X] as compared to 0
 if a match
   update address appropriately
 else
   increment address by 1
}

The function to process each subsequent instruction:

Sub-routine processor
  Expects one argument: an array

  Invoke the method in registers corresponding to the first three-letter string in the array
  Pass as arguments to that function the second and third elements in the array

The main loop:

Do as long as the number stored in address points to a valid location in the list of instructions
  Invoke processor, passing the array at the location stored in address as argument

Lastly:

Return the last element in the ordered list of played sounds

After some troubleshooting, Part 1 was solved!

Part 2

1. Solve for X where X =...
2. Program 1? Sends` a value?
3. I've created a monster!
4. Troubleshooting using my puzzle input
5. Closer...closer...not close enough
6. Last-ditch effort: building a simulator

Solve for X where X = ...

The number of times program 1 sends a value

Program 1? Sends` a value?

• I need to run two copies of the program in parallel

Each running copy of the program has its own set of registers and follows the code independently - in fact, the programs don't even necessarily run at the same speed.

Oh, my. Intimidation sets in.

Each program also has its own program ID (one 0 and the other 1); the register p should begin with this value.

Interesting. I may use a 2-element array to track the state of each program.

• snd is send, not sound
• rcv is receive, not recover

Each program has its own message queue, so a program can never receive a message it sent.

Phew! That should make things less complicated.

Although, that's one more thing I'll have to track.

If no values are in the queue, the program waits for a value to be sent to it. Programs do not continue to the next instruction until they have received a value. Values are received in the order they are sent.

Hmm. So the rules for program termination are now:

• Halt if the address of the next instruction is outside of the bounds of the list
• Halt if there are no queued messages

My biggest question right now is:

• How will I craft a while loop that appropriately toggles between programs and ends when each one is meant to terminate?

I feel like I need to carefully analyze the new example input.

And then think on all of this for a bit.

I've created a monster!

• I need two copies of the program
• And for each program: a queue for received messages, instructions, an address pointer, an id, a dictionary for registers, and a tally for the number of sent messages
• I went all-out and created two nearly-identical objects full of properties and methods, each one stored in a two-element array
• It's a ton of duplicate code - with only the index changed between either 0 or 1
• But, at least for the example input, it terminates correctly and with the correct answer

Troubleshooting using my puzzle input

• I tried running my algorithm using my puzzle input
• I immediately got an error, then another, then another
• Looks like I need to go one step - and, sadly, error message - at a time

To help debug my code, I currently print for each program copy:

• The location of the address pointer
• Any queued received messages
• The tally of sent messages
• The registers and their values

I should probably also print the instruction about to run.

Closer...closer...not close enough

Hurdles:

• My jnz function wasn't working as expected. After some careful analysis, I fixed my issue: a copy-paste error
• Each program's queued message lists kept growing and growing. After some careful analysis, I changed my algorithm to attempt to deplete a queue's messages before letting the other program resume. This seemed like a step in the right direction, until...
• Both programs stop abruptly at the same line of the program, but one has a full queue and the other has an empty one. I'm dumbfounded as to what to put in a condition to ensure my loop only breaks when both queues are empty and neither one has moved its address pointer since the last iteration.
• When I nest several identical conditions in attempts to clear out both queues, I notice that the remaining queue is filling with exponentially more amounts of the same integer. This can't be right.

I'm stumped!

Last-ditch effort: building a simulator

• I desperately wanted to see how each program's queued message list and registers' values changed over the course of thousands of iterations
• So, I made a simulator that lets me step by increments in multiples of 10: 1, 10, 100, 1000, 10000
• It helped paint a picture that proves my algorithm must be buggy, as each list of queued messages seems to exponentially grow and become filled with the same integer: 95

Celebrating my accomplishments

• I solved part 1!
• I wrote an algorithm that solved the example input for Part 2
• I tried my hardest to troubleshoot and solve Part 2 using my puzzle input
• I even built a simulator in hopes of revealing the underlying issue with my algorithm
• I think I have enough knowledge to attempt Day 23 Part 1 now - and I certainly have the foundation to built a simulator for it!

Bummers:

• I couldn't figure out the winning condition to cause my loop to escape
• I couldn't even tell you if what I need to make it work is a different condition! It could be something else entirely!

This puzzle - much like 2018 Day 24 - will likely remain thorns in my brain for a while.