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.

## Top comments (0)