2019/36.pl

   1 #!/usr/bin/perl -w
   2
   3 use v5.36;
   4 use Data::Dumper;
   5 use Array::Heap;
   6 use feature 'multidimensional';
   7
   8 my @map = map { chomp; [ split // ] } <>;
   9
  10 my %pos_of;
  11 for my $y (0 .. $#map) {
  12         for my $x (0 .. $#{ $map[0]}) {
  13                 my $c = $map[$y][$x];
  14                 next if $c !~ /[a-z1-4]/;
  15                 $pos_of{$c} = [ $x, $y ];
  16         }
  17 }
  18
  19 my $nkeys = keys %pos_of;
  20 say "nkeys = $nkeys";
  21
  22 $; = ';';
  23
  24 my $best;
  25
  26 my $min_dist = 1_000_000;
  27
  28 my %min_cost;
  29 my $max_opened;
  30 my $max_cost;
  31 my @q0;
  32 sub walk {
  33         my ($cost0, $cost, @opened) = @_;
  34
  35         my @robots = splice(@opened, 0, 4);
  36         my %opened = map { $_ => 1 } @opened;
  37
  38         my $key = join('', $robots[0], sort(@robots[1..3]), '|', sort @opened);
  39
  40         if (defined $min_cost{$key} && $min_cost{$key} <= $cost) {
  41                 return;
  42         }
  43
  44         $min_cost{$key} = $cost;
  45
  46         $max_opened = @opened if (!defined $max_opened || @opened > $max_opened);
  47         if (!defined $max_cost || $max_cost < $cost) {
  48                 $max_cost = $cost;
  49                 say "walk $cost - $key ", length $key, ' ', $max_opened;
  50         }
  51         if ($nkeys == @opened) {
  52                 say "Found!";
  53                 exit 1;
  54         }
  55
  56
  57         my $p = $pos_of{$robots[0]};
  58         my @q = [ @$p, $cost ];
  59
  60         my %seen;
  61         $seen{$p->[0],$p->[1]} = 1;
  62
  63         my %dist;
  64
  65         while (my $pos = shift @q) {
  66                 my ($x, $y, $steps) = @$pos;
  67
  68                 my $v = $map[$y][$x];
  69                 next if $v eq '#';
  70                 if ($v =~ /[a-z]/ && !$opened{$v}) {
  71                         $dist{$v} //= $steps;
  72                         my $cost = $steps + $nkeys - @opened;
  73                         # say "opened=". scalar @opened;
  74                         push_heap @q0, [ $cost, $steps, $v, @robots[1..3], $v, @opened ];
  75                         push_heap @q0, [ $cost, $steps, $robots[1], $v, @robots[2..3], $v, @opened ];
  76                         push_heap @q0, [ $cost, $steps, $robots[2], $v, @robots[1,3], $v, @opened ];
  77                         push_heap @q0, [ $cost, $steps, $robots[3], $v, @robots[1..2], $v, @opened ];
  78                 }
  79                 if ($v =~ /[A-Z]/) {
  80                         next if !$opened{lc($v)};
  81                 }
  82
  83                 for my ($dx, $dy) (1, 0, 0, 1, -1, 0, 0, -1) {
  84                         my ($nx, $ny) = ($x + $dx, $y + $dy);
  85                         next if $seen{$nx,$ny}++;
  86                         push @q, [ $nx, $ny, $steps+1 ];
  87                 }
  88         }
  89 }
  90
  91 push_heap @q0, [0, 0, 1, 2, 3, 4, 1, 2, 3, 4];
  92 while (@q0) {
  93         my $elem = pop_heap @q0;
  94         walk(@$elem);
  95 }
  96