From 30d5b6b31df9772b49ea4285806451aecc02b119 Mon Sep 17 00:00:00 2001 From: "Jan \"Yenya\" Kasprzak" 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.5