Dazbo's Advent of Code solutions, written in Python
We’re told that we have wires - identified by lowercase letters - which carry 16 bit signals. A signal is provided to each wire by a gate, another wire, or a specific value. Wires can only take a single input signal, but can provide a signal to multiple destinations. The gates are:
Gate | Meaning |
---|---|
x AND y |
Bitwise AND of x and wy |
x OR y |
Bitwise OR of x and y |
x LSHIFT y |
Left-shift x by y positions |
x RSHIFT y |
Right-shift x by y positions |
NOT x |
Bitwise complement of x |
Gates will only provide an ouput signal when all of its inputs have a signal.
Instructions look like this:
123 -> x
x AND y -> d
x OR y -> e
456 -> y
x LSHIFT 2 -> f
y RSHIFT 2 -> g
NOT x -> h
NOT y -> i
What signal is ultimately provided to wire a?
What we need to do is process each instruction in the input.
The challenge is that some instructions can be processed straight away, but some cannot. Specifically: if an instruction refers to any wires that do not yet have a value, then that instruction can not be processed yet. To explain this further, look at the example instructions above. We can process this instruction straight away:
123 -> x
But we can’t yet process these instruction, because we don’t yet have a value for y
:
x AND y -> d
x OR y -> e
But the next instruction sets our value for y
:
456 -> y
So if we process the instructions for a second time, we will be able to process those two instructions that were previously blocked.
Thus, my strategy is:
We could now write some regex to parse each instruction, determine the instruction type, and take action accordingly. But we’ve done some of that already, so I thought it would be more fun to use a cool library.
Here we’re going to use Parsimonious. This is a library that allows the depth-first parsing of grammars, i.e. the capability to recognise language terms, and follow rules depending on those terms.
Think of it like regex on steroids, since it has the ability to recognise specific language terms, but also recurse into those terms.
First, let’s install Parsimonious:
py -m pip install parsimonious
Now let’s write a grammar, i.e. some language that describes the instructions we need to parse:
expr = input? (op input)? feeds wire
input = (number / wire) ws+
op = ("AND" / "OR" / "LSHIFT" / "RSHIFT" / "NOT") ws+
number = ~r"\d+"
feeds = "-> "
wire = ~r"[a-z]{1,2}"
ws = ~r"\s"
What does it mean? Well, check out the Parsimonious Syntax Reference to get an understanding of how this grammar is constructed. But let’s break it down, line-by-line:
expr
- will be used to parse the entirety of each instruction. This rule checks that we have zero or more input
elements, followed by zero or more combinations of op input
, followed by a mandatory feeds
, followed by a mandatory wire
.input
as either a number
or a wire
, followed by some whitespace.op
as one of AND
, OR
, LSHIFT
, RSHIFT
, and NOT
, followed by some whitespace.number
as one or more digits. We use simple regex to achieve this, and escape the regex with ~r
.feeds
, which is set to the value ->
.wire
as one or two alphabetical characters. We use regex to achieve this.ws
as some whitespace, using regex. We’ve made a variable for this, since whitespace is used frequently throughout the grammar.Hopefully it’s now apparent how this set of rules can be used to validate and parse our input instructions.
Now we need to write the class that will actually parse the input lines, according to our grammar, and return the resulting output wire value. We do this by extending the NodeVisitor
class, which is supplied by the parsimonious package.
class BitwiseLogicVisitor(NodeVisitor):
""" PEG Parser for processing the Bitwise instructions """
# override the parse method, to initialise instance variables and perform the bitwise logic
def parse(self, *args):
"""
Arguments
args[0] - the str to be parsed. E.g. 'k AND m -> n'
args[1] - a dict of known wire values
Returns:
[dict] - output wire:value
Raises:
ParseError, VisitationError
"""
self._wires_dict = args[1]
# These instance variables are updated after we parse the input line
self._inputs = [] # store int input values, left of the '->'. E.g. [7102, 65023]
self._op = "" # E.g. AND
self._target_wire = "" # E.g. n
self._processing_input = True # Set to False after we process the '->'
self._output = {} # Initialise empty wire:value dict
# Parse out input line, calling our visit_xxx methods
# This will update our instance variables
super().parse(args[0])
# perform bitwise operation on the values in the _inputs list
if "AND" in self._op:
res = self._inputs[0] & self._inputs[1]
elif "OR" in self._op:
res = self._inputs[0] | self._inputs[1]
elif "LSHIFT" in self._op:
res = self._inputs[0] << self._inputs[1]
elif "RSHIFT" in self._op:
res = self._inputs[0] >> self._inputs[1]
elif "NOT" in self._op:
# The ~ operator in Python may return a signed -ve value.
# We don't want this, so we & with 16 bit of 1s to convert to +ve representation
res = ~self._inputs[0] & 0xFFFF
else:
# Where there is no op. E.g. '19138 -> b'
res = sum(self._inputs)
self._output[self._target_wire] = res
# logger.debug("Inputs were: %s, op was: %s, result: %s", self._inputs, self._op, self._output)
# Wire name and wire value, as dict
return self._output
def visit_expr(self, node, visited_children):
# here we can print the overall expr being parsed
# logger.debug("EXPR Node:\n%s\nVisited_children: %s", node, visited_children)
pass
def visit_feeds(self, node, visited_children):
""" Handle '-> '
Change state so that the next wire we parse is treated as output
"""
self._processing_input = False
def visit_op(self, node, visited_children):
""" Handle "AND" / "OR" / "LSHIFT" / "RSHIFT" / "NOT"
"""
self._op = node.text.strip()
return self._op
def visit_number(self, node, visited_children):
""" A numeric input value """
number = int(node.text)
self._inputs.append(number)
return number
def visit_wire(self, node, visited_children):
""" Handle ~r"[a-z]{1,2}"
A wire is always passed as a str designation. E.g. 'lf'
Use the _wires_dict to get the numeric value for this wire.
If we don't have a value, this will result in a KeyError,
which will be caught and thrown as a VisitationError. """
wire = node.text.strip()
if (self._processing_input):
# if we have an input wire, then try to extract its numeric value
self._inputs.append(self._wires_dict[wire])
else: # otherwise, this is an output wire
self._target_wire = wire
return wire
def generic_visit(self, node, visited_children):
return visited_children or node
Here’s how it works…
parse()
method expects two arguments:
456 -> y
.dict
containing all the wires that have known signal values.parse()
method then:
_processing_input
to True
. This signals that whenever we parse a wire
, we should treat it as an input
, rather than a target wire.super().parse()
, and passes in the current instruction line. This causes the BitwiseLogicVisitor
to fire the appropriate visit_xxxx()
method, for each string it matches from the grammar. E.g.
expr
, which results in visit_expr()
being fired.feeds
, it fires the visit_feeds()
method.Let’s look at what some of these visit_xxxx
methods do:
visit_feeds
sets the private variable _processing_input
to False
. As a result, the next wire that is parsed will be treated as the target wire, not an input wire.visit_op
stores the operation type.visit_number
converts the str
repesentation of the number to an int
, and stores it in the _inputs
list.visit_wire
:
_processing_input
is True
, this method attempts to obtain the signal value stored in this input wire. If this wire currently has no value, then the dict lookup will cause a KeyError
, which is thrown by the class as a VisitationError
._processing_input
is False
, then we set the _target_wire
to be this particular wire str.VisitationError
- we return to the parse()
method. We are now able to perform our logic gate operation, since we now have all required inputs.