Rainfall challenge: how big are the basins?

Question

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(stdin);

            StringBuilder output = new StringBuilder();
            for (int basinSize : grid.solve()) {
                output.append(basinSize);
                output.append(' ');
            }
            System.out.println(output);
        }
    }

}

Grid.java

public class Grid {

    Cell[][] grid;

    public Grid(int size) {
        grid = new Cell[size][size];
        for (int row = 0; row < grid.length; row++) {
            for (int column = 0; column < grid[row].length; column++) {
                grid[row][column] = new Cell(grid, row, column);
            }
        }
    }

    public void read(Scanner stdin) {
        for (int row = 0; row < grid.length; row++) {
            for (int column = 0; column < grid[row].length; column++) {
                grid[row][column].setHeight(stdin.nextInt());
            }
        }
    }

    public void test(int[][] heights) {
        for (int row = 0; row < grid.length; row++) {
            for (int column = 0; column < grid[row].length; column++) {
                grid[row][column].setHeight(heights[row][column]);
            }
        }
    }

    public List<Integer> solve() {
        for (int row = 0; row < grid.length; row++) {
            for (int column = 0; column < grid[row].length; column++) {
                grid[row][column].findSink();
            }
        }

        Map<Cell, List<Cell>> basins = new HashMap<>();
        for (int row = 0; row < grid.length; row++) {
            for (int column = 0; column < grid[row].length; column++) {
                Cell end = grid[row][column].getSink();

                List<Cell> cells = basins.get(end);
                if (cells == null) {
                    cells = new ArrayList<>();
                    basins.put(end, cells);
                }

                cells.add(grid[row][column]);
            }
        }

        List<Integer> results = new ArrayList<>();
        for (List<Cell> basin : basins.values()) {
            results.add(basin.size());
        }

        Collections.sort(results, Collections.reverseOrder());

        return results;
    }

}

Cell.java

public class Cell {

    private final int row;
    private final int column;
    private int height;
    private Cell next = this;
    private Cell sink = next;
    private Cell[][] grid;

    public Cell(Cell[][] grid, int row, int column) {
        this.grid = grid;
        this.row = row;
        this.column = column;
        next = this;
        sink = next;
    }

    public Cell getNext() {
        return next;
    }

    private void setNextIfLower(Cell candidate) {
        if (candidate.getHeight() < next.getHeight()) {
            next = candidate;
        }
    }

    public Cell getSink() {
        return sink;
    }

    public void setHeight(int height) {
        this.height = height;
    }

    public int getHeight() {
        return height;
    }

    public int getRow() {
        return row;
    }

    public int getColumn() {
        return column;
    }

    // package visibility is intentional
    void findSink() {
        _findSink();
    }

    private Cell _findSink() {
        // if we've already updated the sink, just return it
        if (sink != this) {
            return sink;
        }

        if (row > 0) {
            setNextIfLower(grid[row - 1][column]);
        }

        if (column > 0) {
            setNextIfLower(grid[row][column - 1]);
        }

        if (row + 1 < grid.length) {
            setNextIfLower(grid[row + 1][column]);
        }

        if (column + 1 < grid[row].length) {
            setNextIfLower(grid[row][column + 1]);
        }

        if (next != this) {
            sink = next._findSink();
        }

        return sink;
    }

}

RainfallTest.java

public class RainfallTest {

    @Test
    public void test3() {
        int[][] heights = {{1, 5, 2},
                           {2, 4, 7},
                           {3, 6, 9}};
        Grid grid = new Grid(heights.length);
        grid.test(heights);
        List<Integer> basinSizes = grid.solve();
        assert(basinSizes.size() == 2);
        assert(basinSizes.get(0) == 7);
        assert(basinSizes.get(1) == 2);
    }

    @Test
    public void test1() {
        int[][] heights = {{10}};
        Grid grid = new Grid(heights.length);
        grid.test(heights);
        List<Integer> basinSizes = grid.solve();
        assert(basinSizes.size() == 1);
        assert(basinSizes.get(0) == 1);
    }

    @Test
    public void test5() {
        int[][] heights = {{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}};
        Grid grid = new Grid(heights.length);
        grid.test(heights);
        List<Integer> basinSizes = grid.solve();
        assert(basinSizes.size() == 3);
        assert(basinSizes.get(0) == 11);
        assert(basinSizes.get(1) == 7);
        assert(basinSizes.get(2) == 7);
    }

    @Test
    public void test4() {
        int[][] heights = {{0, 2, 1, 3},
                           {2, 1, 0, 4},
                           {3, 3, 3, 3},
                           {5, 5, 2, 1}};
        Grid grid = new Grid(heights.length);
        grid.test(heights);
        List<Integer> basinSizes = grid.solve();
        assert(basinSizes.size() == 3);
        assert(basinSizes.get(0) == 7);
        assert(basinSizes.get(1) == 5);
        assert(basinSizes.get(2) == 4);
    }

}

The jUnit tests are based on the examples from the linked question.

Answer 1

Tests - Focus and naming

Since you had provided them, the first bit of your code I looked at were your tests. As has been pointed out by @Roman Vottner, their names are not very descriptive. test1, test2 etc tell the reader nothing about the scenario that is being tested. I'm guessing that they should be called something like test5x5GridContains3Basins.

The tests themselves are quite concise, although again as has been pointed out by @Roman, you're not calling assert.assertEquals which is what I'd expect. All of your tests are also validating all of the basins in the returned list. This is a good way to test a whole scenario, however it doesn't help you to know if you're testing all of the edge cases. Having more tests that validate only a single thing can be more descriptive (this also makes it easier to name the tests). For example:

`test5x5GridDetectsSingleCentralBasin`
`test4x4GridDetectsLowerRightCornerBasin`
`test3x3GridDetectsTopLeftCornerBasin`

Tests - Writing code for tests / testable code

Your Grid method exposes two public methods for populating the grids initial values:

public void read(Scanner stdin) 
public void test(int[][] heights) 

The first method read is called from the Challenge class and the second test is called from your test classes. This duplication is caused by Grid knowing how to read information from the user. It would be better to only expose a single method, possibly populateGrid(int [][] heights) or populateGrid(List<Integer>) and have another class responsible (or the main method) for constructing the array from user input. This prevents the need the Grid class to differentiate between when it's being called properly and when it's being called under test. This also removes one of the confusing aspects of your unit tests where you do this:

grid.test(heights);
List<Integer> basinSizes = grid.solve();

Having the method named test makes it appear like you're expecting grid to test itself, then solve itself. Whereas with a different name it feels more expressive:

grid.populateGrid(heights);
List<Integer> basinSizes = grid.solve();

Cell

The responsibilities of your Cell class are confusing. It seems strange for a class called Cell to contain an array of Cells. I also found the field next particularly unexpected. What does it mean to be the next cell?

Overall

That said, overall despite some of the naming quirks and distributed responsibilities I did find your code to be mostly expressive and easy to follow. I particularly liked the way you had constructed the grids within your tests, so that they were laid out like a map to be processed.

Answer 2

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.