<jupyter_start><jupyter_text>Day 08<jupyter_code>from __future__ import annotations
from typing import List, Tuple, NamedTuple<jupyter_output><empty_output><jupyter_text>Part One<jupyter_code>class Instruction(NamedTuple):
    op: str
    arg: int

    @staticmethod
    def parse(line: str) -> Instruction:
        op, arg = line.strip().split()
        arg = int(arg)
        return Instruction(op, arg)


class Booter:
    def __init__(self, instructions: List[Instruction]) -> None:
        self.instructions = instructions
        self.index = 0
        self.accumulator = 0

    def execute_one(self) -> None:
        op, arg = self.instructions[self.index]
        #         print(self.index, op, arg)
        if op == "acc":
            self.accumulator += arg
            self.index += 1
        elif op == "jmp":
            self.index += arg
        elif op == "nop":
            self.index += 1
        else:
            raise ValueError(f"unknown op: {op}")

    def run_until_repeat(self) -> None:
        executed = set()
        while self.index not in executed:
            executed.add(self.index)
            self.execute_one()

    def does_terminate(self) -> bool:
        executed = set()
        while self.index not in executed:
            if self.index == len(self.instructions):
                return True
            executed.add(self.index)
            self.execute_one()
        return False
RAW = """
nop +0
acc +1
jmp +4
acc +3
jmp -3
acc -99
acc +1
jmp -4
acc +6
"""
INSTRUCTIONS = [Instruction.parse(line) for line in RAW.strip().split("\n")]
BOOTER = Booter(INSTRUCTIONS)
BOOTER.run_until_repeat()
assert BOOTER.accumulator == 5
with open("../input/day08.txt") as f:
    raw = f.read()
    instructions = [Instruction.parse(line) for line in raw.strip().split("\n")]
    booter = Booter(instructions)
    booter.run_until_repeat()
    print(booter.accumulator)
def parse_data(data: str) -> List[Tuple[str, int]]:
    data = data.strip()
    data = data.split("\n")
    data = [o.split() for o in data]
    data = [(o[0], int(o[1])) for o in data]
    return data
def accumulate(cmds):
    acc = 0
    visited = [False] * len(cmds)
    idx = 0
    while idx < len(cmds):
        visited[idx] = True
        cmd, n = cmds[idx]
        if cmd == "acc":
            acc += n
            idx += 1
        elif cmd == "jmp":
            idx += n
        elif cmd == "nop":
            idx += 1
        if visited[idx] == True:
            break
    return acc
data = """
nop +0
acc +1
jmp +4
acc +3
jmp -3
acc -99
acc +1
jmp -4
acc +6
"""
cmds = parse_data(data)
assert accumulate(cmds) == 5
with open("../input/day08.txt") as f:
    data = f.read()
    cmds = parse_data(data)
    print(accumulate(cmds))<jupyter_output>2051<jupyter_text>Part Two<jupyter_code>def dfs(idx, cmds, visited, acc, flip):
    if idx == len(visited):
        return True, acc
    if visited[idx]:
        return False, -1
    cmd, n = cmds[idx]
    visited[idx] = True
    if cmd == "acc":
        res = dfs(idx + 1, cmds, visited, acc + n, flip)
        if res[0]:
            return res
    elif cmd == "nop":
        res = dfs(idx + 1, cmds, visited, acc, flip)
        if res[0]:
            return res
        elif flip == False:
            res = dfs(idx + n, cmds, visited, acc, True)
            if res[0]:
                return res
    elif cmd == "jmp":
        res = dfs(idx + n, cmds, visited, acc, flip)
        if res[0]:
            return res
        elif flip == False:
            res = dfs(idx + 1, cmds, visited, acc, True)
            if res[0]:
                return res
    visited[idx] = False
    return False, -1
data = """
nop +0
acc +1
jmp +4
acc +3
jmp -3
acc -99
acc +1
jmp -4
acc +6
"""
cmds = parse_data(data)
visited = [False] * len(cmds)
assert dfs(0, cmds, visited, 0, False)[1] == 8
with open("../input/day08.txt") as f:
    data = f.read()
    cmds = parse_data(data)
    visited = [False] * len(cmds)
    print(dfs(0, cmds, visited, 0, False)[1])
def find_terminator(instructions: List[Instruction]) -> int:
    booter = Booter(instructions)
    if booter.does_terminate():
        return booter.accumulator

    for i, (op, arg) in enumerate(instructions):
        orig = instructions[i]
        if op == "nop":
            instructions[i] = Instruction("jmp", arg)
        elif op == "jmp":
            instructions[i] = Instruction("nop", arg)
        else:
            continue

        booter = Booter(instructions)
        if booter.does_terminate():
            return booter.accumulator
        instructions[i] = orig

    raise RuntimeError("never terminates")
assert find_terminator(INSTRUCTIONS) == 8
with open("../input/day08.txt") as f:
    raw = f.read()
    instructions = [Instruction.parse(line) for line in raw.strip().split("\n")]
    print(find_terminator(instructions))<jupyter_output>2304
{'fraction_non_alphanumeric': 0.1340057636887608, 'fraction_numerical': 0.016055990119390694, 'mean_word_length': 2.1737426518615286, 'pattern_counts': {'":': 11, '<': 12, '<?xml version=': 0, '>': 18, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '3', 'dir': 'jupyter-structured-clean-dedup', 'id': '596257', 'license': 'MIT', 'n_tokens_mistral': 1672, 'n_tokens_neox': 1621, 'n_words': 453, 'path': 'notebooks/day08.ipynb', 'repo_name': 'giwankim/advent-of-code-2020', 'size': '4858'}