Opening the Turing Lock

Advent of Code 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

2020

• Day 8: Handheld Halting

2019

• Day 25: Cryostasis
• Day 23: Category Six
• Day 21: Springdroid Adventure
• Day 19: Tractor Beam
• Day 17: Set and Forget
• Day 15: Oxygen System
• Day 13: Care Package
• Day 11: Space Police
• Day 9: Sensor Boost
• Day 7: Amplification Circuit
• Day 5: Sunny with a Chance of Asteroids
• Day 2: 1202 Program Alarm

2018

• Day 21: Chronal Conversion
• Day 19: Go With The Flow
• Day 16: Chronal Classification

2017

• Day 23: Coprocessor Conflagration
• Day 18: Duet
• Day 8: I Heard You Like Registers
• Day 5: A Maze of Twisty Trampolines, All Alike

2016

• Day 25: Clock Signal
• Day 23: Safe Cracking
• Day 12: Leonardo's Monorail

2015

• Day 23: Opening the Turing Lock
• 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

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

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

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

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

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

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

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

function jmp(offset) {
  pointer += offset
}

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

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)

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:

/(\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:

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!