diff options
| -rw-r--r-- | 2020/day-08/README.org | 266 | ||||
| -rwxr-xr-x | 2020/day-08/day-08.raku | 88 | ||||
| -rw-r--r-- | 2020/day-08/input | 641 |
3 files changed, 995 insertions, 0 deletions
diff --git a/2020/day-08/README.org b/2020/day-08/README.org new file mode 100644 index 0000000..58bfbff --- /dev/null +++ b/2020/day-08/README.org @@ -0,0 +1,266 @@ +#+SETUPFILE: ~/.emacs.d/org-templates/level-3.org +#+HTML_LINK_UP: ../../index.html#2020 +#+OPTIONS: toc:1 +#+EXPORT_FILE_NAME: index +#+TITLE: Day 08 - Handheld Halting + +* Puzzle +- This puzzle is taken from: https://adventofcode.com/2020/day/8 + +Your flight to the major airline hub reaches cruising altitude without +incident. While you consider checking the in-flight menu for one of +those drinks that come with a little umbrella, you are interrupted by +the kid sitting next to you. + +Their handheld game console won't turn on! They ask if you can take a +look. + +You narrow the problem down to a strange infinite loop in the boot code +(your puzzle input) of the device. You should be able to fix it, but +first you need to be able to run the code in isolation. + +The boot code is represented as a text file with one instruction per +line of text. Each instruction consists of an operation (acc, jmp, or +nop) and an argument (a signed number like +4 or -20). + +- =acc= increases or decreases a single global value called the + accumulator by the value given in the argument. For example, acc +7 + would increase the accumulator by 7. The accumulator starts at 0. + After an acc instruction, the instruction immediately below it is + executed next. +- =jmp= jumps to a new instruction relative to itself. The next + instruction to execute is found using the argument as an offset from + the jmp instruction; for example, jmp +2 would skip the next + instruction, jmp +1 would continue to the instruction immediately + below it, and jmp -20 would cause the instruction 20 lines above to be + executed next. +- =nop= stands for No OPeration - it does nothing. The instruction + immediately below it is executed next. + +For example, consider the following program: +#+BEGIN_SRC +nop +0 +acc +1 +jmp +4 +acc +3 +jmp -3 +acc -99 +acc +1 +jmp -4 +acc +6 +#+END_SRC + +These instructions are visited in this order: +#+BEGIN_SRC +nop +0 | 1 +acc +1 | 2, 8(!) +jmp +4 | 3 +acc +3 | 6 +jmp -3 | 7 +acc -99 | +acc +1 | 4 +jmp -4 | 5 +acc +6 | +#+END_SRC + +First, the nop +0 does nothing. Then, the accumulator is increased from +0 to 1 (acc +1) and jmp +4 sets the next instruction to the other acc +1 +near the bottom. After it increases the accumulator from 1 to 2, jmp -4 +executes, setting the next instruction to the only acc +3. It sets the +accumulator to 5, and jmp -3 causes the program to continue back at the +first acc +1. + +This is an infinite loop: with this sequence of jumps, the program will +run forever. The moment the program tries to run any instruction a +second time, you know it will never terminate. + +Immediately before the program would run an instruction a second time, +the value in the accumulator is 5. + +Run your copy of the boot code. Immediately before any instruction is +executed a second time, what value is in the accumulator? +** Part 2 +After some careful analysis, you believe that exactly one instruction is +corrupted. + +Somewhere in the program, either a jmp is supposed to be a nop, or a nop +is supposed to be a jmp. (No acc instructions were harmed in the +corruption of this boot code.) + +The program is supposed to terminate by attempting to execute an +instruction immediately after the last instruction in the file. By +changing exactly one jmp or nop, you can repair the boot code and make +it terminate correctly. + +For example, consider the same program from above: +#+BEGIN_SRC +nop +0 +acc +1 +jmp +4 +acc +3 +jmp -3 +acc -99 +acc +1 +jmp -4 +acc +6 +#+END_SRC + +If you change the first instruction from nop +0 to jmp +0, it would +create a single-instruction infinite loop, never leaving that +instruction. If you change almost any of the jmp instructions, the +program will still eventually find another jmp instruction and loop +forever. + +However, if you change the second-to-last instruction (from jmp -4 to +nop -4), the program terminates! The instructions are visited in this +order: +#+BEGIN_SRC +nop +0 | 1 +acc +1 | 2 +jmp +4 | 3 +acc +3 | +jmp -3 | +acc -99 | +acc +1 | 4 +nop -4 | 5 +acc +6 | 6 +#+END_SRC + +After the last instruction (acc +6), the program terminates by +attempting to run the instruction below the last instruction in the +file. With this change, after the program terminates, the accumulator +contains the value 8 (acc +1, acc +1, acc +6). + +Fix the program so that it terminates normally by changing exactly one +jmp (to nop) or nop (to jmp). What is the value of the accumulator after +the program terminates? +* Solution +=Instruction= is a grammar that parses the instruction & seperates +operation from argument. +#+BEGIN_SRC raku +# Instruction grammar seperates the operation & argument. +grammar Instruction { + rule TOP { <operation> <argument> } + token operation { acc|jmp|nop } + token argument { .* } +} +#+END_SRC + +=execute-from= takes an index & executes instructions from that point. It +returns the accumulator value. If the instruction has already been +executed then it will stop & avoid infinite loop. +#+BEGIN_SRC raku +sub execute-from ( + @instructions, Int $idx --> Int +) { + my Int $acc = 0; + + return $acc unless @instructions[$idx]; + my $entry = @instructions[$idx]; + + $repeated++ if $entry<executed>; + return $acc if $entry<executed>; + + if Instruction.parse($entry<instruction>) -> $match { + $entry<executed> = 1; + given $match<operation> { + when 'acc' { + $acc += $match<argument>; + $acc += execute-from(@instructions, $idx + 1); + } + when 'jmp' { + $acc += execute-from(@instructions, $idx + $match<argument>); + } + when 'nop' { + $acc += execute-from(@instructions, $idx + 1); + } + } + } + return $acc; +} + +#+END_SRC + +Each instruction is pushed to =@instructions= along with =executed= value +which indicates the number of time that instruction has been executed. +It'll be useful to avoid infinite loops. + +=@instructions='s 0th index is set to a dummy instruction to make it +easier for =execute-from= to run the operations. The operations are +written around instruction file which is numbered from 1. It's easier to +add a dummy instruction than to make =execute-from= understand this. +#+BEGIN_SRC raku +sub MAIN ( + Int $part where * == 1|2 = 1 #= part to run (1 or 2) +) { + # To match the numbers in instructions with array we just push an + # element at 0th index. + my @instructions = %(instruction => "", executed => 0),; + + for "input".IO.lines { + push @instructions, %( + instruction => $_.Str, + executed => 0, + ); + } + + my Int $acc; + if $part == 1 { + ... + } elsif $part == 2 { + ... + } + say "Part $part: ", $acc; +} +#+END_SRC + +For part 1, we just call =execute-from= & print the =$acc= value. +#+BEGIN_SRC raku +$acc = execute-from(@instructions, 1) if $part == 1; +#+END_SRC +** Part 2 +=$repeated= is a Int that keeps track of whether an instruction is +executed multiple times. It is a global variable. +#+BEGIN_SRC raku +my Int $repeated = 0; +#+END_SRC + +=reset-executed= is a subroutine which will reset the =executed= field for +all instructions in =@instructions=. +#+BEGIN_SRC raku +sub reset-executed ( + @instructions is copy --> List +) { + $_<executed> = 0 for @instructions; + return @instructions; +} +#+END_SRC + +For part 2, we loop over =@instructions=, change =jmp= operation to =nop= & +vice versa & run =execute-from= on changed =@instructions=. We check +=$repeated= value, if it indicates that nothing was repeated then we just +exit the loop & print =$acc=. + +If not then we do the same thing again with next operation. This is done +after reverting the change we made & resetting =executed= value for all +instructions by calling =reset-executed=. +#+BEGIN_SRC raku +for @instructions.kv -> $idx, $entry { + next if $idx == 0; + $repeated = 0; + if Instruction.parse($entry<instruction>) -> $match { + @instructions[$idx]<instruction> = "nop $match<argument>" + if $match<operation> eq "jmp"; + + @instructions[$idx]<instruction> = "jmp $match<argument>" + if $match<operation> eq "nop"; + + $acc = execute-from(@instructions, 1); + + @instructions[$idx]<instruction> = "$match<operation> $match<argument>"; + @instructions = reset-executed(@instructions); + + last if $repeated == 0; + } +} +#+END_SRC diff --git a/2020/day-08/day-08.raku b/2020/day-08/day-08.raku new file mode 100755 index 0000000..ee9556f --- /dev/null +++ b/2020/day-08/day-08.raku @@ -0,0 +1,88 @@ +#!/usr/bin/env raku + +# Instruction grammar seperates the operation & argument. +grammar Instruction { + rule TOP { <operation> <argument> } + token operation { acc|jmp|nop } + token argument { .* } +} + +my Int $repeated = 0; + +sub MAIN ( + Int $part where * == 1|2 = 1 #= part to run (1 or 2) +) { + # To match the numbers in instructions with array we just push an + # element at 0th index. + my @instructions = %(instruction => "", executed => 0),; + + for "input".IO.lines { + push @instructions, %( + instruction => $_.Str, + executed => 0, + ); + } + + my Int $acc; + if $part == 1 { + $acc = execute-from(@instructions, 1) if $part == 1; + } elsif $part == 2 { + for @instructions.kv -> $idx, $entry { + next if $idx == 0; + $repeated = 0; + if Instruction.parse($entry<instruction>) -> $match { + @instructions[$idx]<instruction> = "nop $match<argument>" + if $match<operation> eq "jmp"; + + @instructions[$idx]<instruction> = "jmp $match<argument>" + if $match<operation> eq "nop"; + + $acc = execute-from(@instructions, 1); + + @instructions[$idx]<instruction> = "$match<operation> $match<argument>"; + @instructions = reset-executed(@instructions); + + last if $repeated == 0; + } + } + } + say "Part $part: ", $acc; +} + +sub reset-executed ( + @instructions is copy --> List +) { + $_<executed> = 0 for @instructions; + return @instructions; +} + +# execute-from takes an index & executes instructions from that point. +# It returns the accumulator value. +sub execute-from ( + @instructions, Int $idx --> Int +) { + my Int $acc = 0; + + return $acc unless @instructions[$idx]; + my $entry = @instructions[$idx]; + + $repeated++ if $entry<executed>; + return $acc if $entry<executed>; + + if Instruction.parse($entry<instruction>) -> $match { + $entry<executed> = 1; + given $match<operation> { + when 'acc' { + $acc += $match<argument>; + $acc += execute-from(@instructions, $idx + 1); + } + when 'jmp' { + $acc += execute-from(@instructions, $idx + $match<argument>); + } + when 'nop' { + $acc += execute-from(@instructions, $idx + 1); + } + } + } + return $acc; +} diff --git a/2020/day-08/input b/2020/day-08/input new file mode 100644 index 0000000..020ccbc --- /dev/null +++ b/2020/day-08/input @@ -0,0 +1,641 @@ +acc +3 +jmp +599 +nop +311 +jmp +605 +acc -3 +acc +50 +acc -6 +jmp +461 +jmp -4 +acc -7 +jmp +1 +acc +19 +acc -18 +jmp +485 +nop +182 +jmp +174 +acc +41 +acc +10 +nop +570 +jmp +428 +acc +18 +acc +33 +jmp +197 +jmp +202 +acc +43 +acc -19 +acc -12 +jmp +453 +acc +8 +jmp +55 +acc +5 +nop +482 +acc -11 +jmp +475 +acc -5 +acc +38 +acc -16 +nop +111 +jmp +230 +acc +41 +acc -4 +jmp +16 +nop +147 +jmp -15 +nop -28 +jmp +96 +acc +34 +acc +27 +jmp -25 +jmp +8 +acc +8 +nop +28 +jmp +515 +jmp +247 +jmp +474 +nop +392 +jmp +57 +nop +271 +acc +20 +jmp +514 +acc +22 +jmp +337 +acc +47 +acc +43 +acc +42 +nop +263 +jmp +144 +acc +26 +acc +49 +acc +22 +jmp +170 +nop +502 +acc +26 +acc -3 +jmp +96 +acc -9 +nop +213 +acc +1 +jmp +111 +nop +189 +jmp +533 +acc -18 +acc -15 +jmp +209 +nop +464 +jmp +463 +acc +16 +acc +39 +acc +36 +jmp +499 +acc +42 +jmp +1 +jmp +444 +acc +33 +acc -5 +nop +513 +acc +17 +jmp +377 +jmp +410 +acc -5 +jmp +312 +jmp +235 +acc -4 +acc +32 +acc +40 +jmp +477 +jmp +388 +jmp +112 +acc +45 +acc +36 +jmp -68 +nop +296 +jmp +496 +acc -19 +acc +1 +acc -8 +jmp +1 +jmp +479 +jmp +195 +acc -13 +acc +50 +acc +30 +jmp +167 +jmp +217 +acc +17 +acc +8 +jmp +22 +acc +46 +acc -5 +jmp +53 +jmp +152 +acc +29 +acc +1 +acc +24 +jmp +278 +acc +20 +jmp +95 +acc +15 +jmp +1 +acc +36 +jmp +286 +acc +44 +acc +33 +jmp +117 +acc +12 +acc +16 +jmp +1 +jmp +284 +acc -15 +nop +478 +acc -17 +jmp +13 +nop +274 +nop +217 +nop +91 +jmp -113 +nop -58 +acc +11 +acc +28 +nop +301 +jmp +132 +acc -7 +acc +18 +jmp +173 +acc +39 +nop +435 +jmp +388 +acc +15 +acc +50 +jmp +152 +acc -8 +acc -10 +acc +15 +acc +39 +jmp +166 +acc +14 +jmp +310 +nop +371 +acc +26 +jmp +161 +acc +37 +jmp -147 +acc -12 +acc +37 +nop -78 +jmp +11 +acc +5 +nop -130 +jmp +182 +acc +23 +acc +17 +jmp -14 +acc +42 +acc +16 +acc +40 +jmp -39 +nop +325 +acc +15 +jmp +70 +acc +39 +acc +13 +nop +211 +jmp +210 +acc -18 +nop +384 +acc +28 +jmp -98 +acc +21 +acc +12 +jmp +217 +acc +22 +acc +4 +acc +12 +jmp +421 +acc +26 +nop +298 +acc +1 +acc +43 +jmp -15 +acc +39 +nop +217 +nop +31 +acc +17 +jmp -189 +jmp -68 +acc -14 +jmp +287 +nop +62 +acc +20 +acc +50 +jmp -5 +acc +26 +acc -14 +acc +24 +acc -2 +jmp -181 +acc +12 +nop -89 +acc +13 +jmp -50 +acc +39 +jmp +233 +nop -214 +acc +47 +jmp +216 +acc +21 +acc +30 +nop +347 +acc +34 +jmp -240 +nop -196 +jmp +345 +acc +48 +acc +43 +acc +4 +nop +266 +jmp +72 +acc +7 +acc +43 +jmp +1 +acc +44 +acc +1 +acc +21 +jmp +358 +acc +20 +acc +28 +acc +48 +jmp +266 +acc +14 +acc +30 +jmp +167 +nop +18 +acc +17 +nop +125 +acc +14 +jmp -111 +nop +332 +acc -12 +nop -177 +jmp +355 +acc -8 +jmp -125 +acc +6 +jmp -185 +nop +270 +acc +32 +acc +19 +acc -9 +jmp +339 +jmp -13 +nop +23 +jmp -109 +acc -4 +acc +23 +acc +39 +nop +305 +jmp +130 +nop -57 +acc +46 +jmp +301 +jmp +1 +jmp +150 +acc -6 +nop -184 +acc +18 +jmp -123 +acc +11 +acc +40 +jmp -304 +acc +16 +acc +26 +nop -307 +jmp +3 +jmp -194 +jmp -224 +acc +8 +acc +22 +acc +1 +acc -1 +jmp +73 +jmp +41 +acc +40 +jmp +80 +acc +0 +acc +39 +acc +6 +acc +45 +jmp -186 +acc +32 +acc -5 +jmp -99 +acc +47 +acc +17 +acc +1 +acc +0 +jmp +265 +jmp +264 +nop +114 +acc +13 +jmp -108 +nop -278 +acc +29 +acc -14 +jmp -297 +acc +20 +acc +37 +nop +175 +acc -4 +jmp +9 +acc -11 +nop +136 +acc +2 +jmp -37 +acc +48 +acc +9 +acc -7 +jmp +36 +acc -15 +jmp -118 +acc -9 +jmp -68 +acc +26 +nop -1 +acc +9 +jmp -15 +acc +21 +acc +13 +acc -2 +acc -17 +jmp -365 +acc +5 +acc +8 +jmp +255 +acc +16 +nop -312 +acc -14 +jmp -19 +acc +32 +acc +37 +acc +9 +jmp +1 +jmp -302 +jmp +1 +acc +5 +acc +45 +acc +42 +jmp +61 +acc +20 +acc +36 +jmp +156 +acc -9 +jmp +117 +acc -1 +nop -389 +jmp +242 +acc +9 +acc -18 +jmp -5 +jmp -77 +acc +17 +acc +30 +jmp +172 +acc -1 +acc +11 +acc -6 +jmp -334 +jmp +215 +acc +3 +acc +24 +jmp +13 +jmp +1 +jmp -369 +acc +49 +acc -6 +acc -14 +acc -6 +jmp -234 +acc +13 +acc +9 +acc +11 +nop +78 +jmp +115 +nop -332 +nop +177 +jmp +109 +jmp +157 +nop -372 +acc +25 +jmp +166 +nop +171 +jmp -253 +acc +27 +acc -11 +acc -4 +acc +34 +jmp +98 +jmp -240 +acc +41 +nop -381 +acc -4 +nop -270 +jmp -328 +acc +31 +acc +11 +acc -2 +nop -163 +jmp +148 +jmp +1 +nop -91 +jmp -197 +jmp +132 +acc +31 +nop +109 +acc +43 +jmp -319 +acc -19 +acc +49 +acc +38 +acc +48 +jmp +86 +acc -1 +acc -11 +acc +2 +jmp -355 +acc -3 +acc +11 +acc +39 +jmp -110 +acc +10 +nop -465 +nop -121 +jmp -110 +acc +0 +jmp -5 +nop -278 +nop -199 +nop +118 +acc +6 +jmp -47 +jmp +129 +acc +26 +jmp -391 +acc -15 +acc +8 +nop -86 +jmp +115 +nop -94 +acc -7 +acc +14 +jmp -183 +acc -16 +acc +15 +acc +23 +jmp -178 +jmp +1 +jmp -365 +jmp +1 +jmp -320 +acc +42 +nop -289 +acc +21 +acc -17 +jmp -440 +acc +0 +acc +5 +acc +35 +acc +20 +jmp +29 +acc -1 +acc +20 +acc +44 +jmp +50 +jmp -61 +acc -2 +acc +41 +acc -5 +jmp -410 +acc +13 +nop -315 +acc -2 +jmp -46 +acc +20 +acc +9 +acc +38 +nop -279 +jmp -113 +acc +48 +jmp +86 +jmp -151 +jmp +1 +acc -18 +nop -291 +jmp -101 +jmp +49 +nop -378 +jmp -445 +acc +36 +acc +41 +nop -286 +acc -19 +jmp -142 +nop -393 +acc +0 +acc -3 +jmp +10 +acc +17 +jmp -327 +jmp -219 +acc -5 +nop -123 +acc +49 +acc +36 +jmp -145 +jmp -496 +jmp +48 +acc +10 +jmp +11 +jmp -97 +acc -8 +acc +22 +jmp +53 +jmp -316 +acc +32 +acc -15 +acc +27 +acc +33 +jmp -266 +jmp -10 +acc +48 +acc -10 +acc +7 +acc +5 +jmp +28 +acc -15 +acc -19 +acc -8 +nop -150 +jmp -388 +acc +14 +acc +45 +acc -11 +jmp -451 +acc +42 +acc -8 +jmp -104 +nop -228 +acc +0 +jmp -327 +acc +19 +acc -7 +jmp +1 +jmp -291 +acc -8 +jmp -495 +jmp -61 +jmp -392 +acc +1 +jmp -227 +acc -10 +jmp -286 +jmp -397 +jmp -539 +jmp -215 +acc +15 +acc +36 +acc -12 +acc +5 +jmp -147 +acc +28 +acc -15 +acc +19 +jmp +16 +jmp -493 +acc +7 +acc +40 +acc +23 +nop -122 +jmp -567 +acc -4 +acc +23 +jmp -218 +jmp -13 +acc -18 +acc -10 +acc -13 +nop -541 +jmp -105 +acc +14 +acc +40 +acc +0 +jmp -614 +acc +3 +acc +14 +jmp -357 +jmp -510 +jmp -416 +acc +12 +nop -245 +acc +26 +acc +15 +jmp +1 |