/ domm

I hack Perl for fun and profit

Follow me on twitter!
Atom Icom ... on Atom!
03.01.2021: Bulk downloading all episodes of a podcast
12.12.2020: Advent of Code Day 12 - sailing to a pause
11.12.2020: Advent of Code Day 11 - slow SeatGoL
10.12.2020: Advent of Code Day 10 - trillion jolts
09.12.2020: Advent of Code Day 9 - while learning
08.12.2020: Advent of Code Day 8 - running code

This was a fun day. The first part was rather simple, but when I read the second part I thought that this will get very hard. It wasn't that bad in the end..

https://adventofcode.com/2020/day/8

Part 1

First we parse the input into an array containing another array with each op and value. As we need to stop when we've seen a line, we use the index $i of the code-array and exit the loop via last if $i was already seen.

my @code = map {[split(/ /)]} <>;
my %seen;
my $i   = 0;
my $acc = 0;
while (1) {
    last if $seen{$i}++;

    my ( $op, $val ) = $code[$i]->@*;
    if ( $op eq 'jmp' ) { $i   += $val; next }
    if ( $op eq 'acc' ) { $acc += $val }
    $i++;
}
say $acc;

To actually "execute" the code, we fetch the op and val of the current line. We jump (via next) if it's a jmp, we accumulate if it's acc; and we increment $i (which will not happen for jmp, because we already skipped the rest of the block)

Finally we just output the value of $acc

Part 2

Now we need to figure out which of 638 command we need to change to avoid an endless loop and get the "correct" result. Uff...

But in the end it's quite easy (and of course there are way more elegant solutions to be found on reddit).

I decided to copy the original code into a temporary code array, and then walk through the code, remembering which lines I already changed, and always only changing the first unchanged line. After the one line in the code is changed, I run() it, and if we get a result back, we exit and print.

my @original = <>;
my %tried;
my $acc;
while (1) {
    my @try = @original;
    for ( my $i = 0; $i < @original; $i++ ) {
        my $line = $try[$i];
        next if $line =~ /acc/;
        if ( $tried{$i}++ ) {
            next;
        }
        else {
            $line =~ /nop/ ? $line =~ s/nop/jmp/ : $line =~ s/jmp/nop/;
            $try[$i] = $line;
            last;
        }
    }

    $acc = run(@try);
    last if $acc;
}
say $acc;

sub run {
    my @code = @_;
    my %seen;
    my $i   = 0;
    my $acc = 0;
    while (1) {
        return 0    if $seen{$i}++;
        return $acc if $i >= @code;
        my ( $op, $val ) = split( / /, $code[$i] );

        if ( $op eq 'jmp' ) { $i   += $val; next }
        if ( $op eq 'acc' ) { $acc += $val }
        $i++;
    }
}

The run() function is basically the same as the solution for part 1, with the only change that we return 0 if the code looped, or the accumulators value if we reached the end of the code.

Stats & Links

Comments (via senph)

07.12.2020: Advent of Code Day 7 - baggy recursion
06.12.2020: Advent of Code Day 6 - simple counting
05.12.2020: Advent of Code Day 5 - hard fail
04.12.2020: Advent of Code Day 4 - validating regex
>>>>>>>>>>
<