2016/48.pl

   1 #!/usr/bin/perl -w
   2
   3 use strict;
   4 use v5.30;
   5
   6 my @ducts;
   7 my %duct_pos;
   8 my @map;
   9 while (<>) {
  10         chomp;
  11         push @map, [ split // ];
  12         my $line = $_;
  13         while ($line =~ /\d/g) {
  14                 my $x = pos($line) - 1;
  15                 my $y = $#map;
  16                 $ducts[$&] = [ $x, $y ];
  17                 $duct_pos{$x,$y} = $&;
  18                 say "$& at ", pos($line)-1, ",$#map";
  19         }
  20 }
  21
  22 my $xmax = $#{ $map[0] };
  23 my $ymax = $#map;
  24 $; = ',';
  25
  26 my %dist;
  27
  28 sub walk {
  29         my ($duct) = @_;
  30
  31         my ($x, $y) = @{ $ducts[$duct] };
  32         my @q = ([ $x, $y, 0 ]);
  33         my %seen = ("$x,$y" => 1);
  34         my $ducts_seen = 0;
  35         while (@q) {
  36                 my $entry = shift @q;
  37                 my ($x, $y, $dist) = @$entry;
  38                 if ($map[$y][$x] =~ /\d/) {
  39                         $dist{$duct}{$&} = $dist;
  40                         say "dist $duct -> $& = $dist";
  41                         return if (++$ducts_seen >= @ducts);
  42                 }
  43                 for ([0, 1], [0, -1], [1, 0], [-1, 0]) {
  44                         my $dx = $x + $_->[0];
  45                         my $dy = $y + $_->[1];
  46                         next if $dx < 0 || $dx > $xmax || $dy < 0 || $dy > $ymax
  47                                 || $map[$y][$x] eq '#';
  48                         next if $seen{$dx,$dy}++;
  49                         push @q, [ $dx, $dy, $dist+1];
  50                 }
  51         }
  52 }
  53
  54 walk($_) for 0 .. 7;
  55
  56 my $min_dist;
  57
  58 sub perm {
  59         my ($dist, $now, @rest) = @_;
  60         if (!@rest) {
  61                 $dist += $dist{$now}{0};
  62                 $min_dist = $dist if !defined $min_dist || $dist < $min_dist;
  63         }
  64         for my $i (0 .. $#rest) {
  65                 my @nr = @rest;
  66                 my $duct = splice @nr, $i, 1;
  67                 perm($dist + $dist{$now}{$duct}, $duct, @nr);
  68         }
  69 }
  70
  71 perm(0, 0 .. 7);
  72
  73 say $min_dist;