Advent of Code 2019 Day 5
Try the simulator!
Task: Solve for X where...
Part 1
X = the diagnostic code produced after providing 1 as the input instruction and passing all the tests
Part 2
X = the diagnostic code produced after providing 5 as the input instruction
Example input
1002,4,3,4,33
It represents:
- A program that runs on an Intcode computer
Part 1
- This may not be much fun, but is necessary
- Confirming understanding of all Intcode syntax and terminology described thus far
- Analyzing my puzzle input
- Writing an algorithm that I hope outputs something
This may not be much fun, but is necessary
- This puzzle's instructions are intimidating
- There's a lot to unpack
- I sense an uphill battle filled with slowly acquired understanding, algorithmic exploration and troubleshooting, and hopefully the reward of a correct answer
As mentioned in my post about 2019 Day 25:
- Day 5 is one of the dependencies
So - whether I like it or not - it seems I must prevail!
Confirming understanding of all Intcode syntax and terminology described thus far
Knowledge gained from Day 2
An Intcode program is a list of integers separated by commas
Each of these is an Intcode program
1,0,0,3,99
1,10,20,30
1,9,10,3,2,3,11,0,99,30,40,50
1,0,0,0,99
2,3,0,3,99
2,4,4,5,99,0
1,1,1,4,99,5,6,0,99
Numbers 1, 2 and 99 are special, at least when located at specific positions.
- Each one represents an
opcode
- Opcodes are the beginning of an instruction
- They indicate what should happen next
The opcodes 1, 2, and 99 do as follows:
- 1 indicates a sum
- 2 indicates a product
- 99 indicates immediate termination of the program
The values used immediately after an opcode, if any, are called the instruction's parameters.
- 1 is followed by 3 parameters
- 2 is followed by 3 parameters
- 99 is followed by 0 parameters
More fun facts:
- A position in memory is called an address (for example, the first value in memory is at "address 0")
- The address of the current instruction is called the instruction pointer; it starts at 0
- After an instruction finishes, the instruction pointer increases by the number of values in the instruction
- Once the program has halted, its output is available at address 0
- When you run an Intcode program, make sure to start by initializing memory to the program's values
Summarizing Day 2 knowledge
- Each Intcode program features
integers
- That represent
opcodes
(a.k.a. instructions) orparameters
(a.k.a. actors for those instructions) - Thus far,
opcodes
calculate and store the sum (1) or product (2) of values at addresses in memory specified by the parameters that follow them...or terminate the program entirely (e.g. 99) - The first integer is at
address
0 and is anopcode
- An increasing
instruction pointer
starts at 0 and changes based on each subsequentopcode
- Each Intcode program's journey will change depending on the initial values - which the author can change before running the program
- When a program is finished running, its
output
is contained in the value at address 0
Knowledge gained from Day 5
The list of potential instructions has grown by two.
Here's an exhaustive rule set:
Numbers 1, 2, 3, 4 and 99 are special, at least when located at specific positions.
- Each one represents an
opcode
- Opcodes are the beginning of an instruction
- They indicate what should happen next
The opcodes 1, 2, 3, 4 and 99 do as follows:
- 1 indicates a sum
- 2 indicates a product
- 3 indicates storage of an input at an address
- 4 indicates output of a value at an address
- 99 indicates immediate termination of the program
The values used immediately after an opcode, if any, are called the instruction's parameters.
- 1 is followed by 3 parameters
- 2 is followed by 3 parameters
- 3 is followed by 1 parameter
- 4 is followed by 1 parameter
- 99 is followed by 0 parameters
Next, the list of parameter modes
has grown by 1.
Unbeknownst to me, my Intcode computer already supported parameter mode 0
(a.k.a. position mode
).
It now must accommodate immediate mode
represented by a 1
.
Parameter modes operate on the parameters that follow opcode
instructions.
- 0 indicates that parameter values signify positions, or addresses
- 1 indicates that parameter values signify values
Parameter modes and opcodes are represented as portions of a single integer:
Instruction
1002
Breakdown
1002
321Op
02 = Opcode 2 - expects three parameters
0 = Parameter mode for first parameter
1 = Parameter mode for second parameter
0 = Missing mode defaults to 0 for third parameter
More fun facts:
- Parameters that an instruction writes to will never be in immediate mode
- The instruction pointer should increase by the number of values in the instruction after the instruction finishes...not always by 4 (like in Day 2's Intcode computer)
- Integers can be negative
The diagnostic program
- The program will start running with input instruction
1
Now for the part I don't get:
It will then perform a series of diagnostic tests confirming that various parts of the Intcode computer, like parameter modes, function correctly. For each test, it will run an output instruction indicating how far the result of the test was from the expected value, where 0 means the test was successful. Non-zero outputs mean that a function is not working correctly; check the instructions that were run before the output instruction to see which one failed.
- Series of diagnostic tests:
while
loop? - Check whether parameter modes function correctly: so...expect some parameter modes from the puzzle input to be incorrect?
- For each test, output a value representing a difference between the actual value and the expected value: 0?
- Non-zero outputs mean that a function is not working correct:
while output does not equal 0
? - Check the instructions run prior to the value indicated by the output to see which function failed: so...keep track of the most recent instruction?
Then, the last two parts of the instructions seem to indicate:
- My algorithm must attempt to run the program again and again
- Until all tests pass (a.k.a. all output instructions except the last are 0)
- Meaning my algorithm must attempt to self-heal: update any malfunctioning parameter mode functions to iteratively eradicate non-zero output instructions
...because only after doing that will I see a diagnostic code:
If all outputs were zero except the diagnostic code, the diagnostic program ran successfully.
Analyzing my puzzle input
These are my first few instructions:
3,225,1,225,6,6,1100,1,238,225,104,0
Knowing the program must receive 1
as input instruction:
First opcode:
3
Expects 1 parameter and 1 input
Input: 1
Parameter: 225 (defaults to position mode 0)
Performs look-up of value at address 225:
0
Updates value at address to value of input:
0 -> 1
Moves instruction pointer by 2 to next instruction
3,225,1,225,6,6,1100,1,238,225,104,0,...
----->*
Next opcode:
1
Expects 3 parameters and no input
Parameter 1: 225 (defaults to position mode 0)
Parameter 2: 6 (defaults to position mode 0)
Parameter 3: 6 (defaults to position mode 0)
Performs look-up of value at address 225:
1
Performs look-up of value at address 6:
1100
Calculates sum and stores result in value at address 6:
1101
Moves instruction pointer by 4 to next instruction
3,225,1,225,6,6,1101,1,238,225,104,0,...
--------------->*
Next opcode
1
Expects 3 parameters and no input
Parameter 1: 1 (use immediate mode 1)
Parameter 2: 238 (use immediate mode 1)
Parameter 3: 225 (defaults to position mode 0)
Uses value of Parameter 1:
1
Uses value of Parameter 2:
238
Calculates sum and stores result in value at address 225:
239
Moves instruction pointer by 4 to next instruction
3,225,1,225,6,6,1101,1,238,225,104,0,...
------------------------------>*
Next opcode
4
Expects 1 parameter and no input
Parameter 1: 0 (use immediate mode 1)
Uses value of Parameter 1:
0
Outputs 0:
The test was successful!
Moves instruction pointer by 2 to next instruction
3,225,1,225,6,6,1101,1,238,225,104,0,...
------------------------------------>*
Looking for opcode 4:
- There are 10
- The last one is followed by opcode 99 (halt)
Looking for opcode 99:
- There are 2
Other observations:
- There are 18 0s
- There are several instances of four-digit integers that contain 10 or 11 as the first two digits and 0,1,2,5,6,7,8 as the fourth digit
Writing an algorithm that I hope outputs something
- Account for both parameter modes: position and immediate
- Account for all four opcode instructions
- Parse a combined opcode-parameter integer
- Run the program
Account for both parameter modes: position and immediate
- I used a 2-element array
- Each element is an anonymous function
- Thus, the correct function will run on a pointer location as input for either mode:
0
for position, or1
for value
modes = [(i) => ic[i], (i) => i]
Account for all four opcode instructions
- I used a 5-element array
- Each element except the first is an object
- The index of each object corresponds to the opcode: 1-4
- Each object contains two properties: number of expected parameters, and the function to run
- Each function operates on the Intcode program's ordered integers using the appropriate values based on the parsed opcode and parameter modes
Here's a snippet of that object - for opcode 2:
{
params: 3,
instructions(params) {
Intcodes[modes[0](pointer + 3)] =
Intcodes[modes[params[0]](pointer + 1)] *
Intcodes[modes[params[1]](pointer + 2)]
}
}
Parse a combined opcode-parameter integer
Examples of this integer include:
1
2
3
4
104
1101
1002
For any of these patterns, I need to:
Extract the last two digits to get the opcode
Extract all but the last two digits, reverse their order and join to form a string of digits
Check whether the number of non-opcode digits is less than the number of parameters expected by the opcode
If there are less, add '0's to the end of the string to make the number of digits equal the number of expected parameters expected by the opcode
Run the program
Do as long as pointer is less than the length of the number of integers in the program, and the value at pointer is not 99
Parse the opcode-parameter integer to generate the opcode and list of parameter modes
Look-up the object mapped to the opcode and run the instruction function
Doing so will either mutate the Intcode program
Or output a value
Update pointer to move it N addresses forward where N is one greater than the length of the parameter list
Return the value output right before the program terminates
Much to my surprise, my output looked like this:
0
0
0
0
0
0
Non-zero number
And voila! That non-zero number was the correct answer for Part 1!
The last bit of instructions for Part 1 of the puzzle confused me into thinking that not all tests would pass.
I was therefore delighted to see all 0's except the one at the end.
Building a simulator
I wanted to see the program running with each test output displayed.
Luckily, it wasn't too difficult to fork and update my Day 2 Intcode Program Simulator.
I'm biting my nails in fear of an even tougher Part 2.
Part 2
- Ugh...more opcodes!
- Updating and troubleshooting my opcode object
Ugh...more opcodes!
The list of potential instructions has grown by four.
Here's an exhaustive rule set:
Numbers 1-8 and 99 are special, at least when located at specific positions.
- Each one represents an
opcode
- Opcodes are the beginning of an instruction
- They indicate what should happen next
The opcodes 1-8 and 99 do as follows:
- 1 indicates a sum
- 2 indicates a product
- 3 indicates storage of an input at an address
- 4 indicates output of a value at an address
- 5 indicates an if-else: check parameter 1 for non-zero integer. True? Set pointer to parameter 2. False? Do nothing.
- 6 indicates an if-else: check parameter 1 for 0. True? Set pointer to parameter 2. False? Do nothing.
- 7 indicates an if-else: check whether parameter 1 is less than parameter 2 True? Store 1 in parameter 3. False? Store 0 in parameter 3.
- 8 indicates an if-else: check whether parameter 1 is equal to parameter 2 True? Store 1 in parameter 3. False? Store 0 in parameter 3.
- 99 indicates immediate termination of the program
The values used immediately after an opcode, if any, are called the instruction's parameters.
- 1 is followed by 3 parameters
- 2 is followed by 3 parameters
- 3 is followed by 1 parameter
- 4 is followed by 1 parameter
- 5 is followed by 2 parameters
- 6 is followed by 2 parameters
- 7 is followed by 3 parameters
- 8 is followed by 3 parameters
- 99 is followed by 0 parameters
An important call-out that highlights opcodes 5 and 6's behavior:
Normally, after an instruction is finished, the instruction pointer increases by the number of values in that instruction. However, if the instruction modifies the instruction pointer, that value is used and the instruction pointer is not automatically increased.
This means I can no longer always increment pointer, but need additional checks based on the opcode and the result of its instructions.
Updating and troubleshooting my opcode object
- I added four new objects, one for each opcode, to my array
- I removed my general-purpose pointer-update statement
- I added pointer-update statements to all eight opcode instruction functions
- I ran my algorithm and watched it hang on the number 7
- After reviewing my code, I noticed I put a few pointer-update statements in the wrong part of a few functions
- I added more logging statements inside each function
- I ran my algorithm again and saw it terminate and output a 7-digit number
- That was the correct answer!
I updated my simulator to run using the new opcodes and input.
Interestingly, I noticed one number changes a bunch!
Sadly, it isn't very interesting to watch.
[Try the simulator on your puzzle input!]
(https://aocsunnywithachanceofasteroids.rmion.repl.co/)
I did it!!
- This puzzle was intimidating, complicated, difficult to understand, and seemed impossible to solve at times
- But by working through it by way of writing this article, I eventually solve both parts!
- Thank goodness, because today's puzzle was one of the five puzzles referenced by Day 25
- I'm glad I've been able to build the necessary components of an Intcode computer thus far
Fingers crossed Day 6 isn't as intense.
Top comments (0)