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
- Solve for
X
whereX =
... - Recovered frequency?
rcv
instruction? - This all feels very familiar
- Here we go again: building a registry-based instruction-processing computer
- 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 ofrcv
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
- Solve for
X
whereX =
... -
Program 1
? Sends` a value? - I've created a monster!
- Troubleshooting using my puzzle input
- Closer...closer...not close enough
- 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
issend
, notsound
-
rcv
isreceive
, notrecover
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
or1
- 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.
Top comments (0)