Safe Cracking
Tags: adventofcode, algorithms, programming, javascript
Published: 2022-08-12 15:57:46

## [Advent of Code 2016 Day 23](https://adventofcode.com/2016/day/23)

> Author's note: this article features a lot of JavaScript instead of my usual language-agnostic pseudocode

## Part 1
1. That's one complicated `opcode`!
2. Writing my `tgl` method
3. Updating my other `opcode` methods
4. The method that caused me the most grief

### That's one complicated `opcode`!
- What a fun twist: an `opcode` that re-writes an instruction!
- I count six branches of control flow: yikes!
- This could be a beast to code

### Writing my `tgl` method
First, some setup:
- I want to make determining the `arity` of a method easier

```js
let arity = [['inc','dec','tgl'],['cpy','jnz']]
```

Now to write `tgl`.

- I need to store a location and the instruction at that location, if any
- The location will be represented either as a number or a string. If it's a string, I need to look-up the number stored in that register
- In JavaScript, I can conditionally set a value based on the type of data I'm evaluated

```js
// Set arity
tgl(x) {
  let location = pointer + (
    (typeof x == 'number') ? x : registers[x]
  )
  let rule = rules[location]
}
```

Next, I'll account for this rule:
> If an attempt is made to toggle an instruction outside the program, nothing happens.

- In JavaScript, when I attempt to access an array index that does not exist, the program returns `undefined`, a false-y value

```js
tgl(x) {
  // Set location and rule
  if (rule) {
    // The target instruction is inside the program
  } else {
    // The target instruction is outside the program
  }
}
```

Next, I'll account for these rules:
> For one-argument instructions, `inc` becomes `dec`, and all other one-argument instructions become `inc`. For two-argument instructions, `jnz` becomes `cpy`, and all other two-instructions become `jnz`.

In my algorithm, `rule` will be an array containing either two or three elements, where the first element is guaranteed to be a three-letter string: one of the `opcodes`.

I can check the first element - at index `0` - for inclusion in `arity` to dictate whether it is a one- or two-argument instruction.

```js
// Set arity
tgl(x) {
  // Set location and rule
  if (rule) {
    if (arity[0].includes(rule[0]) {
      // Account for one-argument instructions
    } else if (arity[0].includes(rule[0]) {
      // Account for two-argument instructions
    }
  }
}
```

Inside each branch, I'll use a `switch` statement to dictate which of two `cases` to use when updating each target instruction's `opcode`.

```js
if (arity[0].includes(rule[0]) {
  // Account for one-argument instructions
  switch (rule[0]) {
    case "inc":
      rules[location][0] = "dec"
      break;
    default:
      rules[location][0] = "inc"
      break;
  }
} else if (arity[0].includes(rule[0]) {
  // Account for two-argument instructions
  switch (rule[0]) {
    case "jnz":
      rules[location][0] = "cpy"
      break;
    default:
      rules[location][0] = "jnz"
      break;
  }
}
```

Lastly for `tgl`, I need to move `pointer` forward.

My original method had an `else` branch associated with the `if` that checked whether `rule` was `undefined`.

I don't need that `else` branch, since all it was going to do was increment `pointer`...and I need to do that regardless of what `rule` is.

```js
// Set arity
tgl(x) {
  // Set location and rule
  if (rule) {
    // All code written thus far
  }
  pointer++
}
```

Next, I need to update all other `opcode` methods to account for these new possible argument data types.

### Updating my other `opcode` methods
The major change is small, but important, and based on this impact from `tgl`:
> If toggling produces an invalid instruction (like cpy 1 2) and an attempt is later made to execute that instruction, skip it instead.

In each of the four other methods, I'll add this condition:
```
If the type of the argument being written to is a number
  Increment pointer by 1
```

For `cpy`, the argument is `y`.

For `inc`, `dec` and `jnz`, the argument is `x`.

### The method that caused me the most grief
It was `jnz`.

This was my original method:
```js
jnz(x,y) {
  if (typeof x == 'number') {
    x !== 0 ? pointer += y : pointer++
  } else {
    registers[x] !== 0 ? pointer += y : pointer++
  }
}
```

How I discovered it was `jnz` that was misbehaving:
- My program terminated near-instantly
- `42` was stored in register `a`
- That was not the correct answer
- I added logging statements to the `tgl` method
- My puzzle input only had one `tgl` instruction
- The first and only time `tgl` ran, `rule` was `undefined`
- That's because the location of the instruction to be modified was outside of the bounds of the rules list
- The next instruction was `cpy` - no issue
- The next instruction was `jnz`
- More exact: `jnz 1 c`
- By now, register `c` contained `16`

Walking through my `jnz` method:
```
jnz(x=1,y='c')

1 is a number
  1 is not 0 ? pointer += 'c'

pointer was 18

pointer += 'c'

pointer is now '18c'

That's not good!
```

I could not depend on `y` always being a number.

Instead, I need to check its type, and either change `pointer` by a number or the number associated with a register.

My updated, working method:
```js
jnz(x,y) {
  if (typeof x == 'number') {
    x !== 0 ? pointer += (
      (typeof y == 'number') ? y : registers[y]
    ) : pointer++
  } else {
    registers[x] !== 0 ? pointer += (
      (typeof y == 'number') ? y : registers[y]
    ) : pointer++
  }
}
```

After making this change, my algorithm took a few seconds to run.

After terminating, register `a` stored a value over 10,000.

That was the correct answer!

## Part 2
1. Great, my least favorite exercise
2. What am I supposed to do this that implication?
3. Investigating as best I can

### Great, my least favorite exercise
- Once again, an `opcode` challenge that seemingly requires that I diagnose the parts of the program that cause the program to take so long to terminate
- I've failed to successfully do this in all prior exercises in other years
- I don't anticipate being successful this time, either
- But I've got to try!

### What am I supposed to do this that implication?
The author posits:
> ...whether the lack of any instruction more powerful than "add one" has anything to do with (the program taking so long to terminate). Don't bunnies usually multiply?

- Am I supposed to change my `inc` method to increase the appropriate register's value by a more substantial amount?
- I'm pretty sure I'm not expected to change the rules
- I know I must start with register `a` as `12`
- I could attempt to start other registers with a value other than `0`, but that doesn't seem correct

Perhaps I should attempt to identify the part of the program that recycles the most.

### Investigating as best I can
- I tried logging a few different things
- I noticed register `d` repeatedly becoming exponentially larger and slowly return to `0`
- And I noticed register `a` repeatedly fluctuating at a faster rate
- While registers `b` and `c` seemed to not change nearly as much
- But, ultimately, I didn't find any significant hook into deriving an answer

### Finding the answer on Reddit
I'm grateful for [one commenter](https://www.reddit.com/r/adventofcode/comments/5jvbzt/comment/dbjbqtq/?utm_source=share&utm_medium=web2x&context=3) sharing the shortcut to the solution:
- Find the `cpy` and `jnz` instruction pair toward the end of the program featuring double-digit `x` arguments
- Calculate the sum of the factorial of `12` and the product of both those double-digit numbers

For me, that looks like:
```
cpy 73 c
jnz 82 d

12! + (73 * 82)
---------------
      479007586
```

I am not going to submit it, though, since I didn't arrive upon the answer without help.

However, it is fun knowing the answer was 'staring me in the face' the whole time...like it usually is!

## Celebrating my accomplishments
- I solved Part 1!
- By troubleshooting and identifying the misbehaving method!
- Then by writing, debugging and re-testing that method until no further errors appeared!
- Thanks to one reddit solver, I discovered what is highly likely the correct answer to Part 2!

Although today's puzzle featured a fun challenge in implementing the `tgl` opcode, I'm hopeful that Day 25 features the last of this theme of puzzle among this year and 2015.

Onward to the third and hopefully final round of this year's `opcode` puzzles!