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
- That's one complicated
opcode
! - Writing my
tgl
method - Updating my other
opcode
methods - 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
becomesdec
, and all other one-argument instructions becomeinc
. For two-argument instructions,jnz
becomescpy
, and all other two-instructions becomejnz
.
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 registera
- 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
wasundefined
- 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
contained16
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
- Great, my least favorite exercise
- What am I supposed to do this that implication?
- 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
as12
- 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 to0
- And I noticed register
a
repeatedly fluctuating at a faster rate - While registers
b
andc
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
andjnz
instruction pair toward the end of the program featuring double-digitx
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!
Top comments (0)