Skip to content

Instantly share code, notes, and snippets.

@geolffreym

geolffreym/Percolation.java

Last active October 15, 2021 13:48
Show Gist options
  • Save geolffreym/ca869b97a46ec924d91f0c188d74170d to your computer and use it in GitHub Desktop.
Save geolffreym/ca869b97a46ec924d91f0c188d74170d to your computer and use it in GitHub Desktop.
Download ZIP
Quick-Find Percolation
Raw
Percolation.java
package DynamicConnection.example;
import DynamicConnection.WeightedQuickUnion;
public class Percolation {
private enum States {
CLOSE,
OPEN
}
private final int N;
private final int TOP = 0;
private int openBoxes = 0;
private final States[][] boxes;
private final WeightedQuickUnion unionFind;
// creates n-by-n grid, with all sites initially blocked
public Percolation(int n) {
if (n <= 0) throw new IllegalArgumentException();
this.N = n; // Grid size
this.boxes = new States[n][n];
// Allow to Quick-Find holds virtual root node top and bottom
// Add an extra object to top and bottom eg: 5 x 5 + 2
// Not Zer0-based indexes in operations params row, col
unionFind = new WeightedQuickUnion(n * n + 2);
// Init Blocking all boxes
for (int k = 0; k < this.N; k++) {
for (int j = 0; j < this.N; j++) {
boxes[k][j] = States.CLOSE;
}
}
}
private void virtualTopUnion(int row, int col) {
// Populate top virtual component tree
// Get the corresponding index for flat 1D
int index = find1DIndexFrom2D(row, col);
unionFind.union(index, this.TOP); // 0 root tree
}
private void virtualBottomUnion(int row, int col) {
// Populate top virtual component tree
// Get the corresponding index for flat 1D
int index = find1DIndexFrom2D(row, col);
// Add object to virtual bottom component this.N * this.N + 1
// eg: 5 x 5 + 1 = 26 <= root for bottom
unionFind.union(index, this.N * this.N + 1);
}
/**
* Open box in grid (row,col) if not open, also add union
*
* @param row index in grid
* @param col index in grid
*/
public void open(int row, int col) {
if (row < 1 || row > this.N || col < 1 || col > this.N)
throw new IllegalArgumentException();
// Row and col are passed as non-zero based numbering
boxes[row - 1][col - 1] = States.OPEN;
if (row == 1) virtualTopUnion(row, col);
if (row == this.N) virtualBottomUnion(row, col);
unionDirection(row, col, row - 1, col); // Top union
unionDirection(row, col, row + 1, col);// Bottom union
unionDirection(row, col, row, col + 1); // Right union
unionDirection(row, col, row, col - 1); // Left union
openBoxes++;
}
/**
* Is open site in (row, col) in grid?
*
* @param row index in grind
* @param col index in grid
* @return - true if box is OPEN state else return false
* @throws IllegalArgumentException - if both 1 > row > N and 1 > col > N
*/
public boolean isOpen(int row, int col) {
if (row < 1 || row > this.N || col < 1 || col > this.N)
throw new IllegalArgumentException();
return boxes[row - 1][col - 1] == States.OPEN;
}
/**
* Add union in diff directions for grid
*
* @param x1 from row
* @param y1 from col
* @param x2 to row
* @param y2 to col
*/
private void unionDirection(int x1, int y1, int x2, int y2) {
// Avoid index over/under flow
// If x2 underflow or x2 overflow or y2 underflow or y2 overflow
if (x2 < 1 || x2 > this.N || y2 < 1 || y2 > this.N) return;
if (!this.isOpen(x2, y2)) return;
int from = this.find1DIndexFrom2D(x1, y1);
int to = this.find1DIndexFrom2D(x2, y2);
unionFind.union(from, to);
}
/**
* Ss the site (row, col) full?
*
* @param row index in grid
* @param col index in grid
* @return - true if is object for row, col is connected to TOP else return false
* @throws IllegalArgumentException - if both 1 > row > N and 1 > col > N
*/
public boolean isFull(int row, int col) {
if (row < 1 || row > this.N || col < 1 || col > this.N)
throw new IllegalArgumentException();
return unionFind.connected(find1DIndexFrom2D(row, col), TOP);
}
// returns the number of open sites
public int numberOfOpenSites() {
return openBoxes;
}
// does the system percolate?
public boolean percolates() {
// Is the bottom connected with top over open boxes?
return unionFind.connected(TOP, this.N * this.N + 1);
}
/**
* Locate index for 1D flat array from 2D corresponding array
*
* @param row in 2D - Not zero-based index
* @param col in 2D - Not zero-based index
* @return int projected 1D index from 2D array
*/
private int find1DIndexFrom2D(int row, int col) {
// Current N size eg. 5x5, get in 2D (col 2, row 2) = 7 in 1D
// [
// 0=> 0,1,2,3,4,
// 1=> 5,6,7,8,9
// 2=> ....
// 3=> ....
// ]
return (this.N * (row - 1)) + col;
}
public static void main(String[] args) {
}
}
Raw
PercolationStats.java
import edu.princeton.cs.algs4.StdOut;
import edu.princeton.cs.algs4.StdRandom;
import edu.princeton.cs.algs4.StdStats;
public class PercolationStats {
private double percolationResults[];
private int trials;
// perform independent trials on an n-by-n grid
public PercolationStats(int n, int trials) {
if (n <= 0 || trials <= 0) throw new IllegalArgumentException();
this.percolationResults = new double[trials];
this.trials = trials;
for (int i = 0; i < trials; i++) {
Percolation percolation = new Percolation(n);
while (!percolation.percolates()) {
int randomCol = StdRandom.uniform(1, n + 1);
int randomRow = StdRandom.uniform(1, n + 1);
percolation.open(randomRow, randomCol);
}
this.percolationResults[i] = percolation.numberOfOpenSites() / Math.pow(n, 2);
}
}
// sample mean of percolation threshold
public double mean() {
return StdStats.mean(this.percolationResults);
}
// sample standard deviation of percolation threshold
public double stddev() {
return StdStats.stddev(this.percolationResults);
}
// low endpoint of 95% confidence interval
public double confidenceLo() {
return mean() - (1.96 / Math.sqrt(this.trials));
}
// high endpoint of 95% confidence interval
public double confidenceHi() {
return mean() + (1.96 / Math.sqrt(this.trials));
}
public static void main(String[] args) {
int n = Integer.parseInt(args[0]);
int trials = Integer.parseInt(args[1]);
PercolationStats percolationTest = new PercolationStats(n, trials);
StdOut.println(String.format("mean = %f", percolationTest.mean()));
StdOut.println(String.format("stddev = %f", percolationTest.stddev()));
StdOut.println(
String.format(
"95%% confidence interval = [ %f, %f ]",
percolationTest.confidenceLo(),
percolationTest.confidenceHi()
)
);
}
}
Raw
WeightedQuickUnion.java
package DynamicConnection;
public class WeightedQuickUnion {
private final int[] tree;
private final int[] sizes;
public WeightedQuickUnion(int N) {
// Initialize with N objects
this.tree = new int[N];
this.sizes = new int[N];
// Initial fill components with value=index
for (int i = 0; i < this.tree.length; i++) {
this.tree[i] = i;
this.sizes[i] = 0;
}
}
/**
* Return the root in tree for node i
* Auto path compression to avoid tall tree.
* Move `i` subtree root to 1 depth below main root.
*
* @param i node to search root for
* @return the root for node i
*/
private int find(int i) {
// Go up through the tree until find the `reflexive node` = root
while (i != this.tree[i]) {
// Root for `i` will be one degree below main root now.
this.tree[i] = this.tree[this.tree[i]];
i = this.tree[i];
}
return i;
}
/**
* Check if node p 's root belongs to node q 's root
* If the value is the same then they are connected
*
* @param p index
* @param q index
* @return boolean true if connected else false
*/
public boolean connected(int p, int q) {
return find(p) == find(q);
}
/**
* Replace one value only in array to connect components
* With p and q 's root corresponding [0,1] => [1,1] p is now sub-tree of q's root
*
* @param p index
* @param q index
*/
public void union(int p, int q) {
// root for index p
int pRoot = find(p);
// root for index q
int qRoot = find(q);
// Same root? Do nothing!
if (pRoot == qRoot) return;
weightedUnion(pRoot, qRoot);
}
/**
* Check for size in two trees.
* Add the smaller tree below the big one.
*
* @param pRoot root for p
* @param qRoot root for q
*/
void weightedUnion(int pRoot, int qRoot) {
int pSize = this.sizes[pRoot];
int qSize = this.sizes[qRoot];
if (pSize < qSize) {
this.tree[pRoot] = qRoot;
this.sizes[qRoot] += pSize;
} else {
this.tree[qRoot] = pRoot;
this.sizes[pRoot] += qSize;
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment