Rainfall challenge solution using Union-find

Question

I have tried to implement a solution to the Rainfall challenge based on the suggestions from 200_success♦ (Rainfall challenge).

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

The code is in java. It would be great if anyone can review.

class Topography {

    int[][] elevationData;
    Cell[][] map;
    List<Basin> basinList;

    Topography(int[][] elevationData) {

        this.elevationData = elevationData;
        this.basinList = new ArrayList<Basin>();
        this.map = new Cell[elevationData.length][elevationData.length];
    }

    private class Cell {

        int altitude;
        Basin basin;

        Cell(int altitude) {

            this.altitude = altitude;
            this.basin = new Basin(this);
        }
    }

    private class Basin {

        Cell sinkCell;
        HashSet<Cell> memberCells;

        Basin(Cell sinkCell) {

            this.sinkCell = sinkCell;
            this.memberCells = new HashSet<Cell>();
            this.memberCells.add(sinkCell);
        }

    }

    private class BasinComparator implements Comparator<Basin> {

        public int compare(Basin basin1, Basin basin2) {

            if( basin1.memberCells.size() < basin2.memberCells.size() )
                return 1;

            else if( basin1.memberCells.size() > basin2.memberCells.size() )
                return -1;

            else 
                return 0;
        }
    }

    private void createTopography() {

        Cell tmpCell;
        for(int i=0; i<elevationData.length; i++) {

            for(int j=0; j<elevationData.length; j++) {

                tmpCell = new Cell(elevationData[i][j]);
                map[i][j] = tmpCell;
                basinList.add(tmpCell.basin);

            }
        }
    }

    private Cell findSink(Cell cell) {

        if(cell == null)
            return null;

        if(cell != cell.basin.sinkCell) {
            cell.basin.sinkCell = findSink(cell.basin.sinkCell);
        }

        return cell;
    }

    private void union(Cell cellX, Cell cellY) {

        Cell sinkX = findSink(cellX);
        Cell sinkY = findSink(cellY);

        if(sinkX == null || sinkY == null || sinkX == sinkY)
            return;

        if(sinkX.altitude > sinkY.altitude) {
            sinkY.basin.memberCells.addAll(sinkX.basin.memberCells);
            basinList.remove(sinkX.basin);
            sinkX.basin = sinkY.basin;
        } else {
            sinkX.basin.memberCells.addAll(sinkY.basin.memberCells);
            basinList.remove(sinkY.basin);
            sinkY.basin = sinkX.basin;
        }
    }

    void printBasinLength() {

        createTopography();

        for(int i=0; i<map.length; i++) {

            for(int j=0; j<map.length; j++) {

                Cell current_cell = map[i][j];
                Cell minNeighbor = findMinimumNeighbor(i, j, current_cell);

                if(minNeighbor != current_cell) {

                    union(minNeighbor, current_cell);
                }
            }
        }

        Collections.sort(basinList, new BasinComparator());

        for(Basin basin: basinList)
            System.out.print(basin.memberCells.size()+ " ");

    }

    private Cell findMinimumNeighbor(int i, int j, Cell current_cell) {

        Cell min = current_cell;

        if(i>0){

            if(map[i-1][j].altitude < min.altitude)
                min = map[i-1][j];

        }

        if(i<map.length-1){

            if(map[i+1][j].altitude < min.altitude)
                min = map[i+1][j];

        }

        if(j>0) {

            if(map[i][j-1].altitude < min.altitude)
                min = map[i][j-1];

        }

        if(j<map.length-1){

            if(map[i][j+1].altitude < min.altitude)
                min = map[i][j+1];
        }

        return min;
    }

}

Answer 1

Fun problem! This is looking quite good.

That said, there are always stuff to improve... ;)

---

Format

1. Whitespace

You seem to have a lot of whitespace going on, many times without a particular meaning.

I can understand whitespace cutting off a paragraph of code into sub-actions (though extracting to methods is better if possible). But why all the line jumps after ifs, fors, and method definitions? That is what indenting is for. So your line jumps seem redundant, they prevent having a good chunk of code on sight, as well as provoke lots of scrolling.

2. Missing brackets.

You alternate between using brackets, and not using them. IT is strongly advised to use brackets everywhere. IDEs will insert them for ou, and even though their presence is not required to read the code, it helps when editing it, as adding an instruction in or out an else clause is made completely obvious.

One exception to this rule that I use is that I do not add the bracket in else if series to keep indents manageable:

if(conditionA) {
    // Do something, in either a one-liner is in brackets
} else if {
    // Do something else
}

3. Javadoc

Where is it?

It is always good to have it, and real easy. And there's this feeling of satisfaction when you come back to your code, find it Javadoc'ed, and think "attaboy" :D

4. Nested ifs

if(i>0){
    if(map[i-1][j].altitude < min.altitude)
        min = map[i-1][j];
}

This is equivalent to:

if(i > 0 && if(map[i-1][j].altitude < min.altitude) {
    min = map[i-1][j];
}

But this last snipped has less indents and is shorter. Breaking if contitions is good if you want to leave room to make several internal ifs, but this is clearly not the case here.

Also for polling neighbouring cells, you might want to screen an offset array like [[0, -1], [0, 1], [-1, 0], [1, 0]] and make a generic checkBound(int i, int j) method. This is easily expandable e.g. to 8-connected cells.

---

Architecture

1. External Comparators

Why externalize the Comparators? Do you think you may use different comparators at times? I doubt it, it's a highly specialized class. You should rather let Basin implement Comparable<Basin>.

2. Single Responsibility

printBasinLength starts by calling createTopography. Then it goes on making union of basins. Wait, that's not part of the deal! According to its name (and in absence of Javadoc) it was only supposed to print something, not compute it. What if it was already computed?

You should split the computing, the presenting, and the printing. You've partly done it, you just need to explode printBasinLength into logical components:

• Remove that createTopography() call altogether from
• Move those for...for...union calls and put them in a new void mergeBasins() 'business' method
• Move the sorting in a sortBasinsBySurface() method
• Break the prints into a call to concatenate the basins in String getRepresentation() method
• Never use System.out in a business method. Move it at last resort in main(). If you don't, anyone using the framework will get those prints on console without any control over it.

Then make a :

public String splitTopologyInBasins(){
    createTopography();
    sortBasinsBySurface();
    mergeBasins()
    return getRepresentation();
}

---

Algorithm

You chose to:

• Instantiate immediately one object per cell
• Then make one pass per cell where:
  • You then find its lowest neighbour
  • Make a union of their sinks by:
    • Recursing over both to find their sink

The head-on cost of instancing all cells is unnecessary, they could be lazily generated. Many improvements in being lazy:

• Cells that flow in a known cell have very little work left to : just copy the data over, the sink will be the same.
• Because cells which are flowing are not sinks, they do not need to have a Basin generated at the start for them, which would later be deleted through union.

I'd rather start with no cells anywhere, and use the recursive function to make a bunch of cells on the way to their sink, and only create one Basin for them all when and if I get there (unless the sink cell already existed or a previously-existing cell was encountered, then everyone inherits of that basin). In the double for-loop, you'd simply skip any Cell that are already generated. This reduces greatly the number of Basins (and lists) and merges.