summary refs log tree commit diff stats
path: root/2020/day-08/README.org
diff options
context:
space:
mode:
Diffstat (limited to '2020/day-08/README.org')
-rw-r--r--2020/day-08/README.org266
1 files changed, 266 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