Advent of Code 2015 - Day 7

Day 7: Some Assembly Required

Useful Links

‹›

• 2015 Main Page
• My solution code

Concepts and Packages Demonstrated

Parsimonious (PEG)binary and hexadecimalBinary and Other BasesenumerateLambda functions

Problem Intro

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

Part 1

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:

1. Process the instructions from top to bottom. For each instruction:
   • If we are able to process the instruction (because all required inputs have values), then process the instruction, and then pop it (remove it) from the instruction list. This instruction is done.
   • If we are unable to process the instruction (because we don’t have all required input values), then we don’t pop it yet.
2. For as long as we have instructions left, go back to 1.

Solution Code

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:

• Each line describes rules for validating the input.
• Within each line, individual terms are separated by a single white space character.
• The first line - called 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.
• We define an input as either a number or a wire, followed by some whitespace.
• We define an op as one of AND, OR, LSHIFT, RSHIFT, and NOT, followed by some whitespace.
• We defined a number as one or more digits. We use simple regex to achieve this, and escape the regex with ~r.
• We define a literal constant called feeds, which is set to the value -> .
• We define a wire as one or two alphabetical characters. We use regex to achieve this.
• We define 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] # store our known wire values
        
        # 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 a 16 bit mask of all 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…

• The parse() method expects two arguments:
  1. The current instruction line to be parsed. E.g. 456 -> y.
  2. A dict containing all the wires that have known signal values.
• The parse() method then:
  • Initialises some instance variables. This includes setting the private instance variable _processing_input to True. This signals that whenever we parse a wire, we should treat it as an input, rather than a target wire.
  • It then calls 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.
    • Any complete instruction should match expr, which results in visit_expr() being fired.
    • When the parser matches 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:
  • If _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.
  • If _processing_input is False, then we set the _target_wire to be this particular wire str.
• Finally - assuming we didn’t exit parsing with a VisitationError - we return to the parse() method. We are now able to perform our logic gate operation, since we now have all required inputs. We can now perform the desired bitwise operation. We then return our output value.

That’s most of the hard work done. Now all we need to do is implement the strategy; i.e. to process the full set of instructions, processing those that we can, and parking those that we can’t until the next iteration. Here’s how we do that:

def process_instructions(instructions, blc_visitor):
    wire_values = {}

    # treat all our input as a stack.  
    # Some input values will not be known yet, so park these instructions and try on the next iteration
    while instructions:
        for i, line in enumerate(instructions):
            try:
                wire_values.update(blc_visitor.parse(line, wire_values))
                # if we're here, the instruction parsed successfully, so remove it from the stack permanently
                popped = instructions.pop(i)
                logger.debug("Processed: %s", popped)
            except (ParseError, VisitationError):
                # If the parser tries to retrieve a wire value that is not yet known
                # a KeyError is thrown, caught, and rethrown as a VisitationError, which we catch here.
                # This instruction can't be processed yet, as we don't have all necessary input values
                continue

        # We're ready to process the list again. 
    
    return wire_values

This is a function that takes our instructions as the first parameter, and an instance of our BitwiseLogicVisitor as the second parameter.

We then iterate through the instructions, line-by-line, enumerating as we go. For each instruction:

• Attempt to parse using our BitwiseLogicVisitor. Pass in all wire values that we’ve determined so far.
• If the parse succeeds, then:
  • The parse() method will return a value for a new wire.
  • We add this wire:value pair to the existing wire_values dictionary.
  • We pop() the current instruction from the list of instructions. I.e. we’re removing this instruction line so that it won’t be processed again.
• If we’re trying to perform an instruction using a wire that we don’t know the value of, then this will cause a KeyError to be generated in the visit_wire() method of the BitwiseLogicVisitor. I.e. when we try to obtain the value of a key that doesn’t exist in the dictionary. This is thrown as a VisitationError, which we catch.

Once we’ve processed all the instruction lines, we then start again with all remaining instructions. We keep doing this until no instructions remain.

The final solution looks like this:

import logging
import os
import time
import re
from parsimonious import Grammar, NodeVisitor, ParseError, VisitationError

logging.basicConfig(format="%(asctime)s.%(msecs)03d:%(levelname)s:%(name)s:\t%(message)s", 
                    datefmt='%H:%M:%S')
logger = logging.getLogger(__name__)
logger.setLevel(logging.INFO)

SCRIPT_DIR = os.path.dirname(__file__) 
INPUT_FILE = "input/input.txt"
SAMPLE_INPUT_FILE = "input/sample_input.txt"

# define the grammar rules
# EXPR matches any whole line, e.g. 'k AND m -> n'
# Note, wires can be one or two chars in name, e.g. a, aa, xy.
grammar = Grammar(r"""
    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"
""")

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

def main():
    # input_file = os.path.join(SCRIPT_DIR, SAMPLE_INPUT_FILE)
    input_file = os.path.join(SCRIPT_DIR, INPUT_FILE)
    with open(input_file, mode="rt") as f:
        data = f.read().splitlines()

    blc_visitor = BitwiseLogicVisitor()
    blc_visitor.grammar = grammar

    # Part 1
    # Pass in a copy of the input data, as we'll need to parse it again for Part 2
    results = process_instructions(data.copy(), blc_visitor)
    a_val = results['a']
    logger.info("Part 1: Value of input a is %s", a_val)

def process_instructions(instructions, blc_visitor):
    wire_values = {}

    # treat all our input as a stack.  
    # Some input values will not be known yet, so park these instructions and try on the next iteration
    while instructions:
        for i, line in enumerate(instructions):
            try:
                wire_values.update(blc_visitor.parse(line, wire_values))
                # if we're here, the instruction parsed successfully, so remove it from the stack permanently
                popped = instructions.pop(i)
                logger.debug("Processed: %s", popped)
            except (ParseError, VisitationError):
                # If the parser tries to retrieve a wire value that is not yet known
                # a KeyError is thrown, caught, and rethrown as a VisitationError, which we catch here.
                # This instruction can't be processed yet, as we don't have all necessary input values
                continue

        # We're ready to process the list again. 
    
    return wire_values

if __name__ == "__main__":
    t1 = time.perf_counter()
    main()
    t2 = time.perf_counter()
    print(f"Execution time: {t2 - t1:0.4f} seconds")

Part 2

We need to take the value of a that we’ve just determined, set b to that value, reset all the other wires and then repeat all the instructions. And, as before, determine what value is now emitted on wire a.

So, we want to find the single instruction in the instruction list that sets the value of wire b. We want to replace this instruction so that it instead sets b to the value we obtained for wire a in Part 1.

This is pretty easy and doesn’t require many extra lines:

    # Part 2
    wire_b_instr = list(filter(re.compile(r"-> b$").search, data)) # return only rows that match
    assert len(wire_b_instr) == 1, "There should only be one matching instruction"
    wire_b_instr_index = data.index(wire_b_instr[0])  # the position of this instruction in the list
    data[wire_b_instr_index] = f"{a_val} -> b"  # replace the instruction with this new one

    results = process_instructions(data.copy(), blc_visitor)
    logger.info("Part 2: Value of input a is %s", results['a'])

How this works:

• We use some regex to look for any string that ends in -> b. This is to identify the single instruction that sets the value of b. The regex search() function returns a match object, if the regex matches.
• We wrap our regex search() inside a call to filter(). Recall that when we filter, the filter() method expects the first parameter to be a function that returns a boolean. The search() method evaluates to False if there are no matches, but True if there is a match. Thus, we use filter to extract only instructions (from data) where the regex evaluates to True.
• This should only be true for one single line in the instructions. We can assert this is true using aasert, as described here.
• We use the index() method of the our data list to identify the location of our -> b instruction.
• Then we replace this instruction with a new instruction, i.e. one that sets b to the value of a that we determined in Part 1.
• Finally, we repeat our call to process_instructions().
• Note how we always take a copy() of the instructions we pass in (called data). This ensures that if we make any changes to data in our process_instructions() function - which we do because of all the popping - then these changes are not persisted between Part 1 and Part 2.

No other changes to the program are required.

The output looks like this:

23:18:16.560:INFO:__main__:     Part 1: Value of input a is 16076
23:18:17.395:INFO:__main__:     Part 2: Value of input a is 2797
Execution time: 1.7042 seconds

And that’s all we need to do.

‹›