2016/44.pl

   1 #!/usr/bin/perl -w
   2
   3 use strict;
   4 use v5.30;
   5
   6 $_ = <>; # header
   7 $_ = <>; # header
   8 $; = ',';
   9
  10 my (%dead);
  11 my ($xmax, $ymax);
  12 my ($fx, $fy);
  13 while (<>) {
  14         my ($x, $y, $size, $used) = m|/dev/grid/node-x(\d+)-y(\d+)\s+(\d+)T\s+(\d+)T|;
  15         die "no match at $_" if !defined $used;
  16         if ($size > 100) {
  17                 $dead{$x,$y} = 1;
  18         } elsif ($used == 0) {
  19                 $fx = $x;
  20                 $fy = $y;
  21         }
  22         $xmax = $x if !$xmax || $xmax < $x;
  23         $ymax = $y if !$ymax || $ymax < $y;
  24 }
  25
  26 use Array::Heap;
  27 my @q = ( [ $xmax + $xmax-$fx + $fy, $xmax, 0, $fx, $fy, 0 ] );
  28
  29 my %seen;
  30 while (@q) {
  31         my $state = pop_heap @q;
  32         my ($score, $gx, $gy, $fx, $fy, $steps) = @$state;
  33         say "score $score, goal at $gx,$gy, free at $fx,$fy, steps $steps";
  34         last if $gx == 0 && $gy == 0;
  35         for ([0, 1], [0, -1], [1, 0], [-1, 0]) {
  36                 my ($dx, $dy) = ($fx + $_->[0], $fy + $_->[1]);
  37                 next if $dx < 0 || $dx > $xmax || $dy < 0 || $dy > $ymax;
  38                 next if $dead{$dx,$dy};
  39                 my ($ngx, $ngy) = ($gx, $gy);
  40                 if ($dx == $gx && $dy == $gy) {
  41                         ($ngx, $ngy) = ($fx, $fy);
  42                 }
  43                 next if $seen{$ngx,$ngy,$dx,$dy}++;
  44                 my $nscore = $ngx+$ngy+abs($dx-$ngx)+abs($dy-$ngy);
  45                 push_heap @q, [ $nscore,
  46                         $ngx, $ngy, $dx, $dy, $steps+1 ];
  47                 say "    F->$dx,$dy $nscore";
  48         }
  49 }