Advent of Code - 2015
This is a solution to Day 7 of Advent of Code 2015.
Day 7 - Some Assembly Required
This year, Santa brought little Bobby Tables a set of wires and bitwise logic gates! Unfortunately, little Bobby is a little under the recommended age range, and he needs help assembling the circuit.
Each wire has an identifier (some lowercase letters) and can carry a 16-bit signal (a number from 0 to 65535). A signal is provided to each wire by a gate, another wire, or some specific value. Each wire can only get a signal from one source, but can provide its signal to multiple destinations. A gate provides no signal until all of its inputs have a signal.
The included instructions booklet describes how to connect the parts together: x AND y -> z means to connect wires x and y to an AND gate, and then connect its output to wire z.
For example:
123 -> xmeans that the signal 123 is provided to wire x.x AND y -> zmeans that the bitwise AND of wire x and wire y is provided to wire z.p LSHIFT 2 -> qmeans that the value from wire p is left-shifted by 2 and then provided to wire q.NOT e -> fmeans that the bitwise complement of the value from wire e is provided to wire f.Other possible gates include
OR(bitwise OR) andRSHIFT(right-shift). If, for some reason, you'd like to emulate the circuit instead, almost all programming languages (for example, C, JavaScript, or Python) provide operators for these gates.For example, here is a simple circuit:
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 -> iAfter it is run, these are the signals on the wires:
d: 72 e: 507 f: 492 g: 114 h: 65412 i: 65079 x: 123 y: 456
Read input
from utils import read_input
def transformer(line):
s, e = line.split(' -> ')
return (s, e)
connections = read_input(7, transformer)Oh wow, this was quite a journey.
I have to say, Eric (who runs Advent of Code) has improved his spec writing so so much over the years.
I spent 2.5 hours on a Wednesday night debugging my solution because I had not realized that for example in x AND y, it's also possible to have 1 AND x. I treated all of them as wire identifiers and ended up in endless loop for hours.
Sure, it wasn't explicitly said they couldn't but the spec also didn't say it could.
The included instructions booklet describes how to connect the parts together:
x AND y -> zmeans to connect wires x and y to an AND gate, and then connect its output to wire z.
This one is what confused me to think both sides of AND would always be wires.
Alright, let's take a look at how it's solved:
First (but to be honest, I refactored it into this last after finding out what my bug was), I define all the operations as functions.
In addition to checking for potential numeric inputs, there's one catch in NOT where we must take into account underflow.
MAX_VALUE = 65535
MIN_VALUE = 0
def AND(a, b, wires):
left = int(a) if a.isnumeric() else wires[a]
right = int(b) if b.isnumeric() else wires[b]
return left & right
def OR(a, b, wires):
left = int(a) if a.isnumeric() else wires[a]
right = int(b) if b.isnumeric() else wires[b]
return left | right
def NOT(a, wires):
value = int(a) if a.isnumeric() else wires[a]
new_value = ~value
if new_value < MIN_VALUE:
new_value = MAX_VALUE + new_value + 1
return new_value
def VALUE(signal, wires):
if signal.isnumeric():
return int(signal)
else:
return wires[signal]
def LSHIFT(a, b, wires):
left = int(a) if a.isnumeric() else wires[a]
return left << int(b)
def RSHIFT(a, b, wires):
left = int(a) if a.isnumeric() else wires[a]
return left >> int(b)For the actual solution, I create two variables:
wires that presents our final wiring and connections that is a deque, acting as a FIFO queue.
We take the first connection and ran it through our pattern matching to calculate new values. Since the instructions are not guaranteed to be in order that can be one after another (another thing that the example input did and it wasn't mentioned anywhere that's not a universal case), if I run into a case where we try to access a value for wire that doesn't exist yet, we put it back to the end of the queue.
We repeat this until the queue is empty.
from collections import deque
def wire(connections, wires):
if not wires:
wires = {}
connections = deque(connections)
while connections:
connection = connections.pop()
signal, wire = connection
try:
match signal.split():
case [signal]:
wires[wire] = VALUE(signal, wires)
case [a, 'AND', b]:
wires[wire] = AND(a, b, wires)
case [a, 'OR', b]:
wires[wire] = OR(a, b, wires)
case ['NOT', a]:
wires[wire] = NOT(a, wires)
case [a, 'LSHIFT', b]:
wires[wire] = LSHIFT(a, b, wires)
case [a, 'RSHIFT', b]:
wires[wire] = RSHIFT(a, b, wires)
except KeyError as e: # Couldn't run yet, return back to back of queue
connections.appendleft(connection)
return wiresIn little Bobby's kit's instructions booklet (provided as your puzzle input), what signal is ultimately provided to wire a?
result_wires = wire(connections, None)
result = result_wires['a']
print(f'Solution: {result}')
assert result == 3176Part 2
Now, take the signal you got on wire a, override wire b to that signal, and reset the other wires (including wire a). What new signal is ultimately provided to wire a?
I have no idea what this even means.
I had to check someone's solution from 2015 from Reddit to even understand what the "reset" meant.
What it means is this:
in Part 1, we started with wires = {} and this time we wanted to start with wires = {'b': 3176 } with 3176 being the solution to part 1.
Maybe someone who's been tinkering with wires and signals knew what the terminology meant but I didn't.
starting_wires = {}
starting_wires['b'] = result
part2 = wire(connections, starting_wires)
part2['a']