Newbie here, presenting the code for close public scrutiny.
Couple remarks regarding the context (taken from Princeton's COS 226 course):
- In this problem I model a percolation system using an N-by-N grid of sites. Each site could be either open or blocked (all of them are blocked initially). To open the site, client should call open(row, col) method.
- There is a notion of full site. "A full site is an open site that can be connected to an open site in the top row via a chain of neighboring (left, right, up, down) open sites [1]"
- The system percolates, when there is a full site in the bottom row.
Below you can find an image of 2 percolation systems:
- Now the goal is to perform efficient percolates() queries (boolean method that checks whether system percolates or not), using the UnionFind algorithm (Brute-force solution will take quadratic time, which is not scalable for huge systems).
Additional materials that might be useful:
Quick video for visualizing the entire process:
https://www.youtube.com/watch?v=xUWuZjadbbQSource code for WeightedQuickUnionUF: http://algs4.cs.princeton.edu/15uf/WeightedQuickUnionUF.java.html
[1] Reference: https://www.cs.princeton.edu/courses/archive/fall15/cos226/assignments/percolation.html
Below goes my implementation of Percolation:
Percolation.java
package percolation;
import edu.princeton.cs.algs4.WeightedQuickUnionUF;
/**
* Modeling a percolation system using an N-by-N grid of sites.
* Each site is either open or blocked. A full site is an open site
* that can be connected to an open site in the top row via a chain of
* neighboring (left, right, up, down) open sites.
* The system percolates if there is a full site in the bottom row.
* In other words, a system percolates if we fill all open sites
* connected to the top row and that process fills some open site on the bottom row.
* <p>
* Application in practice: <a href="http://www.geoffreylandis.com/percolation.htp">The Fermi Paradox: An Approach Based on Percolation Theory</a> </p>
* <p>
* Code for Percolation Visualization can be found at: <a href="http://www.cs.princeton.edu/courses/archive/fall16/cos226/checklist/percolation.html">Princeton COS 226</a>
* </p>
*/
public class Percolation {
private final boolean[][] open;
private final boolean[][] full;
private int n;
private final int N;
private final WeightedQuickUnionUF uf;
private final int top; // virtual top-site
private final int bottom; // virtual bottom-site
/* Rep Invariant
* open, full, uf != null
* open.length == full.length
* n >= 0
* N > 0
* top != bottom
* Abstraction Function
* AF(N) represents a percolation system with N^2 sites in it (N-by-N grid).
* Safety Exposure Argument
* All fields are private. All fields except n are final.
* All fields except open, full and uf are immutable;
* however they are not being shared with clients.
*/
/**
* Creates N-by-N grid, with all sites initially blocked.
* @param N dimension of the grid. Should be greater than 0.
* @throws IllegalArgumentException if N <= 0
*/
public Percolation(int N) {
if (N <= 0) throw new IllegalArgumentException("N must be more than zero");
this.open = new boolean[N][N];
this.full = new boolean[N][N];
this.n = 0;
this.N = N;
this.uf = new WeightedQuickUnionUF(N*N + 2); // to allow top & bottom virtual sites
this.top = N*N; // top virtual site
this.bottom = N*N + 1; // bottom virtual site
for (int i = 0 ; i < N; i++) {
if (i != N * (N - 1) + i) { // avoids bug in 1x1 case
uf.union(top, i);
uf.union(bottom, N * (N - 1) + i);
}
}
checkRep(); // checking rep invariant, assertions should be enabled!
}
/**
* Opens the site (row, col) on the grid. This method has no effect
* if the site is already open.
* @param row row of the site to be opened
* @param col column of the site to be opened
* @throws IllegalArgumentException if row or col is < 0 or >= N
*/
public void open(int row, int col) {
if (row < 0 || row >= N) throw new IllegalArgumentException("Illegal value for row: must be between 0 and N - 1");
if (col < 0 || col >= N) throw new IllegalArgumentException("Illegal value for col: must be between 0 and N - 1");
if (!isOpen(row, col)) {
open[row][col] = true;
n++;
}
else return; // to avoid unnecessary computations
if (row == 0) {
checkAdjacent(full, open, row, col);
full[row][col] = true;
}
// filling in
if (row + 1 < N && isFull(row + 1, col)) checkAdjacent(full, open, row, col);
if (col + 1 < N && isFull(row, col + 1)) checkAdjacent(full, open, row, col);
if (col - 1 >= 0 && isFull(row, col - 1)) checkAdjacent(full, open, row, col);
if (row - 1 >= 0 && isFull(row - 1, col)) checkAdjacent(full, open, row, col);
// merging
if (row + 1 < N && isOpen(row + 1, col)) uf.union(row * N + col, (row + 1) * N + col);
if (col + 1 < N && isOpen(row, col + 1)) uf.union(row * N + col, row * N + col + 1);
if (col - 1 >= 0 && isOpen(row, col - 1)) uf.union(row * N + col, row * N + col - 1);
if (row - 1 >= 0 && isOpen(row - 1, col)) uf.union(row * N + col, (row - 1) * N + col);
if (N == 1) { // for 1x1 case
uf.union(bottom, 0);
uf.union(top, 0);
}
checkRep(); // checking rep invariant, assertions should be enabled!
}
// Recursively checks adjacent sites to be filled
private void checkAdjacent(boolean[][] full, boolean[][] open, int row, int col) {
if (row < 0 || row >= N) return;
if (col < 0 || col >= N) return;
if (!isOpen(row, col)) return;
if (isFull(row, col)) return;
full[row][col] = true;
checkAdjacent(full, open, row + 1, col);
checkAdjacent(full, open, row, col + 1);
checkAdjacent(full, open, row, col - 1);
checkAdjacent(full, open, row - 1, col);
}
/**
* Checks whether the site (row, col) is open.
* @param row row of the site
* @param col column of the site
* @return true iff, the site is open
* @throws IllegalArgumentException if row or col is < 0 or >= N
*/
public boolean isOpen(int row, int col) {
if (row < 0 || row >= N) throw new IllegalArgumentException("Illegal value for row: must be between 0 and N - 1");
if (col < 0 || col >= N) throw new IllegalArgumentException("Illegal value for col: must be between 0 and N - 1");
return open[row][col];
}
/**
* Checks whether the site (row, col) is full.
* @param row row of the site
* @param col column of the site
* @return true iff, the site is full
* @throws IllegalArgumentException if row or col is < 0 or >= N
*/
public boolean isFull(int row, int col) {
if (row < 0 || row >= N) throw new IllegalArgumentException("Illegal value for row: must be between 0 and N - 1");
if (col < 0 || col >= N) throw new IllegalArgumentException("Illegal value for col: must be between 0 and N - 1");
return full[row][col];
}
/**
* @return the number of opened sites.
*/
public int numberOfOpenSites() {
return n;
}
/**
* Checks whether system percolates or not. This method takes constant time.
* @return true iff the system percolates
* (i.e possible to reach bottom row from top row,
* with the help of opened sites).
*/
public boolean percolates() {
return uf.connected(top, bottom);
}
// Note to self: checkRep ought to be called at every operation
// that creates or mutates rep
/**
* Checks whether the rep invariant is being preserved.
* Assertions should be enabled.
*/
private void checkRep() {
assert open != null;
assert full != null;
assert uf != null;
assert open.length == full.length;
assert n >= 0;
assert N > 0;
assert top != bottom;
}
}
And below goes the implementation of JUnit test case for Percolation
PercolationTest.java
package percolation;
import static org.junit.Assert.*;
import org.junit.Test;
public class PercolationTest {
// check if assertions are on
@Test(expected = AssertionError.class)
public void testAssertionsEnabled() {
assert false;
}
@Test
public void emptyPercolationTest() {
Percolation perc = new Percolation(5);
for (int i = 0; i < 5; i++) {
for (int j = 0; j < 5; j++) {
assertFalse(perc.isOpen(i, j));
assertFalse(perc.isFull(i, j));
}
}
assertFalse(perc.percolates());
assertEquals(0, perc.numberOfOpenSites());
}
@Test
public void tinyPercolationTest() {
Percolation perc = new Percolation(1);
assertFalse(perc.isOpen(0, 0));
assertFalse(perc.isFull(0, 0));
assertFalse(perc.percolates());
assertEquals(0, perc.numberOfOpenSites());
perc.open(0, 0);
assertTrue(perc.isOpen(0, 0));
assertTrue(perc.isFull(0, 0));
assertTrue(perc.percolates());
assertEquals(1, perc.numberOfOpenSites());
}
@Test
public void basicPercolationTest() {
Percolation perc = new Percolation(3);
perc.open(0, 0);
assertTrue(perc.isOpen(0, 0));
assertTrue(perc.isFull(0, 0));
assertFalse(perc.percolates());
perc.open(1, 0);
assertTrue(perc.isOpen(1, 0));
assertTrue(perc.isFull(1, 0));
assertFalse(perc.percolates());
perc.open(1, 1);
assertTrue(perc.isOpen(1, 1));
assertTrue(perc.isFull(1, 1));
assertFalse(perc.percolates());
perc.open(2, 2);
assertTrue(perc.isOpen(2, 2));
assertFalse(perc.isFull(2, 2));
assertFalse(perc.percolates());
perc.open(2, 0);
assertTrue(perc.isOpen(2, 0));
assertTrue(perc.isFull(2, 0));
assertTrue(perc.percolates());
assertEquals(5, perc.numberOfOpenSites());
}
// common problem
@Test
public void backwashPercolationTest() {
Percolation perc = new Percolation(4);
perc.open(0, 0);
perc.open(1, 0);
perc.open(2, 0);
// sites not intended to be full, added before model percolates
perc.open(2, 2);
perc.open(3, 2);
perc.open(3, 0);
assertTrue(perc.percolates());
assertFalse(perc.isFull(2, 2));
assertFalse(perc.isFull(3, 2));
// sites not intended to be full, added after model percolates
perc.open(1, 2);
perc.open(1, 3);
perc.open(3, 3);
assertFalse(perc.isFull(1, 2));
assertFalse(perc.isFull(1, 3));
assertFalse(perc.isFull(3, 3));
}
@Test
public void sameNumberOfOpenSitesTest() {
Percolation perc = new Percolation(3);
perc.open(0, 0);
perc.open(0, 0);
assertEquals(1, perc.numberOfOpenSites());
}
}
Any constructive feedback is very much welcome!
connected()
and hencepercolates()
take time proportional to log2 N + log2 M where N and M are the number of connected nodes totop
andbottom
nodes \$\endgroup\$