Moved 2021 to a subdir

[aoc.git] / 2021 / 18.pl

diff --git a/2021/18.pl b/2021/18.pl
new file mode 100755 (executable)
index 0000000..f328873
--- /dev/null
+++ b/2021/18.pl
@@ -0,0 +1,49 @@
+#!/usr/bin/perl -w
+
+use v5.16;
+
+my @m = map { chomp; [ split // ]; } <>; 
+my $maxy = $#m;
+my $maxx = $#{$m[0]};
+
+my @basins;
+my $max_id = 0;
+my @prev_row;
+for my $row (@m) {
+       my $prev_l = undef;
+       for my $i (0 .. $#$row) {
+               my $b_id;
+               if ($row->[$i] == 9) {
+                       $b_id = undef;
+               } elsif (!$prev_l && !$prev_row[$i]) {
+                       $b_id = ++$max_id;
+               } elsif (!$prev_l) {
+                       $b_id = $prev_row[$i];
+               } elsif (!$prev_row[$i] || $prev_l == $prev_row[$i]) {
+                       $b_id = $prev_l;
+               } else { # merge
+                       $b_id = $prev_row[$i];
+                       $basins[$b_id] += $basins[$prev_l];
+                       $basins[$prev_l] = undef;
+                       for my $j (0 .. $#$row) {
+                               next if !$row->[$j] || $row->[$j] != $prev_l;
+                               $row->[$j] = $b_id;
+                       }
+                       for my $j (0 .. $#$row) {
+                               next if !$prev_row[$j] || $prev_row[$j] != $prev_l;
+                               $prev_row[$j] = $b_id;
+                       }
+               }
+               $prev_l = $b_id;
+               $row->[$i] = $b_id;
+               $basins[$b_id]++ if defined $b_id;
+       }
+       @prev_row = @$row;
+}
+
+@basins = sort { $b <=> $a } grep { defined $_ } @basins;
+
+say $basins[0]*$basins[1]*$basins[2];
+
+
+