2023/45.pl

   1 #!/usr/bin/perl -w
   2
   3 use v5.38;
   4 use experimental 'multidimensional';
   5 $; = ',';
   6
   7 my @map = map { chomp; [ split // ] } <>;
   8 my $xmax = $#{ $map[0] };
   9 my $ymax = $#map;
  10
  11 my @dx = (1, 0, -1, 0);
  12 my @dy = (0, 1, 0, -1);
  13
  14 my %seen;
  15 my @q = [ 1, 1, 1, [1, 1] ];
  16 while (@q) {
  17         my ($x, $y, $steps, @path) = @{ shift @q };
  18
  19         next if $seen{$x,$y} && $seen{$x,$y} > $steps;
  20         $seen{$x,$y} = $steps;
  21         if ($x == $xmax-1 && $y == $ymax) {
  22                 say "at $x,$y, $steps, ", join(' ', map { "[$_->[0],$_->[1]]" } @path);
  23                 say "path len $steps";
  24                 next;
  25         }
  26         my %visited;
  27         $visited{$_->[0],$_->[1]} = 1 for @path;
  28         for my $d (0 .. 3) {
  29                 my $nx = $x + $dx[$d];
  30                 my $ny = $y + $dy[$d];
  31                 next if $map[$ny][$nx] eq '#';
  32                 next if $ny == 0;
  33                 next if $visited{$nx,$ny};
  34                 next if $d != 0 && $map[$y][$x] eq '>';
  35                 next if $d != 1 && $map[$y][$x] eq 'v';
  36                 next if $d != 2 && $map[$y][$x] eq '<';
  37                 next if $d != 3 && $map[$y][$x] eq '^';
  38                 push @q, [ $nx, $ny, $steps+1, @path, [ $nx, $ny ] ];
  39         }
  40 }
  41