Zikoat · January 13, 2020 15:00 · Aug 16, 2017 · Aug 16, 2017 · Aug 16, 2017 · Aug 16, 2017
diff --git a/percolation.html b/percolation.html
@@ -6,6 +6,10 @@
 
 runTest(20, 100);
 
+// the Percolation and WeightedQuickUnionUF functions come from this article:
+// http://michaeltoth.me/using-javascript-to-visualize-a-percolation-system.html
+// stripped of all its nice UI, to barebones javascript
+
 function runTest(N, amount) {
 
     var t0 = performance.now();

diff --git a/percolation.html b/percolation.html
@@ -1,8 +1,8 @@
 <script type="text/javascript">
-// download and open this HTML file in the browser, and open the console
-// you can use runTest(N, amount) in the console to calculate the average
-// percolation threshold.
-// reasonable arguments are runTest(1000,10)
+// Download the ZIP(on github), and open this HTML file in the browser. 
+// Open the console, and you should see the result of runTest(20, 100);
+
+// try writing "runTest(1000,10)" in the console
 
 runTest(20, 100);
 

diff --git a/percolation.html b/percolation.html
@@ -1,6 +1,6 @@
 <script type="text/javascript">
-// open this HTML file in the browser, and open the console. 
-// you can use runTest(N, amount) in the console to calculate the average 
+// download and open this HTML file in the browser, and open the console
+// you can use runTest(N, amount) in the console to calculate the average
 // percolation threshold.
 // reasonable arguments are runTest(1000,10)
 

diff --git a/percolation.html b/percolation.html
@@ -0,0 +1,163 @@
+<script type="text/javascript">
+// open this HTML file in the browser, and open the console. 
+// you can use runTest(N, amount) in the console to calculate the average 
+// percolation threshold.
+// reasonable arguments are runTest(1000,10)
+
+runTest(20, 100);
+
+function runTest(N, amount) {
+
+    var t0 = performance.now();
+    console.log("The average is: " + getAverage(N, amount));
+    var t1 = performance.now();
+
+    console.log("Calculating the average took " + (t1 - t0) + " milliseconds.");
+}
+
+function getAverage(N, amount){
+    let openTiles = [];
+
+    for (var i = 0; i < amount; i++) {
+        let perc = new Percolation(N);
+        let count = 0;
+
+        while (!perc.percolates()) {
+            perc.openRandom();
+            count++;
+        }
+
+        openTiles.push(count);
+    }
+
+    var sum = openTiles.reduce(function(a, b) { return a + b; });
+    let averageCount = sum / openTiles.length;
+    let averagePercolationThreshold = averageCount / (N**2);
+
+    return averagePercolationThreshold;
+}
+
+// Percolation system.  Grid begins closed with functions to open sites and check status
+function Percolation(N) {
+    // Constructor
+    var size = N;
+    var uf = new WeightedQuickUnionUF(N * N + 2);
+    var topUF = new WeightedQuickUnionUF(N * N + 2);
+    var opened = [];
+    for (var i = 0; i < N * N; i++) {
+        opened[i] = false;
+    }
+
+    // Helper function to convert 2 digit references to 1 digit
+    function xyTo1D(i, j) {
+        return size * (i - 1) + j;
+    }
+        // Open a site uniformly at random within the grid
+    this.openRandom = function() {
+        // Generate random integers between 1 and N
+        var i = Math.floor(Math.random() * N + 1);
+        var j = Math.floor(Math.random() * N + 1);
+
+        if (this.isOpen(i, j)) {
+            this.openRandom();
+        } else {
+            this.open(i, j);
+            return;
+        }
+    }
+
+    // Open a new site in the grid
+    this.open = function(i, j) {
+        // Mark open in boolean array:
+        opened[xyTo1D(i, j)] = true;
+
+        // Connect with open neighbors:
+        if (i != 1 && this.isOpen(i - 1, j)) {
+            uf.union(xyTo1D(i, j), xyTo1D(i - 1, j));
+            topUF.union(xyTo1D(i, j), xyTo1D(i - 1, j));
+        }
+        if (i != size && this.isOpen(i + 1, j)) {
+            uf.union(xyTo1D(i, j), xyTo1D(i + 1, j));
+            topUF.union(xyTo1D(i, j), xyTo1D(i + 1, j));
+        }
+        if (j != 1 && this.isOpen(i, j - 1)) {
+            uf.union(xyTo1D(i, j), xyTo1D(i, j - 1));
+            topUF.union(xyTo1D(i, j), xyTo1D(i, j - 1));
+        }
+        if (j != size && this.isOpen(i, j + 1)) {
+            uf.union(xyTo1D(i, j), xyTo1D(i, j + 1));
+            topUF.union(xyTo1D(i, j), xyTo1D(i, j + 1));
+        }
+
+        // If in top or bottom row, connect to virtual sites:
+        if (i === 1) {
+            uf.union(xyTo1D(i, j), 0);
+            topUF.union(xyTo1D(i, j), 0);
+        }
+        if (i === size) {
+            // Don't connect topUF.  Prevents backwash problem
+            uf.union(xyTo1D(i, j), size * size + 1);
+        }
+
+
+    }
+
+    this.isOpen = function(i, j) {
+        return opened[xyTo1D(i, j)];
+    }
+
+    // A site is full if a path exists from it to the top
+    this.isFull = function(i, j) {
+        return topUF.connected(xyTo1D(i, j), 0);
+    }
+
+    // System percolates if top and bottom virtual sites are connected
+    this.percolates = function() {
+        return uf.connected(0, size * size + 1);
+        return 0;
+    }
+}
+
+// Union find implementation for efficient checking of percolation
+function WeightedQuickUnionUF(N) {
+
+    // Constructor
+    var id = [];
+    var sz = []; 
+    for (var i = 0; i < N; i++) {
+        id[i] = i; // id[i] = parent of i
+        sz[i] = 1; // sz[i] = number of objects in subtree rooted at i
+    }
+
+    // Returns the number of components, which starts at N
+    this.count = N;
+
+    // Returns the component id for the component containing site
+    this.find = function(p) {
+        while (p != id[p]) {
+            p = id[p];
+        }
+        return p;
+    }
+
+    // Returns true if two elements are part of the same component
+    this.connected = function(p, q) {
+        return this.find(p) === this.find(q);
+    }
+
+    // Connects the components of two elements
+    this.union = function(p, q) {
+        var rootP = this.find(p);
+        var rootQ = this.find(q);
+        if (rootP === rootQ) { return; }
+
+        // make smaller root point to large one
+        if (sz[rootP] < sz[rootQ]) {
+            id[rootP] = rootQ; sz[rootQ] += sz[rootP];
+        } else {
+            id[rootQ] = rootP; sz[rootP] += sz[rootQ];
+        }
+        this.count--;
+    }
+}
+</script>
No results found