2023/42.pl

   1 #!/usr/bin/perl -w
   2
   3 use v5.38;
   4 use experimental 'multidimensional';
   5 $; = ';';
   6
   7 my @map;
   8 my ($sx, $sy);
   9 while (<>) {
  10         chomp;
  11         if (/S/g) {
  12                 $sx = pos()-1;
  13                 $sy = $.-1;
  14                 s/S/./;
  15         }
  16         push @map, [ split // ];
  17 }
  18 my $xmax = $#{ $map[0] };
  19 my $ymax = $. - 1;
  20
  21 my @dx = (1, 0, -1, 0);
  22 my @dy = (0, 1, 0, -1);
  23
  24 my @sums;
  25 my @oddeven;
  26 my @todo = [ $sx, $sy ];
  27 my %seen;
  28 $seen{$sx,$sy}++;
  29
  30 for my $step (0 .. 1000) {
  31         my @ntodo;
  32         for my $pt (@todo) {
  33                 my ($x, $y) = @$pt;
  34                 $oddeven[$step & 1]++;
  35                 for my $d (0 .. 3) {
  36                         my $nx = $x + $dx[$d];
  37                         my $ny = $y + $dy[$d];
  38                         next if $map[$ny % ($ymax + 1)][$nx % ($xmax + 1)] ne '.';
  39                         next if $seen{$nx,$ny}++;
  40                         push @ntodo, [$nx, $ny];
  41                 }
  42         }
  43
  44         push @sums, $oddeven[$step & 1];
  45         @todo = @ntodo;
  46 }
  47
  48 my $start = 100;
  49 my $period = 1;
  50 my $steps = 26501365;
  51
  52 PERIOD:
  53 while ($period++) {
  54         for my $i ($start .. ($#sums - 3*$period)) {
  55                 my @d;
  56                 push @d, $sums[$i+($_+1)*$period]
  57                         -$sums[$i+$_*$period]
  58                         for 0 .. 2;
  59                 next PERIOD if $d[1]-$d[0] != $d[2]-$d[1];
  60         }
  61         last;
  62 }
  63
  64 $start += ($steps - $start) % $period;
  65 my $a = $sums[$start+$period] - $sums[$start];
  66 my $d = $sums[$start+2*$period] - $sums[$start+$period] - $a;
  67 my $n = ($steps - $start) / $period;
  68 say $sums[$start] + (2*$a + ($n-1)*$d)*$n/2;
  69