Year 2018

[aoc.git] / 2018 / 40.pl

diff --git a/2018/40.pl b/2018/40.pl
new file mode 100755 (executable)
index 0000000..6a7e76c
--- /dev/null
+++ b/2018/40.pl
@@ -0,0 +1,110 @@
+#!/usr/bin/perl -w
+
+use v5.36;
+use strict;
+use List::Util qw(max);
+use feature 'multidimensional';
+
+my (%hdoor, %vdoor);
+my ($minx, $miny, $maxx, $maxy) = (0, 0, 0, 0);
+my $was_change;
+my $maxdist;
+chomp (my $re = <>);
+
+$re =~ s/\A\^//;
+$re =~ s/\$\z//;
+
+sub walk($positions, $re) {
+       my @npos;
+       my %seen;
+       for my $p (@$positions) {
+               next if $seen{$p->[0],$p->[1]}++;
+               push @npos, [ @$p ];
+       }
+
+        say "len=", length($re), " npos=", scalar @npos;
+
+       my @rv;
+
+       while (length $re) {
+               my ($first, $rest) = $re =~ /\A(.)(.*)\z/;
+
+               if ($first =~ /[NSWE]/) {
+                       for my $p (@npos) {
+                               my ($x, $y) = @$p;
+                               if    ($first eq 'N') { $hdoor{$x,$y} = 1; $y--; }
+                               elsif ($first eq 'S') { $y++; $hdoor{$x,$y} = 1; }
+                               elsif ($first eq 'W') { $vdoor{$x,$y} = 1; $x--; }
+                               elsif ($first eq 'E') { $x++; $vdoor{$x,$y} = 1; }
+                               $p->[0] = $x;
+                               $p->[1] = $y;
+                               $minx = $x if $minx > $x;
+                               $maxx = $x if $maxx < $x;
+                               $miny = $y if $miny > $y;
+                               $maxy = $y if $maxy < $y;
+                       }
+               } elsif ($first eq '|') {
+                       push @rv, @npos;
+                       @npos = map { [ @$_ ] } @$positions;
+               } elsif ($first eq ')') {
+                       push @rv, @npos;
+                       return (\@rv, $rest);
+               } elsif ($first eq '(') {
+                       my ($n, $re1) = walk(\@npos, $rest);
+                       @npos = @$n;
+                       $rest = $re1;
+               }
+               $re = $rest;
+       }
+       return (\@npos, '');
+}
+
+sub print_map {
+       for my $y ($miny .. $maxy+1) {
+               for my $x ($minx .. $maxx) {
+                       print $hdoor{$x,$y} ? '#-' : '##';
+               }
+               print "#\n";
+               if ($y <= $maxy) {
+                       for my $x ($minx .. $maxx) {
+                               print $vdoor{$x,$y} ? '|.' : '#.';
+                       }
+                       print "#\n";
+               }
+       }
+}
+
+walk([ [0, 0] ], $re);
+print_map();
+
+my @q = ([ 0, 0, 0 ]);
+my %seen;
+$seen{0,0} = 1;
+my $max_dist = 0;
+my $rooms = 0;
+
+while (@q) {
+       my $h = shift @q;
+       my ($x, $y, $dist) = @$h;
+       $rooms++ if $dist >= 1000;
+       
+       if (!$max_dist || $dist > $max_dist) {
+               $max_dist = $dist;
+       }
+       if ($hdoor{$x,$y} && !$seen{$x,$y-1}++) {
+               push @q, [$x, $y-1, $dist+1];
+       }
+       if ($hdoor{$x,$y+1} && !$seen{$x,$y+1}++) {
+               push @q, [$x, $y+1, $dist+1];
+       }
+       if ($vdoor{$x,$y} && !$seen{$x-1,$y}++) {
+               push @q, [$x-1, $y, $dist+1];
+       }
+       if ($vdoor{$x+1,$y} && !$seen{$x+1,$y}++) {
+               push @q, [$x+1, $y, $dist+1];
+       }
+}
+
+say $max_dist;
+
+say $rooms;