The rest of Year 2016

[aoc.git] / 2016 / 47.pl

diff --git a/2016/47.pl b/2016/47.pl
new file mode 100755 (executable)
index 0000000..2810d61
--- /dev/null
+++ b/2016/47.pl
@@ -0,0 +1,72 @@
+#!/usr/bin/perl -w
+
+use strict;
+use v5.30;
+
+my @ducts;
+my %duct_pos;
+my @map;
+while (<>) {
+       chomp;
+       push @map, [ split // ];
+       my $line = $_;
+       while ($line =~ /\d/g) {
+               my $x = pos($line) - 1;
+               my $y = $#map;
+               $ducts[$&] = [ $x, $y ];
+               $duct_pos{$x,$y} = $&;
+               say "$& at ", pos($line)-1, ",$#map";
+       }
+}
+
+my $xmax = $#{ $map[0] };
+my $ymax = $#map;
+$; = ',';
+
+my %dist;
+
+sub walk {
+       my ($duct) = @_;
+       
+       my ($x, $y) = @{ $ducts[$duct] };
+       my @q = ([ $x, $y, 0 ]);
+       my %seen = ("$x,$y" => 1);
+       my $ducts_seen = 0;
+       while (@q) {
+               my $entry = shift @q;
+               my ($x, $y, $dist) = @$entry;
+               if ($map[$y][$x] =~ /\d/) {
+                       $dist{$duct}{$&} = $dist;
+                       say "dist $duct -> $& = $dist";
+                       return if (++$ducts_seen >= @ducts);
+               }
+               for ([0, 1], [0, -1], [1, 0], [-1, 0]) {
+                       my $dx = $x + $_->[0];
+                       my $dy = $y + $_->[1];
+                       next if $dx < 0 || $dx > $xmax || $dy < 0 || $dy > $ymax
+                               || $map[$y][$x] eq '#';
+                       next if $seen{$dx,$dy}++;
+                       push @q, [ $dx, $dy, $dist+1];
+               }
+       }
+}
+
+walk($_) for 0 .. 7;
+
+my $min_dist;
+
+sub perm {
+       my ($dist, $now, @rest) = @_;
+       if (!@rest) {
+               $min_dist = $dist if !defined $min_dist || $dist < $min_dist;
+       }
+       for my $i (0 .. $#rest) {
+               my @nr = @rest;
+               my $duct = splice @nr, $i, 1;
+               perm($dist + $dist{$now}{$duct}, $duct, @nr);
+       }
+}
+
+perm(0, 0 .. 7);
+
+say $min_dist;