From: Jan "Yenya" Kasprzak <kas@fi.muni.cz>
Date: Thu, 9 Dec 2021 07:56:34 +0000 (+0100)
Subject: Day 9 task 2: one-pass solution
X-Git-Url: https://www.fi.muni.cz/~kas/git//home/kas/public_html/git/?p=aoc2021.git;a=commitdiff_plain;h=e9a6c1478b4afb1d88b9d877e19fe9abde6d6ff9

Day 9 task 2: one-pass solution
---

diff --git a/18.pl b/18.pl
index c4223b4..f328873 100755
--- a/18.pl
+++ b/18.pl
@@ -5,52 +5,45 @@ use v5.16;
 my @m = map { chomp; [ split // ]; } <>; 
 my $maxy = $#m;
 my $maxx = $#{$m[0]};
-say "$maxx x $maxy";
-
-my @low;
-for my $y (0 .. $maxy) {
-	for my $x (0 .. $maxx) {
-		my $val = $m[$y][$x];
-		next if $y > 0     && $m[$y-1][$x] <= $val;
-		next if $y < $maxy && $m[$y+1][$x] <= $val;
-		next if $x > 0     && $m[$y][$x-1] <= $val;
-		next if $x < $maxx && $m[$y][$x+1] <= $val;
-		push @low, [$x, $y];
-	}
-}
 
-my @sizes;
-
-for my $start (@low) {
-	my $added = 0;
-	my $size =1;
-	my @points = ($start);
-	my %pts = (join(',', @$start) => 1);
-	do {
-		$added = 0;
-		for my $p (@points) {
-			for my $add (([0, 1], [1, 0], [-1, 0], [0, -1])) {
-				my ($x, $y) = ($p->[0]+$add->[0], $p->[1]+$add->[1]);
-				# say "trying $x, $y";
-				next if $pts{join(',',$x,$y)};
-				next if $x < 0 || $x > $maxx;
-				next if $y < 0 || $y > $maxy;
-				next if $m[$y][$x] == 9;
-				$added = 1;
-				$pts{join(',',$x,$y)} = 1;
-				push @points, [$x, $y];
-				# say "adding $x, $y = $m[$y][$x]";
-				$size++;
+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;
 			}
 		}
-	} while ($added);
-	# say "$start->[0], $start->[1] : $size";
-	push @sizes, $size;
+		$prev_l = $b_id;
+		$row->[$i] = $b_id;
+		$basins[$b_id]++ if defined $b_id;
+	}
+	@prev_row = @$row;
 }
 
-@sizes = sort { $b <=> $a } @sizes;
+@basins = sort { $b <=> $a } grep { defined $_ } @basins;
 
-say $sizes[0]*$sizes[1]*$sizes[2];
+say $basins[0]*$basins[1]*$basins[2];