Sunny with a Chance of Asteroids

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

1. This may not be much fun, but is necessary
2. Confirming understanding of all Intcode syntax and terminology described thus far
3. Analyzing my puzzle input
4. 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) or parameters (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 an opcode
• An increasing instruction pointer starts at 0 and changes based on each subsequent opcode
• 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

1. Account for both parameter modes: position and immediate
2. Account for all four opcode instructions
3. Parse a combined opcode-parameter integer
4. 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, or 1 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.

Try the simulator for Part 1

I'm biting my nails in fear of an even tougher Part 2.

Part 2

1. Ugh...more opcodes!
2. 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.