<jupyter_start><jupyter_text>Day 8 - Simple instructions* https://adventofcode.com/2020/day/8We regularly are given a CPU opcode task, this year we are dealing with infinite loops! It starts simple, just execute and detect when we have jumped to a memory position we have visited before:<jupyter_code>from dataclasses import dataclass
from enum import Enum, auto
from functools import singledispatchmethod
from typing import Sequence

class OpCode(Enum):
    jmp = auto()
    nop = auto()
    acc = auto()

@dataclass(frozen=True)
class Instr:
    opc: OpCode
    arg: int

    @classmethod
    def from_line(cls, line: str) -> "Instr":
        opc, arg = line.split(None, 1)
        return cls(OpCode[opc], int(arg))

    def __repr__(self) -> str:
        return f"{self.opc.name} {self.arg:+d}"


class CPU:
    acc: int
    pos: int
    mem: Sequence[Instr]
    seen: set[int]

    def __init__(self, mem: Sequence[Instr]) -> None:
        self.acc = 0
        self.pos = 0
        self.mem = mem
        self.seen = set()

    def execute(self) -> int:
        mem, seen = self.mem, self.seen
        while self.pos not in seen and self.pos < len(mem):
            seen.add(self.pos)
            instr = mem[self.pos]
            if instr.opc is OpCode.jmp:
                self.pos += instr.arg
                continue
            if instr.opc is OpCode.acc:
                self.acc += instr.arg
            self.pos += 1
        return self.acc

def parse_assembly(lines: str) -> Sequence[Instr]:
    return [Instr.from_line(line) for line in lines]

test = parse_assembly("""\
nop +0
acc +1
jmp +4
acc +3
jmp -3
acc -99
acc +1
jmp -4
acc +6
""".splitlines())

assert CPU(test).execute() == 5
import aocd
instructions = parse_assembly(aocd.get_data(day=8, year=2020).splitlines())
print("Part 1:", CPU(instructions).execute())<jupyter_output>Part 1: 1614<jupyter_text>Part 2Now it gets to be more tricky, but we only have to change a _single_ jump or no-op code. We also don't have to bother with several categories of changes:- `nop` instructions that, if changed to a jump, would put us anywhere we have already been, on _any_ run tested so far.- `nop` instructions that, if changed to a jump, would put us _outside_ of the program (except for the position right after)With only 222 jump instructions and 64 qualifying no-op instructions, I decided to go with a brute-force solution, and try out changing each nop or jmp encountered, in turn, then see if the program will complete.An alternative approach could be to generate a directed graph of all the jumps, and one of the no-ops-converted-to-jumps, and backtrack from the target position. While this too would require some brute-forcing of dropping one edge from the first graph or inserting one edge into the first from the second graph, the number of candidate options for this would be pruned more rapidly perhaps. However, I didn't think it was worth exploring this method.<jupyter_code>def repair_program(instructions: Sequence[Instr]) -> int:
    seen = set()
    for pos, instr in enumerate(instructions):
        if instr.opc is OpCode.acc:
            continue
        elif instr.opc is OpCode.nop:
            target = instr.arg + pos
            if 0 <= instr.arg <= 1 or target in seen or not 0 < target <= len(instructions):
                # would not jump, or jump to a position we've already seen or outside of the range
                continue
            alt = Instr(OpCode.jmp, instr.arg)
        else:
            alt = Instr(OpCode.nop, 0)
        cpu = CPU([*instructions[:pos], alt, *instructions[pos + 1:]])
        result = cpu.execute()
        if cpu.pos == len(instructions):
            return result
        # remember what positions we already visited, to prune
        # the search tree a bit
        seen |= cpu.seen

assert repair_program(test) == 8
print("Part 2:", repair_program(instructions))<jupyter_output>Part 2: 1260
{'fraction_non_alphanumeric': 0.09072375127421, 'fraction_numerical': 0.0127420998980632, 'mean_word_length': 2.818093385214008, 'pattern_counts': {'":': 1, '<': 12, '<?xml version=': 0, '>': 13, 'https://': 1, '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': '2', 'dir': 'jupyter-structured-clean-dedup', 'id': '641905', 'license': 'MIT', 'n_tokens_mistral': 1213, 'n_tokens_neox': 1133, 'n_words': 466, 'path': '2020/Day 08.ipynb', 'repo_name': 'AwesomeGitHubRepos/adventofcode', 'size': '3924'}