Year 2018

[aoc.git] / 2018 / 33.pl

diff --git a/2018/33.pl b/2018/33.pl
new file mode 100755 (executable)
index 0000000..60094a5
--- /dev/null
+++ b/2018/33.pl
@@ -0,0 +1,113 @@
+#!/usr/bin/perl -w
+
+use v5.30;
+use strict;
+
+my %map;
+
+my ($ymin, $ymax, $xmin, $xmax);
+
+while (<>) {
+       chomp;
+       my ($c1n, $c1, $c2min, $c2max) = /\A(.)=(\d+), .=(\d+)\.\.(\d+)/;
+
+       for my $c2 ($c2min .. $c2max) {
+               if ($c1n eq 'x') {
+                       $map{$c1}{$c2} = '#';
+                       $ymin = $c2 if !defined $ymin || $ymin > $c2;
+                       $ymax = $c2 if !defined $ymax || $ymax < $c2;
+                       $xmin = $c1 if !defined $xmin || $xmin > $c1;
+                       $xmax = $c1 if !defined $xmax || $xmax < $c1;
+               } else {
+                       $map{$c2}{$c1} = '#';
+                       $ymin = $c1 if !defined $ymin || $ymin > $c1;
+                       $ymax = $c1 if !defined $ymax || $ymax < $c1;
+                       $xmin = $c2 if !defined $xmin || $xmin > $c2;
+                       $xmax = $c2 if !defined $xmax || $xmax < $c2;
+               }
+       }
+}
+$xmin--;
+$xmax++;
+
+say "y=$ymin .. $ymax";
+
+my $iter = 0;
+sub dump_map {
+       return if $iter++ % 1000;
+       my $total = 0;
+       for my $y (0 .. $ymax) {
+               for my $x ($xmin .. $xmax) {
+                       print $map{$x}{$y} // ' ';
+                       $total++ if defined $map{$x}{$y}
+                               && $map{$x}{$y} =~ /[~0]/;
+               }
+               print "\n";
+       }
+       say "total=$total";
+       return $total;
+}
+
+dump_map();
+
+my $total = 0;
+
+sub explore {
+       my ($x, $y) = @_;
+       return 0 if $y > $ymax;
+       $map{$x}{$y} //= 0;
+       my $was_change;
+       while (1) {
+               $was_change = 0;
+               say "explore $x, $y";
+               dump_map();
+               my $xp = $x;
+               while ($map{$xp}{$y+1}) {
+                       last if $map{$xp+1}{$y};
+                       $xp++;
+                       $map{$xp}{$y} //= 0;
+               }
+               my $xm = $x;
+               while ($map{$xm}{$y+1}) {
+                       last if $map{$xm-1}{$y};
+                       $xm--;
+                       $map{$xm}{$y} //= 0;
+               }
+
+               say "$xm .. $xp";
+               if (!$map{$xp}{$y+1} && $y < $ymax) {
+                       $map{$xp}{$y} //= 0;
+                       if (!defined $map{$xp}{$y+1}) {
+                               say "calling to $xp, $y+1";
+                               $was_change += explore($xp, $y+1);
+                       }
+               }
+
+               if (!$map{$xm}{$y+1} && $y < $ymax) {
+                       $map{$xm}{$y} //= 0;
+                       if (!defined $map{$xm}{$y+1}) {
+                               say "calling to $xm, $y+1";
+                               $was_change += explore($xm, $y+1);
+                       }
+               }
+               say "was_change = $was_change";
+               
+               next if $was_change;
+
+               if ($map{$xp+1}{$y} && $map{$xm-1}{$y}) {
+                       for my $x0 ($xm .. $xp) {
+                               $map{$x0}{$y} = '~';
+                       }
+                       return 1;
+               }
+               last;
+       }
+       say "$x,$y returning $was_change";
+       return $was_change;
+}
+
+explore(500, $ymin);
+
+$iter = 0;
+dump_map();
+