The code below is one of three Java files for a percolation program. I\'ve added
ID: 3840550 • Letter: T
Question
The code below is one of three Java files for a percolation program. I've added bits and pieces of my code but need help finishing it. Any insight and explanation would be much appreciated.
package algs15.perc;
import stdlib.*;
import algs15.*;
// Uncomment the import statements above.
// You can test this using InteractivePercolationVisualizer and PercolationVisualizer
// All methods should make at most a constant number of calls to the UF data structure,
// except percolates(), which may make up to N calls to the UF data structure.
// You can use a second UF to answer percolates. For the second UF, you can connect
// all of the elements of the top row and separately all of the elements of the bottom row.
// Then you can implement percolates as a single call to "connected".
public class Percolation {
int N;
boolean[] open;
// TODO: more fields to add here
WeightedUF WUF;
public Percolation(int N) {
this.N = N;
this.open = new boolean[N*N];
// TODO: more to do here
this.WUF = new WeightedUF(N*N);
}
// open site (row i, column j) if it is not already
public void open(int i, int j) {
int position = i*N+j;
open[position] = true;
// TODO: more to do here. 4 cases. (Is is connect on both the top and the bottom?)
// make a special case WUF.
// Check left
if (i >= 0 && isOpen(i-1, j)) {
WUF.union(position, (i-1)*N+j);
}
// Check right
if (i <= N && isOpen(i+1, j)) {
WUF.union(position, (i+1)*N+j);
}
// Check above
if (j >= 0 && isOpen(i, j-1)) {
WUF.union(position, i*N+(j-1));
}
// Check below
if (j <= N && isOpen(i, j+1)) {
WUF.union(position, i*N+(j+1));
}
}
// is site (row i, column j) open?
public boolean isOpen(int i, int j) {
return open[i*N+j];
}
// is site (row i, column j) full?
public boolean isFull(int i, int j) {
// TODO 1 line of code (only connected on the top row)
// Need a loop here to connect all of the top elements together to answer isFull()
return false;
}
// does the system percolate?
public boolean percolates() {
// TODO 1 line of code (only connected on the bottom row)
return false;
}
}
Explanation / Answer
To execute this code you need WeightedQuickUnionUF.java
Code:
public class PercolationAlgorithmExample {
private WeightedQuickUnionUF WUF; //Keeps track of connectivity
private boolean[] open; //Keeps track of whether a site is blocked or not
int N, head, foot;
// create N-by-N grid, with all sites blocked
public PercolationAlgorithmExample(int N) {
this.N = N;
WeightedQuickUnionUF WUF = new WeightedQuickUnionUF(N*N + 2);
boolean[] open = new boolean[N*N];
//Sets all the sites to be blocked
for(int i=0; i<open.length; i++)
open[i] = false;
//Sets the values for the head and foot nodes
head = N*N + 1;
foot = N*N + 2;
//Connects the head node to all the "top" nodes (0 - N-1)
for(int i=0; i<N; i++)
WUF.union(head, i);
//Connects the foot node to all the "bottom" nodes ((N^2 - N) - N^2-1)
for(int i=0; i<N; i++)
WUF.union(foot, (N*N)-N+i);
}
// open site (row i, column j) if it is not already
public void open(int i, int j) {
if((i < 1 || i > N) || (j < 1 || j > N)) {
throw new java.lang.IndexOutOfBoundsException();
}
int connectingNode = N*(i-1) + j-1;
if(open[connectingNode]==false) { // ensure not already open
open[connectingNode] = true;
if(connectingNode % N != 0) //node not on the left
WUF.union(connectingNode, connectingNode - 1);
if(connectingNode >= N) //node not on the top
WUF.union(connectingNode, connectingNode - N);
if(connectingNode % N != N-1) //node not on the right
WUF.union(connectingNode, connectingNode + 1);
if(connectingNode <= N*(N-1)) //node not on the bottom
WUF.union(connectingNode, connectingNode + N);
}
}
// is site (row i, column j) open?
public boolean isOpen(int i, int j) {
if((i < 1 || i > N) || (j < 1 || j > N)) {
throw new java.lang.IndexOutOfBoundsException();
}
return open[(i-1)*N + j-1];
}
// is site (row i, column j) full (connects to the head node)
public boolean isFull(int i, int j) {
if((i < 1 || i > N) || (j < 1 || j > N)) {
throw new java.lang.IndexOutOfBoundsException();
}
return WUF.connected((i-1)*N + j-1, head);
}
// does the system percolate?
public boolean percolates() {
return WUF.connected(head, foot);
}
}
Hope this helps.