Advent of Code 2015 Day 7
Part 1
- The original Assembly-themed puzzle, finally?
- So many functions!
- Determining the instruction
- Building the function store
- Writing the instruction invoker
- Hurdle 1: A phased approach
- Hurdle 2: 32-bit vs. 16-bit
- Hurdle 3: That's a
1
, not anl
! - 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
andC
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 bitwiseNOT
of123
is-124
, not65412
- 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 (amongAND
andOR
) 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 a1
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 froml
s! - I wrote some messy code - in my opinion - but got the job done!
Top comments (0)