Rainfall challenge

About a year ago when I was applying to jobs for the first time, I had an interview at a company and they posed the following problem to me, which I preceded to bomb.

A year later I actually came up with a solution to the problem, and I couldn't be happier. However, I would love for some critiques as to the design of my solution or other feedback about: style, OOP practices, etc..


Problem Statement


A group of farmers has some elevation data, and we're going to help
them understand how rainfall flows over their farmland.


We'll represent the land as a two-dimensional array of altitudes and
use the following model, based on the idea that water flows downhill:


If a cell’s four neighboring cells all have higher altitudes, we call
this cell a sink; water collects in sinks.


Otherwise, water will flow to the neighboring cell with the lowest
altitude. If a cell is not a sink, you may assume it has a unique
lowest neighbor and that this neighbor will be lower than the cell.


Cells that drain into the same sink – directly or indirectly – are
said to be part of the same basin.


Your challenge is to partition the map into basins. In particular,
given a map of elevations, your code should partition the map into
basins and output the sizes of the basins, in descending order.


Assume the elevation maps are square. Input will begin with a line
with one integer, S, the height (and width) of the map. The next S
lines will each contain a row of the map, each with S integers – the
elevations of the S cells in the row. Some farmers have small land
plots such as the examples below, while some have larger plots.
However, in no case will a farmer have a plot of land larger than S =
5000.


Your code should output a space-separated list of the basin sizes, in
descending order. (Trailing spaces are ignored.)


A few examples are below:



`-----------------------------------------
Input:

This is some very nice-looking code, and it looks like it is working. My criticism falls into the following topics:

• Discussions about style, naming, tools used etc. I assume you have consciously settled on a certain style, but some aspects strike me as so unusual that I would like to talk about them.

• I too, like to overengineer. But there are some parts of the design which I feel could be improved.

Cell

-
Style I was surprised to see that you did all your OOP yourself. Where is Moo/Mouse/Moose? What are your reasons for not using any of them? There are valid reasons like less dependencies, but they are becoming rare.

-
Style Two-space indent is very debatable. I (along with perlstyle) recommend 4 columns.

-
Style I noticed you are using { package Foo; ... }.

• It is recommendable to put different classes in different files so this isn't necessary.

• In v5.14 or later (IIRC) there is the package Foo { ... } form which reads nicer. Unless you are targeting older perls, you might want to use that instead.

-
Style You have the array reference $neighbors. This is OK if as a personal style decision you prefer references over non-scalar variables. This does not appear to be the case, and the only usage of that variables is as @$neighbors.

-
Note Avoid subroutines called y whenever possible, as that is also a transliteration operator. Of course this is no issue when only used as a method.

-
Design The is_sink method just returns a state value. It would be better if it would (lazily?) search the neighbors to see whether it's a sink. Currently, this is implemented in the confusingly named Rainfall::is_sink which arguably brakes encapsulation. There is no good reason to do that outside of the Cell class.

-
Style The xy method is not used anywhere. It also returns an arrayref which makes it harder to use the values. It would be more Perlish to return a flat list, so that we could do my ($x, $y) = $cell->xy. But as we already have accessors, we might as well remove that method.

-
Style to_s strikes me as a rather Ruby-ish name. In Perl there is no convention for naming a toString method. However, it is possible to override the stringification operator which is arguably a better thing to do:

use overload '""' => sub { ... };

-
Design Some of your methods require a Rainfall instance to be passed in. As each cell belongs to a certain grid, it might be better to store the grid in each cell. To avoid cyclic references you should use Scalar::Util::weaken to use weak references. Or if you've switched to an object system: has grid => (weak => 1).

-
Style A grep is not always the best solution:

grep {  
  $self->elevation elevation
  && all { $self->elevation elevation } $_->get_neighbors($rainfall)
} $self->get_neighbors($rainfall);

What this code expresses: Select all neighbors who are higher than me and where I am the lowest neighbour. But it's rather hard to read as $_ is bound to many different values. Never nest multiple meanings of $_. A simple solution would be to add a lowest_neighbor method. Then:

grep { !$_->is_sink && $self == $_->lowest_neighbor } $self->get_neighbors;

Otherwise, using explicit loops can improve readability:

my @flowing_neighbors;
for my $neighbor ($self->get_neighbors) {
    next if not $self->elevation elevation;
    next if not all { $self->elevation elevation } $neighbor->get_neighbors;
    push @flowing_neighbors, $neighbor;
}
return @flowing_neighbors;

-
Style Using @adjs as an abbreviation for @adjacents is unnecessary obfuscation.

-
To do the bounds checking, it might be clearer to do instead of

next NEIGHBORS 
  if $xmod > $rows - 1 || $ymod > $cols - 1 || $xmod < 0 || $ymod < 0;

this:

next NEIGHBORS if not 0 <= $xmod && $xmod < $rows;
next NEIGHBORS if not 0 <= $ymod && $xmod < $cols;

It's sad that Perl does not support chaining comparison operators, but this is the best way to show that a variable is in a specific range. Compare also range specifications in C-style for loops:

for (my $i = 0; $i < 10; $i++) {...} # 0..9

Rainfall

-
Design You build a grid of cell objects. It might be more fun to use the Flyweight Pattern, as each cell only contains very little state (whether it's a sink, which can be checked rather cheaply).

-
Design To find all sinks, you look at each cell in the grid. If we forget for a moment that you wanted to write object-oriented code, we could consider this algorithm:

create a set of all cells.
while the set contains elements:
  pick one element from the set.
  until the element is a sink:
    element = element->lowest_neighbor
  calculate the size of the basin,
  remove each member of the basin from the cells-set

While can construct a pathological case where this is as a loop through all cells, this will usually find the next sink much faster.

In Perl the set of cells could be implemented as a hash that

StackExchange Code Review Q#38500, answer score: 24