07.md

Day 07

Part 1

Follow the instructions and connect the wires – what signal is ultimately provided to wire a?

The first thing to realize is that the instructions can't be followed in the order they are given. (The sample instructions can, but Part 1's instructions can't.) For example, Part 1's first instruction is af AND ah -> ai, but we don't yet know the values of af and ah.

So, let's start by finding the first instruction which doesn't have any unknown dependencies:

const input = `123 -> x
456 -> y
x AND y -> d
x OR y -> e
x LSHIFT 2 -> f
y RSHIFT 2 -> g
NOT x -> h
NOT y -> i`

const instructions = () =>
  input.split('\n').map((instruction) => instruction.split(' -> '))

const wires = {
  // This object is empty for now,
  // but eventually it will contain the values of each wire.
  // For example:
  // x: 123,
}

const getNextIndex = () =>
  instructions.findIndex(([operation]) => {
    const dependencies = operation.match(/([a-z]+)/g)
    return (
      !dependencies || dependencies.every((key) => wires[key] !== undefined)
    )
  })

Next we have to somehow parse the instructions. Turns out that if a string is split with a regex which contains a capturing group, the capturing group is included in the resulting array:

const operatorRegex = / ?(NOT|AND|OR|[LR]SHIFT) /

const [x, operator, y] = '123'.split(operatorRegex)
// => x = '123'
//    operator = undefined
//    y = undefined

const [x, operator, y] = 'a AND b'.split(operatorRegex)
// => x = 'a'
//    operator = 'AND'
//    y = 'b'

const [x, operator, y] = 'a LSHIFT 2'.split(operatorRegex)
// => x = 'a'
//    operator = 'LSHIFT'
//    y = '2'

const [x, operator, y] = 'NOT a'.split(operatorRegex)
// => x = ''
//    operator = 'NOT'
//    y = 'x'

Excellent! Now we can just™ loop over the instructions:

const getInstructions = () =>
  input.split('\n').map((instruction) => instruction.split(' -> '))

const getNextIndex = (instructions, wires) =>
  instructions.findIndex(([operation]) => {
    const dependencies = operation.match(/([a-z]+)/g)
    return (
      !dependencies || dependencies.every((key) => wires[key] !== undefined)
    )
  })

const parse = (instructions, wires = {}) => {
  const index = getNextIndex(instructions, wires)
  const [operation, key] = instructions[index]

  const operatorRegex = / ?(NOT|AND|OR|[LR]SHIFT) /
  const [x, operator, y] = operation.split(operatorRegex)

  if (!operator) {
    wires[key] = wires[x] ?? Number(x)
  } else if (operator === 'AND') {
    wires[key] = (wires[x] ?? Number(x)) & wires[y]
  } else if (operator === 'OR') {
    wires[key] = wires[x] | wires[y]
  } else if (operator === 'LSHIFT') {
    wires[key] = wires[x] << y
  } else if (operator === 'RSHIFT') {
    wires[key] = wires[x] >> y
  } else if (operator === 'NOT') {
    wires[key] = 2 ** 16 - 1 - wires[y]
  } else {
    throw new Error('Unknown operator: ' + operator)
  }

  const newInstructions = instructions.filter((_, i) => i !== index)
  return newInstructions.length === 0 ? wires : parse(newInstructions, wires)
}

const initialInstructions = getInstructions()
const wires = parse(initialInstructions)
console.log('Part 1 answer:', wires.a)

Flems link in Part 2.

Part 2

Set Part 1's answer -> b and follow the instructions from scratch. What signal is now provided to wire a?

Since there aren't any mutable variables from Part 1 to take care of, we can just append this code to get Part2's answer:

const newInstructions = [
  [wires.a.toString(), 'b'],
  ...initialInstructions.filter(([_, key]) => key !== 'b'),
]
const newWires = parse(newInstructions)
console.log('Part 2 answer:', newWires.a)

Try out the final code on flems.io

What did I learn?

I used the bitwise XOR operator (^) for the first time in the 2015/06 puzzle. Other than that, in this puzzle I used bitwise operators for the first time. Very simply, but that's a good start.

I'm not sure if I already knew it, but splitting a string with a regex which contains capturing groups includes the capturing group results in the resulting array. I didn't think of it when I used it, but later when I was later writing this document, I was like "huh, that's possible?" 😀 From MDN's split() page:

If separator is a regular expression with capturing parentheses, then each time separator matches, the results (including any undefined results) of the capturing parentheses are spliced into the output array.

This was a very fun puzzle! Probably partly because I'm very satisfied with my final solution; I had some difficulties in the beginning, but in the end the code turned out nice and clear.