Homework 2: Disjoint Sets and Percolation

CS61B

看了Percolation, Part 2 : Introduction，因为之前草草刷Algorithm Part 1的时候做过，所以记得大概是干什么的。

第一次几乎全是brute force, 没在意performance requirements,想先实现再慢慢修改。但运行PercolationVisualizer发现出错：

发现自己犯了个错，我写的open方法里，有一部分代码是当一个block被open之后，根据情况来决定要不要跟上下左右的block来union. 其中比如col + 1< gridSize - 1 的情况下，就要和右边如果已经open的block union. 但我居然写成:

while(col + 1< gridSize - 1 ) {
  if(isOpen(row, col + 1)) {
    uf.union(xyTo1D(row, col), xyTo1D(row, col + 1));
  }
}

这种写法会使得while变成死循环， 很简单地用一个&&来结合成一个if语句就解决问题了：

  if(col + 1< gridSize - 1 &&isOpen(row, col + 1)) {
    uf.union(xyTo1D(row, col), xyTo1D(row, col + 1));
  }

但visualizer出来的结果还是对不上。

我的结果：

答案的结果：

修改了一下isFull, 还是有问题：

换了一个更简单的输入，尝试找到问题所在：

我的结果：

正确答案：

果然数据输入较小的时候，更容易清楚地找到问题所在。我在main方法里依次检查了可以block的isFull和isConnected状态，最后debug发现了问题：

我的open里原先这样写的：

 public void open(int row, int col) {
        if(row < 0 || row > gridSize - 1 || col < 0 || col > gridSize - 1){
            throw new IndexOutOfBoundsException();
        }
        if(isGridOpened[row][col]){
            return;
        } else{
            isGridOpened [row][col] = true;
        }
        //if left,right,top,bottom block is open, connect them.
        if (col + 1< gridSize  && isOpen(row, col + 1)) {
            uf.union(xyTo1D(row, col), xyTo1D(row, col + 1));
        }
        if (col - 1 > 0 && isOpen(row, col - 1)) {
            uf.union(xyTo1D(row, col), xyTo1D(row, col - 1));
        }
        if( row + 1 < gridSize  && isOpen(row + 1, col)){
            uf.union(xyTo1D(row,col),xyTo1D(row + 1, col));
        }
        if (row - 1 > 0 && isOpen(row - 1, col)) {
            uf.union(xyTo1D(row, col), xyTo1D(row - 1, col));
        }
    }

问题就处在两行：

if (col - 1 > 0 && isOpen(row, col - 1)) {
            uf.union(xyTo1D(row, col), xyTo1D(row, col - 1));
}
if (row - 1 > 0 && isOpen(row - 1, col)) {
    uf.union(xyTo1D(row, col), xyTo1D(row - 1, col));
}

这里注意，index是可以等于0，但永远不能等于gridSize的，改为：

if (col - 1 >= 0 && isOpen(row, col - 1)) {
            uf.union(xyTo1D(row, col), xyTo1D(row, col - 1));
}
if (row - 1 >= 0 && isOpen(row - 1, col)) {
    uf.union(xyTo1D(row, col), xyTo1D(row - 1, col));
}

这下初步完成了功能实现，下面进行runtime的优化。

正确实施：

注意到Performance requirements里讲到Your numberOfOpenSites() method must take constant time. 于是换掉了原来那种N2的扫描全部blocks然后统计isOpened个数的方式，添加了一个field variable private int numOfOpenSite; 然后每一次open这个数字自加一，最终达到constant time执行numberOfOpenSites()方法：

public int numberOfOpenSites(){
        return numOfOpenSites;
    }

Performance requirements里还有一句话：all methods should take constant time plus a constant number of calls to the union-find methods union(), find(), connected(), and count().

我的isFull()里面有这么短代码：

 for(int i = 0; i < gridSize; i++) {
                if (isOpen(row, col) && isOpen(0, i) && uf.connected(xyTo1D(row,col), i)) {
                    return true;
                }
            }

显然有Linear time次call了connected()，不满足要求。所以要用到instruction视频里说的virtual sites.

我修改了this.uf = new WeightedQuickUnionUF( N * N + 2 );来新增两个site. 一个top virtual site （N*N), 一个bottom virtual site(N*N -1). 然后在open()里特意留意第一行和最后一行的情况，如果要打开的是这两行的block, 最后要分别与top virtual site或者bottom virtual site 实现connect.

public void open(int row, int col) {
        if(row < 0 || row > N - 1 || col < 0 || col > N - 1){
            throw new IndexOutOfBoundsException();
        }
        if(isGridOpened[row][col]){
            return;
        } else{
            isGridOpened [row][col] = true;
            numOfOpenSites += 1;
            if(row == 0){
                uf.union(xyTo1D(row,col), N*N);
            }
            if(row == N -1 ){
                uf.union(xyTo1D(row,col), N*N +1);
            }
        }
        //if left,right,top,bottom block is open, connect them.
        if (col + 1< N  && isOpen(row, col + 1)) {
            uf.union(xyTo1D(row, col), xyTo1D(row, col + 1));
        }
        if (col - 1 >= 0 && isOpen(row, col - 1)) {
            uf.union(xyTo1D(row, col), xyTo1D(row, col - 1));
        }
        if( row + 1 < N  && isOpen(row + 1, col)){
            uf.union(xyTo1D(row,col),xyTo1D(row + 1, col));
        }
        if (row - 1 >= 0 && isOpen(row - 1, col)) {
            uf.union(xyTo1D(row, col), xyTo1D(row - 1, col));
        }
    }

最后还剩下一个由virtual sites引发的backwash问题：

为了避免backwash，可以多增加一个WeightedQuickUnionUF对象，这个对象size只有N*N + 1，也就是只有一个virtual top site. 这样就可以避免因为Bottom virtual site引发的问题。 在isFull()方法里就只需要看这个block是不是跟这个new WeightedQuickUnionUF的virtual top site是connected就可以。相应地对每个方法里的union要添加新的UF对象。之前的那个UF对象可以保证判断percolates().

private WeightedQuickUnionUF uf;
private WeightedQuickUnionUF noBackWash;
public Percolation(int N) {
        if( N <= 0){
            throw new IllegalArgumentException();
        }
        this.isGridOpened = new boolean[N][N];
        this.N = N;
        for( int i = 0; i < N; i++){
            for(int j = 0; j < N; j++) {
                this.isGridOpened[i][j] = false;
            }
        }
        this.numOfOpenSites = 0;
        this.uf = new WeightedQuickUnionUF( N * N + 2 );
        this.noBackWash = new WeightedQuickUnionUF( N * N + 1);
    }

做了PercolationStats.java，刚开始的时候发现所有threshold数组的元素都等于0.0，后来加了一个cast到double后才显示成正常的数.因为那里默认是int，而结果是小于零的小数，若为int类型就会直接舍掉小数部分，结果就会显示为0.

public PercolationStats(int N, int T) {
        if( N <= 0 || T <= 0){
            throw new java.lang.IllegalArgumentException();
        }
        Percolation p = new Percolation(N);
        this.threshold = new double [T];
        this.numOfExperiment = T;
        for(int i = 0; i < T; i++){
            //uniform(int n) returns a random integer uniformly in [0, n).
            while(!p.percolates()){
                p.open(StdRandom.uniform(N),StdRandom.uniform(N));
            }
            this.threshold[i] = (double) p.numberOfOpenSites() / (N * N);
        }
    }

这个hw我在上coursera上的Princeton Part 1的时候就已经做过。现在才觉得当时完全不懂这道题在干什么，而这一次是真正理解了并完全独立做的。时间间隔只是4个月左右，自己的水平还是相当不同了，看同样的题目完全是两种feel。继续加油，说明编程入了门就好懂，一直不开始才是最浪费时间的。