******************************************* This is the code that i already am u
ID: 3663507 • Letter: #
Question
*******************************************
This is the code that i already am using,
/******************************************************************************
* Compilation: javac PercolationVisualizer.java
* Execution: java PercolationVisualizer input.txt
* Dependencies: Percolation.java
*
* This program takes the name of a file as a command-line argument.
* From that file, it
*
* - Reads the grid size N of the percolation system.
* - Creates an N-by-N grid of sites (intially all blocked)
* - Reads in a sequence of sites (row i, column j) to open.
*
* After each site is opened, it draws full sites in light blue,
* open sites (that aren't full) in white, and blocked sites in black,
* with with site (0, 0) in the upper left-hand corner.
*
******************************************************************************/
import java.awt.Font;
import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.StdDraw;
public class PercolationVisualizer {
// delay in miliseconds (controls animation speed)
private static final int DELAY = 100;
// draw N-by-N percolation system
public static void draw(Percolation perc, int N) {
StdDraw.clear();
StdDraw.setPenColor(StdDraw.BLACK);
StdDraw.setXscale(-.05*N, 1.05*N);
StdDraw.setYscale(-.05*N, 1.05*N); // leave a border to write text
StdDraw.filledSquare(N/2.0, N/2.0, N/2.0);
// draw N-by-N grid
for (int row = 0; row < N; row++) {
for (int col = 0; col < N; col++) {
if (perc.isFull(row, col)) {
StdDraw.setPenColor(StdDraw.BOOK_LIGHT_BLUE);
}
else if (perc.isOpen(row, col)) {
StdDraw.setPenColor(StdDraw.WHITE);
}
else {
StdDraw.setPenColor(StdDraw.BLACK);
}
StdDraw.filledSquare(col + 0.5, N - row - 0.5, 0.45);
}
}
// write status text
StdDraw.setFont(new Font("SansSerif", Font.PLAIN, 12));
StdDraw.setPenColor(StdDraw.BLACK);
StdDraw.text(.25*N, -N*.025, perc.numberOfOpenSites() + " open sites");
if (perc.percolates()) StdDraw.text(.75*N, -N*.025, "percolates");
else StdDraw.text(.75*N, -N*.025, "does not percolate");
}
private static void simulateFromFile(String filename) {
In in = new In(filename);
int N = in.readInt();
Percolation perc = new Percolation(N);
// turn on animation mode
StdDraw.show(0);
// repeatedly read in sites to open and draw resulting system
draw(perc, N);
StdDraw.show(DELAY);
while (!in.isEmpty()) {
int i = in.readInt();
int j = in.readInt();
perc.open(i, j);
draw(perc, N);
StdDraw.show(DELAY);
}
}
public static void main(String[] args) {
String filename = args[0];
simulateFromFile(filename);
}
}
*************************************************************************
NEXT class
/******************************************************************************
* Compilation: javac InteractivePercolationVisualizer.java
* Execution: java InteractivePercolationVisualizer N
* Dependencies: PercolationVisualizer.java Percolation.java
*
* This program takes the grid size N as a command-line argument.
* Then, the user repeatedly clicks sites to open with the mouse.
* After each site is opened, it draws full sites in light blue,
* open sites (that aren't full) in white, and blocked sites in black.
*
******************************************************************************/
import edu.princeton.cs.algs4.StdDraw;
import edu.princeton.cs.algs4.StdOut;
public class InteractivePercolationVisualizer {
private static final int DELAY = 20;
public static void main(String[] args) {
// N-by-N percolation system (read from command-line, default = 10)
int N = 10;
if (args.length == 1) N = Integer.parseInt(args[0]);
// turn on animation mode
StdDraw.show(0);
// repeatedly open site specified my mouse click and draw resulting system
StdOut.println(N);
Percolation perc = new Percolation(N);
PercolationVisualizer.draw(perc, N);
StdDraw.show(DELAY);
while (true) {
// detected mouse click
if (StdDraw.mousePressed()) {
// screen coordinates
double x = StdDraw.mouseX();
double y = StdDraw.mouseY();
// convert to row i, column j
int i = (int) (N - Math.floor(y) - 1);
int j = (int) (Math.floor(x));
// open site (i, j) provided it's in bounds
if (i >= 0 && i < N && j >= 0 && j < N) {
if (!perc.isOpen(i, j)) {
StdOut.println(i + " " + j);
}
perc.open(i, j);
}
// draw N-by-N percolation system
PercolationVisualizer.draw(perc, N);
}
StdDraw.show(DELAY);
}
}
}
*************************************************************************************************************************
Next class
import edu.princeton.cs.algs4.WeightedQuickUnionUF;
public class Percolation {
boolean [][] tileBox;
WeightedQuickUnionUF unionFind;
int top;
int bottom;
public Percolation(int N)
{
this.tileBox = new boolean [N][N];
this.unionFind = new WeightedQuickUnionUF(N);
int top = (N * N) + 1;
int bottom = top -top;
// 2d array
// create NbyN grid, with all sites blocked
}
public void open(int i, int j)
{
tileBox[i][j]=true;
// open site (row i, column j) if it is not open already
}
public boolean isOpen(int i, int j)
{
return tileBox[i][j];
// is site (row i, column j) open?
}
public boolean isFull(int i, int j)
{
//unionFind.connected(p, q);
return false;
// is site (row i, column j) full?
}
public boolean percolates()
{
return false;
}
public String numberOfOpenSites() {
// TODO Auto-generated method stub
return null;
}
public int getFlatGridNum(int row, int col)
{
return ((row *10) + (col) +1 );
}
}
**************************************************************************************************
next class
/******************************************************************************
* Compilation: javac WeightedQuickUnionUF.java
* Execution: java WeightedQuickUnionUF < input.txt
* Dependencies: StdIn.java StdOut.java
*
* Weighted quick-union (without path compression).
*
******************************************************************************/
package edu.princeton.cs.algs4;
/**
* The <tt>WeightedQuickUnionUF</tt> class represents a union-find data structure.
* It supports the <em>union</em> and <em>find</em> operations, along with
* methods for determinig whether two objects are in the same component
* and the total number of components.
* <p>
* This implementation uses weighted quick union by size (without path compression).
* Initializing a data structure with <em>N</em> objects takes linear time.
* Afterwards, <em>union</em>, <em>find</em>, and <em>connected</em> take
* logarithmic time (in the worst case) and <em>count</em> takes constant
* time.
* <p>
* For additional documentation, see <a href="http://algs4.cs.princeton.edu/15uf">Section 1.5</a> of
* <i>Algorithms, 4th Edition</i> by Robert Sedgewick and Kevin Wayne.
*
* @author Robert Sedgewick
* @author Kevin Wayne
*/
public class WeightedQuickUnionUF {
private int[] parent; // parent[i] = parent of i
private int[] size; // size[i] = number of objects in subtree rooted at i
private int count; // number of components
/**
* Initializes an empty union-find data structure with N isolated components 0 through N-1.
* @param N the number of objects
* @throws java.lang.IllegalArgumentException if N < 0
*/
public WeightedQuickUnionUF(int N) {
count = N;
parent = new int[N];
size = new int[N];
for (int i = 0; i < N; i++) {
parent[i] = i;
size[i] = 1;
}
}
/**
* Returns the number of components.
* @return the number of components (between 1 and N)
*/
public int count() {
return count;
}
/**
* Returns the component identifier for the component containing site <tt>p</tt>.
* @param p the integer representing one site
* @return the component identifier for the component containing site <tt>p</tt>
* @throws java.lang.IndexOutOfBoundsException unless 0 <= p < N
*/
public int find(int p) {
validate(p);
while (p != parent[p])
p = parent[p];
return p;
}
// validate that p is a valid index
private void validate(int p) {
int N = parent.length;
if (p < 0 || p >= N) {
throw new IndexOutOfBoundsException("index " + p + " is not between 0 and " + N);
}
}
/**
* Are the two sites <tt>p</tt> and <tt>q</tt> in the same component?
* @param p the integer representing one site
* @param q the integer representing the other site
* @return <tt>true</tt> if the two sites <tt>p</tt> and <tt>q</tt>
* are in the same component, and <tt>false</tt> otherwise
* @throws java.lang.IndexOutOfBoundsException unless both 0 <= p < N and 0 <= q < N
*/
public boolean connected(int p, int q) {
return find(p) == find(q);
}
/**
* Merges the component containing site<tt>p</tt> with the component
* containing site <tt>q</tt>.
* @param p the integer representing one site
* @param q the integer representing the other site
* @throws java.lang.IndexOutOfBoundsException unless both 0 <= p < N and 0 <= q < N
*/
public void union(int p, int q) {
int rootP = find(p);
int rootQ = find(q);
if (rootP == rootQ) return;
// make smaller root point to larger one
if (size[rootP] < size[rootQ]) {
parent[rootP] = rootQ;
size[rootQ] += size[rootP];
}
else {
parent[rootQ] = rootP;
size[rootP] += size[rootQ];
}
count--;
}
/**
* Reads in a sequence of pairs of integers (between 0 and N-1) from standard input,
* where each integer represents some object;
* if the objects are in different components, merge the two components
* and print the pair to standard output.
*/
public static void main(String[] args) {
int N = StdIn.readInt();
WeightedQuickUnionUF uf = new WeightedQuickUnionUF(N);
while (!StdIn.isEmpty()) {
int p = StdIn.readInt();
int q = StdIn.readInt();
if (uf.connected(p, q)) continue;
uf.union(p, q);
StdOut.println(p + " " + q);
}
StdOut.println(uf.count() + " components");
}
}
/******************************************************************************
* Copyright 2002-2015, Robert Sedgewick and Kevin Wayne.
*
* This file is part of algs4.jar, which accompanies the textbook
*
* Algorithms, 4th edition by Robert Sedgewick and Kevin Wayne,
* Addison-Wesley Professional, 2011, ISBN 0-321-57351-X.
* http://algs4.cs.princeton.edu
*
*
* algs4.jar is free software: you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation, either version 3 of the License, or
* (at your option) any later version.
*
* algs4.jar is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with algs4.jar. If not, see http://www.gnu.org/licenses.
******************************************************************************/
Explanation / Answer
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
/**
*
* @author paul
*/
public class Percolation {
private int[][] siteStatus;
private int count;
//Check the WeightedQuickUnionUF implemented in this blog.
private WeightedQuickUnionUF quickunion;
private int N;
public Percolation(int N) {
this.N = N;
siteStatus = new int[N][N];
quickunion = new WeightedQuickUnionUF((N*N)+2);
count = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
//initialise site status as blocked
siteStatus[i][j] = 1;
//initialise site ids
count++;
if (i == 0) {
quickunion.union(count, 0);
} else if (i == N-1) {
quickunion.union(count, (N*N)+1);
}
}
}
}
public void open(int i, int j) {
int x, y;
x = i-1;
y = j-1;
siteStatus[x][y] = 0;
for (int a = x-1; a <= x+1; a += 2) {
if (a >= 0 && a < N && y >= 0 && y < N) {
if (isOpen(a+1, y+1)) {
quickunion.union((a*N)+(y+1), (x*N)+j);
}
}
}
for (int b = y-1; b <= y+1; b += 2) {
if (x >= 0 && x < N && b >= 0 && b < N) {
if (isOpen(x+1, b+1)) {
quickunion.union((x*N)+(b+1), (x*N)+j);
}
}
}
}
public boolean isOpen(int i, int j) {
if (i > 0 && i <= N && j > 0 && j <= N) {
return siteStatus[i-1][j-1] == 0;
} else {
throw new IndexOutOfBoundsException("Values are out of range");
}
}
public boolean isFull(int i, int j) {
if (i > 0 && i <= N && j > 0 && j <= N) {
if (quickunion.connected(((i-1)*N) + j, 0)) {
return siteStatus[i-1][j-1] == 0;
} else {
return false;
}
} else {
throw new IndexOutOfBoundsException("Values are out of range");
}
}
public boolean percolates() {
return quickunion.connected(0, (N*N)+1);
}
}
2. PercolationStats.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
/**
*
* @author paul
*/
public class PercolationStats {
private Percolation percolation;
private double[] threshold;
private double T;
private int openSites;
public PercolationStats(int T, int N) {
if (N <= 0 || T <= 0) {
throw new IllegalArgumentException("Value is out of range");
}
threshold = new double[T];
int randx, randy;
this.T = T;
for (int i = 0; i < T; i++) {
percolation = new Percolation(N);
randx = StdRandom.uniform(1, N+1);
randy = StdRandom.uniform(1, N+1);
percolation.open(randx, randy);
openSites = 1;
while (!percolation.percolates()) {
randx = StdRandom.uniform(1, N+1);
randy = StdRandom.uniform(1, N+1);
if (!percolation.isOpen(randx, randy)) {
percolation.open(randx, randy);
openSites++;
}
}
threshold[i] = ((double) openSites)/(N*N);
}
}
public double mean() {
return StdStats.mean(threshold);
}
public double stddev() {
return StdStats.stddev(threshold);
}
public double confidenceLo() {
return mean() - (1.96*stddev())/Math.sqrt(T);
}
public double confidenceHi() {
return mean() + (1.96*stddev())/Math.sqrt(T);
}
public static void main(String[] args) {
int T, N;
T = Integer.parseInt(args[0]);
N = Integer.parseInt(args[1]);
PercolationStats percolationStats = new PercolationStats(T, N);
//Instead of StdOut.println() function, you can use your own output format
StdOut.println("%Java PercolationStats " + T + " " + N);
StdOut.println("Mean "+percolationStats.mean());
StdOut.println("stddev " + percolationStats.stddev());
StdOut.println("95% confidence interval = "+ percolationStats.confidenceLo()
+ ", " + percolationStats.confidenceHi());
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
/**
*
* @author paul
*/
public class Percolation {
private int[][] siteStatus;
private int count;
//Check the WeightedQuickUnionUF implemented in this blog.
private WeightedQuickUnionUF quickunion;
private int N;
public Percolation(int N) {
this.N = N;
siteStatus = new int[N][N];
quickunion = new WeightedQuickUnionUF((N*N)+2);
count = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
//initialise site status as blocked
siteStatus[i][j] = 1;
//initialise site ids
count++;
if (i == 0) {
quickunion.union(count, 0);
} else if (i == N-1) {
quickunion.union(count, (N*N)+1);
}
}
}
}
public void open(int i, int j) {
int x, y;
x = i-1;
y = j-1;
siteStatus[x][y] = 0;
for (int a = x-1; a <= x+1; a += 2) {
if (a >= 0 && a < N && y >= 0 && y < N) {
if (isOpen(a+1, y+1)) {
quickunion.union((a*N)+(y+1), (x*N)+j);
}
}
}
for (int b = y-1; b <= y+1; b += 2) {
if (x >= 0 && x < N && b >= 0 && b < N) {
if (isOpen(x+1, b+1)) {
quickunion.union((x*N)+(b+1), (x*N)+j);
}
}
}
}
public boolean isOpen(int i, int j) {
if (i > 0 && i <= N && j > 0 && j <= N) {
return siteStatus[i-1][j-1] == 0;
} else {
throw new IndexOutOfBoundsException("Values are out of range");
}
}
public boolean isFull(int i, int j) {
if (i > 0 && i <= N && j > 0 && j <= N) {
if (quickunion.connected(((i-1)*N) + j, 0)) {
return siteStatus[i-1][j-1] == 0;
} else {
return false;
}
} else {
throw new IndexOutOfBoundsException("Values are out of range");
}
}
public boolean percolates() {
return quickunion.connected(0, (N*N)+1);
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.