-
Notifications
You must be signed in to change notification settings - Fork 0
/
GameOfLife.java
137 lines (121 loc) · 4.85 KB
/
GameOfLife.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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.FileReader;
import java.io.BufferedReader;
import java.util.*;
public class GameOfLife
{
public static void main(String[] args) throws FileNotFoundException
{
// will test all examples given by parsing the input file(s), make a 2D matrix then perform the evolution task
for(int i=0; i<args.length; i++)
{
String filePath = args[i];
ArrayList<ArrayList<Integer>> input = parseInput(filePath);
System.out.println("input: ");
printGrid(input);
System.out.println("\n" + "output: ");
ArrayList<ArrayList<Integer>> output = evolve(input);
printGrid(output);
System.out.println();
}
}
public static ArrayList<ArrayList<Integer>> parseInput(String filePath) throws FileNotFoundException
{
/*
* Chose to implement the matrix with ArrayLists because they are dynamic and we don't know the dimensions of the matrix ahead of time.
* The outer data structure will be an ArrayList holding an ArrayList of integers, growing every time there is a new line of input
*/
ArrayList<ArrayList<Integer>> input = new ArrayList<ArrayList<Integer>>();
FileReader fileReader = new FileReader(filePath); // used to read the file
BufferedReader bufferedReader = new BufferedReader(fileReader); // used to read the file
String cellInput; // will be reading the input line by line, storing into here
int col = 0;
try
{
boolean brHasNext = true;
while(brHasNext)
{
cellInput = bufferedReader.readLine(); // get the next line from the file
if(cellInput != null)
{
input.add(new ArrayList<Integer>());
for(int i=0; i<cellInput.length(); i++)
{
int val = ((cellInput.charAt(i)) == 49) ? 1 : 0; // for each line, get each character which we will then need to get it's ASCII file
input.get(col).add(val); // ASCII for 0 and 1 is 48 and 49 respectively
}
col++;
}
else
{
brHasNext = false;
bufferedReader.close();
}
}
}
catch (IOException e)
{
e.printStackTrace();
}
return input;
}
public static void printGrid(ArrayList<ArrayList<Integer>> input) // basic function to traverse through every single element of the 2d matrix and print it
{
for(int i=0; i<input.size(); i++)
{
for(int j=0; j<input.get(i).size(); j++)
System.out.print(input.get(i).get(j));
System.out.println();
}
}
public static int countNeighbors(int row, int col, ArrayList<ArrayList<Integer>> grid)
{
int numNeighbors = 0; //check all 8 possible neighbors
int xDir[] = { row-1, row, row+1,
row-1, row+1,
row-1, row, row+1 }; //an array of all the x-coordinates of the surrounding cells
int yDir[] = { col-1, col-1, col-1,
col, col,
col+1, col+1, col+1 }; //an array of all the y-coordinates of the surrounding cells
for(int i=0; i<8; i++) // there are a max of 8 neighbors
{
try
{
numNeighbors += grid.get(xDir[i]).get(yDir[i]); // tries to get a specific adjacent cell using the x and y direction arrays. if the cell is reachable add its value to the count
}
catch (IndexOutOfBoundsException e) // if one of the surrounding cells is out of bounds, thats ok ignore it and continue
{
continue;
}
}
return numNeighbors;
}
public static ArrayList<ArrayList<Integer>> evolve(ArrayList<ArrayList<Integer>> curGrid)
{
/*
* rule is a 2D matrix representing the next generation's outcome
* if (cell == dead) && (aliveNeighbors == 3) then this cell will be alive next gen
* if (cell == alive) && (aliveNeighbors == (2 || 3)) then this cell will be alive next gen
*/
// how many alive neighbors?
// 0,1,2,3,4,5,6,7,8
int[][] rule = { {0,0,0,1,0,0,0,0,0} , // this row is if the cell is currently dead.
{0,0,1,1,0,0,0,0,0} }; // this row is if the cell is currently alive.
int row = curGrid.size();
int col = curGrid.get(0).size();
// make a new matrix and assign the value for each cell by using the rule matrix above
ArrayList<ArrayList<Integer>> nextGrid = new ArrayList<ArrayList<Integer>>(); // 2d matrix to represent after one cycle of evolution
for(int i=0; i<row; i++)
{
nextGrid.add(new ArrayList<Integer>());
for(int j=0; j<col; j++)
{
int cell = curGrid.get(i).get(j); // get the cell from the original grid and check if its alive or not
int liveNeighbors = countNeighbors(i, j, curGrid); // get the number of neighbors for the cell
nextGrid.get(i).add(rule[cell][liveNeighbors]); // get the next stage of that cell using the rule matrix above
}
}
return nextGrid;
}
}