Opening the Turing Lock
Tags: adventofcode, algorithms, programming, javascript
Published: 2022-09-05 23:52:21

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

## Part 1
1. Assembly-code-themed puzzle memory lane
2. Coding the registers and instructions
3. Processing the puzzle input
4. Writing the main loop

### Assembly-code-themed puzzle memory lane
#### 2021
- [Day 24: Arithmetic Logic Unit](https://adventofcode.com/2021/day/24)

#### 2020
- [Day 8: Handheld Halting](https://adventofcode.com/2020/day/8)

#### 2019
- [Day 25: Cryostasis](https://adventofcode.com/2019/day/25)
- [Day 23: Category Six](https://adventofcode.com/2019/day/23)
- [Day 21: Springdroid Adventure](https://adventofcode.com/2019/day/21)
- [Day 19: Tractor Beam](https://adventofcode.com/2019/day/19)
- [Day 17: Set and Forget](https://adventofcode.com/2019/day/17)
- [Day 15: Oxygen System](https://adventofcode.com/2019/day/15)
- [Day 13: Care Package](https://adventofcode.com/2019/day/13)
- [Day 11: Space Police](https://adventofcode.com/2019/day/11)
- [Day 9: Sensor Boost](https://adventofcode.com/2019/day/9)
- [Day 7: Amplification Circuit](https://adventofcode.com/2019/day/7)
- [Day 5: Sunny with a Chance of Asteroids](https://adventofcode.com/2019/day/5)
- [Day 2: 1202 Program Alarm](https://adventofcode.com/2019/day/2)

#### 2018
- [Day 21: Chronal Conversion](https://adventofcode.com/2018/day/21)
- [Day 19: Go With The Flow](https://adventofcode.com/2018/day/19)
- [Day 16: Chronal Classification](https://adventofcode.com/2018/day/16)

#### 2017
- [Day 23: Coprocessor Conflagration](https://adventofcode.com/2017/day/23)
- [Day 18: Duet](https://adventofcode.com/2017/day/18)
- [Day 8: I Heard You Like Registers](https://adventofcode.com/2017/day/8)
- [Day 5: A Maze of Twisty Trampolines, All Alike](https://adventofcode.com/2017/day/5)

#### 2016
- [Day 25: Clock Signal](https://adventofcode.com/2016/day/25)
- [Day 23: Safe Cracking](https://adventofcode.com/2016/day/23)
- [Day 12: Leonardo's Monorail](https://adventofcode.com/2016/day/12)

#### 2015
- [Day 23: Opening the Turing Lock](https://adventofcode.com/2015/day/23)
- Others???

### Coding the registers and instructions
> The computer supports two registers and six instructions. The registers are named a and b, can hold any non-negative integer, and begin with a value of 0

```js
let registers = { 'a': 0, 'b': 0 }
let instructions = { } // store all six methods
let pointer = 0
```

The instructions are as follows:
> `hlf r` sets register `r` to half its current value, then continues with the next instruction

```js
function hlf(r) {
  registers[r] /= 2
  pointer++
}
```

> `tpl r` sets register `r` to triple its current value, then continues with the next instruction

```js
function tpl(r) {
  registers[r] *= 3
  pointer++
}
```

> `inc r` increments register `r`, adding 1 to it, then continues with the next instruction

```js
function inc(r) {
  registers[r]++
  pointer++
}
```

> `jmp offset` is a jump; it continues with the instruction `offset` away relative to itself

```js
function jmp(offset) {
  pointer += offset
}
```

> `jie r, offset` is like `jmp`, but only jumps if register `r` is even ("jump if even")

```js
function jie(r, offset) {
  registers[r] % 2 == 0 ? jmp(offset) : jmp(1)
}
```

> `jio r, offset` is like `jmp`, but only jumps if register `r` is `1` ("jump if one", not odd)

```js
function jio(r, offset) {
  registers[r] == 1 ? jmp(offset) : jmp(1)
}
```

The last two functions were a bit confusing:
- Neither one specifies what to do if the register's value is 0, other than `not jump`
- Does that mean stay at the same instruction?
- How could it, though, when that would just cause an infinite loop?
- I think the program should proceed to the next instruction

Proof that I'm thinking correctly:
- The first line of my puzzle input is `jie a, +16`
- Per the instructions, `a` starts at `0`
- Which would cause the instruction not the jump under the circumstances of my initial thinking: don't move pointer at all
- Which would cause the program to never end

So, I'm pretty sure the pointer should move forward by one for both of these functions

### Processing the puzzle input
My puzzle input features instructions like these:
```
jio a, +16
inc a
tpl a
jmp +23
jio a, +8
inc b
jie a, +4
jmp +2
hlf a
jmp -7
```

The last instruction is the only negative offset.

Otherwise, the pattern goes: 
- Three letters and space
- Letter or negative/positive digit  
- Optional comma and space and negative/positive digit

Will it be easier to use a regular expression or split each instruction and process the results using a series of control flows?

I think I'll try `regex` first.

#### Using a `regex`
Well, this is overly specific and messy, but it captures everything I need:
```js
/(\w{3}) ([ab\-\+]\d*),? ?([\-\+]*\d*)/g
```
- `\w{3}` matches three letters
- `[ab\-\+]` matches `a`,`b`,`-` or `+`
- `\d*` matches 0 or more numbers
- `,? ?` matches an optional comma and optional space
- `[\-\+]*` matches 0 or more `-` or `+`
- `\d*` matches 0 or more numbers
- Three capture groups `( )` results in minimum of two being filled with the correct values and an occasional empty capture group for instructions other than `jie` and `jio`

Since this `regex` suits my needs, I don't need to resort to string splitting or manipulation.

### Writing the main loop
> The program exits when it tries to run an instruction beyond the ones defined

My algorithm in pseudocode:
```
Do as long as pointer is within the bounds of the list of instructions
  Extract the three captured groups from the regex
  Call the proper method in instructions
    Passing as arguments either the name of the register or the number
Return the value stored in register 'b'
```

My algorithm in JavaScript:
```js
let program = input.split('\n')
let lines = program.length
while (pointer >= 0 && pointer < lines) {
  let [a, b, c] = [
    ...program[pointer]
      .matchAll(
        /(\w{3}) ([ab\-\+]\d*),? ?([\-\+]*\d*)/g
      )
  ][0].slice(1,4)
  instructions[a](isNaN(+b) ? b : +b, isNaN(+c) ? c : +c)
}
return registers['b']
```

It generated the correct answer for Part 1!

## Part 2

### What a relief!
I've seen this before:
- Change a register's starting value
- Re-run the program until termination
- What value is stored in a particular register?

Usually this requires the program to run billions of times.

So, instead, I would have to study how the program works in order to identify what some value would ultimately become.

Thankfully, this was an easy win!
- I changed the register's value
- Re-ran the program
- It terminated immediately
- And generated the correct answer!

## I did it!!
- I solved both parts!
- Of what I hope is the last - first? - Assembly-code-themed puzzle!
- And also, honestly, the easiest!