Advent of Code 2020 Day 8/25 in the Raku programming language

Here is Day 8 of Advent of Code 2020. Today, we are building a program to read an execute programs in the assembly language. Well, a very limited assembly with only three opcodes and one register, accumulator.

nop +0
acc +1
jmp +4
acc +3
jmp -3
acc -99
acc +1
jmp -4
acc +6

The nop code is a no-operation (but it still has a parameter, we’ll use it in the second part). The acc code adds the value to the current state of the accumulator register. And jmp moves the instruction pointer to the given amount of positions forward of backwards (each position is a full instruction with the operation code and the argument). jmp +1 means to execute the next instruction.

The first part is to detect the loop in execution flow and stop the program at that moment. The value of the accumulator is the result we need.

I would say we’d better use grammars for this kind of task. But I used simpler ad hoc parsing that you can see in the below program.

my @program;

for 'input.txt'.IO.lines -> $line {
    $line ~~ / (\w+) ' ' (\S+) /;
    
    @program.push: {
        operation => $/[0].Str,
        argument => $/[1].Int,
    };
}

my %pc;
my $pc = 0;
my $acc = 0;

while !(%pc{$pc}:exists) {
    my $instruction = @program[$pc];
    %pc{$pc} = 1;

    # say "$pc: $instruction<operation> $instruction<argument>";

    given $instruction<operation> {
        when 'nop' {
            $pc++;
        }
        when 'acc' {
            $acc += $instruction<argument>;
            $pc++;
        }
        when 'jmp' {
            $pc += $instruction<argument>;
        }
    }
}

say $acc;

Each line of the program is parsed with a regex / (\w+) ' ' (\S+) /, and the parsed instruction is saved in the @program array. Then we execute the instructions and also keep track of those that were executed. As soon as %pc{$pc}:exists we know we made a loop, so the program can be stopped and the value of $acc printed.

In the second part of the problem, we need to replace one of the nop or one of the jmp opcodes with, respectively, jmp and nop. It is only possible to make only one such change in the whole program, and this change should eliminate the loop. If such a change makes it possible to reach the end of the program, we succeeded. Accumulator’s value is the expected result.

My approach is to embrace the central part of the program with another loop, where I will try different opcode replacements. In the end, the first good replacement allows us to execute the whole program.

my @program;

for 'input.txt'.IO.lines -> $line {
    $line ~~ / (\w+) ' ' (\S+) /;
    
    @program.push: {
        operation => $/[0].Str,
        argument => $/[1].Int,
    };
}

my $replacement-pos = 0;
my $pc = 0;
my $acc;
until $pc >= @program.end {
    my %pc;
    $pc = 0;
    $acc = 0;
    my $nop-jmp = 0;

    while !(%pc{$pc}:exists) && $pc <= @program.end {
        my $instruction = @program[$pc];
        %pc{$pc} = 1;

        # say "$pc: $instruction<operation> $instruction<argument>";

        my $operation = $instruction<operation>;
        if $operation eq 'nop' | 'jmp' {
            if $nop-jmp == $replacement-pos {
                $operation = $operation eq 'nop' ?? 'jmp' !! 'nop';
                # say "REPLACED";
            }
            $nop-jmp++;
        }

        given $operation {
            when 'nop' {
                $pc++;
            }
            when 'acc' {
                $acc += $instruction<argument>;
                $pc++;
            }
            when 'jmp' {
                $pc += $instruction<argument>;
            }
        }
    }

    $replacement-pos++;
}

say $acc;

* * *

→ Browse the code on GitHub
→ See all blog posts on Advent of Code 2020