#!/usr/bin/env perl
use strict;
use warnings;

use Storable qw(dclone);

# Read in the grid
my @G;
my $i = 0;
while (<ARGV>) {
    chomp;
    $G[$i] = [split('', $_)];
    $i++;
}

$i = 0;
while (evolve(\@G)) {
    print "Evolving ... $i\n";
    $i++;
}

my $total = 0;
for my $r (@G) {
    $total += scalar grep { $_ eq '#' } @$r;
}
print "$total\n";

# TRICK! because floor is static, the neighbors NEVER CHANGE
# so we can pay the cost of finding them once, and then never
# again :)
my %neigh_cache;
sub neigh {
    my ($i, $j, $G) = @_;
    my $key = "$i,$j";
    if (exists $neigh_cache{$key}) {
        return @{$neigh_cache{$key}};
    }

    # Not in cache, compute
    my $R = scalar @$G;
    my $C = scalar @{$G->[0]};
    my $finder = sub {
        my ($updater) = @_;
        my ($si, $sj) = $updater->($i, $j);
        while ($si >= 0 && $si < $R && $sj >= 0 && $sj < $C) {
            if ($G->[$si]->[$sj] ne '.') {
                return [$si, $sj];
            }
            ($si, $sj) = $updater->($si, $sj);
        }
        return;
    };

    my @neighs = grep { defined($_) } (
        $finder->(sub { return $_[0] + 1, $_[1] }),
        $finder->(sub { return $_[0] - 1, $_[1] }),
        $finder->(sub { return $_[0] + 1, $_[1] + 1 }),
        $finder->(sub { return $_[0] + 1, $_[1] - 1 }),
        $finder->(sub { return $_[0] - 1, $_[1] + 1 }),
        $finder->(sub { return $_[0] - 1, $_[1] - 1 }),
        $finder->(sub { return $_[0], $_[1] + 1 }),
        $finder->(sub { return $_[0], $_[1] - 1 }),
    );
    $neigh_cache{$key} = \@neighs;
    return @neighs;
}

sub evolve {
    my ($G) = @_;
    # 1. deep clone
    # 2. for loop over grid, change (mark did_change)
    # 3. return did_change
    my $orig = dclone($G);
    my $did_change;

    my $R = scalar @$orig;
    my $C = scalar @{$orig->[0]};
    for (my $i = 0; $i < $R; $i++) {
        for (my $j = 0; $j < $C; $j++) {
            my $seat = $orig->[$i]->[$j];
            next if $seat eq '.'; # floor don't change
            
            # neighbors...
            my @coords = neigh($i, $j, $orig);
            my @neighs = map { $orig->[$_->[0]]->[$_->[1]] } @coords;
            my $num_occ = scalar grep { $_ eq '#' } @neighs;

            if ($seat eq 'L' && $num_occ == 0) {
                $G->[$i]->[$j] = '#';
                $did_change = 1;
            } elsif ($seat eq '#' && $num_occ >= 5) {
                $G->[$i]->[$j] = 'L';
                $did_change = 1;
            }
        }
    }

    return $did_change;;
}
