DEV Community ๐Ÿ‘ฉโ€๐Ÿ’ป๐Ÿ‘จโ€๐Ÿ’ป

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.

Create account Log in
Cover image for AoC 2015 - Day 7 - recursion(recursion())
Jules
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):

Screenshot of Advent of Code puzzle

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()
Enter fullscreen mode Exit fullscreen mode

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)
Enter fullscreen mode Exit fullscreen mode

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:

Screenshot of Advent of Code puzzle

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'))
Enter fullscreen mode Exit fullscreen mode

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)

๐ŸŒš Life is too short to browse without dark mode