DEV Community

Cover image for Some Assembly Required
Robert Mion
Robert Mion

Posted on

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
Enter fullscreen mode Exit fullscreen mode
  • 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
Enter fullscreen mode Exit fullscreen mode

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]
}
Enter fullscreen mode Exit fullscreen mode

bitwise OR

OR(A, B, C) {
    wires[C] = wires[A] | wires[B]
}
Enter fullscreen mode Exit fullscreen mode

bitwise compliment a.k.a. NOT

NOT(A, B) {
    wires[B] = ~wires[A]
}
Enter fullscreen mode Exit fullscreen mode

right-shift

RSHIFT(A, N, C) {
    wires[C] = wires[A] >> +N
}
Enter fullscreen mode Exit fullscreen mode

left-shift

LSHIFT(A, N, C) {
    wires[C] = wires[A] << +N
}
Enter fullscreen mode Exit fullscreen mode

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;
}
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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!

Top comments (0)