TL;DR

On with Advent of Code puzzle 9 from 2021: using the flood fill algorithm.

This puzzle starts quiet by asking us to calculate local minima in a grid of values. The thing is made easy by the fact that these minima are always exactly in one single spot, i.e. there are never cases of two adjacent cells that are both at the local minimum.

My approach is brute-forcey without any attempt at optimizing the sweep. In particular, for each position we check the condition about the surrounding 4 positions (diagonals don’t count) and if it’s a local minimum I record it.

sub part1 ($in) {
   my $inputs = $in<data>;
   my $lr = $inputs.end;      # last row
   my $lc = $inputs[0].end;   # last column
   my $sum = 0;               # result
   $in<low> = my @low;        # find out low points
   for 0 .. $lr -> $br {
      ITEM:
      for 0 .. $lc -> $bc {
         for [1, 0], [0, 1], [-1, 0], [0, -1] -> ($dr, $dc) {
            my ($r, $c) = $br + $dr, $bc + $dc;
            next unless 0 <= $r <= $lr && 0 <= $c <= $lc;
            next ITEM if $inputs[$br][$bc] >= $inputs[$r][$c];
         }
         $sum += 1 + $inputs[$br][$bc];
         @low.push: [$br, $bc];
      }
   }
   return $sum;
}

The $input is supposed to be a double-dimensional array of integers, read from the input grid of values.

I’m not particularly fond of the way I iterate over the surrounding positions, but it works.

Part 2 is about finding the size of basins. Basically the spots at height 9 are divisions across these basins, and each local minimum is associated to exactly one basin. Again this is a simplification over the general case in which two adjacent basins might be divided by lower walls. Thanks Mr. Wastl 😅

To do this, I decided to go for a search algorithm that implements a flood fill, using the borders or the height of 9 as a stopping condition. The implementation is iterative, leveraging a queue of nodes to check that is fed in a way that actually implements a breadth first visit of the graph induced by the grid.

sub part2 ($inputs) {
   my $lr = $inputs<data>.end;     # last row
   my $lc = $inputs<data>[0].end;  # last column
   my %size-of;                    # size of each basin
   for $inputs<low>.List -> ($br, $bc) {  # iterate on basins' low pts
      my $key = "$br-$bc";         # to index %size-of
      my @queue = $($br, $bc,);    # starting point for flood fill
      while @queue.elems {
         my ($r, $c) = @queue.shift.List;
         next unless 0 <= $r <= $lr && 0 <= $c <= $lc;
         next if $inputs<data>[$r][$c] == 9; # edge or marked
         $inputs<data>[$r][$c] = 9;  # mark as done - DIRTY!
         ++%size-of{$key};

         # just add all candidates, will check later
         for [1, 0], [0, 1], [-1, 0], [0, -1] -> ($dr, $dc) {
            @queue.push: [$r + $dr, $c + $dc];
         }
      }
   }
   return [*] %size-of.values.sort.reverse.Array.splice(0, 3);
}

I’m reusing the positions of the local minima from the first part here, conveniently added to the $inputs. I now it’s dirty but in my defense you never know what comes in puzzle #2 and hurry can be a great motivator to introduce technical debt that will never be paid back.

Well… today also we arrived to the end of it. I feel the tingling sensation that Mr. Wastl is preparing for something really hard eventually… let’s hope it’s not too hard!