Chronal Classification
Tags: adventofcode, algorithms, computerscience, programming
Published: 2022-06-06 19:54:24

## [Advent of Code 2018 Day 16](https://adventofcode.com/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.
```js
/\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()`:
```js
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:
![Identifying each opcode using a matrix](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/ogyvtk66ez45dl1bndrf.gif)

### 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.