Safe Cracking

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

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

// 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

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.

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

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.

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

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:

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 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!