2023/46.pl

   1 #!/usr/bin/perl -w
   2
   3 use v5.38;
   4 use experimental 'multidimensional';
   5 use Array::Heap;
   6 $; = ',';
   7
   8 my @map = map { chomp; y/<>^v/..../; [ split // ] } <>;
   9 my $xmax = $#{ $map[0] };
  10 my $ymax = $#map;
  11
  12 my @dx = (1, 0, -1, 0);
  13 my @dy = (0, 1, 0, -1);
  14
  15 my @crossings = ([1, 0], [$xmax-1, $ymax]);
  16
  17 for my $y (1 .. $ymax-1) {
  18         for my $x (1 .. $xmax-1) {
  19                 next if $map[$y][$x] ne '.';
  20                 my $cnt;
  21                 for my $d (0 .. 3) {
  22                         my $nx = $x + $dx[$d];
  23                         my $ny = $y + $dy[$d];
  24                         $cnt++ if $map[$ny][$nx] eq '.';
  25                 }
  26                 next if $cnt <= 2;
  27                 say "cross ", scalar @crossings, " at $x,$y: $cnt";
  28                 push @crossings, [$x,$y];
  29         }
  30 }
  31
  32 my %is_cross;
  33 for (0 .. $#crossings) {
  34         $is_cross{$crossings[$_]->[0],$crossings[$_]->[1]} = $_;
  35 }
  36
  37 my %xnei;
  38
  39 my %seen;
  40 my @q = [ 1, 1, 0, 0, 0 ];
  41 while (@q) {
  42         my ($x, $y, $len, $prevx, $prevdist) = @{ shift @q };
  43
  44         if (defined $is_cross{$x,$y}) {
  45                 my $self = $is_cross{$x,$y};
  46                 if (defined $prevx) {
  47                         if ($self != $prevx) {
  48                                 my $l = $len - $prevdist;
  49                                 say "$prevx-$self $l";
  50                                 $xnei{$self}{$prevx} = $l;
  51                                 $xnei{$prevx}{$self} = $l;
  52                         }
  53                 }
  54                 $prevx = $self;
  55                 $prevdist = $len;
  56         }
  57         next if $seen{$x,$y,$prevx}++;
  58
  59         for my $d (0 .. 3) {
  60                 my $nx = $x + $dx[$d];
  61                 my $ny = $y + $dy[$d];
  62                 next if $ny == 0;
  63                 next if $ny > $ymax;
  64                 next if $map[$ny][$nx] eq '#';
  65                 push @q, [$nx, $ny, $len+1, $prevx, $prevdist];
  66         }
  67 }
  68
  69 my $maxlen = 0;
  70 %seen = ();
  71 sub walk {
  72         my ($self, $dist) = @_;
  73
  74         # say "at $self $dist @path";
  75         if ($self == 1) {
  76                 if ($maxlen < $dist) {
  77                         $maxlen = $dist;
  78                         say "$dist";
  79                 }
  80         }
  81         $seen{$self} = 1;
  82         for my $nxt (keys %{ $xnei{$self} }) {
  83                 next if $seen{$nxt};
  84                 walk($nxt, $dist + $xnei{$self}{$nxt});
  85         }
  86         $seen{$self} = 0;
  87 }
  88
  89 walk(0, 1);
  90