aoc

Advent of Code Solutions
git clone git://git.alexkarle.com.com/aoc
Log | Files | Refs | README | LICENSE

sol2.pl (2536B) [raw]

      1 #!/usr/bin/env perl
      2 use strict;
      3 use warnings;
      4 
      5 use Storable qw(dclone);
      6 
      7 # Read in the grid
      8 my @G;
      9 my $i = 0;
     10 while (<ARGV>) {
     11     chomp;
     12     $G[$i] = [split('', $_)];
     13     $i++;
     14 }
     15 
     16 $i = 0;
     17 while (evolve(\@G)) {
     18     print "Evolving ... $i\n";
     19     $i++;
     20 }
     21 
     22 my $total = 0;
     23 for my $r (@G) {
     24     $total += scalar grep { $_ eq '#' } @$r;
     25 }
     26 print "$total\n";
     27 
     28 # TRICK! because floor is static, the neighbors NEVER CHANGE
     29 # so we can pay the cost of finding them once, and then never
     30 # again :)
     31 my %neigh_cache;
     32 sub neigh {
     33     my ($i, $j, $G) = @_;
     34     my $key = "$i,$j";
     35     if (exists $neigh_cache{$key}) {
     36         return @{$neigh_cache{$key}};
     37     }
     38 
     39     # Not in cache, compute
     40     my $R = scalar @$G;
     41     my $C = scalar @{$G->[0]};
     42     my $finder = sub {
     43         my ($updater) = @_;
     44         my ($si, $sj) = $updater->($i, $j);
     45         while ($si >= 0 && $si < $R && $sj >= 0 && $sj < $C) {
     46             if ($G->[$si]->[$sj] ne '.') {
     47                 return [$si, $sj];
     48             }
     49             ($si, $sj) = $updater->($si, $sj);
     50         }
     51         return;
     52     };
     53 
     54     my @neighs = grep { defined($_) } (
     55         $finder->(sub { return $_[0] + 1, $_[1] }),
     56         $finder->(sub { return $_[0] - 1, $_[1] }),
     57         $finder->(sub { return $_[0] + 1, $_[1] + 1 }),
     58         $finder->(sub { return $_[0] + 1, $_[1] - 1 }),
     59         $finder->(sub { return $_[0] - 1, $_[1] + 1 }),
     60         $finder->(sub { return $_[0] - 1, $_[1] - 1 }),
     61         $finder->(sub { return $_[0], $_[1] + 1 }),
     62         $finder->(sub { return $_[0], $_[1] - 1 }),
     63     );
     64     $neigh_cache{$key} = \@neighs;
     65     return @neighs;
     66 }
     67 
     68 sub evolve {
     69     my ($G) = @_;
     70     # 1. deep clone
     71     # 2. for loop over grid, change (mark did_change)
     72     # 3. return did_change
     73     my $orig = dclone($G);
     74     my $did_change;
     75 
     76     my $R = scalar @$orig;
     77     my $C = scalar @{$orig->[0]};
     78     for (my $i = 0; $i < $R; $i++) {
     79         for (my $j = 0; $j < $C; $j++) {
     80             my $seat = $orig->[$i]->[$j];
     81             next if $seat eq '.'; # floor don't change
     82             
     83             # neighbors...
     84             my @coords = neigh($i, $j, $orig);
     85             my @neighs = map { $orig->[$_->[0]]->[$_->[1]] } @coords;
     86             my $num_occ = scalar grep { $_ eq '#' } @neighs;
     87 
     88             if ($seat eq 'L' && $num_occ == 0) {
     89                 $G->[$i]->[$j] = '#';
     90                 $did_change = 1;
     91             } elsif ($seat eq '#' && $num_occ >= 5) {
     92                 $G->[$i]->[$j] = 'L';
     93                 $did_change = 1;
     94             }
     95         }
     96     }
     97 
     98     return $did_change;;
     99 }