code for : Percolation using Weighted Quick Union Find Algorithm.
this is a homework assignment. iv made the code do what its supposed to do, and it works perfectly.
The only problem im facing now is to model the code structure according to the given API. when i try to do so, i go into null pointer exceptions. i have somewhat understanding of why that happens, but still, cant figure out a solution.
so here is about the assignment:
Percolation: calculate how many sites are needed for a connection between top row n bottom row to take place
algorithm:
open an NxN array, such that initially all 'sites' ie, elements of the array are blocked, ie their state is 'b' connect all top row elements to a 'virtual' TOP site, and all bottom row elements to a virtual 'bottom' site. sites connected to the TOP site directly(as with first row elememts) or indirectly are called 'full'
iterate, opening one site in each process, assign the state of this site 'o' (for open)
once opened, check the neighbors (up,down,left,right) for other open or 'full' members
connect open/full neighbors,
if connected to a 'full' site, change state of the newly opened site to 'f' (full)
else state remains as 'o'check if TOP n BOTTOM are connected,
if yes > system percolates, display num of open sites
else go back to loop
following this algorithm, we have to make a code that that performs computational experiments with percolation.
the api is:
public class PercolationStats {
public PercolationStats(int N, int T) // perform T independent computational experiments on an N-by-N grid
public double mean() // sample mean of percolation threshold
public double stddev() // sample standard deviation of percolation threshold
public double confidenceLo() // returns lower bound of the 95% confidence interval
public double confidenceHi() // returns upper bound of the 95% confidence interval
public static void main(String[] args) // test client, described below
}
im running into problems with creating separate methods for stddev(),confidenceLo(),confidenceHi().
my code below shows the program running WITHOUT creating separate methods for these
my code :
public class PercolationStats{
private int arrDim;
private char[][] state;
private WeightedQuickUnionUF qu;
private int top = 0;
private int bottom;
private double count;
public PercolationStats(int N){
arrDim = N;
qu = new WeightedQuickUnionUF((N*N)+2); // +2 is for the virtual top n bottom site
state = new char[N][N];
for(int i = 0; i< N; i++){
for(int j = 0; j < N ; j++){
// 'b' = blocked
// 'o' = open
// 'f' = full
state[i][j]='b';
}
}
bottom = N*N + 1; // (N*N + 2) - 1;
for(int i = 1; i<= N; i++){
qu.union(top, i); // creating virtual connection of top row to Top site
qu.union(bottom,bottom - i); // connecting bottom row sites to Bottom
}
}
public int convertTo1D(int row, int col){
// the conversion is needed as union find has 1D array, and return value will give the index of that array
// but, since the initial(0) and final(N*N+1) positions of the (N*N + 2) array are reserved for TOP n BOTTOM virtual sites
// the array index range for use is from 1 to N*N
return ((row*arrDim + col) + 1);
}
public void open(int row,int col){
if (row < 1 || row > arrDim || col < 1 || col > arrDim)
throw new IndexOutOfBoundsException("Illegal parameter value.");
// passed values are in 1:N convention , here, since 2D to 1D conversion is used, row convention changed to 0:(N-1)
row = row - 1;
col = col - 1;
if(calledBefore(row,col)){
// if the site is already opened, do nothing
}
else{
count++;
int myIndex = convertTo1D(row,col);
if(row == 0){
state[row][col] = 'f';
}
else if(row == (arrDim - 1)){
state[row][col] = 'o';
}
else{
// if neither in top or bottom row just mark state as open n check for open neighbors, and connect them.
state[row][col] = 'o';
}
// opening a site means connecting the newly opened site with its neighboring sites
if(row < (arrDim - 1)){
// do row + 1
int neighborIndex = convertTo1D(row+1,col);
if(isOpen(row+1,col)){ // ||
qu.union(myIndex, neighborIndex);
// isOpen returns true, so state[row + 1][col] is open. thus it can only change to full if state[row][col] = 'f'
// state[row][col] is either full or open, so state[row + 1][col] has nothing to lose, only it can gain.
state[row + 1][col] = state[row][col];
}else if(isFull(row+1,col)){
qu.union(myIndex, neighborIndex);
state[row][col] = 'f';
}
}
if(row > 0){
// do row - 1
int neighborIndex = convertTo1D(row-1,col);
if(isOpen(row-1,col)){// ||
qu.union(myIndex, neighborIndex);
state[row - 1][col] = state[row][col];
}else if(isFull(row-1,col)){
qu.union(myIndex, neighborIndex);
state[row][col] = 'f';
}
}
if(col < (arrDim - 1)){
// do col + 1
int neighborIndex = convertTo1D(row,col+1);
if(isOpen(row,col + 1)){ // ||
qu.union(myIndex, neighborIndex);
state[row][col + 1] = state[row][col];
}else if(isFull(row,col + 1)){
qu.union(myIndex, neighborIndex);
state[row][col] = 'f';
}
}
if(col > 0){
// do col - 1
int neighborIndex = convertTo1D(row,col-1);
if(isOpen(row,col - 1)){ //
qu.union(myIndex, neighborIndex);
state[row][col - 1] = state[row][col];
}else if(isFull(row,col - 1)){
qu.union(myIndex, neighborIndex);
state[row][col] = 'f';
}
}
}
}
public boolean isOpen(int row, int col){
return (state[row][col] == 'o');
}
public boolean isFull(int row, int col){
return (state[row][col] == 'f');
}
public boolean calledBefore(int row, int col){
return (state[row][col] == 'o' || state[row][col] == 'f');
}
public boolean percolates(){
if(qu.connected(top, bottom)){
System.out.println("\n\n percolates: true");
return true;
}
else{
return false;
}
}
// public double mean(double[] fraction){
// return(StdStats.mean(fraction));
// }
// public double stddev(double[] fraction){
// return(StdStats.stddev(fraction));
// }
// public double confidenceHi(double mu, double sigma, double T){
// return(mu + (1.96*sigma/Math.sqrt((double)T)));
// }
// public double confidenceLo(double mu, double sigma, double T){
// return(mu - (1.96*sigma/Math.sqrt((double)T)));
// }
public static void main(String[] args){
final long startTime = System.nanoTime();
int size = Integer.parseInt(args[0]);
int numOfRuns = Integer.parseInt(args[1]);
PercolationStats perC;
double[] fraction = new double[numOfRuns];
for(int runCount = 0; runCount < numOfRuns ; runCount++){
//
// System.out.println("enter size: ");
// int size = StdIn.readInt() ;
// int size=200;
int arraySize= size*size;
perC = new PercolationStats(size);
// System.out.println("enter number of iterations: ");
// int numOfRuns = StdIn.readInt();
for(;;){
int row = StdRandom.uniform(size) + 1;
int column = StdRandom.uniform(size) + 1;
// System.out.format("\n row n column: %d %d",row,column);
// int row = StdIn.readInt();
// int column = StdIn.readInt();
if((row<1 || row>size) || (column < 1 || column > size )) throw new java.lang.IndexOutOfBoundsException("entered value is not valid \n");
perC.open(row,column);
if(perC.percolates()){
System.out.println("percolates with: " + perC.count + "counts");
fraction[runCount] = perC.count/arraySize;
break;
}
}
}
// double mu = perC.mean(fraction);
// double sigma = perC.stddev(fraction);
// double confHi = perC.confidenceHi(mu, sigma, numOfRuns);
// double confLow = perC.confidenceLo(mu, sigma, numOfRuns);
double mu = StdStats.mean(fraction);
double sigma = StdStats.stddev(fraction);
double confHi = mu + (1.96*sigma/Math.sqrt((double)numOfRuns));
double confLow = mu - (1.96*sigma/Math.sqrt((double)numOfRuns));
System.out.println("\n mean: " + mu);
System.out.println(" stddev: " + sigma);
System.out.println(" confHi: " + confHi);
System.out.println(" confLow: " + confLow);
final long duration = System.nanoTime() - startTime;
System.out.println("duration: " + duration);
}
}
iv kept my attempts at creating the separate methods within comments.
all the supporting codes like StdRandom and StdIn can be found here
im really working hard on this, any suggestion will be of great help!
regards
somjit.
