AoC 2015 - 7일차 - 재귀(recursion())

오늘날 이항 연산자와 재귀 모두에 의존하는 거대한 퍼즐입니다. 나는 재귀가 싫어! (내가 잘 못한다는 또 다른 표현입니다.)

다음은 퍼즐(어쨌든 파트 1)의 모든 영광입니다(확장하려면 클릭).



가장 먼저 해야 할 일은 Python에서 이진 연산을 수행하는 방법을 상기시키는 것이었습니다. 이는 일상적인 주제가 아니기 때문입니다.


작업
파이썬


그리고
&

또는
|

XOR
^^

아니다
~

LSHIFT
<<

RSHIFT
>>


고맙게도 Google에서 테스트 데이터에 문제가 있는 이유를 발견했습니다. NOT x -> h가 이미 123으로 설정된 줄 x에서 퍼즐은 65412로 끝나야 한다고 말하고 -124를 얻었습니다. 이것은 퍼즐을 주의 깊게 읽어야 하는 경우인데 결국 그렇게 했습니다. 퍼즐은 와이어의 값이 a number from 0 to 65535 일 수 있다고 말합니다. 이는 부호 없는 정수를 말하는 또 다른 방법입니다! 그렇지 않을 때 0에서 65535 범위의 숫자를 유지하는 방법은 무엇입니까? 두 가지 방법:

나. ~ 123 & 65535ii. 123 ^ 65535 (XOR)

LSHIFT는 각 LSHIFT가 숫자를 두 배로 하므로 허용 범위를 벗어난 와이어 값을 사용할 수도 있으므로 LSHIFT에도 & 65535를 사용했습니다.

내가 한 첫 번째 작업은 모든 명령을 대상 와이어에 입력된 사전에 로드하는 것입니다.

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

그 결과 ly OR lz -> ma와 같은 명령어는 wires{'ma': ['ly', 'OR', 'lz']}가 됩니다. 이 모든 것을 로드하면 재귀를 시작할 수 있습니다. 순수한 재귀에서 나는 루프에서 빙글빙글 돌아가는 것을 발견했지만 '해결된' 와이어를 저장하기 위해 다시 작성했을 때 코드는 매우 빠르게 해결책을 찾았습니다.

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)

파트 1의 솔루션을 직접 인쇄하지 않고 변수에 저장하는 이유는 파트 2에 필요하기 때문입니다.



고맙게도 이로 인해 파트 2의 코드도 매우 간단해졌습니다. 나는 단순히 wireb의 값을 무시하고 다시 실행했습니다.

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

재귀는 올바르게 하면 매우 효율적이지만 제대로 하는 것은 정말 고통스러운 일이 될 수 있습니다. 그날 리더 보드에 올라간 사람에게 공을 돌립니다. 당연히 그날 'golf'라는 단어는 megathread에 나타나지 않으며 대부분의 게시물에 많은 코드 줄이 있습니다.