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
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
|
{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Advent of Code 2020\n",
"#### Day 8: Handheld Halting\n",
"\n",
"A series of instructions consisting of jumps, accumulator increments and no-ops has an infinite loop, but changing one no-op to a jump or vice versa will allow it to run to completion.\n",
"\n",
"1. What's the value of the accumulator immediately before the instructions begin to loop?\n",
"2. After fixing the wrong instruction, what's the value of the accumulator at the end of execution?\n",
"\n",
"No surprises in the preamble, just the usual AOC utility functions and the threading macros."
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {},
"outputs": [],
"source": [
"#lang iracket/lang #:require racket\n",
"(require advent-of-code\n",
" threading)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The instructions are in a text file that looks like\n",
"```\n",
"nop +0\n",
"acc +1\n",
"jmp +4\n",
"acc +3\n",
"jmp -3\n",
"acc -99\n",
"acc +1\n",
"jmp -4\n",
"acc +6\n",
"```\n",
"Since we need to keep track of which instructions to jump to, I've turned it into a hash table so each instruction is indexed starting at 0."
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {},
"outputs": [
{
"data": {
"text/html": [
"<code>'((0 acc . 49) (1 jmp . 274) (2 acc . 49) (3 acc . 49) (4 jmp . 476) (5 jmp . 409) (6 jmp . 269) (7 jmp . 1) (8 acc . -11) (9 acc . 5))</code>"
],
"text/plain": [
"'((0 acc . 49) (1 jmp . 274) (2 acc . 49) (3 acc . 49) (4 jmp . 476) (5 jmp . 409) (6 jmp . 269) (7 jmp . 1) (8 acc . -11) (9 acc . 5))"
]
},
"execution_count": 2,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"(define raw-instructions (~> (fetch-aoc-input (find-session) 2020 8) (string-split \"\\n\")))\n",
"\n",
"(define instruction-set\n",
" (for/hash ([instruction (in-list raw-instructions)] [i (in-naturals)])\n",
" (match-define (list op val) (string-split instruction))\n",
" (values i (cons (string->symbol op) (string->number val)))))\n",
"\n",
"(for/list ([i (in-range 10)])\n",
" (cons i (hash-ref instruction-set i)))\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"#### Part 1\n",
"\n",
"Now I write a little interpreter using structural pattern matching and recursion to execute the code.\n",
"* If the program tried to execute an instruction on the line immediately after the last instruction, the program terminates normally. (This won't happen in part 1, but it's important for part 2.)\n",
"* We track the line numbers that have been visited in each step. If a number comes up a second time, that means we're about to start looping, so we break execution here.\n",
"* `acc n` instructions increment the accumulator by `n` and go to the next line.\n",
"* `jmp n` instructions skip up or down `n` instructions.\n",
"* `nop n` instructions don't do anything besides go to the next line."
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {},
"outputs": [
{
"data": {
"text/html": [
"<code>'(looping . 1949)</code>"
],
"text/plain": [
"'(looping . 1949)"
]
},
"execution_count": 3,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"(define (execute code [acc 0] [line 0] [visited (set)])\n",
" (match (hash-ref code line 'terminated)\n",
" ['terminated (cons 'terminated acc)]\n",
" [_\n",
" #:when (set-member? visited line)\n",
" (cons 'looping acc)]\n",
" [(cons 'acc n) (execute code (+ acc n) (add1 line) (set-add visited line))]\n",
" [(cons 'jmp n) (execute code acc (+ n line) (set-add visited line))]\n",
" [(cons 'nop _) (execute code acc (add1 line) (set-add visited line))]))\n",
"\n",
"(execute instruction-set)\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"#### Part 2\n",
"\n",
"So far so good. Now we're told that flipping exactly one `jmp` to a `nop` or vice versa will fix the code, so let's write a utility function to perform that flip, identify the potential candidates for the fix and get an idea of what our workload will be for this problem."
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {},
"outputs": [
{
"data": {
"text/html": [
"<code>305</code>"
],
"text/plain": [
"305"
]
},
"execution_count": 4,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"(define (flip-op op)\n",
" (match op\n",
" [(cons 'jmp n) (cons 'nop n)]\n",
" [(cons 'nop n) (cons 'jmp n)]))\n",
"\n",
"(define instruction-count (hash-count instruction-set))\n",
"(define flippable-bits\n",
" (filter (λ (i) (member (car (hash-ref instruction-set i)) '(jmp nop))) (range instruction-count)))\n",
"\n",
"(length flippable-bits)\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"There's only 305 cases to check, so just starting from the top and trying each possible swap in sequence should work fine, rather than trying to come up with some fancier backtracking algorithm. `for/or` stops at the first non-falsy result, so we just have to wait for the first result that matches the `(cons 'terminated _)` pattern."
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {},
"outputs": [
{
"data": {
"text/html": [
"<code>'(terminated . 2092)</code>"
],
"text/plain": [
"'(terminated . 2092)"
]
},
"execution_count": 5,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"(for/or ([i (in-list flippable-bits)])\n",
" (define flipped-instruction-set (hash-update instruction-set i flip-op))\n",
" (match (execute flipped-instruction-set)\n",
" [(cons 'looping _) #f]\n",
" [(and success (cons 'terminated _)) success]))\n"
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Racket (trusted)",
"language": "racket",
"name": "racket-trusted"
},
"language_info": {
"codemirror_mode": "scheme",
"file_extension": ".rkt",
"mimetype": "text/x-racket",
"name": "racket",
"pygments_lexer": "racket",
"version": "8.7"
},
"orig_nbformat": 4
},
"nbformat": 4,
"nbformat_minor": 2
}
|
