## DEV Community ๐ฉโ๐ป๐จโ๐ป is a community of 966,904 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

Jules

Posted on • Updated on

# AoC 2015 - Day 7 - recursion(recursion())

A huge puzzle today, that depends on both binary operators and recursion. I hate recursion! (Which is another way of saying I'm not very good at it.)

Here's the puzzle (Part 1, anyway) in all its glory (click to expand):

The first thing I had to do was remind myself how to do binary operations in Python, as it's not an everyday topic:

Operation Python
AND &
OR |
XOR ^
NOT ~
LSHIFT <<
RSHIFT >>

Thankfully, by having to Google around for these I discovered why I was having problems with the test data. In the line `NOT x -> h` where `x` has already been set to 123, the puzzle says we should end up with 65412, and I was getting -124. This is a case of needing to read the puzzle carefully, which I eventually did. The puzzle says the value on the wire can be `a number from 0 to 65535`, which is another way of saying unsigned integer! How to keep a number in the range 0 to 65535 when you NOT it? Two ways:

i. `~ 123 & 65535`
ii. `123 ^ 65535` (XOR)

LSHIFT can also take wire values outside the allowed range, as each LSHIFT doubles the number, so I used `& 65535` for LSHIFT too.

The first thing I did was to load all the instructions into a dictionary, keyed on the destination wire:

``````wires = {}
with open('src/day07.txt') as f:
for line in f:
wire = line.rstrip().split(' -> ')
wires[wire[-1]] = wire[0].split()
``````

The result of this is that an instruction like `ly OR lz -> ma` becomes `wires{'ma': ['ly', 'OR', 'lz']}`. Having loaded all these, we can start our recursion. In a pure recursion, I found I was going round and round in loops, but when I rewrote it to store 'solved' wires, the code found a solution pretty quickly:

``````solved = {}

def solve(node):

if node.isnumeric():
return int(node)

if node not in solved:

ops = wires[node]

if len(ops) == 1:
n = solve(ops[0])

else:
op = ops[-2]
if op == 'AND':
n = solve(ops[0]) & solve(ops[2])
elif op == 'OR':
n = solve(ops[0]) | solve(ops[2])
elif op == 'NOT':
n = ~solve(ops[1]) & 65535
elif op == 'RSHIFT':
n = solve(ops[0]) >> solve(ops[2])
else: #    'LSHIFT':
n = solve(ops[0]) << solve(ops[2]) & 65535

solved[node] = n

return solved[node]

#Part 1
part1_solution = solve('a')
print(part1_solution)
``````

The reason I store the solution for Part 1 in a variable instead of printing it directly, is because it's needed for Part 2, which is mercifully short:

Thankfully, this made the code for Part 2 very straightforward too. I simply overrode the value of wire `b` and ran again:

``````wires['b'] = [str(part1_solution)]
solved = {}
print(solve('a'))
``````

Recursion is so efficient when you get it right, but getting it right can be a real pain. Credit to anyone who got on the leader board that day. Unsurprisingly, the word 'golf' doesn't appear on the megathread for that day, and there are a lot of lines of code in most posts.