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!

Comments? Octodon, , GitHub, Reddit, or drop me a line!