Coursera算法课Programming Assignment 1: Percolation

Percolation

目标
通过蒙特卡洛模拟来计算 percolation threshold即渗滤阈值。

渗滤
percolation渗滤是一个由绝缘体和金属随机分布的复杂系统。那么它的金属分布在什么情况下会导致它是一个导体。科学家定义了一个抽象的被称作percolation的过程来为这些情况建模。

模型
这个模型被定义为一个n*n的方格来表示。方格site有两种状态：阻塞block和打开open。当一个方格被称为full时，表示这个方格是打开的并且通过一系列与之相邻（上下左右）的打开的方格与最上层的open的方格连接。当一个系统是percolates时，表示该系统最上层的打开的方格与最底层的打开的方格连接。

主要思路
运用WeightedQuickUnionUF数据结构将二维的sites表示为一维
open函数里需要检查上下左右的site是否需要与其union
sites是否percolate可以通过添加一个顶部虚拟site和一个底部虚拟site，最终验证这两个site是否connected。避免了遍历第一行和最后一行的每个site。
backwash
关于backwash问题，这个并不影响percolation的结果，但是作业评判系统会检查full这个函数。
解决方法是创建多一个WeightedQuickUnionUF对象，这个对象只包含顶部虚拟点，在full函数里利用这个对象可以避免backwash。

代码

Percolation

import edu.princeton.cs.algs4.WeightedQuickUnionUF;

public class Percolation {
    private WeightedQuickUnionUF sites;             // including upper and lower virtual sites
    private WeightedQuickUnionUF secSites;       // including only upper virtual sites
    private int num;                                              // the number of a low of sites
    private int opens;                                           // the number of open sites
    private boolean[] flags;                                  // flag of the state of site
    
    public Percolation(int n) { // create n-by-n grid, with all sites blocked
        if (n > 0) {  
            sites = new WeightedQuickUnionUF(n*n+2);
            secSites = new WeightedQuickUnionUF(n*n+1);
            num = n;
            opens = 0;      
            flags = new boolean[n*n]; // false means blocked
        }
        else    throw new IllegalArgumentException();
    }
    
    public void open(int row, int col) { // open site (row, col) if it is not open already 
        int ind = xyTo1D(row, col);
        if (row > 0 && row <= num && col > 0 && col <= num) {
            if (!isOpen(row, col)) {
                if (ind <= num) {
                    sites.union(0, ind);
                    secSites.union(0, ind);
                }
                if (ind < (num*num+1) && ind >= (num*(num-1)+1))          sites.union(ind, num*num+1);
                // the sites before ind and after ind
                int bind = ind - 1, aind = ind + 1;
                int [] before = oneDToxy(bind);
                int [] after = oneDToxy(aind);
                // condition of union ind and bind or aind: 1.in the interval     2.the same row      3.open
                if (aind <= num*num && isOpen(after[0], after[1]) && row == after[0]) {
                    sites.union(ind, aind);
                    secSites.union(ind, aind);
                }
                if (bind > 0 && isOpen(before[0], before[1]) && row == before[0]) {
                    sites.union(ind, bind);
                    secSites.union(ind, bind);
                }
                // condition of union ind and upper or lower : 1.in the interval    2.open
                if ((ind-num) > 0 && this.isOpen(row-1, col)) {
                    sites.union(ind, ind-num);
                    secSites.union(ind, ind - num);
                }       
                if ((ind+num) < (num*num+1) && this.isOpen(row+1, col)) {
                    sites.union(ind, ind+num);
                    secSites.union(ind, ind+num);
                }
                opens++;
                flags[ind-1] = true;  // true means opened
            }
        }
        else    throw new java.lang.IllegalArgumentException();
    }
    
    public boolean isOpen(int row, int col) { // is site (row, col) open?
        int ind = xyTo1D(row, col);
        if (row > 0 && row <= num && col > 0 && col <= num) {
            return flags[ind-1];
        }
        else    throw new java.lang.IllegalArgumentException();
    }
    
    public boolean isFull(int row, int col) {  // is site (row, col) full?      back wash!!!
        int ind = xyTo1D(row, col);
        if (row > 0 && row <= num && col > 0 && col <= num) {
            return secSites.connected(ind, 0) && this.isOpen(row, col);
        }
        else    throw new java.lang.IllegalArgumentException();
    }
    
    public int numberOfOpenSites() {       // number of open sites
        return opens;
    }
    
    public boolean percolates() {              // does the system percolate?
        return sites.connected(0, num*num+1);
    }
    
    private int xyTo1D(int row, int col) {  // index = (row-1)*num+col
        return (row-1)*num+col;
    }
    
    private int[] oneDToxy(int ind) {
        int row = ind / num, col  = ind % num;
        if (col == 0)   col = num;
        else              row += 1;
        int[] xy = {row, col};
        return xy;
    }
}

PercolationStats

import edu.princeton.cs.algs4.StdRandom;
import edu.princeton.cs.algs4.StdStats;
import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut;

public class PercolationStats {
    
    private static final double CONFIDENCE = 1.96;
    private int times;              // times of trials
    private double[] x;   // the fraction of open sites
    private int sites;
    
    public PercolationStats(int n, int trials) {    // perform trials independent experiments on an n-by-n grid
        if (n > 0 && trials > 0) {
            times = trials;
            sites  = n*n;
            x = new double[trials];
            for (int i = 0; i < trials; i++) {
                Percolation test = new Percolation(n);
                while (!test.percolates()) {
                    int row = StdRandom.uniform(1, n+1);
                    int col  = StdRandom.uniform(1, n+1);
                    test.open(row, col);
                }
                x[i] = test.numberOfOpenSites()/((double)sites);
            }
        }
        else    throw new IllegalArgumentException();
    }
    
    public double mean() { // sample mean of percolation threshold
        return StdStats.mean(x);
    }
    
    public double stddev() {                        // sample standard deviation of percolation threshold
        return StdStats.stddev(x);
    }
    
    public double confidenceLo() {            // low  endpoint of 95% confidence interval
        return  this.mean() - CONFIDENCE*this.stddev()/(Math.sqrt(times));
    }
    
    public double confidenceHi() {             // high endpoint of 95% confidence interval
        return  this.mean() + CONFIDENCE*this.stddev()/(Math.sqrt(times));
    }
    
    public static void main(String[] args) {    // test client
        int n, trials;
        StdOut.printf("%% java-algs4 PercolationStats ");
        n = StdIn.readInt();
        trials = StdIn.readInt();
        PercolationStats client = new PercolationStats(n, trials);
        StdOut.printf("mean                    = %f\n", client.mean());
        StdOut.printf("stddev                  = %f\n", client.stddev());
        StdOut.printf("95%% confidence interval = [%f, %f]\n", client.confidenceLo(), client.confidenceHi());
    }
}