Code review: Percolation.java

[Ken Austin]

Hey, friends. I am teaching myself to program by working my way through David Eck's Javanotes. I'm currently on Chapter 12 of 13.

I am also taking an online course over at the Coursera website called Introduction to Algorithms. I wrote this class for the first programming assignment. It is supposed to create an N by N grid, randomly open sites, and stop when there is an open path from the top to the bottom. It seems to work, except that the notes on the course website say that my results say that it is taking longer for the grid to show up as open than it is supposed to. (Their site says around 51% over a large number of tests. I'm closer to 60%.)

After lurking around here for awhile, I know better than to post any code that isn't commented. Hopefully, you'll find it easy to follow.

This is my first time to post any code anywhere.

The instructor supplied WeightedQuickUnionUF class can be viewed at their booksite.
EDIT: The instructor supplied StdRandom class can be viewed at the same booksite.

/**
 * This class tests an N by N grid to see if there are enough open
 * locations to connect the top of the grid with the bottom of the
 * grid. It uses an two dimensional array of integers to represent
 * the grid, and an instructor supplied WeightedQuickUnionUF object
 * to keep track of the connections between open sites in the grid.
 *
 * The percolates() method returns true if a path can be found from a
 * site at the top to the bottom. These two sites are are not actually
 * represented in the grid, although they are represented in the 
 * union-find object at locations 0 and N*N + 2. They are "located"  
 * above and below the grid, and each connects to all the sites 
 * immediately above or below it. This simplifies the pathfinding
 * process.
 *
 * This class was written by Ken Austin in partial fulfillment of the
 * requirements for the Coursera online course, Introduction to Algorithms.
 *
 * Dependencies: WeightedQuickUnionUF.java, StdRandom.java,
 */

public class Percolation {

    private static final int FULL = 0;     // Makes it easier to keep track of the
    private static final int OPEN = 1;     // status of the sites in the grid.

    private int N;          // Dimensions of the N by N grid used in the simulation.
    private int[][] grid;   // Keeps track of which sites are open or full.
                            // Begins with default initialization: FULL (0)
                            
    private WeightedQuickUnionUF ufHelper; // Class supplied by course instructor.
                                           // We use union(), find(), connected(),
                                           // and count() in this program.
    
    /**
     * Constructor initializes two dimensional array of integers
     * with default values: all sites set to CLOSED (0).
     *
     * The WeightedQuickUnionUF object is initialized to a size that will
     * contain one element for each site in the grid (N*N), plus two more
     * to represent "imaginary" sites at the top and bottom of the grid
     * that will make it easier to test the grid for percolation.
     *
     * @param n the number of rows and column in the grid
     */
    public Percolation(int n) {
        N = n;
        grid = new int[N][N];
        ufHelper = new WeightedQuickUnionUF((N * N) + 2);
    } // end constructor

    /**
     * Open site (row i, column j) by setting site to OPEN
     * and calling the union method in the union-find object
     * for any open adjacent sites.
     *
     * @param i the integer representing the site location on the x axis
     * @param j the integer representing the site location on the y axis
     * @throws  IndexOutOfBoundsException if the values for i and j are 
     *          off the grid
     */
    public void open(int i, int j) {
        int row = i - 1;
        int col = j - 1;
        if (row < 0 || row > N || col < 0 || col > N)
            throw new IndexOutOfBoundsException("Illegal parameter value.");
        grid[row][col] = OPEN;
        if (row == 0) { // If it's on the top row, connect to imaginary site at 0.
            ufHelper.union(0, xyTo1D(row, col));
        }
        if (row == N - 1) { // If it's on the bottom row, connect to imaginary
                            // site at (N*N) + 1.
            ufHelper.union((N*N) + 1, xyTo1D(row, col));
        }
        if ((row + 1) < N) { // Make sure we don't fall off the grid
            if (grid[row+1][col] == OPEN)
                ufHelper.union(xyTo1D(row, col), xyTo1D(row+1, col));
        }
        if ((row - 1) >= 0) { // Make sure we don't fall off the grid
            if (grid[row-1][col] == OPEN)
                ufHelper.union(xyTo1D(row, col), xyTo1D(row-1, col));
        }
        if ((col + 1) < N) { // Make sure we don't fall off the grid
            if (grid[row][col+1] == OPEN)
                ufHelper.union(xyTo1D(row, col), xyTo1D(row, col+1));
        }
        if ((col - 1) >= 0) { // Make sure we don't fall off the grid
            if (grid[row][col-1] == OPEN)
                ufHelper.union(xyTo1D(row, col), xyTo1D(row, col-1));
        }
    } // end open()
    
    /**
     * Is site (row i, column j) open?
     *
     * @param i the integer representing the site location on the x axis
     * @param j the integer representing the site location on the y axis
     * @return  true if the site at (i, j) is OPEN
     * @throws  IndexOutOfBoundsException if the values for i and j are 
     *          off the grid
     */
    public boolean isOpen(int i, int j) {
        int row = i - 1;
        int col = j - 1;
        if (row < 0 || row > N || col < 0 || col > N)
            throw new IndexOutOfBoundsException("Illegal parameter value.");
        return grid[row][col] == OPEN;
    } // end isOpen()
    
    /**
     * Is site (row i, column j) full?
     *
     * @param i the integer representing the site location on the x axis
     * @param j the integer representing the site location on the y axis
     * @return  true if the site at (i, j) is FULL
     * @throws  IndexOutOfBoundsException if the values for i and j are 
     *          off the grid
     */
    public boolean isFull(int i, int j) {
        int row = i - 1;
        int col = j - 1;
        if (row < 0 || row > N || col < 0 || col > N)
            throw new IndexOutOfBoundsException("Illegal parameter value.");
        return grid[row][col] == FULL;
    } // end isFull()
    
    /**
     * Does the system percolate? Checks to see if the imaginary site
     * at location 0 in the union-find object is in the same set as 
     * the imaginary site at location N*N+1 in the union-find object.
     * These two sites are imaginary; they are not actually represented
     * in the grid, although they are represented in the union-find
     * object. They are "located" at the top and the bottom of the 
     * grid, and each connects to all the sites above/below it.
     *
     * @return true if open path from the bottom of the grid to the top exists
     */
    public boolean percolates() {
        return ufHelper.connected(0, (N*N)+1);
    } // end percolates()
    
    /**
     * Converts 2D point to 1D array location for the union-find object
     * to use.
     *
     * @param i the integer representing the site location on the x axis
     * @param j the integer representing the site location on the y axis
     * @return  the location in the union-find object where the site
     *          should be stored
     * @throws  IndexOutOfBoundsException if the values for i and j are 
     *          off the grid
     */
    private int xyTo1D(int i, int j) {
        if (i < 0 || i > N || j < 0 || j > N)
            throw new IndexOutOfBoundsException("Illegal parameter value.");
        return ((i*N) + j) + 1;  // The +1 compensates for the site at the
                                 // beginning used to facilitate the 
                                 // percolation algorithm. (There is a
                                 // corresponding single site added to the
                                 // end that does not affect this
                                 // calculation.)
    }
    
    private int count() {        // Convenience method. Returns the number of
        return ufHelper.count(); // groups in the union find object.
    }
    private int getN() {         // Convenience method. Returns N.
        return N;
    }
    
    public static void main(String[] args) {
        final int TESTS = 1000;
        final int GRID_SIZE = 20;
        
        System.out.println("\n***Percolation: Monte Carlo Simulation ***\n");
        
        Percolation perc = new Percolation(GRID_SIZE);
        System.out.println("Successfully created Percolation object.");
        System.out.println("N: " + perc.getN());
        System.out.println();
        
        System.out.println("Starting to open random sites...");
        int row, col, ct;
        double sum = 0.0;
        for (int i = 0; i < TESTS; i++) {
            ct = 0;
            perc = new Percolation(GRID_SIZE);
			while (!perc.percolates()) {
				row = StdRandom.uniform(perc.getN()) + 1;
				col = StdRandom.uniform(perc.getN()) + 1;
				if (perc.isFull(row, col)) {
					perc.open(row, col);
					ct++;
				}
				// System.out.println("Count: " + ct);
			}
			sum += ct;
        }
        System.out.println("After " + TESTS + " attempts, the average number of sites");
        System.out.printf("opened was %.2f", sum/TESTS);
        System.out.printf(" or %.2f", ((sum/TESTS)/(GRID_SIZE * GRID_SIZE)) * 100);
        System.out.println("%.");
        System.out.println("\nDone.\n");
    }
}

[Jayesh A Lalwani]

You never set any of the grid elements to FULL. Is that the right thing to do?

If it is then why keep a grid at all, just assume everything is OPEN

[Ken Austin]

Hey, Jayesh. Thanks for your response.

The default initialization for the int[][] array is 0, which is the value I'm using to represent a closed site. So they all start FULL.

[Junilu Lacar]

As a matter of standard coding style, only constants (static final) are all caps. Attributes and other variables start with lowercase and camel-caps for the rest of the name. 'N' goes against this convention. What's more, since it has a wide scope of use, it should be more self documenting. 'gridSize' or just 'size' would be better names instead of 'N'. Also, since you won't be changing the value after it is initialized in the constructor, it might be a good idea to declare it as final. The formal parameter name in your constructor should also be more descriptive. The usual convention is to use the same name as the instance attribute and differentiate using this, as in:

    this.gridSize = gridSize;

[Junilu Lacar]

Since the getter for the variable for grid size (currently 'N') is declared as private, there's really no point in declaring a getter. There's no "convenience" gained in writing 'getN()' vs. just 'N' or 'getGridSize()' vs just 'gridSize', if you follow my previous advice. An accessor/getter is more useful when you have an expression or calculation involved rather than direct access to a value.

[Junilu Lacar]

You have this expression repeated multiple times in your code:

row < 0 || row > N || col < 0 || col > N

Don't Repeat Yourself (DRY).

This is a good candidate for the "Extract Method" refactoring. Also, that expression evaluates two values. You should strive to have methods that are focused on one responsibility only. How would your code look if you had a method called 'isOutOfBounds(n)'?

An exception is thrown when you have either the row or column value out of bounds but it's not clear which one is not valid. Exceptions are more helpful when they are more specific.

[Ken Austin]

Junilu, thanks for your helpful comments.

I agree that N is not very descriptive. That was the nomenclature used in the programming exercise description of the API, and I guess I assumed they wanted us to leave it as it it was.

I added isOutOfBounds(n) to the original. That makes it a lot easier to read.

I made N final. That makes good sense.

The reason I added the getN() method was because I wasn't able to access it from main() because it was non-static. Was that not the right way to handle that? Should I have made it static instead?

[Junilu Lacar]

You probably tried to just reference N directly, right? Did you try perc.N? If you keep the N name, that might be a compelling reason to provide a better-named accessor like getSize() or getGridSize(), even if it only just returns the value of N directly.

Edit: I was looking at your use of getN() again and realized that you don't even need access to N. Just print out GRID_SIZE -- that should be the same as N anyway. If it isn't, then you'd have a bug.

[Junilu Lacar]

Ken Austin wrote:
I added isOutOfBounds(n) to the original. That makes it a lot easier to read.

Ok, now that you've seen what wonders Extract Method can do for your code's readability, what expression(s) can you extract from the section of your code quoted below to make it more readable? Hint: an intention-revealing name such as isOutOfBounds() is almost always better than a comment. Comments tend to get ignored whereas you always pay attention to a method name.

        if (row == 0) { // If it's on the top row, connect to imaginary site at 0.  
            ufHelper.union(0, xyTo1D(row, col));  
        }  
        if (row == N - 1) { // If it's on the bottom row, connect to imaginary  
                            // site at (N*N) + 1.  
            ufHelper.union((N*N) + 1, xyTo1D(row, col));  
        }  
        if ((row + 1) < N) { // Make sure we don't fall off the grid  
            if (grid[row+1][col] == OPEN)  
                ufHelper.union(xyTo1D(row, col), xyTo1D(row+1, col));  
        }  
        if ((row - 1) >= 0) { // Make sure we don't fall off the grid  
            if (grid[row-1][col] == OPEN)  
                ufHelper.union(xyTo1D(row, col), xyTo1D(row-1, col));  
        }  
        if ((col + 1) < N) { // Make sure we don't fall off the grid  
            if (grid[row][col+1] == OPEN)  
                ufHelper.union(xyTo1D(row, col), xyTo1D(row, col+1));  
        }  
        if ((col - 1) >= 0) { // Make sure we don't fall off the grid  
            if (grid[row][col-1] == OPEN)  
                ufHelper.union(xyTo1D(row, col), xyTo1D(row, col-1));  
        }  

You'll probably go for the easy win and extract the conditional expressions of the if statements but see what you can do to clarify and generalize the intent of the statements inside the if statements because those look like they could use a little DRYing out.

[Junilu Lacar]

I noticed that you are doing bounds checking in a private method. Bounds checking should be done in methods that are part of the class API, that is, any method that can be called by someone else and you have no way of controlling the validity of the values being passed in. There should be no need to do bounds checking in private methods since you have control over the calls made to it. If an exception occurs because out of bounds values have been passed to a private method, that's either a bug or a lack of bounds checking in the calling method.

[Ken Austin]

So the private method would be a good place for an assert statement, rather than the bounds checking?

Junilu Lacar wrote:I noticed that you are doing bounds checking in a private method. Bounds checking should be done in methods that are part of the class API, that is, any method that can be called by someone else and you have no way of controlling the validity of the values being passed in. There should be no need to do bounds checking in private methods since you have control over the calls made to it. If an exception occurs because out of bounds values have been passed to a private method, that's either a bug or a lack of bounds checking in the calling method.

[Ken Austin]

Yes, perc.N works, so I yanked the get method out. Thanks for that tidbit.

Junilu Lacar wrote:You probably tried to just reference N directly, right? Did you try perc.N? If you keep the N name, that might be a compelling reason to provide a better-named accessor like getSize() or getGridSize(), even if it only just returns the value of N directly.

Edit: I was looking at your use of getN() again and realized that you don't even need access to N. Just print out GRID_SIZE -- that should be the same as N anyway. If it isn't, then you'd have a bug.

[Ken Austin]

I'm going to sleep on this one and try again in the morning. Something like...

if ( hasOpenNeighbor(row, column) )
     connectSite();

Junilu Lacar wrote:

Ok, now that you've seen what wonders Extract Method can do for your code's readability, what expression(s) can you extract from the section of your code quoted below to make it more readable? Hint: an intention-revealing name such as isOutOfBounds() is almost always better than a comment. Comments tend to get ignored whereas you always pay attention to a method name.

You'll probably go for the easy win and extract the conditional expressions of the if statements but see what you can do to clarify and generalize the intent of the statements inside the if statements because those look like they could use a little DRYing out.

[Junilu Lacar]

Ken Austin wrote:I'm going to sleep on this one and try again in the morning. Something like...

if ( hasOpenNeighbor(row, column) )
     connectSite();

That's the general idea. The point is to make the code read like a story: it should be immediately apparent to the reader what is happening. If the reader has to pause to analyse what a line of code is doing, that line of code should not be just one of many in a method; ideally it would be the only line of code in that method.

// poor readability: poor names & inline formula
double c = (5/9)*(f-32)

// better
double c = toCelcius(f);

// even better
double temperature = toCelcius(fahrenheit);

...
double toCelcius(double fahr) {
     return (5/9) * (fahr - 32);
} 

Check out this page for my favorite example of how a little effort in refactoring for clarity can greatly improve readability: http://www.industriallogic.com/xp/refactoring/composeMethod.html

[Junilu Lacar]

It's a subtle difference but since you are using 0==FULL and 1==OPEN, these are more naturally represented as boolean values. So instead of int constants FULL and OPEN, you'd have the convenience methods isFull(i, j) and isOpen(i, j):

boolean[][] grid;  // assigning new array defaults all to false
...

private boolean isOpen(int row, int col) {
    return ! isFull(row, col);
}

private boolean isFull(int row, int col) {
    return ...; // provide the appropriate boolean expression
}

The advantage of doing it this way is that you don't have to write the calculations twice. Since one is simply the negative of the other, just write the calculation in one and then use the negation operator for the other. This is a common approach for binary states like this. You just have to make sure that they're not both negating the other, i.e., one of the methods has to do an actual calculation.

[Junilu Lacar]

The method

xyTo1D(int i, int j)

is a bit cryptic -- it makes the reader pause to figure out what it means. Try to find a better name. What is the intent of this method? Try to go beyond the obvious and dig deeper for a clear explanation. 'xy' and '1d' are hints to the implementation detail, something you actually want to hide. What's more 'xy' has to be mapped to 'i' and 'j', the formal parameter names. All this creates cognitive overhead for the reader: it requires more effort to understand. I have a suggestion but will give you a chance to find a better name first.

[Junilu Lacar]

Ken Austin wrote:So the private method would be a good place for an assert statement, rather than the bounds checking?

I suppose you could do that. I personally don't use assert in my production code; I prefer to make assertions in my automated unit tests instead.

[Campbell Ritchie]

Assertions would not necessarily be out of place in production code, because they are disabled by default.

[Diana Cristina]

I read the specification list from coursera and I don't understand your isFull() method.

A full site is an open site that can be connected to an open site in the top row via a chain of neighboring (left, right, up, down) open sites .
We say the system percolates if there is a full site in the bottom row.

Your method return true if a site is closed, not full. Is that correct or i didn't understand well? Can you explain please?Thanks.

[Campbell Ritchie]

Difficult to be sure, since the method is a confusing mass of ifs. And there is a good chance the OP is not listening for responses any more. It would be possible to walk through the method on paper; maybe you have done that already.
I would suggest you write down on paper how you would define full and closed or open cells. Then write down what the algorithm is for determining that. Does it differ whether you have a cell on the edges or in the middle of the grid? When you have that algorithm it should be easy to convert to pseudocode and real code.

And while we are on about it, kick me for not noticing last year that you would always always get 0℃.