Moved 2021 to a subdir

[aoc.git] / 2021 / 44.pl

diff --git a/2021/44.pl b/2021/44.pl
new file mode 100755 (executable)
index 0000000..c98c77f
--- /dev/null
+++ b/2021/44.pl
@@ -0,0 +1,80 @@
+#!/usr/bin/perl -w
+
+use v5.16;
+
+$; = ',';
+my @cuboids;
+while (<>) {
+       my $state = /^on / ? 1 : 0;
+       my ($xmin, $xmax, $ymin, $ymax, $zmin, $zmax) = /-?\d+/g;
+       ($xmin, $xmax) = ($xmax, $xmin) if $xmax < $xmin;
+       ($ymin, $ymax) = ($ymax, $ymin) if $ymax < $ymin;
+       ($zmin, $zmax) = ($zmax, $zmin) if $zmax < $zmin;
+       push @cuboids, [$xmin, $xmax, $ymin, $ymax, $zmin, $zmax, $state];
+}
+
+sub overlaps_int {
+       my ($min1, $max1, $min2, $max2) = @_;
+       return ($min1 >= $min2 && $min1 <= $max2)
+               || ($max1 >= $min2 && $max1 <= $max2)
+               || ($min1 <= $min2 && $max1 >= $max2)
+               || ($min1 >= $min2 && $max1 <= $max2);
+}
+
+sub overlaps_axis {
+       my ($c1, $c2, $axis) = @_;
+       $axis *=2;
+       return overlaps_int($c1->[$axis], $c1->[$axis+1], $c2->[$axis], $c2->[$axis+1]);
+}
+
+my @on_cuboids;
+for my $c1 (@cuboids) {
+       my @on_new;
+       CUBOID:
+       while (@on_cuboids) {
+               my $c2 = shift @on_cuboids;
+               for (0 .. 2) { # does $c1 overlap $c2?
+                       if (!overlaps_axis($c1, $c2, $_)) {
+                               push @on_new, $c2;
+                               next CUBOID;
+                       }
+               }
+               for (0 .. 2) {
+                       my ($min, $max) = (2*$_, 2*$_+1);
+                       if ($c1->[$min] > $c2->[$min] && $c1->[$min] <= $c2->[$max]) {
+                               my @c = @$c2;
+                               $c[$max] = $c1->[$min]-1;
+                               push @on_cuboids, [ @c ];
+                               @c = @$c2;
+                               $c[$min] = $c1->[$min];
+                               push @on_cuboids, [ @c ];
+                               next CUBOID;
+                       }
+                       if ($c1->[$max] >= $c2->[$min] && $c1->[$max] < $c2->[$max]) {
+                               my @c = @$c2;
+                               $c[$max] = $c1->[$max];
+                               push @on_cuboids, [ @c ];
+                               @c = @$c2;
+                               $c[$min] = $c1->[$max]+1;
+                               push @on_cuboids, [ @c ];
+                               next CUBOID;
+                       }
+                       if ($c1->[$min] > $c2->[$min]
+                               || $c1->[$max] < $c2->[$max]) {
+                               push @on_new, $c2;
+                               next CUBOID;
+                       }
+               }
+       }
+       push @on_new, $c1 if $c1->[6];
+       @on_cuboids = @on_new;
+}
+
+my $count;
+for my $c1 (@on_cuboids) {
+       $count += ($c1->[1] - $c1->[0] + 1)
+               * ($c1->[3] - $c1->[2] + 1)
+               * ($c1->[5] - $c1->[4] + 1);
+}
+
+say $count;