2022/48.pl

   1 #!/usr/bin/perl -w
   2
   3 use v5.36;
   4 use strict;
   5 use Array::Heap;
   6
   7 my @map = map { chomp; [ split // ] } <>;
   8 my $xmax = $#{$map[0]};
   9 my $ymax = $#map;
  10
  11 my $mod;
  12 if ($xmax == 101 && $ymax == 36) { # too lazy to compute GCD
  13         $mod = 700;
  14 } else {
  15         $mod = ($xmax-1) * ($ymax-1);
  16 }
  17
  18 my @nmaps;
  19 sub occupied($x,$y,$time) {
  20         my $t = $time % $mod;
  21         my $nmap = $nmaps[$t];
  22         return $nmap->{"$x,$y"}
  23                 if defined $nmap;
  24         for my $y (0 .. $ymax) {
  25                 for my $x (0 .. $xmax) {
  26                         next if ($map[$y][$x] eq '.');
  27                         my ($nx, $ny) = ($x, $y);
  28                         if ($map[$y][$x] eq '>') {
  29                                 $nx = 1 + (($x+$t-1) % ($xmax-1));
  30                         } elsif ($map[$y][$x] eq 'v') {
  31                                 $ny = 1 + (($y+$t-1) % ($ymax-1));
  32                         } elsif ($map[$y][$x] eq '^') {
  33                                 $ny = 1 + (($y-$t-1) % ($ymax-1));
  34                         } elsif ($map[$y][$x] eq '<') {
  35                                 $nx = 1 + (($x-$t-1) % ($xmax-1));
  36                         }
  37                         if ($nmap->{"$nx,$ny"}) {
  38                                 if ($nmap->{"$nx,$ny"} =~ /\d/) {
  39                                         $nmap->{"$nx,$ny"}++;
  40                                 } else {
  41                                         $nmap->{"$nx,$ny"} = 2;
  42                                 }
  43                         } else {
  44                                 $nmap->{"$nx,$ny"} = $map[$y][$x];
  45                         }
  46                 }
  47         }
  48         $nmaps[$t] = $nmap;
  49         return $nmap->{"$x,$y"};
  50 }
  51
  52 my @q = [3*($xmax+$ymax), 1, 0, 0, 0];
  53 my %seen;
  54 while (@q) {
  55         my $now = pop_heap @q;
  56         my ($dist, $x, $y, $time, $phase) = @$now;
  57         my $key = join(',',$x, $y, ($time % $mod), $phase);
  58         next if $seen{$key}++;
  59         # say "at $x $y dist $dist time $time phase $phase";
  60         if ($phase % 2 == 0) {
  61                 if ($x == $xmax-1 && $y == $ymax) {
  62                         if (++$phase == 3) {
  63                                 say $time;
  64                                 last;
  65                         }
  66                 }
  67         } else {
  68                 if ($x == 1 && $y == 0) {
  69                         ++$phase;
  70                 }
  71         }
  72
  73         $time++;
  74         $dist++;
  75         my $add = ($phase % 2) ? -1 : 1;
  76         if (!occupied($x,$y,$time)) {
  77                 push_heap @q, [ $dist, $x, $y, $time, $phase ];
  78         }
  79         if (!occupied($x+1,$y,$time)) {
  80                 push_heap @q, [ $dist-$add, $x+1, $y, $time, $phase ];
  81         }
  82         if (!occupied($x-1,$y,$time)) {
  83                 push_heap @q, [ $dist+$add, $x-1, $y, $time, $phase ];
  84         }
  85         if ($y < $ymax && !occupied($x,$y+1,$time)) {
  86                 push_heap @q, [ $dist-$add, $x, $y+1, $time, $phase ];
  87         }
  88         if ($y > 0 && !occupied($x,$y-1,$time)) {
  89                 push_heap @q, [ $dist+$add, $x, $y-1, $time, $phase ];
  90         }
  91 }
  92