Win a copy of Kotlin in Action this week in the Kotlin forum!
  • Post Reply Bookmark Topic Watch Topic
  • New Topic

Code review: Percolation.java  RSS feed

 
Ken Austin
Ranch Hand
Posts: 39
Chrome Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.

 
Jayesh A Lalwani
Rancher
Posts: 2762
32
Eclipse IDE Spring Tomcat Server
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Ranch Hand
Posts: 39
Chrome Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Sheriff
Posts: 11126
160
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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:
 
Junilu Lacar
Sheriff
Posts: 11126
160
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Sheriff
Posts: 11126
160
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
You have this expression repeated multiple times in your code:


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
Ranch Hand
Posts: 39
Chrome Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Sheriff
Posts: 11126
160
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Sheriff
Posts: 11126
160
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.



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
Sheriff
Posts: 11126
160
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Ranch Hand
Posts: 39
Chrome Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Ranch Hand
Posts: 39
Chrome Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Ranch Hand
Posts: 39
Chrome Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I'm going to sleep on this one and try again in the morning. Something like...



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
Sheriff
Posts: 11126
160
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Ken Austin wrote:I'm going to sleep on this one and try again in the morning. Something like...


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.


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
Sheriff
Posts: 11126
160
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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):

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
Sheriff
Posts: 11126
160
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Sheriff
Posts: 11126
160
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Marshal
Posts: 55678
161
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Assertions would not necessarily be out of place in production code, because they are disabled by default.
 
Diana Cristina
Greenhorn
Posts: 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Marshal
Posts: 55678
161
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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℃.
 
It is sorta covered in the JavaRanch Style Guide.
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!