The code below is one of three Java files for a percolation program. I\'ve added

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.

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

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