From e9a6c1478b4afb1d88b9d877e19fe9abde6d6ff9 Mon Sep 17 00:00:00 2001 From: "Jan \"Yenya\" Kasprzak" Date: Thu, 9 Dec 2021 08:56:34 +0100 Subject: [PATCH] Day 9 task 2: one-pass solution --- 18.pl | 73 +++++++++++++++++++++++++++-------------------------------- 1 file changed, 33 insertions(+), 40 deletions(-) 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]; -- 2.43.5