Advent of Code Day 11 - slow SeatGoL

Finally, some Game of Life

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

Part 1

Today I needed quite a bit of code, so let's split it up:

my @map = map { chomp; [ split // ] } <>;
my $h   = @map;
my $w   = $map[0]->@*;
my $occ = 0;
my $max = 4;
my @around =
    ( [ -1, -1 ], [ -1, 0 ], [ -1, 1 ], [ 0, -1 ], [ 0, 1 ], [ 1, -1 ], [ 1, 0 ], [ 1, 1 ] );

After getting the input and storing it into a 2-dimensional list, I set up some other things we'll need: the **h**eight and **w**idth of the map, the number of occupied seats, the maximum number of neighbors and a list of "vectors" to look around (left/up, up, right/up, left, right, left/down, down, right/down) as array index offsets.

while (1) {
    my @next;
    my $thisocc = 0;
    for ( my $r = 0; $r < $h; $r++ ) {
        for ( my $c = 0; $c < $w; $c++ ) {
            my $new = $next[$r][$c] = gol( \@map, $r, $c );
            $thisocc++ if $new eq '#';
        }
    }
    last if $thisocc == $occ;
    @map = @next;
    $occ = $thisocc;
    say '.';
}
say $occ;

This is the main loop, which we run until the current number of occupied seats is the same is the previous number (last if $thisocc == $occ;). Inside the loop, we walk through the rows and cols of the map, and call the gol() function with the current map and position (see later). gol() will return the new value for this position, which we store in the new map (we cannot use the same map). If we get an occupied seat, we count it ($thisocc++ if $new eq '#').

Outside the loop, we check for termination. If we're not done yet, we define the newly generated map as the map to be used in the next iteration, and remember the current occupied count. And we output a ., so we know we're still running (this is a very slow solution, taking ~6 secs. I'm sure you can find faster algorithms on reddit...)

sub gol {
    my ( $map, $r, $c ) = @_;

    my $count = look( $map, $r, $c );
    my $old   = $map[$r][$c];
    return '#' if $old eq 'L' && $count == 0;
    return 'L' if $old eq '#' && $count >= $max;
    return $old;
}

gol() first calls another function, look(), to figure out how many seats around the current one are occupied. It the uses the old value and this count to figure out the next value and returns it.

sub look {
    my ( $map, $r, $c ) = @_;
    my $count = 0;
    foreach my $vec (@around) {
        my $m = $r + $vec->[0];
        my $n = $c + $vec->[1];
        next     if $m < 0 || $n < 0 || $m >= $h || $n >= $w;
        $count++ if $map[$m][$n] eq '#';
    }
    return $count;
}

look() uses the list of vectors to look around the current position, by calculating $m and $n. We skip if $m or $n are outside the map. And finally we increment the count if the place we are looking at is occupied (#).

Rather simple, but of course it took me some time to get all the parts arranged the right way. I'm quite sure that I have some nearly identical code lying around in last years repo. Maybe it would make sense to prepare a AdventOfCode helper distribution? Or is that cheating?

Part 2

The second part just changes the way consider which seats should be counted. I again implemented a simple brute-force solution (my trademark!). The original code was of course copy/pasted and manically adapted, but after my submission I cleaned up bot solutions and refactored them, so that we only need to change the look() function for part 2 (and the value of $max).

sub look {
    my ( $map, $r, $c ) = @_;
    my $count = 0;
    foreach my $vec (@around) {
        my $tr = $r;
        my $tc = $c;
        while (1) {
            my $m = $tr + $vec->[0];
            my $n = $tc + $vec->[1];
            last if $m < 0 || $n < 0 || $m >= $h || $n >= $w;
            my $val = $map[$m][$n];
            $count++ if $val eq '#';
            last unless $val eq '.';
            $tr = $m;
            $tc = $n;
        }
    }
    return $count;
}

We "only" need to add another loop to look further along the vector. I think this could be refactored even more, because both look() functions share a great deal of code. Patches welcome...

Stats & Links