Some Assembly Required
Tags: adventofcode, algorithms, programming, javascript
Published: 2022-09-21 15:31:14

## [Advent of Code 2015 Day 7](https://adventofcode.com/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`
```js
AND(A, B, C) {
    wires[C] = wires[A] & wires[B]
}
```
#### `bitwise OR`
```js
OR(A, B, C) {
    wires[C] = wires[A] | wires[B]
}
```
#### `bitwise compliment` a.k.a. `NOT`
```js
NOT(A, B) {
    wires[B] = ~wires[A]
}
```
#### `right-shift`
```js
RSHIFT(A, N, C) {
    wires[C] = wires[A] >> +N
}
```
#### `left-shift`
```js
LSHIFT(A, N, C) {
    wires[C] = wires[A] << +N
}
```

### Writing the instruction invoker
```js
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](https://stackoverflow.com/a/37774134)

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 `1`s from `l`s!
- I wrote some messy code - in my opinion - but got the job done!