~schnouki/advent-of-code

ref: f0ce29b9824e6a3b81af0cfc67965fdc7edbc656 advent-of-code/2020/day08.py -rwxr-xr-x 3.9 KiB
f0ce29b9 — Thomas Jost Day 8 7 months ago
                                                                                
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
#!/usr/bin/env python3

from dataclasses import dataclass, field
from typing import Any, Callable, Optional

from aoc import Puzzle, run


@dataclass
class VM:
    ops: list[tuple[str, int]]
    ip: int = field(default=0)  # instruction pointer
    stopped: bool = field(default=False)

    acc: int = field(default=0)  # accumulator

    callback: Optional[Callable[["VM"], Any]] = field(default=None)

    @classmethod
    def from_string(cls, data: str) -> "VM":
        ops: list[tuple[str, int]] = []

        for line in data.splitlines():
            line = line.strip()
            op, arg = line.split()
            ops.append((op, int(arg)))

        return cls(ops=ops)

    def clone(self) -> "VM":
        return VM(ops=self.ops.copy())

    def reset(self):
        self.ip = 0
        self.stopped = False
        self.acc = 0
        self.callback = None

    def step(self):
        """Run one instruction."""
        if self.callback:
            self.callback(self)
        if self.stopped:
            return

        op, arg = self.ops[self.ip]
        func = getattr(self, f"op_{op}")
        keep_ip = func(arg)
        if not keep_ip:
            self.ip += 1

    def run(self):
        """Run the program until stopped."""
        while 0 <= self.ip < len(self.ops) and not self.stopped:
            self.step()

    def op_nop(self, arg):
        pass

    def op_acc(self, arg: int):
        self.acc += arg

    def op_jmp(self, arg: int):
        self.ip += arg
        return True


class Day08(Puzzle):
    test_data = [
        """nop +0
acc +1
jmp +4
acc +3
jmp -3
acc -99
acc +1
jmp -4
acc +6"""
    ]
    test_result_part1 = [5]
    test_result_part2 = [8]

    def prepare_data(self, data: str) -> VM:
        return VM.from_string(data)

    def run_part1(self, data: VM):
        visited_ips = set()
        result = None

        def check_visited_ips(vm):
            nonlocal result
            if vm.ip in visited_ips:
                vm.stopped = True
                result = vm.acc
            else:
                visited_ips.add(vm.ip)

        vm = data.clone()
        vm.callback = check_visited_ips

        vm.run()
        return result

    def run_part2(self, data):
        visited_ips = set()
        prev_fixes = set()
        fixed = False

        def fix_corruption(vm):
            nonlocal fixed
            ip = vm.ip
            looping = False

            if ip in visited_ips:
                looping = True
                if fixed:
                    # Try again.
                    vm.stopped = True

            visited_ips.add(ip)

            op, arg = vm.ops[ip]
            if op == "acc":
                return

            if looping:
                # What would happen if we changed the current op?
                new_ip, alt_ip, alt_op = -1, -1, ""
                if op == "nop":
                    new_ip = ip + 1
                    alt_ip = ip + arg
                    alt_op = "jmp"
                else:
                    new_ip = ip + arg
                    alt_ip = ip + 1
                    alt_op = "nop"

                # Would flipping this op get us out of the loop?
                if (
                    new_ip in visited_ips
                    and alt_ip not in visited_ips
                    and ip not in prev_fixes
                ):
                    # Bingo!
                    # print(f"{ip}: {op} {arg} --> {alt_op} {arg}")
                    vm.ops[ip] = (alt_op, arg)
                    fixed = True
                    prev_fixes.add(ip)

        vm = data.clone()
        vm.stopped = True
        while vm.stopped:
            visited_ips.clear()
            fixed = False

            vm = data.clone()
            vm.callback = fix_corruption
            vm.run()

        # Not stopped: that fix worked! Now let's run it uncorrupted.
        vm.reset()
        vm.run()

        return vm.acc


if __name__ == "__main__":
    run(obj=Day08())