From 30d5b6b31df9772b49ea4285806451aecc02b119 Mon Sep 17 00:00:00 2001
From: "Jan \"Yenya\" Kasprzak" <kas@fi.muni.cz>
Date: Wed, 22 Dec 2021 09:05:24 +0100
Subject: [PATCH] 44.pl: cleaner version, for arbitrary dimension

---
 44.pl | 119 ++++++++++++++++------------------------------------------
 1 file changed, 33 insertions(+), 86 deletions(-)

diff --git a/44.pl b/44.pl
index f045ecf..c98c77f 100755
--- a/44.pl
+++ b/44.pl
@@ -10,7 +10,6 @@ while (<>) {
 	($xmin, $xmax) = ($xmax, $xmin) if $xmax < $xmin;
 	($ymin, $ymax) = ($ymax, $ymin) if $ymax < $ymin;
 	($zmin, $zmax) = ($zmax, $zmin) if $zmax < $zmin;
-	say "cuboid ", join(',', $xmin, $xmax, $ymin, $ymax, $zmin, $zmax, $state);
 	push @cuboids, [$xmin, $xmax, $ymin, $ymax, $zmin, $zmax, $state];
 }
 
@@ -28,106 +27,54 @@ sub overlaps_axis {
 	return overlaps_int($c1->[$axis], $c1->[$axis+1], $c2->[$axis], $c2->[$axis+1]);
 }
 
-my @nonint;
+my @on_cuboids;
 for my $c1 (@cuboids) {
-	my @nonint2;
-	say "=======";
-	while (@nonint) {
-		my $c2 = shift @nonint;
-			say "[", join(',', @$c1), "] and\n[", join(',', @$c2), "] test for overlap";
-			if (($c1->[0] > $c2->[0] && $c1->[0] <= $c2->[1])
-				&& overlaps_axis($c1, $c2, 1)
-				&& overlaps_axis($c1, $c2, 2)) {
-				my @c = @$c2;
-				$c[1] = $c1->[0]-1;
-				push @nonint, [ @c ];
-				@c = @$c2;
-				$c[0] = $c1->[0];
-				push @nonint, [ @c ];
-				say "split at xmin=$c1->[0] :\n", join(',', @{ $nonint[-2] }), "\n", join(',', @{ $nonint[-1] }) ;
-				next;
-			}
-			if (($c1->[1] >= $c2->[0] && $c1->[1] < $c2->[1])
-				&& overlaps_axis($c1, $c2, 1)
-				&& overlaps_axis($c1, $c2, 2)) {
-				my @c = @$c2;
-				$c[1] = $c1->[1];
-				push @nonint, [ @c ];
-				@c = @$c2;
-				$c[0] = $c1->[1]+1;
-				push @nonint, [ @c ];
-				say "split at xmax=$c1->[1] :\n", join(',', @{ $nonint[-2] }), "\n", join(',', @{ $nonint[-1] }) ;
-				next;
-			}
-			if (($c1->[2] > $c2->[2] && $c1->[2] <= $c2->[3])
-				&& overlaps_axis($c1, $c2, 0)
-				&& overlaps_axis($c1, $c2, 2)) {
-				my @c = @$c2;
-				$c[3] = $c1->[2]-1;
-				push @nonint, [ @c ];
-				@c = @$c2;
-				$c[2] = $c1->[2];
-				push @nonint, [ @c ];
-				say "split at ymin=$c1->[2] :\n", join(',', @{ $nonint[-2] }), "\n", join(',', @{ $nonint[-1] }) ;
-				next;
+	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;
 			}
-			if (($c1->[3] >= $c2->[2] && $c1->[3] < $c2->[3])
-				&& overlaps_axis($c1, $c2, 0)
-				&& overlaps_axis($c1, $c2, 2)) {
+		}
+		for (0 .. 2) {
+			my ($min, $max) = (2*$_, 2*$_+1);
+			if ($c1->[$min] > $c2->[$min] && $c1->[$min] <= $c2->[$max]) {
 				my @c = @$c2;
-				$c[3] = $c1->[3];
-				push @nonint, [ @c ];
+				$c[$max] = $c1->[$min]-1;
+				push @on_cuboids, [ @c ];
 				@c = @$c2;
-				$c[2] = $c1->[3]+1;
-				push @nonint, [ @c ];
-				say "split at ymax=$c1->[3] :\n", join(',', @{ $nonint[-2] }), "\n", join(',', @{ $nonint[-1] }) ;
-				next;
+				$c[$min] = $c1->[$min];
+				push @on_cuboids, [ @c ];
+				next CUBOID;
 			}
-			if (($c1->[4] > $c2->[4] && $c1->[4] <= $c2->[5])
-				&& overlaps_axis($c1, $c2, 0)
-				&& overlaps_axis($c1, $c2, 1)) {
+			if ($c1->[$max] >= $c2->[$min] && $c1->[$max] < $c2->[$max]) {
 				my @c = @$c2;
-				$c[5] = $c1->[4]-1;
-				push @nonint, [ @c ];
+				$c[$max] = $c1->[$max];
+				push @on_cuboids, [ @c ];
 				@c = @$c2;
-				$c[4] = $c1->[4];
-				push @nonint, [ @c ];
-				say "split at zmin=$c1->[4] :\n", join(',', @{ $nonint[-2] }), "\n", join(',', @{ $nonint[-1] }) ;
-				next;
+				$c[$min] = $c1->[$max]+1;
+				push @on_cuboids, [ @c ];
+				next CUBOID;
 			}
-			if (($c1->[5] >= $c2->[4] && $c1->[5] < $c2->[5])
-				&& overlaps_axis($c1, $c2, 0)
-				&& overlaps_axis($c1, $c2, 1)) {
-				my @c = @$c2;
-				$c[5] = $c1->[5];
-				push @nonint, [ @c ];
-				@c = @$c2;
-				$c[4] = $c1->[5]+1;
-				push @nonint, [ @c ];
-				say "split at zmax=$c1->[5] :\n", join(',', @{ $nonint[-2] }), "\n", join(',', @{ $nonint[-1] }) ;
-				next;
+			if ($c1->[$min] > $c2->[$min]
+				|| $c1->[$max] < $c2->[$max]) {
+				push @on_new, $c2;
+				next CUBOID;
 			}
-		if (($c1->[0] <= $c2->[0] && $c1->[1] >= $c2->[1])
-			&& ($c1->[2] <= $c2->[2] && $c1->[3] >= $c2->[3])
-			&& ($c1->[4] <= $c2->[4] && $c1->[5] >= $c2->[5])) {
-			say "[", join(',', @$c1), "] fully encloses \n[", join(',', @$c2), "] = enclosed";
-		} else {
-			say "[", join(',', @$c1), "] and\n[", join(',', @$c2), "] do not overlap";
-			push @nonint2, $c2;
 		}
 	}
-	push @nonint2, $c1 if $c1->[6];
-	@nonint = @nonint2;
+	push @on_new, $c1 if $c1->[6];
+	@on_cuboids = @on_new;
+}
 
 my $count;
-for my $c1 (@nonint) {
-	my $size = ($c1->[1] - $c1->[0] + 1)
+for my $c1 (@on_cuboids) {
+	$count += ($c1->[1] - $c1->[0] + 1)
 		* ($c1->[3] - $c1->[2] + 1)
 		* ($c1->[5] - $c1->[4] + 1);
-	say "final: [", join(',', @$c1), "] = $size";
-	$count += $size;
 }
 
 say $count;
-
-}
-- 
2.43.0