Hello! This is a basic percolation program that I\'ve coded for my homework in J

Question

Hello! This is a basic percolation program that I've coded for my homework in Java. The program mostly works, however, when I run it the square at position 0,1 is ALWAYS opened. Can you help me figure out why? I'm not sure what I'm doing wrong. I've included WEIGHTEDUF.java and INTERACTIVEPERCOLATIONVISUALIZER.java which are the related files for the PERCOLATION.java assignment.

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
   int top = N*N;
   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?)
       if (i == 0) {
           WUF.union(position, top);
       }
       // Check left
       if (i > 0 && isOpen(i-1, j)) {
           WUF.union(position, (i-1)*N+j);
       }
       // Check right
       if (i < N-1 && 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-1 && 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()
       int position = i*N+j;
       return WUF.connected(top, position);
   }
  
   // does the system percolate?
   public boolean percolates() {
   // TODO 1 line of code (only connected on the bottom row)
       for (int x = 0; x            if (isFull(N-1, x)) {
               return true;
           }
       }
       return false;
   }
}

WEIGHTEDUF.java

package algs15;
import java.util.Arrays;
import stdlib.*;

public class WeightedUF implements UF {
   private int[] id; // id[i] = parent of i
   private int[] sz; // sz[i] = number of objects in subtree rooted at i
   private int count; // number of components

   /**
   * Create an empty union find data structure with N isolated sets.
   */
   public WeightedUF(int N) {
       if (N < 0) throw new IllegalArgumentException();
       count = N;
       id = new int[N];
       sz = new int[N];
       for (int i = 0; i < N; i++) {
           id[i] = i;
           sz[i] = 1;
       }
   }

   /**
   * Return the id of component corresponding to object p.
   */
   public int find(int p) {
       if (p < 0 || p >= id.length) throw new IndexOutOfBoundsException();
       while (p != id[p]) {
           p = id[p];
       }
       return p;
   }

   /**
   * Return the number of disjoint sets.
   */
   public int count() {
       return count;
   }

   /**
   * Are objects p and q in the same set?
   */
   public boolean connected(int p, int q) {
       return find(p) == find(q);
   }

   /**
   * Replace sets containing p and q with their union.
   */
   public void union(int p, int q) {
       int pid = find(p);
       int qid = find(q);
       if (pid == qid) return;

       // make smaller root point to larger one
       // in the case of a tie, p is the champion
       if (sz[pid] < sz[qid]) { id[pid] = qid; sz[qid] += sz[pid]; }
       else { id[qid] = pid; sz[pid] += sz[qid]; }
       count--;
   }

   public String toString() { return Arrays.toString (id); }

   public static void main(String[] args) {
       StdIn.fromFile ("data/tinyUF.txt");
       //StdIn.fromFile ("data/mediumUF.txt");
       //StdIn.fromFile ("data/largeUF.txt");
       //StdIn.fromFile ("/tmp/quiz1UF.txt");

       int N = StdIn.readInt();
       WeightedUF uf = new WeightedUF(N);

       // read in a sequence of pairs of integers (each in the range 0 to N-1),
       // calling find() for each pair: If the members of the pair are not already
       // call union() and print the pair.
       Stopwatch sw = new Stopwatch ();
       while (!StdIn.isEmpty()) {
           int p = StdIn.readInt();
           int q = StdIn.readInt();
           if (uf.connected(p, q)) continue;
           uf.union(p, q);
           StdOut.println(p + " " + q);
           GraphvizBuilder.ufToFile (uf.id);
       }
       StdOut.format("UF # components: %d [%f] ", uf.count(), sw.elapsedTime ());
       StdOut.println (uf);

   }

}

INTERACTIVEPERCOLATIONVISUALIZER.java

package algs15.perc;
import stdlib.*;

/* **************************************************************************
* This program takes the grid size N as a command-line argument.
* Then, the user repeatedly clicks sites to open with the mouse.
* After each site is opened, it draws full sites in light blue,
* open sites (that aren't full) in white, and blocked sites in black.
*
****************************************************************************/
public class InteractivePercolationVisualizer {
   private static final int delay = 1;

   public static void main(String[] args) {
       args = new String[] { "4" };

       // N-by-N percolation system (read from command-line, default = 10)
       int N = 10;
       if (args.length == 1) N = Integer.parseInt(args[0]);

       // turn on animation mode
       StdDraw.show(0);

       // repeatedly open site specified my mouse click and draw resulting system
       StdOut.println(N);

       Percolation perc = new Percolation(N);
       PercolationVisualizer.draw(perc, N);
       StdDraw.show(delay);
       while (true) {

           // detected mouse click
           if (StdDraw.mousePressed()) {

               // screen coordinates
               double x = StdDraw.mouseX();
               double y = StdDraw.mouseY();

               // convert to row i, column j
               int i = (int) (N - Math.floor(y) - 1);
               int j = (int) (Math.floor(x));

               // open site (i, j) provided it's in bounds
               if (i >= 0 && i < N && j >= 0 && j < N) {
                   if (!perc.isOpen(i, j)) {
                       StdOut.println(i + " " + j);
                   }
                   perc.open(i, j);
               }

               // draw N-by-N percolation system
               PercolationVisualizer.draw(perc, N);
           }
           StdDraw.show(delay);
       }
   }
}

Explanation / Answer

public class PercolationOne
{
  
private int total_sites, trial_size, count;
private double[] iterations;


public PercolationOne(int M, int N)

{
checkException(M,N);
total_sites = M*M;
trial_size = N;
iterations = new double[N];
for (int i = 0; i < N; i++)
{

Percolation perc = new Percolation(N);
count = 0;
while (!perc.percolates())
{

int row = StdRandom.uniform(1,M+1);
int col = StdRandom.uniform(1,M+1);
if (!perc.isOpen(col,row))
{
count++;
}
perc.open(col, row);
}
iterations[k] = (double)count/(double)total_sites;
}
}

public double mean()   
{
double sum = 0;
for (int k = 0; k < trial_size; k++)
{
sum += iterations[k];
}
double mean = sum/(double)trial_size;
return mean;
}
  
public double stddev()   
{
double sum = 0;
double mean = mean();
for (int k = 0; k < trial_size; k++)
{
sum += (iterations[k]-mean)*(iterations[k]-mean);
}
double stddev = Math.sqrt(sum/((double)trial_size-1));
return stddev;
}
  
public double confidenceLo()
{
double mean = mean();
double stddev = stddev();
return mean-(2.96*stddev/Math.sqrt((double)trial_size));
  
}
public double confidenceHi()   
{
double mean = mean();
double stddev = stddev();
return mean+(2.96*stddev/Math.sqrt((double)trial_size));
}
  
private void checkException(int M, int N)
{
if (M <= 0 | N <= 0)
{
throw new java.lang.IllegalArgumentException("input needs to be positive values");
}
}
  
public static void main(String[] args)   
{
int M = Integer.parseInt(args[0]);
int N = Integer.parseInt(args[1]);
PercolationStats PS = new PercolationStats(M,N);
System.out.println(PS.mean());
System.out.println(PS.stddev());
System.out.println(PS.confidenceLo());
System.out.println(PS.confidenceHi());
}

}

public class PercolationTwo
{
private boolean[][] sites;
private int grid;
private int beginNode;
private int endNode;

public PercolationTwo(int M)
{
M = M+1;
QU = new WeightedQuickUnionUF(M*M+1);
Backwash = new WeightedQuickUnionUF(M*M+2);
sites = new boolean[M][M];
grid = M-1;
beginNode = 0;
endNode = M*M+1;

}
public void open(int x, int y)
{


checkException(x, y);
if (!sites[y][x])
{
sites[y][x] = true;
}
int index = indexCalc(y, x);
if (y != 1) {
if (sites[y-1][x])
{
QU.union(index, index-1);
Backwash.union(index,index-1);
}
}

if (y != grid) {
if (sites[y+1][x])
{
QU.union(index, index+1);
Backwash.union(index, index+1);
}
}

if (x != 1)
{
if (sites[j][x-1])
{
QU.union(index, y+grid*(x-1));
Backwash.union(index, y+grid*(x-1));
}
}
else
{

if (x != grid)
{
if (sites[y][x+1])
{
QU.union(index, y+grid*(x+1));
Backwash.union(index, y+grid*(x+1));
}
}
else
{
Backwash.union(index,endNode);
}

}

public boolean isOpen(int i, int j)
{

checkException(x, y);
return sites[y][x];
}

public boolean isFull(int x, int y)
{

checkException(x, y);
return (QU.connected(indexCalc(y,x), beginNode) );
}

public boolean percolate()
{
return Backwash.connected(beginNode,endNode);
}

private int indexCalc(int x, int y)
{
return x + grid*y;
}
private void checkException(int x, int y)
{
if (x <= 0 || x > grid || y <= 0 || y > grid)
{
throw new IndexOutOfBoundsException("row index x out of bounds");
}
}

public static void main(String[] args)
{
int grid_size = 3;
Percolation perc = new Percolation(grid_size);

}
}
perc.open(1,1);
perc.open(3,3);
perc.open(2,2);
perc.open(1,1);
System.out.println(perc.percolates());
System.out.println(perc.isFull(1,2));
}
}

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.