Rainfall challenge

Question

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:                 Output: 
 3                      7 2
 1 5 2 
 2 4 7 
 3 6 9 

The basins, labeled with A’s and B’s, are: 
 A A B 
 A A B 
 A A A 
-----------------------------------------
Input:                  Output: 
 1                       1
 10 

There is only one basin in this case. 
The basin, labeled with A’s is: 
 A
-----------------------------------------
Input:                  Output:            
 5                       11 7 7
 1 0 2 5 8 
 2 3 4 7 9 
 3 5 7 8 9 
 1 2 5 4 3 
 3 3 5 2 1 

The basins, labeled with A’s, B’s, and C’s, are: 
 A A A A A 
 A A A A A 
 B B A C C 
 B B B C C 
 B B C C C 
-----------------------------------------
Input:                  Output: 
 4                       7 5 4
 0 2 1 3                
 2 1 0 4 
 3 3 3 3 
 5 5 2 1 

The basins, labeled with A’s, B’s, and C’s, are: 
 A A B B 
 A B B B 
 A B B C 
 A C C C
-----------------------------------------

My solution, written in Perl, is as follows:

Cell class (models individual cells in the matrix):

{
  package Cell; 
  use List::MoreUtils qw(all);

  # models 4 nearest neighbors to position i,j forall i,j
  my $neighbors = [ [ 0, -1], # left
                    [-1,  0], # top
                    [ 0,  1], # right
                    [+1,  0], # bottom
                  ];
  sub new { 
    my ($class, %attrs) = @_; 
    $attrs{is_sink} ||= 0;

    bless \%attrs, $class;
  }  

  # accessor/setter methods
  sub elevation { 
    return shift->{elevation};
  }

  sub x {
    return shift->{x};
  }

  sub y {
    return shift->{y};
  }

  sub is_sink {
    return shift->{is_sink};
  }

  sub set_sink {
    shift->{is_sink} = 1;
  }

  sub xy {
    my $self = shift;
    return [$self->x, $self->y];
  }

  # string representation of a Cell
  sub to_s { 
    my ($self) = @_;
    return "(" . $self->x . "," . $self->y . ") = " . $self->elevation;
  }

  # returns the neighbors that flow into this Cell
  sub get_flowing_neighbors {
    my ($self, $rainfall) = @_;

    # the neighbors of this cell flow into it 
    # iff this cell's elevation is less than their neighbors
    # AND the neighboring cell has no other neighbors 
    # (that are not this cell) that have a lower (or equal) elevation 
    return  grep {  
              $self->elevation < $_->elevation
              && all { $self->elevation <= $_->elevation } $_->get_neighbors($rainfall)
            } $self->get_neighbors($rainfall);
  }

  # returns the neighbors of this Cell
  sub get_neighbors { 
    my ($self, $rainfall) = @_;

    my ($rows, $cols) = ($rainfall->rows, $rainfall->cols);
    my ($x, $y)       = ($self->x, $self->y);
    my @adjs;

  NEIGHBORS:
    for my $neighbor ( @$neighbors ) {
      my ($xmod, $ymod) = ($x + $neighbor->[0], $y + $neighbor->[1]);

      # x and y must be in the bounds of the matrix
      next NEIGHBORS 
        if $xmod > $rows - 1 || $ymod > $cols - 1 || $xmod < 0 || $ymod < 0;

      push @adjs,
        $rainfall->cell($xmod, $ymod);
    }

    return @adjs;
  }

  1;
} # end Cell 

Rainfall class (models the entire matrix and operations across it):

{
  package Rainfall; 

  sub new { 
    my ($class, %attrs) = @_; 

    # initialize all elements of the matrix to cells O(n)
    for my $i ( 0 .. @{ $attrs{field} } - 1) {
      for my $j ( 0 .. @{ $attrs{field}->[$i] } - 1 ) { 
        $attrs{field}->[$i]->[$j] =
          Cell->new(  x => $i, 
                      y => $j, 
                      elevation => $attrs{field}->[$i]->[$j],
          );
      }
    }

    bless \%attrs, $class;
  }  

  # accessor methods
  sub field { 
    my $self = shift;
    return $self->{field};
  }

  sub cell {
    my ($self, $i, $j) = @_;

    return $self->field->[$i]->[$j];
  }

  sub rows {
    my $self = shift;
    return $self->{rows};
  }

  sub cols {
    my $self = shift;
    return $self->{cols};
  }

  # determines if a given Cell is a sink
  sub is_sink { 
    my ($self, $cell) = @_;

    my $min       = $cell->elevation;
    my @neighbors = $cell->get_neighbors($self);

    for my $neighbor ( @neighbors ) {
      $min = ($min, $neighbor->elevation)[$min > $neighbor->elevation];
    }

    # found a sink, mark it
    if( $min == $cell->elevation ) {
      $cell->set_sink;
      return 1;
    }

    return 0;
  } 

  # returns a list of all Sinks in the matrix
  # O(N * M) where N = # of rows and M = # of cols
  sub find_sinks {
    my ($self) = @_; 

    my @sinks; 
    for my $row ( 0 .. $self->rows - 1 ) {
      for my $cell ( @{ $self->field->[$row] } ) { 
        push @sinks, $cell
          if $self->is_sink($cell);
      }
    }

    return @sinks;
  }

  # given an Array of Sinks, find the Basins in this field
  # O(n)
  sub find_basins_from_sinks {
    my ($self, @sinks) = @_;

    my %basin;
    my $basin_marker = 'A';

    # determine how many cells eventually flow into this one
    for my $sink ( @sinks ) { 
      $basin{$basin_marker++} = $self->basin_size($sink);
    } 

    return %basin;
  }

  # recursively find the number of Cells in the Basin 
  # attached to the given Cell
  sub basin_size { 
    my ($self, $cell) = @_;

    my $size = 1;
    for my $neighbor ( $cell->get_flowing_neighbors($self) ) {
      $size += $self->basin_size($neighbor);
    }

    return $size;
  }

  1;
} # end Rainfall

Unit tests that verify results to match the example cases above:

{ # Tests
  use Test::More tests => 4; 

  { # 3x3 field 
    my $r = Rainfall->new( rows  => 3,
                           cols  => 3,
                           field => [ [1, 5, 2], 
                                      [2, 4, 7], 
                                      [3, 6, 9] ]);

    my @sinks = $r->find_sinks;
    my %basin = $r->find_basins_from_sinks(@sinks);

    is_deeply( 
        [sort { $b <=> $a } values %basin],
        [7, 2],
        'Correctly divided 3x3 field into 2 basins'
    );
  }

  { # 1x1 field
    my $r = Rainfall->new( rows  => 1,
                           cols  => 1,
                           field => [ [1] ]);

    my @sinks = $r->find_sinks;
    my %basin = $r->find_basins_from_sinks(@sinks);

    is_deeply( 
        [sort { $b <=> $a } values %basin],
        [1],
        'Correctly divided 1v1 field into 1 basin'
    );
  }

  { # 5x5 field
    my $r = Rainfall->new( rows  => 5,
                           cols  => 5,
                           field => [ [1, 0, 2, 5, 8],
                                      [2, 3, 4, 7, 9],
                                      [3, 5, 7, 8, 9],
                                      [1, 2, 5, 4, 3],
                                      [3, 3, 5, 2, 1] ]);

    my @sinks = $r->find_sinks;
    my %basin = $r->find_basins_from_sinks(@sinks);

    is_deeply( 
        [sort { $b <=> $a } values %basin],
        [11, 7, 7],
        'Correctly divided 5v5 field into 3 basins'
    );
  }

  { # Test 4x4 field
    my $r = Rainfall->new( rows  => 4,
                           cols  => 4,
                           field => [ [0, 2, 1, 3],
                                      [2, 1, 0, 4],
                                      [3, 3, 3, 3],
                                      [5, 5, 2, 1] ]);

    my @sinks = $r->find_sinks;
    my %basin = $r->find_basins_from_sinks(@sinks);

    is_deeply( 
        [sort { $b <=> $a } values %basin],
        [7, 5, 4],
        'Correctly divided 4v4 field into 3 basins'
    );
  }
}

The basic algorithm searches through each element in the matrix and determines if that element is a sink (meaning that all of its neighbors flow into it).

sinks = []
for i in matrix: # rows
   for j in matrix[i]: # columns
      if matrix[i][j] is a sink:
         sinks.add( matrix[i][j] )

From the problem description you can tell that there will be one Basin per sink, so after you have the sinks you need to find the Basins. To find Basins you start at the Sinks and search outward, adding elements to the basin if they A) flow into the sink or B) flow into a cell that flows into a sink. You stop searching outward when there are no more flow paths to consider.

def find_basins_from_sinks(sinks):
   basins = {} # map
   marker = 'A'

   for sink in sinks:
      basins[marker++] = basin_size(sink)

def basin_size(cell):
   size = 1
   for neighbor in cell.neighbors:
      size += basin_size(neighbor)

Answer 1

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 < $neighbor->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 maps the coordinates to the cell object.

• Design basin_size has no business being in Rainfall. It is a method on a Cell. Indicator: You don't use anything from the Rainfall instance $self. Ergo it should be a static method or ordinary subroutine. You always pass a Cell as first argument, so it should probably be a method on a Cell instance instead.

• Design your constructor has both a rows and cols argument which is always the same per defintion. A single size would suffice, as would be deriving this information from the grid itself!

• Style you perform zero validation on input (e.g. to assure that it actually has the requested size, that all required parameter are actually there, or that no unknown parameters were used). I often use a

  my $thing = delete $args{thing} // die q("thing" required);
  

  pattern for this, followed by a die "Unknown arguments @{[sort keys %args]}" if keys %args check. The alternative is to use an object system and specify an attribute with

  has thing => (required => 1);
  

Tests

This looks very nice, no comments here. However, there is a massive amount of code duplication between the tests which could have been removed with a single loop.

Conclusion

This is very good code which shows the work of an experienced, careful programmer. The algorithm is OK. The design is slightly confused which indicates a code-first, design-later approach (which is OK, as it can be easily refactored).

Answer 2

The fact that this was an interview question changes how I look at the code. The interviewer was almost certainly looking for one answer: "union-find data structure" or "disjoint sets data structure". You were being judged by whether you said those magic words within the first few seconds, could come up with something similar on your own, could come up with something similar with the interviewer's guidance, or not at all.

Your solution could use either the abstract terminology (e.g. Member and DisjointSet) or the domain-specific terminology (Cell and Basin). You are therefore missing the Basin class in your modelling. Using the domain-specific terminology would be better, in my opinion. I would also prefer to rename Rainfall to Topography, since the problem is to analyze a topographic map.

Here is the outline of the solution:

1. Each Cell keeps track of which Basin it belongs to; each Cell is initially assume to be in its own Basin. Each Basin has a sink, or lowest Cell, which acts as a "representative element" of the Basin, as well as a member count. Topography keeps track of all Basins.
2. For each Basin, find lowest of the sink's neighbours. If the lowest is not already a member of this Basin, transfer its cells into the lowest neighbour's Basin, and notify Topography that the higher basin no longer exists.
3. Repeat step 2 until no further action is necessary.
4. Have Topography enumerate the Basins and their counts.

Answer 3

There are a few things I see in here that I would suggest could be different.

I don't like that the logic for determining whether a cell is a sink is on both Rainfall and Cell. In fact, both classes have the method called is_sink...

My preference would be to move the logic on to the Cell, which already knows how to calculate it's neighbours.... and then the Rainfall class can just call:

push @sinks, $cell
      if $cell->is_sink($self);

This indicates a larger problem though, that a fair amount of code is repeated (calculating neighbours, etc.). My suggestion is that you should have an initial pass of the field after creating each cell. This inialization pass should get each cell to compute, and store their neighbour list, as well as compute whether the cell is a sink. Putting it in the constructor of the Rainfall class seems like the right idea, but, since the initalization can also record the sinks, it seems quite a lot for a constructor. I am on the fence. The up-side is that it will make the execution faster.... Consider the RainFall constructor:

  sub new { 
    my ($class, %attrs) = @_; 

    # initialize all elements of the matrix to cells O(n)
    for my $i ( 0 .. @{ $attrs{field} } - 1) {
      for my $j ( 0 .. @{ $attrs{field}->[$i] } - 1 ) { 
        $attrs{field}->[$i]->[$j] =
          Cell->new(  x => $i, 
                      y => $j, 
                      elevation => $attrs{field}->[$i]->[$j],
          );
      }
    }

    my @sinks;
    for my $i ( 0 .. @{ $attrs{field} } - 1) {
      for my $j ( 0 .. @{ $attrs{field}->[$i] } - 1 ) { 
        my $cell = $attrs{field}->[$i]->[$j];
        $cell.initialize($self);
        push @sinks if $cell->is_sink;
      }
    }
    $attrs{sinks} = @sinks;

    bless \%attrs, $class;
  }  

The initialize method on the Cell will calculate, and store, the array of neighbours. This will substantially reduce the number of times they need to be calculated.

If you have the one-off initialization then Cell->is_sink can take no parameters again.

Apart from the restructuring of the is_sink, and the persistence of the neighbours array, I have a nit-pick about some of your loop-conditions.... you often have code like:

for my $row ( 0 .. $self->rows - 1 ) {
    ..

You should rather be using the last-index operator rather than the scalar one:

for my $row ( 0 .. $#{$self->rows} ) {

Similarly with things like:

for my $i ( 0 .. @{ $attrs{field} } - 1) {

Should be:

for my $i ( 0 .. $#{ $attrs{field} }) {

one last nit-pick, why do the subtraction when >= works fine too:

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

This could easily be:

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

Although, again, it is unclear that $rows and $columns are arrays here, and I would prefer:

next NEIGHBORS 
    if $xmod > $#{$rows} || $ymod > $#{$cols} || $xmod < 0 || $ymod < 0;

Answer 4

I see the following three lines:

my $self = shift;
my ($self) = @_;
my ($self, $rainfall) = @_;

It's generally better if you choose one style and stick with it. It may make sense to mix the first and third lines in the same program, but the first two lines should not coexist. I would use the second and third versions, but if you like the first, you could use the following with it:

my $self = shift;
my $rainfall = shift;

That's somewhat longer but makes the code consistent.

Perl has many ways to do things (TIMTOWTDI). It's still helpful though if you can choose just one way to do it in any given program (BSCINABTE).

Similarly, in the following code:

sub x {
  return shift->{x};
}

It's worth thinking about what is happening:

sub x {
  my $self = shift @_;

  return $self->{x};
}

Hopefully you know that the former is a shorthand for the latter but think about the next person maintaining your code. What if this is that person's first time using Perl. People in that situation will see your code and think that shift is some kind of special variable name in Perl classes (once they realize that it's not defined in the class). How does such a person get from there to the latter version?

The shift is a Perl built-in function which is defaulting to the @_ variable. In that context, @_ is set to the arguments to the x function with the object as the first argument. The shift built-in takes an array as the first argument, removes the first entry, and returns that entry. Then you dereference the result with the -> operator and grab the value for the x key with a hash lookup (since classes are generally built on hashes in Perl).

Also, x seems a confusing name for a function. I would find get_x or even get_x_coordinate to be easier to read and understand.

If I were the one evaluating your interview code, then I would give points for writing clean, consistent, readable code. It's often worth taking a little extra time to make the code pretty. Most of my employed time is spent maintaining existing code, not writing new code. Writing the original code correctly is important. I don't care as much about quickly. The most important part is that it should be easy for me to debug and modify. That's where most of the time goes. If you save fifteen minutes writing code but I spend fifteen hours trying to make it work, then that's not a good tradeoff.

As always, other reviewers may vary. The fact that they were asking you to write substantial code with a deadline may be a sign that they have different priorities than me.