Rainfall challenge: how big are the basins?

August 2016 challenge

The Rainfall Challenge


Problem description is copied verbatim from the linked Code Review
question:



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



For examples see the the linked question :)

RainfallChallenge.java

```
public class RainfallChallenge {

public static void main(String[] args) {
try (Scanner stdin = new Scanner(System.in)) {
Grid grid = new Grid(stdin.nextInt());
grid.read(std

This code snippet appears several times in your code:

for (int row = 0; row < grid.length; row++) {
        for (int column = 0; column < grid[row].length; column++) {

And I think it's because there's a conflict of responsibilities about where the location of a cell is stored. In some sense, the used data structure (a nested array)

Cell[][] grid;

contains the 2D location of each cell already. But each cell also stores its position as member variables:

public class Cell {

    private final int row;
    private final int column;

This seems to be duplicated logic that is not synced.


Hyperbolic example interlude not applicable to the code at hand: imagine you swap two Cell objects in grid, who takes care of updating the private properties that are ...final!? - ooops. The data is stored redundantly and only one instance can be altered.

From Grid.java's point of view, the solution is simple: Use a more general data structure like ArrayList for example, that allows you to "iterate over all elements" (which is what you are really doing anyway) with something like a for-in loop. If any action in the loop body requires the position of the cell, it can retrieve it from the cell. This would reduce the necessity for the double for loop to the construction of the cells. I guess Streams could also come in handy to make things even more simple.

However here's this other dependency on the nested array in Cell.java itself, namely the members:

private Cell _findSink()
// and
private void setNextIfLower(Cell candidate)

With the approach outlined above, there's no overall data structure that dictates any structure (except listing all Cell objects), which means that each Cell object has to store references to its neighbours itself. The consequence of this approach is that the whole thing is stored as a graph (which happens to be a grid) with each Cell being a node.

StackExchange Code Review Q#136594, answer score: 7