From 0211c48cce21e17c1fe1026c36f4c8d2108fb96c Mon Sep 17 00:00:00 2001 From: Andinus Date: Tue, 8 Dec 2020 16:49:48 +0530 Subject: Add day-08 solution --- 2020/day-08/README.org | 266 +++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 266 insertions(+) create mode 100644 2020/day-08/README.org (limited to '2020/day-08/README.org') 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 { } + 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; + return $acc if $entry; + + if Instruction.parse($entry) -> $match { + $entry = 1; + given $match { + when 'acc' { + $acc += $match; + $acc += execute-from(@instructions, $idx + 1); + } + when 'jmp' { + $acc += execute-from(@instructions, $idx + $match); + } + 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 +) { + $_ = 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) -> $match { + @instructions[$idx] = "nop $match" + if $match eq "jmp"; + + @instructions[$idx] = "jmp $match" + if $match eq "nop"; + + $acc = execute-from(@instructions, 1); + + @instructions[$idx] = "$match $match"; + @instructions = reset-executed(@instructions); + + last if $repeated == 0; + } +} +#+END_SRC -- cgit 1.4.1-2-gfad0