A one-row in-place Life update needs only one saved row plus a few running sums. Before processing row , When column is processed,
above[j] stores the old row , and all rows and below are still old. Let a column sum be the number of old live cells in that column in rows . The three adjacent column sums, minus the center, give the required neighbour count.java
static int columnSum(boolean[][] board, boolean[] above,
int i, int j) {
int total = above[j] ? 1 : 0;
if (board[i][j]) total++;
if (i + 1 < board.length && board[i + 1][j]) total++;
return total;
}
static void stepInPlace(boolean[][] board) {
int width = board[0].length;
boolean[] above = new boolean[width];
for (int i = 0; i < board.length; i++) {
int left = 0;
int middle = columnSum(board, above, i, 0);
for (int j = 0; j < width; j++) {
int right = j + 1 < width
? columnSum(board, above, i, j + 1) : 0;
boolean oldCenter = board[i][j];
int neighbours = left + middle + right
- (oldCenter ? 1 : 0);
boolean newCenter = neighbours == 3
|| (oldCenter && neighbours == 2);
above[j] = oldCenter;
board[i][j] = newCenter;
left = middle;
middle = right;
}
}
}left and middle were computed before their cells were overwritten. right is computed now from untouched column , including its untouched above[j+1] entry. Thus all three sums describe old cells. Saving oldCenter into above[j] preserves the old current row for the next row's processing; no later computation in the current row rereads that changed entry, because its old contribution is already in the running sums. This proves the inner-loop invariant and then the row invariant by induction.Initially
above is all false, representing the dead exterior above the board. The missing left and right columns contribute zero; the bottom row omits any row below it. Hence all four boundaries follow the required convention. The update takes time and one -element auxiliary boolean vector, which is exactly a 1000-element vector for the requested board. It uses one board array throughout and does not silently keep a second board or two auxiliary rows. Articles by others on the same topic
There are currently no matching articles.