Princeton Algorithm Part 1 Week 1 - Percolation & PercolationStats

这是 coursera Algorithm Part 1 第一周作业， 得分98/100， 测试6错误，可惜没找到原因。

This is the Programming Assignment 1 for Princeton Algorithm part1 course @ coursera.org. (algs4)

98/100, with unsolved error on test 6 (I got no idea what's that error mean)

Test 6 error: Open predetermined sites with long percolating path;

test6.png

Percolation Class:

package ProgrammingAssignment;

import edu.princeton.cs.algs4.WeightedQuickUnionUF;

public class Percolation {
    final private int n; // n-by-n grid;
    private boolean[] flag; // array of opened sites
    private int count; // number of opened site
    private WeightedQuickUnionUF uf; // Using WeightedQuickUnion data type
    private WeightedQuickUnionUF bw; //backwash 

    public Percolation(int n) {
    // create n-by-n grid, with all sites blocked
    if (n <= 0)
        throw new IllegalArgumentException(
            "Fail to create an n-by-n brid, " + "n should be a number larger than 0");
    this.n = n;
    uf = new WeightedQuickUnionUF(n * n);
    bw = new WeightedQuickUnionUF(n * n);
    flag = new boolean[n * n];
    for (int i = 0; i < n * n; i++) {
        flag[i] = false;
    }
    for (int i = 1; i < n; i++) {
        uf.union(0, i);
        bw.union(0, i);
    }
    for (int i = n*(n-1); i < n*n-1; i++) {
        uf.union(i, n*n-1);
    }
    }

    public void open(int row, int col) {
    // open site (row, col) if it is not open already
    if (!isOpen(row, col)) {
        int index = index(row, col);

        flag[index] = true;

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


        if (row + 1 <= n && isOpen(row + 1, col)){
        uf.union(index, index(row + 1, col));
        bw.union(index, index(row + 1, col));
        }

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

        if (col + 1 <= n && isOpen(row, col + 1)){
        uf.union(index, index(row, col + 1));
        bw.union(index, index(row, col + 1));
        }
        count++;
    }
    }

    public boolean isOpen(int row, int col) {
    // is site (row, col) open
    int index = index(row, col);
    return flag[index];
    }

    private int index(int row, int col) {
    // return the index number with knowed row and col
    if (row <= 0 || row > n)
        throw new IllegalArgumentException("rows index out of bounds");
    if (col <= 0 || col > n)
        throw new IllegalArgumentException("cols index out of bounds");
    return (row - 1) * n + col - 1;
    }

    public boolean isFull(int row, int col) {//using bw istead of uf
    // test if site (row, col) full
    int index = index(row, col);
    return bw.connected(0, index) && isOpen(row, col);
    }

    public boolean percolates() {
    // test if the system percolates
    return (uf.connected(0, n * n - 1) && count!=0);
    }

    public int numberOfOpenSites() {
    // number of open sites
    return count;
    }
}

PercolationStats Class:

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

public class PercolationStats {
    private double[] result; // result array
    private double mean; // mean
    private int trials; // number of trials
    private double stddev;
    private double confidenceLo;
    private double confidenceHi;

    public PercolationStats(int n, int trials) {
    // perform trials independent experiments on an n-by-n grid
    if (n < 1)
        throw new IllegalArgumentException(
            "Fail to create an n-by-n brid, " 
        + "n should be a number larger than 0");
    if (trials < 1)
        throw new IllegalArgumentException("Trails too small");
    result = new double[trials];
    this.trials = trials;
    for (int i = 0; i < trials; i++) {
        Percolation perco = new Percolation(n);
        while (!perco.percolates()) {
        perco.open(StdRandom.uniform(n)+1, StdRandom.uniform(n)+1);
        }
        result[i] = (1.0) * perco.numberOfOpenSites() / (n * n);
    }
    mean = StdStats.mean(result);
    stddev = StdStats.stddev(result);
    confidenceLo = mean - (1.96 * stddev() / Math.sqrt(trials));
    confidenceHi = mean + (1.96 * stddev() / Math.sqrt(trials));
    }

    public double mean() {
    // sample mean of percolation threshold
    return mean;
    }

    public double stddev() {
    // sample standard deviation of percolation threshold
    return stddev;
    }

    public double confidenceLo() {
    // low endpoint of 95% confidence interval
    return confidenceLo;
    }

    public double confidenceHi() {
    // high endpoint of 95% confidence interval
    return confidenceHi;
    }

    public static void main(String[] args) {
    // test client
    PercolationStats pstats = new PercolationStats(Integer.parseInt(args[0]), Integer.parseInt(args[1]));

    System.out.printf("mean                     = %f\n", pstats.mean());
    System.out.printf("stddev                   = %f\n", pstats.stddev());
    System.out.printf("95%s confidence interval  = [%f, %f]\n", "%", pstats.confidenceLo(), pstats.confidenceHi());
    }
}