Advent of Code 2015 - Day 7 - Some Assembly Required

31 Jan 2021

On the seventh day of Advent of Code 2015 we are tasked with helping little Bobby Tables assemble a circuit (wires and bitwise logic gates) that Santa brought him for Christmas.

Part 1

Our input is an instruction booklet which describes how to connect these parts together. Based on following the instructions laid out in the booklet we are asked to provide what signal is ultimately provided to wire a. Like before, we will start off by parsing the input into a useable form within our solution.

type Wire = string;
type Instruction = string;
type Circuit = Map<Wire, Instruction>;

const parseCircuit = (input: string): Circuit =>
  input.split('\n').reduce((circuit, line) => {
    const [instruction, wire] = line.split(' -> ');
    return circuit.set(wire, instruction);
  }, new Map());

The parser above converts the instruction listing into a Circuit mapping between the defined Wire and associated actionable Instruction (i.e. bitwise operation, assignment). With the input now parsed we can move on to working out how we wish to emulate this circuit and record the outputted signals. Reviewing the input leads us to the conclusion that we can not expect the instructions to be in dependency order like the provided example is - i.e. b is declared and assigned almost at the end of the listing, but is referenced many times before this. Taking this on board, and as we only wish to work out what a single wire signal is; my initial solution is to begin at wire a’s instruction and recursively build up the resulting signal result. In doing so this will cater for the unsorted ordering, and only perform the instructions that are required to answer the question.

const getEmulatedSignal = (circuit: Circuit, wire: Wire): number => {
  const emulate = memoize((wire: Wire): number => {
    if (/^(\d)+$/.test(wire)) {
      return toInt(wire);
    }

    const instruction = circuit.get(wire).split(' ');

    switch (true) {
      case instruction.includes('AND'):
        return emulate(instruction[0]) & emulate(instruction[2]);
      case instruction.includes('OR'):
        return emulate(instruction[0]) | emulate(instruction[2]);
      case instruction.includes('LSHIFT'):
        return emulate(instruction[0]) << emulate(instruction[2]);
      case instruction.includes('RSHIFT'):
        return emulate(instruction[0]) >> emulate(instruction[2]);
      case instruction.includes('NOT'):
        return ~emulate(instruction[1]) & 0xffff;
      default:
        return emulate(instruction[0]);
    }
  });

  return emulate(wire);
};

Based on the currently supplied wire identifier we provide a base-case of asserting that if the string value is an number that we simply return the integer equivalent. All instructions laid out will eventually hit this base-case, ensuring that the recursion will stop and the callstack tails can be evaluated. Upon experimentation with this apppoach I noticed that performance was a big issue when attempting to run this on the actual input instruction booklet. Upon review, due to naively recursing over all instructions, there was the case that seen instructions would be required to be re-evaluated down many different branches. To resolve this I employed a small generic memoization function which wrapped the closure and opaquely provided a caching mechanism for subsequent calls to the same resolved wire signal.

You will also notice the use of a 0xffff mask when applying the NOT operation on the value. As explained in the question the signals are unsigned 16-bit values, however, JavaScript bitwise operators use 32-bits. So as to produce the desired results we are required to only consider the 16-bit mask supplied.

const part1 = (input: string): number =>
  getEmulatedSignal(parseCircuit(input), 'a');

With the logic in-place we can combine the two functions together and determine what the resulting signal is from wire a 🌟.

Part 2

For part two we are required to replace the original inputs wire b value with the resulting signal that we emulated in part one for wire a. From this, we are the asked to determine what the resulting signal is now from wire a.

const part2 = (input: string): number => {
  const circuit = parseCircuit(input);
  circuit.set('b', getEmulatedSignal(circuit, 'a').toString());
  return getEmulatedSignal(circuit, 'a');
};

Splitting out and modifying the parsed circuit mapping before getting the newly emulated signal provides us with the desired answer 🌟.

Alternative Solution

Since solving this problem, I re-evaluated the provided input and noticed that it did not include any circular dependencies! As such, it could be treated as a Directed acyclic graph (DAG) of which we then would be able to perform a Topological Sort on to return the correctly ordered instruction listing. This would allows us to emulate the circuit without the need for recursion. I set out to re-implement the solution using this new found knowledge and approach.

I began by creating the below function which parses the instruction listing in a very different manor than before. Instead of simply returning the parsed instructions in an unordered map back to the callee, this function returns an array of the correctly ordered instruction execution. Correctness in this case means that all required wire signal values will have already been emulated before attempting to evaluate the given wire instruction. As such, we can just iterate through the instruction listing once to return the entire signal value outputs.

type Wire = string;
type Instruction = string[];

const createInstructionExecutionOrder = (
  input: string
): [Wire, Instruction][] => {
  const dependencies = new Map<Wire, Wire[]>();
  const instructions = new Map<Wire, Instruction>();

  for (const line of input.split('\n')) {
    const [instruction, wire] = line.split(' -> ');
    dependencies.set(wire, instruction.match(/([a-z]+)/g) || []);
    instructions.set(wire, instruction.split(' '));
  }

  const visited = new Set<Wire>();
  const ordered: Wire[] = [];

  [...dependencies.keys()].forEach(function dfs(wire: Wire) {
    if (visited.has(wire)) return;
    visited.add(wire);
    dependencies.get(wire).forEach(dfs);
    ordered.push(wire);
  });

  return ordered.reduce(
    (wires, wire) => [...wires, [wire, instructions.get(wire)]],
    []
  );
};

Treating the instruction booklet as a DAG allows us to perform the Topological Sort (optting for the Depth-First Search approach) and return the ordered instructions. With this in hand we now need a means to emulate and return the signal value for a given wires instruction - based on the signal mapping that we have built up to that point.

type Signals = Map<Wire, number>;

const emulate = (signals: Signals, instruction: Instruction): number => {
  const get = (token: string): number =>
    signals.has(token) ? signals.get(token) : toInt(token);

  switch (true) {
    case instruction.includes('AND'):
      return get(instruction[0]) & get(instruction[2]);
    case instruction.includes('OR'):
      return get(instruction[0]) | get(instruction[2]);
    case instruction.includes('LSHIFT'):
      return get(instruction[0]) << get(instruction[2]);
    case instruction.includes('RSHIFT'):
      return get(instruction[0]) >> get(instruction[2]);
    case instruction.includes('NOT'):
      return ~get(instruction[1]) & 0xffff;
    default:
      return get(instruction[0]);
  }
};

We use a local get helper function to attempt to retrieve the instruction identifier value from the signal mapping, else fallback to assuming if not present it must be an integer value with must parse. From here, we can then perform a single reduction over the instruction execution listing, building up the resulting signal mapping along the way.

const part1 = (input: string): number => {
  const signals: Signals = createInstructionExecutionOrder(input).reduce(
    (signals, [wire, instruction]) =>
      signals.set(wire, emulate(signals, instruction)),
    new Map()
  );

  return signals.get('a');
};

It is then from this built map that we can get the signal value which has been emulated for wire a. Likewise we can solve part two in a similar mannor, except we must first replace the signal value of wire b with part ones answer.

const part2 = (input: string): number => {
  const instructions = createInstructionExecutionOrder(
    input.replace(/^\d+ -> b$/gm, `${part1(input).toString()} -> b`)
  );
  const signals: Signals = instructions.reduce(
    (signals, [wire, instruction]) =>
      signals.set(wire, emulate(signals, instruction)),
    new Map()
  );

  return signals.get('a');
};

I really enjoyed exploring the Topological Sorting algorithm to implment the second solution to today’s problem. In performing this initial ordering we are able to greatly simplify the emulation logic and remove the need for any memoization/recursive calls.