Raku: Advent of Code 2020 - Day Eight

Here is my Raku solution to the puzzle for Day 8 of the 2020 Advent of Code. If you enjoy the post or have improvements to offer, please leave a comment. Code commentary follows the code...

[08.raku] 

#!/usr/bin/env raku
use v6.d;

grammar HGC {
    rule TOP  { <inst>+ }
    rule inst { <op> <arg> }
    token op  { 'acc' | 'jmp' | 'nop' }
    token arg { <[+-]> \d+ }
}

class HGCActions {
    has $!stack = [];

    method inst ($/) { $!stack.push( %( op => ~$<op>, arg => +$<arg> ) ) }

    method exec {
        my ($pos, $acc) = (0, 0);
        for $!stack.list { .<visit> = 0 }

        while $pos < $!stack.elems {
            my ($op, $arg) = $!stack[$pos]<op arg>;
            return (1, $acc)  if ++$!stack[$pos]<visit> > 1; # Err Loop
            given $op {
                when 'nop' { $pos++ }
                when 'acc' { $pos++; $acc += $arg }
                when 'jmp' { $pos += $arg }
            };
        }

        return (0, $acc);
    }

    method ophack {
        for $!stack.grep({ .<op> ~~ /[nop | jmp]/ }) {
            .<op> = .<op> eq 'nop' ?? 'jmp' !! 'nop'; # Swap nop|jmp
            given self.exec { when .[0] == 0 { return .[1]} }
            .<op> = .<op> eq 'nop' ?? 'jmp' !! 'nop'; # Restore op
        }
    }
}

sub MAIN (
    IO() :$input where *.f     = $?FILE.IO.sibling('input'),
    Int  :$part where * == 1|2 = 1, # Solve Part One or Part Two?
    --> Nil
) {
    my $a = HGCActions.new();
    HGC.parse($input.slurp, :actions($a));
    say do given $part {
        when 1 { $a.exec[1] }
        when 2 { $a.ophack }
    }
}

# Tests (run with `raku -MTest --doc -c [THIS_FILE_NAME]`)
DOC CHECK { multi is(|) { callsame }
    my $input = q:to/§/;
        nop +0
        acc +1
        jmp +4
        acc +3
        jmp -3
        acc -99
        acc +1
        jmp -4
        acc +6
        §

    my $a = HGCActions.new();
    HGC.parse($input, :actions($a));

    is($a.exec[1], 5, 'Part One');
    is($a.ophack,  8, 'Part Two');
}

Today's puzzle involved reading instructions for a Handheld Game Console (HGC), identifying an infinite loop, and figuring out which instruction needed to be changed. Since the data was the list of instructions to be processed, Raku grammars were the obvious tool to use.

If you are interested in doing anything with grammars, I would highly recommend checking out Andrew Shitov's series on writing compilers. At the time of writing 11 chapters have been published. I'm still on chapter 2. If anything, that ought to tell you that you can accomplish a great deal with grammars without knowing a whole lot about them :-)

The grammar for today's solution is very simple:

grammar HGC {
    rule TOP  { <inst>+ }
    rule inst { <op> <arg> }
    token op  { 'acc' | 'jmp' | 'nop' }
    token arg { <[+-]> \d+ }
}

Starting at the beginning (TOP) of the input, we look for one or more instructions. Instructions consist of an operation and an argument. There are only three operations: acc, jmp, and nop.  Arguments are signed integers.

Next we have an associated grammar action class:

class HGCActions {
    has $!stack = [];

    method inst ($/) {
        $!stack.push(%( op => ~$<op>, arg => +$<arg>))
    }

    ...
}

When the grammar is used to parse the input, each time an <inst> rule is encountered, the grammar fires off the action classes method of the same name. The .inst method is called with the current match $/ as a parameter. And uses it to push an instruction onto the stack. The stack is represented as array attribute $!stack.

Today's grammar solution breaks a bit of new ground. It provides two additional methods: exec and ophack. These method's names do not match any grammar rules. So they are not used when parsing the grammar. Instead they are used to execute the Handheld Game Console (HGC) instructions.

exec executes the instructions once and returns a result. The result is a two element list holding an exit code and accumulator value.

method exec {
    my ($pos, $acc) = (0, 0);
    for $!stack.list { .<visit> = 0 }

    while $pos < $!stack.elems {
        my ($op, $arg) = $!stack[$pos]<op arg>;
        return (1, $acc)  if ++$!stack[$pos]<visit> > 1; # Err Loop
        given $op {
            when 'nop' { $pos++ }
            when 'acc' { $pos++; $acc += $arg }
            when 'jmp' { $pos += $arg }
        };
    }

    return (0, $acc);
}

exec initializes two lexical variables to hold the stack position ($pos) and accumulator ($acc) results of executing the HGC instructions. It also marks each instruction in the stack to indicate that it has not been visited. Execution begins at the 0-offset in the stack and continues in a while loop until the position is incremented past the last instruction in the stack or an infinite loop is detected. 

If an instruction has already been visited, we detect the infinite loop. If so, the while loop is short-circuited returning a result including an error code and the current accumulator value. Otherwise the instruction's operation is processed. A nop operation does nothing except advance the position to the next instruction. The acc operation stores a new value in the accumulator ($acc) and advances to the next instruction. The jmp operation jumps to a different position in the stack. When all instructions have been processed, a result including a success exit code and the current accumulator value is returned.

The accumulator value in the result returned by the exec method is the answer to Part 1 of the day's puzzle. The answer to Part 2 is the result returned by the next method: ophack.

method ophack {
    for $!stack.grep({ .<op> ~~ /[nop | jmp]/ }) {
        .<op> = .<op> eq 'nop' ?? 'jmp' !! 'nop'; # Swap nop|jmp
        given self.exec { when .[0] == 0 { return .[1]} }
        .<op> = .<op> eq 'nop' ?? 'jmp' !! 'nop'; # Restore op
    }
}

The puzzle for Part Two indicates that the reason for the infinite loop in Part One is that one instruction marked nop should have been marked jmp or vice versa. ophack executes the HGC instructions multiple times; speculatively trying to fix each possibly invalid op in a loop until we get a success exit code.

In the ophack method we loop once for each nop or jmp op in the stack. We flip the instruction from nop to jmp or vice versa, then execute the stack. If the exit code indicates success, we short circuit returning the accumulator value. Otherwise we restore the op back to its original state, and move on to trying the next nop|jmp instruction.

That is the bulk of the program.

sub MAIN (
    IO() :$input where *.f     = $?FILE.IO.sibling('input'),
    Int  :$part where * == 1|2 = 1, # Solve Part One or Part Two?
    --> Nil
) {
    my $a = HGCActions.new();
    HGC.parse($input.slurp, :actions($a));
    say do given $part {
        when 1 { $a.exec[1] }
        when 2 { $a.ophack }
    }
}

Other than containing the command line interface boilerplate, the MAIN sub does little more than parse the input using a grammar and its associated action class. Then depending on whether the solution to part one or two has been requested, it calls the action class method which returns the desired result.

You may have noticed the program doesn't end there. The remainder provides support for conditionally compiled inline tests based on the sample data provided for the puzzle. This technique is described by codesections on their blog.

# Tests (run with `raku -MTest --doc -c [THIS_FILE_NAME]`)
DOC CHECK { multi is(|) { callsame }
    my $input = q:to/§/;
        nop +0
        acc +1
        jmp +4
        acc +3
        jmp -3
        acc -99
        acc +1
        jmp -4
        acc +6
        §

    my $a = HGCActions.new();
    HGC.parse($input, :actions($a));

    is($a.exec[1], 5, 'Part One');
    is($a.ophack,  8, 'Part Two');
}

The DOC CHECK line turns on the conditional compilation and provides a work-around stub is method. Without the stub method, an error would be thrown because the Test module which provides the is routine has not been included via use Test;

Other than the use of a q:to/.../ heredoc to include the test input, and the use of the Test module's is subroutine calls... the rest should be self-explanatory.  Because it is nearly identical to the code block of the MAIN subroutine.

Per the comment, in order to execute the program with testing enabled, at the command line you type:

raku -MTest --doc -c 08.raku

which gives the results:

ok 1 - Part One
ok 2 - Part Two
Syntax OK

A nod of thanks to codesections. Being able to easily test things against the sample data during development was very helpful.

Thank you for reading! -If you found this post interesting, or have ideas on how it could be improved, then please drop me a note in the comments.

In the mean time, I'm finding grammars to be so useful in solving these Advent of Code puzzles, that I need to make time to finish working through Andrew Shitov's Creating a Compiler with Raku eleven part series. I've been able to accomplish a good bit by reading the first two chapters. I'm excited to learn more about what can be accomplished with Raku grammars.