Add day-08 solution

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