Some Assembly Required

Advent of Code 2015 Day 7

Part 1

1. The original Assembly-themed puzzle, finally?
2. So many functions!
3. Determining the instruction
4. Building the function store
5. Writing the instruction invoker
6. Hurdle 1: A phased approach
7. Hurdle 2: 32-bit vs. 16-bit
8. Hurdle 3: That's a 1, not an l!
9. Alas, it finishes!

The original Assembly-themed puzzle, finally?

• It must be, right?
• There can't be one after this, right?
• Thankfully, it's a bitwise one instead of an instruction-jumper one
• I recall only one or two others like this, and I learned a bit about bitwise operators while solving them

So many functions!

• bitwise AND
• bitwise OR
• bitwise compliment a.k.a. NOT
• right-shift
• left-shift

Ok, so, just five.

What they are in JavaScript:

• &
• |
• ~
• >>
• <<

Cool! I've only used the first two in previous challenges. The other three are new to me!

Determining the instruction

There seem to be four patterns:

1. A -> B
2. X A -> B
3. A X B -> C
4. A X N -> B

• A, B and C are the registers
• X is the bitwise operator
• N is the amount to shift

It seems I can progressively account for each instruction type, based on:

• Length, at first
• Then whether the third item is alphabetic or numeric

Depending on the instruction length
  If it is 3
    Match for pattern 1
  Else if it is 4
    Match for pattern 2
  Else if it is 5
    If item 3 is alphabetic
      Match for pattern 3
    Else
      Match for pattern 4

It may not be sophisticated or eloquent, but it has worked in the past!

Building the function store

bitwise AND

AND(A, B, C) {
    wires[C] = wires[A] & wires[B]
}

bitwise OR

OR(A, B, C) {
    wires[C] = wires[A] | wires[B]
}

bitwise compliment a.k.a. NOT

NOT(A, B) {
    wires[B] = ~wires[A]
}

right-shift

RSHIFT(A, N, C) {
    wires[C] = wires[A] >> +N
}

left-shift

LSHIFT(A, N, C) {
    wires[C] = wires[A] << +N
}

Writing the instruction invoker

let parts = instruction.split(' ')
switch (parts.length) {
  case 3:
    wires[parts[2]] = +parts[0]
    break;
  case 4:
    instructions.NOT(parts[1], parts[3])
    break;
  case 5:
    instructions[parts[1]](parts[0], parts[2], parts[4])
    break;
}

Since I coerce a string to a number in my RSHIFT and LSHIFT functions, I don't need any additional clauses in my case 5 to separate the shifts from the and/or bitwise operators.

Hurdle 1: A phased approach

In most other assembly-themed puzzles, the instructions state that all registers start with value 0.

Not here, though - in fact, it's much more difficult:

A gate provides no signal until all of its inputs have a signal.

As in most other puzzles, the example input is deceptively easy:

• It's first two instructions set the values of the two registers needed for the next instruction, and it cascades naturally from there

That's not the case with my puzzle input:

• There are 340 instructions
• Only two instructions set values to a register

• Those instructions are near the middle and end of the list

• I need those instructions to get processed first

• Then I need to find instructions where either of those registers are the only inputs

• And repeat until all instructions have been processed

This got unexpectedly complicated very quickly!

Hurdle 2: 32-bit vs. 16-bit

I found this out the hard way:

• The puzzle states that each wire can carry a 16-bit number
• JavaScript's bitwise operators generate and compare 32-bit numbers
• Without knowing this, I was mistakenly getting negative numbers when processing any bitwise NOT instructions, because, for example, the 32-bit bitwise NOT of 123 is -124, not 65412
• After a Google search for generating or converting from 32- to 16-bit numbers, I found a Stack Overflow thread with a very helpful answer

In essence, take my number, and do a bitwise AND using 0xFFFF as the second operand:

~123 -> -124
~123 & 0xFFFF -> 65412

I updated my function store's NOT method.

And all of the other method's, just to be safe.

Hurdle 3: That's a 1, not an l!

A summary of the last hour or so:

• I made an object to track which instructions had been completed
• I made a loop that ran as long as at least one instruction had not yet completed
• For each not-yet-completed instruction, I checked whether it met all the dependencies to be processed based on the length of the elements in the list of instruction parts
• The branching control flow got pretty ugly pretty fast
• At its core was a lot of checks for whether one of the parts is a number or letter(s), and if letter(s), does there exist a wire by that name yet?
• My algorithm ran forever, unfortunately
• It processed 18 instructions, then not another one
• I wasn't sure why at first
• I eventually hunted down the seemingly next instruction that should be processed
• I thought the instruction read: l AND r -> s
• It actually read: 1 AND r -> s
• My algorithm wasn't accounting for a number as the first operand of a bitwise AND instruction
• After further analysis, thankfully, AND is the only instruction (among AND and OR) that has a number as its first operand...and that number is always 1
• I updated my control flow to account for this
• And I updated my function store's AND method to account for a 1 as the first operand

Alas, it finishes!

After accounting for 16-bit numbers and numbers as the first operand of bitwise AND instructions, my loop finished!

Wire a had a value!

It was the correct answer!

Part 2

An easy edit

• I tampered with the input file, changing the only line that stores a value in wire b so the value matched Part 1's correct answer
• I ran my program again
• Wire a had a different value
• It was the correct answer!

I did it!!

• I solved both parts!
• I initially overlooked how complicated Part 1 was!
• I overcame two other significant hurdles: binary number conversion and discerning 1s from ls!
• I wrote some messy code - in my opinion - but got the job done!