Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

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'
    );
  }
}

Any feedback would be greatly appreciated. Also, alternate solutions are welcome.

EDIT:: Pseudocode

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 a 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)
share|improve this question
    
Would you mind describing the algorithm in pseudo-code ? The problem does seem interesting but I am not very familiar with the Perl syntax anymore. –  Josay Jan 3 at 14:47
1  
@Josay sure, I outlined the basic algorithm in a less Perly fashion above. –  Hunter McMillen Jan 3 at 15:01
    
How much time was given for solving the task? –  mpapec Jan 3 at 15:18
    
@mpapec I think in the interview 100 minutes was allotted, I wasn't able to finish in time. This 2nd time around I finished in ~ 1 hour. –  Hunter McMillen Jan 3 at 15:40
    
An idea: This looks like a good use for a union-find data structure. But that's just a cursory glance... (for a different-I think-approach to the problem) –  anorton Jan 3 at 17:44
add comment

3 Answers 3

up vote 12 down vote accepted

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).

share|improve this answer
    
I wish I could upvote this twice. This has been extremely helpful. –  Hunter McMillen Jan 3 at 17:04
1  
To answer a few of your questions, the company I work for is still using Perl 5.12 (a few versions back), so I don't get the nice encapsulated package syntax of 5.14. In a similar fashion, we also don't use Moose; (or Moo; something I hope to change), instead we have our own object system. I decided to just use a blessed hash for this small program, had it been of a greater size I probably would have used Moose. I still might re-factor the could into a Moose package after I take everyone's comments into consideration. –  Hunter McMillen Jan 3 at 17:07
    
You are right about basin_size(), I moved that into the Cell class and the could looks much cleaner, now I don't have to pass around the Rainfall state. You are write about error checking, and even though I am the only user of program I need to include it (I imagine interviewers' look for that). Regarding to_s That was just for debugging, but thanks for the overload suggestion, I didn't even know that feature existed. Thanks again for all of your suggestions, the Flyweight pattern looks particularly applicable, especially if I allow each Cell to hold a reference to its own neighbors. –  Hunter McMillen Jan 3 at 17:13
    
I have posted a revised version (still w/o error checking to Github), take a look if you have a moment: github.com/mcmillhj/Rainfall –  Hunter McMillen Jan 3 at 17:29
add comment

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.
share|improve this answer
    
+1 for explicitly modeling basin, and for using names specific to the domain. –  Wayne Conrad Jan 4 at 16:06
    
Thanks for your reply, this was really helpful. I will probably attempt this solution and compare my previous one. –  Hunter McMillen Jan 4 at 16:23
add comment

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;
share|improve this answer
    
Thanks for the reply, I totally agree about determining sinks in the constructor for Rainfall, that makes a lot of sense and will allow me to decouple Rainfall and Cell from get_neighbors and get_flowing_neighbors. I also agree about the for my $i ( 0 .. $#{ $attrs{field} } ) statement, but $row and $col are actually just integers that denote the size of the matrix, so the sizeof operator on then returns -1. Your comment about <= vs < makes sense though. –  Hunter McMillen Jan 3 at 16:07
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.