Percolation - Princeton Algorithm 4th


http://coursera.cs.princeton.edu/algs4/assignments/percolation.html
The model. We model 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. We say 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. (For the insulating/metallic materials example, the open sites correspond to metallic materials, so that a system that percolates has a metallic path from top to bottom, with full sites conducting. For the porous substance example, the open sites correspond to empty space through which water might flow, so that a system that percolates lets water fill open sites, flowing from top to bottom.)

Percolates
The problem. In a famous scientific problem, researchers are interested in the following question: if sites are independently set to be open with probability p (and therefore blocked with probability 1 − p), what is the probability that the system percolates? When p equals 0, the system does not percolate; when p equals 1, the system percolates. The plots below show the site vacancy probability p versus the percolation probability for 20-by-20 random grid (left) and 100-by-100 random grid (right).

Percolation threshold for 20-by-20 grid                Percolation threshold for 100-by-100 grid          
When N is sufficiently large, there is a threshold value p* such that when p < p* a random N-by-N grid almost never percolates, and when p > p*, a random N-by-N grid almost always percolates. No mathematical solution for determining the percolation threshold p* has yet been derived. Your task is to write a computer program to estimate p*.
Percolation data type. To model a percolation system, create a data type Percolation with the following API:
public class Percolation {
   public Percolation(int N)               // create N-by-N grid, with all sites blocked
   public void open(int i, int j)          // open site (row i, column j) if it is not open already
   public boolean isOpen(int i, int j)     // is site (row i, column j) open?
   public boolean isFull(int i, int j)     // is site (row i, column j) full?
   public boolean percolates()             // does the system percolate?

   public static void main(String[] args)  // test client (optional)
}
Corner cases.  By convention, the row and column indices i and j are integers between 1 and N, where (1, 1) is the upper-left site: Throw a java.lang.IndexOutOfBoundsException if any argument to open(), isOpen(), or isFull() is outside its prescribed range. The constructor should throw a java.lang.IllegalArgumentException if N ≤ 0.
Performance requirements.  The constructor should take time proportional to N2; all methods should take constant time plus a constant number of calls to the union-find methods union(), find(), connected(), andcount().
Monte Carlo simulation. To estimate the percolation threshold, consider the following computational experiment:

  • Initialize all sites to be blocked.
  • Repeat the following until the system percolates:

    • Choose a site (row i, column j) uniformly at random among all blocked sites.
    • Open the site (row i, column j).
  • The fraction of sites that are opened when the system percolates provides an estimate of the percolation threshold.

For example, if sites are opened in a 20-by-20 lattice according to the snapshots below, then our estimate of the percolation threshold is 204/400 = 0.51 because the system percolates when the 204th site is opened.
By repeating this computation experiment T times and averaging the results, we obtain a more accurate estimate of the percolation threshold. Let xt be the fraction of open sites in computational experiment t. The sample mean μ provides an estimate of the percolation threshold; the sample standard deviation σ measures the sharpness of the threshold.

Estimating the sample mean and variance
Assuming T is sufficiently large (say, at least 30), the following provides a 95% confidence interval for the percolation threshold:

95% confidence interval for percolation threshold
To perform a series of computational experiments, create a data type PercolationStats with the following API.

public class PercolationStats {
   public PercolationStats(int N, int T)     // perform T independent experiments on an N-by-N grid
   public double mean()                      // sample mean of percolation threshold
   public double stddev()                    // sample standard deviation of percolation threshold
   public double confidenceLo()              // low  endpoint of 95% confidence interval
   public double confidenceHi()              // high endpoint of 95% confidence interval

   public static void main(String[] args)    // test client (described below)
}

Now, implement the Percolation data type using the weighted quick union algorithm in WeightedQuickUnionUF. Answer the questions in the previous paragraph.
https://www.cnblogs.com/evasean/p/7204501.html
题目来源http://coursera.cs.princeton.edu/algs4/assignments/percolation.html
作业分为两部分：建立模型和仿真实验。
最关键的部分就是建立模型对象。模型对象要求如下：
The model.  We model 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. We say 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. (For the insulating/metallic materials example, the open sites correspond to metallic materials, so that a system that percolates has a metallic path from top to bottom, with full sites conducting. For the porous substance example, the open sites correspond to empty space through which water might flow, so that a system that percolates lets water fill open sites, flowing from top to bottom.)
 
边界要求：  By convention, the row and column indices are integers between 1 and n, where (1, 1) is the upper-left site: Throw a java.lang.IllegalArgumentException if any argument to open(), isOpen(), or isFull() is outside its prescribed range. The constructor should throw a java.lang.IllegalArgumentException if n ≤ 0.
 
性能要求：  The constructor should take time proportional to n2; all methods should take constant time plus a constant number of calls to the union–find methods union(), find(), connected(), and count().
我的分析
本次作业根据教授在视频课上提示，可以在grid的上方和下方各加入一个虚节点，grid第一行的open节点都与top虚节点连通，grid最后一行的open节点都与bottom虚节点连通。这样只需判断top虚节点与bottom虚节点是否连通就知道grid是否渗透，而不需要去一一选取特定节点比对了。照着这个思路，我实现了下述模型代码。值得注意的是，模型代码的main中测试方法不是仅仅进行各本地测试就可以了，提交作业的时候会进行自动脚本测试，所以提交的版本main方法中必须读取args[0]中的文件名，并加载文件内容进行生成grid和open对应的site。
复制代码
  1 import edu.princeton.cs.algs4.In;
  2 import edu.princeton.cs.algs4.StdOut;
  3 import edu.princeton.cs.algs4.WeightedQuickUnionUF;
  4 /**
  5  * @author evasean www.cnblogs.com/evasean/
  6  */
  7 public class Percolation {
  8     private static final boolean BLOCK = false; // block state
  9     private static final boolean OPEN = true; // open state
 10 
 11     /* topUF bottomUF n 均为final是因为它们只在构造函数时初始化，后续其值未发生变化 */
 12     private final WeightedQuickUnionUF topUF; // 用来记录与top虚节点的连通性
 13     private final WeightedQuickUnionUF bottomUF;// 用来记录与bottom虚节点的连通性
 14     private final int n;
 15 
 16     private boolean[][] grid;
 17     private boolean percolateFlag = false; // grid是否渗透的标志
 18     private int openedNum = 0;// 已经open的site数目
 19 
 20     public Percolation(int n) {
 21         // create n-by-n grid, with all sites blocked
 22         if (n < 1)
 23             throw new IllegalArgumentException("grid size should be bigger than one !");
 24         this.n = n;
 25         topUF = new WeightedQuickUnionUF(n * n + 1); // 多了一个节点的空间，位置n*n处用来代表虚节点
 26         bottomUF = new WeightedQuickUnionUF(n * n + 1); // 多了一个节点的空间，位置n*n处用来代表虚节点
 27         grid = new boolean[n][n];
 28         // 初始化grid设为block
 29         for (int i = 0; i < n; i++)
 30             for (int j = 0; j < n; j++)
 31                 grid[i][j] = BLOCK;
 32     }
 33 
 34     private void validate(int row, int col) {
 35         if (row < 1 || col < 1 || row > n || col > n)
 36             throw new IllegalArgumentException("input row or col is not illegal!");
 37     }
 38 
 39     public void open(int row, int col) {
 40         // open site (row, col) if it is not open already
 41         validate(row, col);
 42         if (grid[row - 1][col - 1] == OPEN)
 43             return;
 44 
 45         grid[row - 1][col - 1] = OPEN;
 46         openedNum++;
 47 
 48         // n为1时，open一个节点就达到渗透要求
 49         if (n == 1) {
 50             topUF.union(0, 1);
 51             bottomUF.union(0, 1);
 52             percolateFlag = true;
 53             return;
 54         }
 55 
 56         // 第一行的所有节点都与top虚节点连通
 57         if (row == 1)
 58             topUF.union(n * n, col - 1);
 59 
 60         // 最后一行的所有节点都与bottom虚节点连通
 61         if (row == n)
 62             bottomUF.union(n * n, (n - 1) * n + col - 1);
 63 
 64         // 与上方节点的连通性
 65         if (row > 1 && grid[row - 2][col - 1] == OPEN) {
 66             topUF.union((row - 2) * n + col - 1, (row - 1) * n + col - 1);
 67             bottomUF.union((row - 2) * n + col - 1, (row - 1) * n + col - 1);
 68         }
 69 
 70         // 与下方节点的连通性
 71         if (row < n && grid[row][col - 1] == OPEN) {
 72             topUF.union(row * n + col - 1, (row - 1) * n + col - 1);
 73             bottomUF.union(row * n + col - 1, (row - 1) * n + col - 1);
 74         }
 75 
 76         // 与左侧节点的连通性
 77         if (col > 1 && grid[row - 1][col - 2] == OPEN) {
 78             topUF.union((row - 1) * n + col - 2, (row - 1) * n + col - 1);
 79             bottomUF.union((row - 1) * n + col - 2, (row - 1) * n + col - 1);
 80         }
 81 
 82         // 与右侧节点的连通性
 83         if (col < n && grid[row - 1][col] == OPEN) {
 84             topUF.union((row - 1) * n + col, (row - 1) * n + col - 1);
 85             bottomUF.union((row - 1) * n + col, (row - 1) * n + col - 1);
 86         }
 87 
 88         /*
 89          * 判断条件!percolateFlag是为了防止渗透以后的重复判断 判断条件openedNum>=n
 90          * 是因为openedNum达到n时才有可能渗透，在未达到n之前，不需要进行后续判断
 91          * 一个节点open的时候刚好使grid渗透的条件是该节点同时与top虚节点和bottom虚节点连通
 92          */
 93         if (!percolateFlag && openedNum >= n && topUF.connected(n * n, (row - 1) * n + col - 1)
 94                 && bottomUF.connected(n * n, (row - 1) * n + col - 1))
 95             percolateFlag = true;
 96 
 97     }
 98 
 99     public boolean isOpen(int row, int col) {
100         // is site (row, col) open?
101         validate(row, col);
102         return grid[row - 1][col - 1] == OPEN;
103     }
104 
105     /**
106      * 一个节点只有同时在open状态并且与top虚节点连通时才是full状态
107      * @param row
108      * @param col
109      * @return
110      */
111     public boolean isFull(int row, int col) {
112         // is site (row, col) full?
113         validate(row, col);
114         if (isOpen(row, col) && topUF.connected(n * n, (row - 1) * n + col - 1))
115             return true;
116         else
117             return false;
118     }
119 
120     public int numberOfOpenSites() {
121         // number of open sites
122         return openedNum;
123     }
124 
125     public boolean percolates() {
126         // does the system percolate?
127         return percolateFlag;
128     }
129 
130     //打印一些便于查看的信息
131     private void printCheckResult(int row, int col) {
132         StdOut.println("p(" + row + "," + col + ") is open=" + isOpen(row, col) + ";is full=" + isFull(row, col)
133                 + ";percolates=" + percolates());
134     }
135 
136     /**
137      * 作业提交时main需要调用该方法，因为提交后在线脚本要用一堆input文件进行测试
138      * 
139      * @param arg0
140      */
141     private static void fileInputCheck(String arg0) {
142         // test client (optional)
143         In in = new In(arg0);//读入input文件名，并加载文件内容
144         String s = null;
145         int n = -1;
146         //读入grid的n
147         while (in.hasNextLine()) {
148             s = in.readLine();
149             if (s != null && !s.trim().equals(""))
150                 break;
151         }
152         s = s.trim();
153         n = Integer.parseInt(s);
154         Percolation p = new Percolation(n);
155         
156         //读入open的site坐标
157         while (in.hasNextLine()) {
158             s = in.readLine();
159             if (s != null && !s.trim().equals("")) {
160                 s = s.trim();//去掉输入字符串头尾空格
161                 String[] sa = s.split("\\s+");//去掉中间所有空格
162                 if (sa.length != 2)
163                     break;
164                 int row = Integer.parseInt(sa[0]);
165                 int col = Integer.parseInt(sa[1]);
166                 p.open(row, col);
167             }
168         }
169 
170     }
171 
172     /**
173      * 本地测试专用
174      */
175     private static void generateCheck() {
176         // test client (optional)
177         Percolation p = new Percolation(3);
178         int row = 1, col = 3;
179         p.open(row, col);
180         p.printCheckResult(row, col);
181         row = 2;
182         col = 3;
183         p.open(row, col);
184         p.printCheckResult(row, col);
185         row = 3;
186         col = 3;
187         p.open(row, col);
188         p.printCheckResult(row, col);
189         row = 3;
190         col = 1;
191         p.open(row, col);
192         p.printCheckResult(row, col);
193         row = 2;
194         col = 1;
195         p.open(row, col);
196         p.printCheckResult(row, col);
197         row = 1;
198         col = 1;
199         p.open(row, col);
200         p.printCheckResult(row, col);
201     }
202 
203     public static void main(String[] args) {
204         //generateCheck();
205         fileInputCheck(args[0]);
206     }
207 }
复制代码

仿真分析这一部分比较简单，其中需要注意的地方就是“随机选取row和col进行open”，如果简单的用random(int n)，选取[0,n)获取row和col，会有很多重复节点被选中，随着n越大，命中率就越低。于是我采用生成一个[0,n*n)的数组，数组内容随机排序，依次读取数组内容，就相当于随机取site。
复制代码
 1 import edu.princeton.cs.algs4.StdOut;
 2 import edu.princeton.cs.algs4.StdRandom;
 3 import edu.princeton.cs.algs4.StdStats;
 4 /**
 5  * @author evasean www.cnblogs.com/evasean/
 6  */
 7 public class PercolationStats {
 8     /* t fractions 均为final是因为它们只在构造函数时初始化，后续其值未发生变化*/
 9     private final int t;//尝试次数
10     private final double[] fractions;//每一次尝试的渗透率得分
11     
12     private double mean;
13     private double stddev;
14 
15     public PercolationStats(int n, int trials) {
16         // perform trials independent experiments on an n-by-n grid
17         if (n <= 0 || trials <= 0)
18             throw new IllegalArgumentException("n ≤ 0 or trials ≤ 0");
19         t = trials;
20         fractions = new double[t];
21         for (int i = 0; i < t; i++) {//t次尝试
22             Percolation p = new Percolation(n);
23             int openNum = 0;
24              //为了实现随机open一个site，模仿QuickUnion的定位方法
25             //先生成一个[0,n*n)的数组，数组内容随机排序,依次读取数组内容，就相当于随机取site
26             int[] rand = StdRandom.permutation(n * n);
27             for (int pos : rand) {
28                 //pos = (row-1)*n + col -1
29                 int row = pos / n + 1; 
30                 int col = pos % n + 1;
31                 p.open(row, col);
32                 openNum++;
33                 //只有openNum>=n时才有判断是否渗透的必要
34                 if (openNum >= n && p.percolates())
35                     break;
36             }
37             double pt = (double) openNum / (n * n);//单次尝试的渗透率
38             fractions[i] = pt;
39         }
40         /* 作业提交时的某个测试案例要求mean()、stddev()、confidenceLo()、confidenceHi()
41          * 在任何时候任何次序调用的情况下都必须返回相同的值，故需要在构造函数中计算mean和stddev
42          */
43         //作业提交时的某个测试案例要调用一次StdStats.mean方法
44         mean = StdStats.mean(fractions);
45         //作业提交时的某个测试案例要求要调用一次StdStats.stddev方法
46         stddev = StdStats.stddev(fractions);
47     }
48 
49     public double mean() {
50         // sample mean of percolation threshold
51         return mean;
52     }
53 
54     public double stddev() {
55         // sample standard deviation of percolation threshold
56         return stddev;
57     }
58 
59     public double confidenceLo() {
60         // low endpoint of 95% confidence interval
61         return mean - 1.96 * stddev / Math.sqrt(t);
62     }
63 
64     public double confidenceHi() {
65         // high endpoint of 95% confidence interval
66         return mean + 1.96 * stddev / Math.sqrt(t);
67     }
68 
69     public static void main(String[] args) {
70         // test client (described below)
71         int n = Integer.parseInt(args[0]);
72         int t = Integer.parseInt(args[1]);
73         PercolationStats ps = new PercolationStats(n, t);
74         StdOut.printf("%-25s %s %f \n", "means", "=", ps.mean());
75         StdOut.printf("%-25s %s %f \n", "stddev", "=", ps.stddev());
76         StdOut.printf("%-25s %s%f%s%f%s\n", "95% confidence interval", "= [", ps.confidenceLo(), ", ",
77                 ps.confidenceHi(), "]");
78     }
http://www.jyuan92.com/blog/coursera-algorithmprinceton-hw1-percolation/
1) 首先，题目要求通过Weighted Quick Union Union Find来判断两个结点是否Union，而对于每个单独的结点是否open，我们通过isOpen来判断，新建一个boolean matrix[][]数组，来存储当前的结点是否open
2) 根据vedio中所说的，要判断是否连通，可以新建两个虚拟结点，一个top，一个bottom，top连接matrix第一行的所有节点，bottom连接matrix[][]的最后一行结点，这样最后只需要判断top和bottom是否连通，即可以判断是否percolation
Problem: 在这种情况下，会出现backwash的情况，对于一些与bottom连通的结点，即便其于top不连通，但是因为bottom和top连通了，最终会导致这些结点也是full的，与题意不相符

Improvement
1） 采用两个Weighted Quick Union Union Find来解决此问题

– 第一个WQUUF只负责维护top结点
– 第二个WQUUF负责维护top和bottom结点
所以，当当判断isFull, 即此结点是否与top连通时，采用第一个WQUUF；判断是否percolation，即top和bottom是否连通时，采用第二个WQUUF，这样很好的解决了backwash的问题，当然也牺牲了空间。
https://github.com/vgoodvin/princeton-algs4/blob/master/Percolation/Percolation.java
public class Percolation {

    private boolean[][] opened;
    private int top = 0;
    private int bottom;
    private int size;
    private WeightedQuickUnionUF qf;

    /**
     * Creates N-by-N grid, with all sites blocked.
     */
    public Percolation(int N) {
        size = N;
        bottom = size * size + 1;
        qf = new WeightedQuickUnionUF(size * size + 2);
        opened = new boolean[size][size];
    }

    /**
     * Opens site (row i, column j) if it is not already.
     */
    public void open(int i, int j) {
        opened[i - 1][j - 1] = true;
        if (i == 1) {
            qf.union(getQFIndex(i, j), top);
        }
        if (i == size) {
            qf.union(getQFIndex(i, j), bottom);
        }

        if (j > 1 && isOpen(i, j - 1)) {
            qf.union(getQFIndex(i, j), getQFIndex(i, j - 1));
        }
        if (j < size && isOpen(i, j + 1)) {
            qf.union(getQFIndex(i, j), getQFIndex(i, j + 1));
        }
        if (i > 1 && isOpen(i - 1, j)) {
            qf.union(getQFIndex(i, j), getQFIndex(i - 1, j));
        }
        if (i < size && isOpen(i + 1, j)) {
            qf.union(getQFIndex(i, j), getQFIndex(i + 1, j));
        }
    }

    /**
     * Is site (row i, column j) open?
     */
    public boolean isOpen(int i, int j) {
        return opened[i - 1][j - 1];
    }

    /**
     * Is site (row i, column j) full?
     */
    public boolean isFull(int i, int j) {
        if (0 < i && i <= size && 0 < j && j <= size) {
            return qf.connected(top, getQFIndex(i , j));
        } else {
            throw new IndexOutOfBoundsException();
        }
    }

    /**
     * Does the system percolate?
     */
    public boolean percolates() {
        return qf.connected(top, bottom);
    }

    private int getQFIndex(int i, int j) {
        return size * (i - 1) + j;
    }
}
https://github.com/vgoodvin/princeton-algs4/blob/master/Percolation/PercolationStats.java
public class PercolationStats {

    private int experimentsCount;
    private Percolation pr;
    private double[] fractions;

    /**
     * Performs T independent computational experiments on an N-by-N grid.
     */
    public PercolationStats(int N, int T) {
        if (N <= 0 || T <= 0) {
            throw new IllegalArgumentException("Given N <= 0 || T <= 0");
        }
        experimentsCount = T;
        fractions = new double[experimentsCount];
        for (int expNum = 0; expNum < experimentsCount; expNum++) {
            pr = new Percolation(N);
            int openedSites = 0;
            while (!pr.percolates()) {
                int i = StdRandom.uniform(1, N + 1);
                int j = StdRandom.uniform(1, N + 1);
                if (!pr.isOpen(i, j)) {
                    pr.open(i, j);
                    openedSites++;
                }
            }
            double fraction = (double) openedSites / (N * N);
            fractions[expNum] = fraction;
        }
    }

    /**
     * Sample mean of percolation threshold.
     */
    public double mean() {
        return StdStats.mean(fractions);
    }

    /**
     * Sample standard deviation of percolation threshold.
     */
    public double stddev() {
        return StdStats.stddev(fractions);
    }

    /**
     * Returns lower bound of the 95% confidence interval.
     */
    public double confidenceLo() {
        return mean() - ((1.96 * stddev()) / Math.sqrt(experimentsCount));
    }

    /**
     * Returns upper bound of the 95% confidence interval.
     */
    public double confidenceHi() {
        return mean() + ((1.96 * stddev()) / Math.sqrt(experimentsCount));
    }

    public static void main(String[] args) {
        int N = Integer.parseInt(args[0]);
        int T = Integer.parseInt(args[1]);
        PercolationStats ps = new PercolationStats(N, T);

        String confidence = ps.confidenceLo() + ", " + ps.confidenceHi();
        StdOut.println("mean                    = " + ps.mean());
        StdOut.println("stddev                  = " + ps.stddev());
        StdOut.println("95% confidence interval = " + confidence);
    }
}
https://segmentfault.com/a/1190000005345079
  1. 既没有复杂的语法使用（仅数组操作），又着实比在基础语言层面上升了一个档次；
  2. 漂亮的visualizer动画效果激励着初学者完成任务；
  3. 强大的autograder功能初次展现，评价算法的主要管道一目了然，每一微秒每一字节都很重要；
  4. 针对学习迅速的同学还隐含了一个很大的挑战：在仅使用一个WeightedQuickUnionUF对象的前提下，解决backwash问题
下面主要聊聊backwash：

问题的核心源自virtual top/bottom，一个强行被导师在课程视频中提到的优化方法，于是天真的同学们（我）就去开心地实现这个看似无辜而又性能楚楚动人的方法，却毫不了解导师在下一节中马上提出的backwash问题是何物，还觉得这种低级错误怎么可能会发生：
I thought that the solution I coded last weekend was fine because it was correctly computing the percolation thresholds for many different grid sizes. 
However, when I tested it today using the provided PercolationVisualizer class, I realized that it was suffering from the "backwash" problem.
It took me a couple of hours but, in the end, I managed to fix it by using two WeightedQuickUnionUF objects instead of one.
1) The easiest way to tackle this problem is to use two different Weighted Quick Union Union Find objects. The only difference between them is that one has only top virtual site (let’s call it uf_A), the other is the normal object with two virtual sites top one and the bottom one (let’s call it uf_B) suggested in the course, uf_A has no backwash problem because we “block” the bottom virtual site by removing it. uf_B is for the purpose to efficiently determine if the system percolates or not as described in the course. So every time we open a site (i, j) by calling Open(i, j), within this method, we need to do  union() twice: uf_A.union() and uf_B.union(). Obviously the bad point of the method is that: semantically we are saving twice the same information which doesn’t seem like a good pattern indeed. The good aspect might be it is the most straightforward and natural approach for people to think of.
public class Percolation {
    
    private WeightedQuickUnionUF grid, auxGrid;
    private boolean[]   state;
    private int     N;

    // create N-by-N grid, with all sites blocked
    public Percolation(int N) {

        int siteCount = N * N;
        this.N = N;

        // index 0 and N^2+1 are reserved for virtual top and bottom sites
        grid    = new WeightedQuickUnionUF(siteCount + 2);
        auxGrid = new WeightedQuickUnionUF(siteCount + 1);
        state   = new boolean[siteCount + 2];

        // Initialize all sites to be blocked.
        for (int i = 1; i <= siteCount; i++)
            state[i] = false;
        // Initialize virtual top and bottom site with open state
        state[0] = true;
        state[siteCount+1] = true;
    }

    // return array index of given row i and column j
    private int xyToIndex(int i, int j) {
        // Attention: i and j are of range 1 ~ N, NOT 0 ~ N-1.
        // Throw IndexOutOfBoundsException if i or j is not valid
        if (i <= 0 || i > N) 
            throw new IndexOutOfBoundsException("row i out of bound");
        if (j <= 0 || j > N) 
            throw new IndexOutOfBoundsException("column j out of bound");

        return (i - 1) * N + j;
    }

    private boolean isTopSite(int index) {
        return index <= N;
    }

    private boolean isBottomSite(int index) {
        return index >= (N - 1) * N + 1;
    }

    // open site (row i, column j) if it is not already
    public void open(int i, int j) {
        // All input sites are blocked at first. 
        // Check the state of site before invoking this method.
        int idx = xyToIndex(i, j);
        state[idx] = true;

        // Traverse surrounding sites, connect all open ones. 
        // Make sure we do not index sites out of bounds.
        if (i != 1 && isOpen(i-1, j)) {
            grid.union(idx, xyToIndex(i-1, j));
            auxGrid.union(idx, xyToIndex(i-1, j));
        }
        if (i != N && isOpen(i+1, j)) {
            grid.union(idx, xyToIndex(i+1, j));
            auxGrid.union(idx, xyToIndex(i+1, j));
        }
        if (j != 1 && isOpen(i, j-1)) {
            grid.union(idx, xyToIndex(i, j-1));
            auxGrid.union(idx, xyToIndex(i, j-1));
        }
        if (j != N && isOpen(i, j+1)) {
            grid.union(idx, xyToIndex(i, j+1));
            auxGrid.union(idx, xyToIndex(i, j+1));
        }
        // if site is on top or bottom, connect to corresponding virtual site.
        if (isTopSite(idx)) {
            grid.union(0, idx);
            auxGrid.union(0, idx);
        }
        if (isBottomSite(idx))  grid.union(state.length-1, idx);
    }

    // is site (row i, column j) open?
    public boolean isOpen(int i, int j) {
        int idx = xyToIndex(i, j);
        return state[idx];
    }

    // is site (row i, column j) full?
    public boolean isFull(int i, int j) {
        // Check if this site is connected to virtual top site
        int idx = xyToIndex(i, j);
        return grid.connected(0, idx) && auxGrid.connected(0, idx);
    }

    // does the system percolate?
    public boolean percolates() {
        // Check whether virtual top and bottom sites are connected
        return grid.connected(0, state.length-1);
    }
}

A final remark: one key observation here is that to test a site is full or not, we only need to know the status of the root of that connected component containing the site, whether a site is full is the same question interpreted by asking whether the connected component is full or not: this make things simple and saves time, someone in the forum proposed to linear scan the whole connected component to update the status of each site which is not necessary and inefficient. each time we only update the status of the root site rather than each site in that component.
2) And there turned out to be more elegant solutions without using 2 WQUUF if we can modify the API or we just wrote our own UF algorithm from scratch. The solution is from “Bobs Notes 1: Union-Find and Percolation (Version 2)“:  Store two bits with each component root. One of these bits is true if the component contains a cell in the top row. The other bit is true if the component contains a cell in the bottom row. Updating the bits after a union takes constant time. Percolation occurs when the component containing a newly opened cell has both bits true, after the unions that result from the cell becoming open. Excellent! However, this one involves the modification of the original API. Based on this and some other discussion from other threads in the discussion forum, I have come up with the following approach which need not to modify the given API but adopt similar idea by associating each connected component root with the information of connection to top and/or bottom sites.
(3) Here we go for the approach based on Bob’s notes while involving no modification of the original given API:
In the original Bob’s notes, it says we have to modify the API to achieve this, but actually it does not have to be like that. We create ONE WQUUF object of size N * N, and allocate a separate array of size N * N to keep the status of each site: blocked, open, connect to top, connect to bottom. I use bit operation for the status so for each site, it could have combined status like Open and connect to top.
The most important operation is open(int i, int j): we need to union the newly opened site (let’s call it site ‘S’) S with the four adjacent neighbor sites if possible. For each possible neighbor site(Let’s call it ‘neighbor’), we first call find(neighbor) to get the root of that connected component, and retrieves the status of that root (Let’s call it ‘status’), next, we do Union(S, neighbor); we do the similar operation for at most 4 times, and we do a 5th find(S) to get the root of the newly (copyright @sigmainfy) generated connected component results from opening the site S, finally we update the status of the new root by combining the old status information into the new root in constant time. I leave the details of how to combine the information to update the the status of the new root to the readers, which would not be hard to think of.
For the isFull(int i, int j), we need to find the the root site in the connected component which contains site (i, j) and check the status of the root.
For the isOpen(int i, int j) we directly return the status.
For percolates(), there is a way to make it constant time even though we do not have virtual top or bottom sites: think about why?
So the most important operation  open(int i, int j) will involve 4 union() and 5 find() API calls.
   这道题看起来难度不大，但是实际上做的时候还是需要想一想的。首先的问题就是，这是一个蓄水问题，而不是图连接问题，如何将蓄水问题转换为图连接问题呢？我的方法是这样的：
（1）Open一个Site
（2）分别检查Open的这个Site的上下左右是不是也有Open的Site
        如果有，那么将这两个Open的Site链接起来
   这样一来，题目就简单多了。

   第二个问题是，如何用提供的API，模拟一个N*N的蓄水池呢？方法肯定是坐标转换，我的方法是将每个i,j的Site表示为一维数组中的i*N+j，那么这个N*N的蓄水池起始点为1*N+1，终止点为N*N+N。先把0*N+1到0*N+N以及（N+1）*N+1到（N*1）*N+N链接起来，这样的好处就是：我们检查是否percolates的条件就是看0*N+1,(N+1)*N+1这两个点是否Connected就行了。如果不这么做，我们需要循环检查所有0*N+1到0*N+N以及（N+1）*N+1到（N*1）*N+N是否Connected。

   这道题看起来难度不大，但是实际上做的时候还是需要想一想的。首先的问题就是，这是一个蓄水问题，而不是图连接问题，如何将蓄水问题转换为图连接问题呢？我的方法是这样的：
（1）Open一个Site
（2）分别检查Open的这个Site的上下左右是不是也有Open的Site
        如果有，那么将这两个Open的Site链接起来
   这样一来，题目就简单多了。

   第二个问题是，如何用提供的API，模拟一个N*N的蓄水池呢？方法肯定是坐标转换，我的方法是将每个i,j的Site表示为一维数组中的i*N+j，那么这个N*N的蓄水池起始点为1*N+1，终止点为N*N+N。先把0*N+1到0*N+N以及（N+1）*N+1到（N*1）*N+N链接起来，这样的好处就是：我们检查是否percolates的条件就是看0*N+1,(N+1)*N+1这两个点是否Connected就行了。如果不这么做，我们需要循环检查所有0*N+1到0*N+N以及（N+1）*N+1到（N*1）*N+N是否Connected。
public class Percolation { private WeightedQuickUnionUF uf; private WeightedQuickUnionUF uf_backwash; private int N; private boolean[] arrayOpen; // create N-by-N grid, with all sites blocked public Percolation(int N){ this.N = N; uf = new WeightedQuickUnionUF((N+1)*(N)+N+1); uf_backwash = new WeightedQuickUnionUF(N*N+N+1); arrayOpen = new boolean[(N+1)*(N)+N+1]; for (int i=1; i<=N; i++){ uf.union(0*N+1, 0*N+i); uf_backwash.union(0*N+1, 0*N+i); arrayOpen[0*N+i] = true; uf.union((N+1)*N+1, (N+1)*N+i); arrayOpen[(N+1)*N+i] = true; } } // open site (row i, column j) if it is not already public void open(int i, int j){ if (i < 1 || i > N){ throw new IndexOutOfBoundsException("row index " + i + " out of bounds"); } if (j < 1 || j > N){ throw new IndexOutOfBoundsException("row index " + j + " out of bounds"); } if (arrayOpen[i*N+j]){ return; } arrayOpen[i*N+j] = true; if (arrayOpen[(i-1)*N+j]){ uf.union(i*N+j, (i-1)*N+j); uf_backwash.union(i*N+j, (i-1)*N+j); } if (arrayOpen[(i+1)*N+j]){ uf.union(i*N+j, (i+1)*N+j); if (i!=N){ uf_backwash.union(i*N+j, (i+1)*N+j); } } if (j!=1 && arrayOpen[i*N+j-1]){ uf.union(i*N+j, i*N+j-1); uf_backwash.union(i*N+j, i*N+j-1); } if (j!=N && arrayOpen[i*N+j+1]){ uf.union(i*N+j, i*N+j+1); uf_backwash.union(i*N+j, i*N+j+1); } } // is site (row i, column j) open? public boolean isOpen(int i, int j){ if (i <1 || i > N){ throw new IndexOutOfBoundsException("row index " + i + " out of bounds"); } if (j < 1 || j > N){ throw new IndexOutOfBoundsException("row index " + j + " out of bounds"); } return arrayOpen[i*N+j]; } // is site (row i, column j) full? public boolean isFull(int i, int j){ if (i <1 || i > N){ throw new IndexOutOfBoundsException("row index " + i + " out of bounds"); } if (j < 1 || j > N){ throw new IndexOutOfBoundsException("row index " + j + " out of bounds"); } return uf_backwash.connected(i*N+j, 0*N+1) && arrayOpen[i*N+j]; } // does the system percolate? public boolean percolates(){ return uf.connected(0*N+1, (N+1)*N+1); } }


at
Labels: , ,

Labels

LeetCode (1432) GeeksforGeeks (1122) LeetCode - Review (1067) Review (882) Algorithm (668) to-do (609) Classic Algorithm (270) Google Interview (237) Classic Interview (222) Dynamic Programming (220) DP (186) Bit Algorithms (145) POJ (141) Math (137) Tree (132) LeetCode - Phone (129) EPI (122) Cracking Coding Interview (119) DFS (115) Difficult Algorithm (115) Lintcode (115) Different Solutions (110) Smart Algorithm (104) Binary Search (96) BFS (91) HackerRank (90) Binary Tree (86) Hard (79) Two Pointers (78) Stack (76) Company-Facebook (75) BST (72) Graph Algorithm (72) Time Complexity (69) Greedy Algorithm (68) Interval (63) Company - Google (62) Geometry Algorithm (61) Interview Corner (61) LeetCode - Extended (61) Union-Find (60) Trie (58) Advanced Data Structure (56) List (56) Priority Queue (53) Codility (52) ComProGuide (50) LeetCode Hard (50) Matrix (50) Bisection (48) Segment Tree (48) Sliding Window (48) USACO (46) Space Optimization (45) Company-Airbnb (41) Greedy (41) Mathematical Algorithm (41) Tree - Post-Order (41) ACM-ICPC (40) Algorithm Interview (40) Data Structure Design (40) Graph (40) Backtracking (39) Data Structure (39) Jobdu (39) Random (39) Codeforces (38) Knapsack (38) LeetCode - DP (38) Recursive Algorithm (38) String Algorithm (38) TopCoder (38) Sort (37) Introduction to Algorithms (36) Pre-Sort (36) Beauty of Programming (35) Must Known (34) Binary Search Tree (33) Follow Up (33) prismoskills (33) Palindrome (32) Permutation (31) Array (30) Google Code Jam (30) HDU (30) Array O(N) (29) Logic Thinking (29) Monotonic Stack (29) Puzzles (29) Code - Detail (27) Company-Zenefits (27) Microsoft 100 - July (27) Queue (27) Binary Indexed Trees (26) TreeMap (26) to-do-must (26) 1point3acres (25) GeeksQuiz (25) Merge Sort (25) Reverse Thinking (25) hihocoder (25) Company - LinkedIn (24) Hash (24) High Frequency (24) Summary (24) Divide and Conquer (23) Proof (23) Game Theory (22) Topological Sort (22) Lintcode - Review (21) Tree - Modification (21) Algorithm Game (20) CareerCup (20) Company - Twitter (20) DFS + Review (20) DP - Relation (20) Brain Teaser (19) DP - Tree (19) Left and Right Array (19) O(N) (19) Sweep Line (19) UVA (19) DP - Bit Masking (18) LeetCode - Thinking (18) KMP (17) LeetCode - TODO (17) Probabilities (17) Simulation (17) String Search (17) Codercareer (16) Company-Uber (16) Iterator (16) Number (16) O(1) Space (16) Shortest Path (16) itint5 (16) DFS+Cache (15) Dijkstra (15) Euclidean GCD (15) Heap (15) LeetCode - Hard (15) Majority (15) Number Theory (15) Rolling Hash (15) Tree Traversal (15) Brute Force (14) Bucket Sort (14) DP - Knapsack (14) DP - Probability (14) Difficult (14) Fast Power Algorithm (14) Pattern (14) Prefix Sum (14) TreeSet (14) Algorithm Videos (13) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Combination (13) Computational Geometry (13) DP - Digit (13) LCA (13) LeetCode - DFS (13) Linked List (13) Long Increasing Sequence(LIS) (13) Math-Divisible (13) Reservoir Sampling (13) mitbbs (13) Algorithm - How To (12) Company - Microsoft (12) DP - Interval (12) DP - Multiple Relation (12) DP - Relation Optimization (12) LeetCode - Classic (12) Level Order Traversal (12) Prime (12) Pruning (12) Reconstruct Tree (12) Thinking (12) X Sum (12) AOJ (11) Bit Mask (11) Company-Snapchat (11) DP - Space Optimization (11) Dequeue (11) Graph DFS (11) MinMax (11) Miscs (11) Princeton (11) Quick Sort (11) Stack - Tree (11) 尺取法 (11) 挑战程序设计竞赛 (11) Coin Change (10) DFS+Backtracking (10) Facebook Hacker Cup (10) Fast Slow Pointers (10) HackerRank Easy (10) Interval Tree (10) Limited Range (10) Matrix - Traverse (10) Monotone Queue (10) SPOJ (10) Starting Point (10) States (10) Stock (10) Theory (10) Tutorialhorizon (10) Kadane - Extended (9) Mathblog (9) Max-Min Flow (9) Maze (9) Median (9) O(32N) (9) Quick Select (9) Stack Overflow (9) System Design (9) Tree - Conversion (9) Use XOR (9) Book Notes (8) Company-Amazon (8) DFS+BFS (8) DP - States (8) Expression (8) Longest Common Subsequence(LCS) (8) One Pass (8) Quadtrees (8) Traversal Once (8) Trie - Suffix (8) 穷竭搜索 (8) Algorithm Problem List (7) All Sub (7) Catalan Number (7) Cycle (7) DP - Cases (7) Facebook Interview (7) Fibonacci Numbers (7) Flood fill (7) Game Nim (7) Graph BFS (7) HackerRank Difficult (7) Hackerearth (7) Inversion (7) Kadane’s Algorithm (7) Manacher (7) Morris Traversal (7) Multiple Data Structures (7) Normalized Key (7) O(XN) (7) Radix Sort (7) Recursion (7) Sampling (7) Suffix Array (7) Tech-Queries (7) Tree - Serialization (7) Tree DP (7) Trie - Bit (7) 蓝桥杯 (7) Algorithm - Brain Teaser (6) BFS - Priority Queue (6) BFS - Unusual (6) Classic Data Structure Impl (6) DP - 2D (6) DP - Monotone Queue (6) DP - Unusual (6) DP-Space Optimization (6) Dutch Flag (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Local MinMax (6) MST (6) Minimum Spanning Tree (6) Number - Reach (6) Parentheses (6) Pre-Sum (6) Probability (6) Programming Pearls (6) Rabin-Karp (6) Reverse (6) Scan from right (6) Schedule (6) Stream (6) Subset Sum (6) TSP (6) Xpost (6) n00tc0d3r (6) reddit (6) AI (5) Abbreviation (5) Anagram (5) Art Of Programming-July (5) Assumption (5) Bellman Ford (5) Big Data (5) Code - Solid (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Convex Hull (5) Crazyforcode (5) DFS - Multiple (5) DFS+DP (5) DP - Multi-Dimension (5) DP-Multiple Relation (5) Eulerian Cycle (5) Graph - Unusual (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Java (5) LogN (5) Manhattan Distance (5) Matrix Chain Multiplication (5) N Queens (5) Pre-Sort: Index (5) Quick Partition (5) Quora (5) Randomized Algorithms (5) Resources (5) Robot (5) SPFA(Shortest Path Faster Algorithm) (5) Shuffle (5) Sieve of Eratosthenes (5) Strongly Connected Components (5) Subarray Sum (5) Sudoku (5) Suffix Tree (5) Swap (5) Threaded (5) Tree - Creation (5) Warshall Floyd (5) Word Search (5) jiuzhang (5)

Popular Posts

  • Archives
  • LeetCode 471 - Encode String with Shortest Length
    Related:  LeetCode 394 - Decode String http://bookshadow.com/weblog/2016/12/11/leetcode-encode-string-with-shortest-length/ Given a  non...
  • Greedy Algorithms | Set 3 (Huffman Coding) | GeeksforGeeks
    Greedy Algorithms | Set 3 (Huffman Coding) | GeeksforGeeks Huffman coding is a lossless data compression algorithm. The idea is to assign ...
  • Buttercola: Buddy System
    Buttercola: Buddy System Given a complete binary tree with nodes of values of either 1 or 0, the following rules always hold: 1. A node...
  • Minimum area of a square enclosing given set of points
    Problem solving with programming: Minimum area of a square enclosing given set of points Given a set of coordinates in a two dimensional ...
  • HackerRank: N Puzzle
    HackerRank: N Puzzle N Puzzle is a sliding blocks game that takes place on a k * k grid with ((k * k) - 1) tiles each numbered from 1 to ...
  • LeetCode 394 - Decode String
    Follow up:  LeetCode 471 - Encode String with Shortest Length https://leetcode.com/problems/decode-string/ Given an encoded string, retu...
  • Hilbert Curve - Airbnb
    airbnb面试题汇总 Hilbert Curve Hilbert曲线可以无限阶下去，从1阶开始，落在一个矩阵里，让你写个function，三个参数（x,y,阶数），return 这个点（x,y）是在这阶curve里从原点出发的第几步 int hilbertCurve(...
  • Simple Text Editor - HackerRank
    https://www.hackerrank.com/challenges/simple-text-editor In this problem, your task is to implement a simple text editor. Initially, a fi...
  • LeetCode 291 - Word Pattern II
    leetcode 291 Word Pattern II Given a  pattern  and a string  str , find if  str  follows the same pattern. Here  follow  means a full m...