Chronal Classification

Advent of Code 2018 Day 16

Why skip five days?

• Day 21's puzzle depended on an algorithm written in Days 19 and 16
• This scenario is a smaller example of Year 2019, where Day 25 depended on an algorithm written throughout several Days prior
• Instead of publish a near-empty Day 21 - like I did for Day 25 of 2019 - I'm opting to just skip to the first referenced Day, attempt to complete it, then work forward up to Day 21, then remain going backwards again

Task: Solve for X where...

Part 1

X = the number of samples in that behave like three or more opcodes

Part 2

X = the value contained in register 0 after executing the test program

Example input

Before: [3, 2, 1, 1]
9 2 1 2
After:  [3, 2, 2, 1]

It represents:

• A sandwich, of sorts:
• Two states of the registers
• Before and after performing the instruction in between
• The instruction represents an opcode and three registers or values

Part 1

1. Opcodes again?!
2. Studying the rules: familiar and new
3. Programming the device as I familiarize myself with each new opcode
4. Outlining how I will test each sample, and testing the example sample
5. From one to many: testing on all the samples

Opcodes again?!

• Year 2019 was full of them!
• Thankfully, this puzzle should feel familiar and be easier to solve as compared to me seeing opcodes for the first time
• However, I'm not looking forward to re-programming an algorithm that must now handle 16 opcodes where the one I made for 2019's Intcode computer only featured 9

Well, here we go: opcode-themed challenge #...13?

Studying the rules: familiar and new

the device has four registers (numbered 0 through 3)

I'll use an ordered list (array) to store the registers.

For example:

[0,1,2,3]

each register can be manipulated by instructions containing one of 16 opcodes

• This is exactly like in the puzzles from 2019

The registers start with the value 0

Interesting. So the initial state would look like this:

[0,0,0,0]

Every instruction consists of four values: an opcode, two inputs (named A and B), and an output (named C), in that order.

The pattern therefore looks like:

opcode A B C

Helpful constraint:

The output, C, is always treated as a register.

Next, we bring back the parameter modes that a given input could be read or written as:

1. Immediate mode: written as value A - take the number given as A literally
2. Position mode: written as register A - use the number given as A to read from (or write to) the register with that number

Next, a confirmatory example:

Where addi (add immediate) stores into register C the result of adding register A and value B

And instruction is:
addi 0 7 3

Modes are:
     P I P

In english:
Value at register 0
                + 7
-------------------
Write to register 3

That makes sense.

Programming the device as I familiarize myself with each new opcode

• Seven categories
• With subtle differences about the mode an argument is interpreted

I'll start with an object full of methods.

Each method follows this rough pattern:

{
  opcode(A,B,C) {
    registers[C] = (registers[A] || A) +*&|=>== (registers[B] || B)
  }
}

• The method is named after the opcode
• Each method expects three parameters: two inputs and one output
• All 16 opcodes sets the value of register C
• Each opcode operates on either a direct value or a value stored in the indicated register

I've got my object and it's methods filled in.

It's time to try the example!

Before: [3, 2, 1, 1]
9 2 1 2
After:  [3, 2, 2, 1]

Outlining how I will test each sample, and testing the example sample

Well, first, a regular expression.

/\d+/g

• That captures all 12 integers, which may be single- or double-digit values
• I'll still need to craft three groups: a register list, instructions, and a stringified register list with which to compare

After matching all of those regular expressions in the sample string, I can extract each group using slice():

let sample =
`Before: [3, 2, 1, 1]
9 2 1 2
After:  [3, 2, 2, 1]`

let matches = [...sample.matchAll(/\d+/g)].map(el => +el[0])

let registers = matches.slice(0,4)
let instructions = matches.slice(5,8)
let expectation = matches.slice(8)

Now I'm ready to test this sample on each opcode:

• I'll use my object of methods as the originating array - leveraging Object.values()
• I'll mutate the functions into booleans using map()
• I'll filter() for truthy values to determine whether three or more opcodes generated the expected value

Create an array of functions from the object
For each function, replace it with a boolean value based on the following operations:
  Store a temporary copy of the Before register list
  Invoke the function, passing in each of the three inputs from the instructions
  Store the boolean representing whether Before is equal to After
  Re-set the register list to its original state
  Return the boolean value

Filter the updated list of booleans to only include truthy values

Return the length of the filtered list

Success! The sample returns 3 as expected.

From one to many: testing on all the samples

First, some setup:

Split the input at three newline characters
  Save the first of two strings as samples
  Save the second of two strings as program, for Part 2

Store an array of four zeros as my initial registers list
Store my object of opcode methods

Now I am ready for the core iteration and processing:

Split the samples string at each pair of newline characters into a list of each three-line sample string

For each three-line sample string
  Set matches as the 12-item list of integers resulting from matching each multi-digit character from the string
  Set registers as a list of the first four of 12 integers
  Set instructions as a list of the sixth thru eighth integers
  Set expectation as a list of the last four integers

  Return the integer that results from the process described earlier as part of solving a single sample

Filter the list of samples-turned-tallies to only include numbers greater than or equal to 3

Return the length of the filtered list

Did it work?

1. First attempt: a number over 10000 - Too high. Error? I was splitting the samples string at each single newline character, not pair.
2. Second attempt: a number over 4000 - Too high. Error? I was incorrectly summing up each tallied integer using reduce() after my filter()
3. Third attempt: a number over 250 - Too low. Error? I was creating a local copy of registers, but using the original one from global scope in each iteration.
4. Fourth attempt: a number over 550 - Correct!

Part 2

1. Example input
2. Why did I think it would be that easy?
3. A short-lived scavenger hunt
4. A smarter, more methodical approach
5. Re-ordering, running, and celebrating

Example input

13 1 0 0
15 0 1 0
6 3 3 1

It represents:

• Executable instructions featuring...
• An opcode, two inputs and an output register

It's time to make use of the second part of the puzzle input.

Why did I think it would be that easy?

• I'll identify the opcodes who's samples only feature one behaving function, I thought
• That will reveal the 16 opcodes, I thought

Nope. Just 1: opcode 2.

Well, that's better than nothing!

A short-lived scavenger hunt

Now that I know the index of the function that represents opcode 2, I can identify opcodes who's samples only feature two behaving functions, and one of them is the function for opcode 1, I thought

That revealed another opcode.

This pattern continued and expanded, until I exhausted samples with fewer than three behaving functions.

Then, a dead end.

A smarter, more methodical approach

• I will create a 16-element array
• Where each element starts as an empty array
• Then, for each sample, I'll identify all behaving functions, record their index - or null if misbehaving - reduce the list to only behaving functions, and insert that list into the array that corresponds to the location of the mystery opcode

With that object filled in, I can analyze each array and perform a process of elimination using a matrix.

Here's an animation of my process:

Re-ordering, running, and celebrating

Now that I know which opcode each function maps to, I can re-order the key-value pairs in my object.

After doing that, I can start with registers as 0,0,0,0 and run the program...this time using the first of the four integers in each instruction!

Viola! The value at register 0 once complete was the correct answer!

I did it!!

• I solved both parts!
• I made a GIF showing how I manually identified each opcode's function!
• I've solved 1/3 known opcode-themed puzzles this year!

Bummer:
No simulator. I made enough Intcode computer simulators in 2019. Plus, this one wasn't going to be that interesting to watch run.

Let's skip ahead to Day 19 for opcode-themed puzzle 2/3.