Simple Rules $\rightarrow$ Surprising Results

Computer Science Level 2

Conway's Game of Life is a simple algorithm that produces complex and often beautiful results. It is played on a grid and follows the rules below.

Any live cell with fewer than two live neighbors dies, simulating under-population.
Any live cell with two or three live neighbors lives on to the next generation.
Any live cell with more than three live neighbors dies, simulating overcrowding.
Any dead cell with exactly three live neighbors becomes a live cell, simulating reproduction.

If the image above is the first generation (where black cells are living), which of the following would be the second?

Details and assumptions

Every cell not on the edges of the grid has $8$ neighbors: namely, any cell that is horizontally, vertically, or diagonally adjacent.

A generation constitutes one simultaneous application of the rules to every cell in the grid.

D C A B

2 solutions

Discussions for this problem are now closed

Arman Siddique
Jan 27, 2014

First of all, we notice that the four corner cells will die because they only have one living neighbor. We can also see that the cells that are diagonally adjacent to the corner cells will live on because they have two neighbors. The four cells in the middle, however, will not live on because each one has more than three living neighbors. The only answer choice that satisfies these three conditions is $\boxed{D}$ .

i have implemented the following java code for the problem and it clearly gives the answer as C(1 denotes live cell and 0 denotes dead cell)

public class SimpleRulesSurprisingResults {

static int[][] board = new int[6][6];

public static void main(String[] args) {

    for (int i = 0; i < 6; i++) {
        for (int j = 0; j < 6; j++)
            if (i == j)
                board[i][j] = 1;
        board[i][5 - i] = 1;
    }

    for (int i = 0; i < 6; i++)
        for (int j = 0; j < 6; j++) {
            if (board[i][j] == 1) {
                if (numOfLiveNeighbours(i, j) < 2)
                    board[i][j] = 0;
                else if (numOfLiveNeighbours(i, j) <= 3)
                    continue;
                else
                    board[i][j] = 0;
            } else {
                if (numOfLiveNeighbours(i, j) == 3)
                    board[i][j] = 1;
            }
        }

    for (int i = 0; i < 6; i++) {
        for (int j = 0; j < 6; j++) {
            System.out.print(board[i][j] + " ");
        }
        System.out.println();
    }

}

static int numOfLiveNeighbours(int i, int j) {
    int count = 0;
    if (i > 0 && board[i - 1][j] == 1)
        count++;
    if (i < 5 && board[i + 1][j] == 1)
        count++;
    if (j > 0 && board[i][j - 1] == 1)
        count++;
    if (j < 5 && board[i][j + 1] == 1)
        count++;
    return count;
}

}

output:

0 0 0 0 0 0

0 0 1 1 0 0

0 0 0 0 0 0

Robin Kumar - 7 years, 3 months ago

This might happen because the program is marking some cells dead and alive on the same array. This is creating some problems to the rest of the cell for computation. I suggest, use a duplicate array only to store first generation, don't alter that array at all, and store the computed results in separate array.

Sandeep Thakur - 7 years, 2 months ago

Amazing solution! I wish I could upvote this 100 times.

This solution put me to tears when I first read. An outstanding display of elegance, you, Arman Siddique, should go to MathCounts Chapter .-.

William Cui - 7 years, 4 months ago

What about the other cells? Shouldn't they be dead?

Kaleil Salomon -Jacob - 7 years, 4 months ago

The great Arman Siddique is using process of elimination to rule out the other three choices.

By the way, Arman, Mrs. P has your student ID. It is on the board stickied with a magnet and has an arrow pointing to it saying 'Arman'. I will be sure to take it tomorrow morning and hide it somewhere else.

William Cui - 7 years, 4 months ago

Charlie Wilkinson
Jan 28, 2014

This is just a matter of going through every cell in the grid and checking the rules on it.

i have implemented the following java code for the problem and it clearly gives the answer as C(1 denotes live cell and 0 denotes dead cell)

public class SimpleRulesSurprisingResults {

static int[][] board = new int[6][6];

public static void main(String[] args) {

for (int i = 0; i < 6; i++) {
    for (int j = 0; j < 6; j++)
        if (i == j)
            board[i][j] = 1;
    board[i][5 - i] = 1;
}

for (int i = 0; i < 6; i++)
    for (int j = 0; j < 6; j++) {
        if (board[i][j] == 1) {
            if (numOfLiveNeighbours(i, j) < 2)
                board[i][j] = 0;
            else if (numOfLiveNeighbours(i, j) <= 3)
                continue;
            else
                board[i][j] = 0;
        } else {
            if (numOfLiveNeighbours(i, j) == 3)
                board[i][j] = 1;
        }
    }

for (int i = 0; i < 6; i++) {
    for (int j = 0; j < 6; j++) {
        System.out.print(board[i][j] + " ");
    }
    System.out.println();
}

}

static int numOfLiveNeighbours(int i, int j) { int count = 0; if (i > 0 && board[i - 1][j] == 1) count++; if (i < 5 && board[i + 1][j] == 1) count++; if (j > 0 && board[i][j - 1] == 1) count++; if (j < 5 && board[i][j + 1] == 1) count++; return count; } }

output:

0 0 0 0 0 0

0 0 1 1 0 0

0 0 0 0 0 0

Robin Kumar - 7 years, 3 months ago

First of all, u have to use another matrix to store changes and after whole process overwrite original matrix. And u're not considering diagonal elements to find noOfLivingNeighbours. Your final code should look like this.

public class RulesOfLiving {
    static int[][] board = new int[6][6];
    public static void main(String[] args) {
        for (int i = 0; i < 6; i++) {
            for (int j = 0; j < 6; j++)
                if (i == j)
                    board[i][j] = 1;
            board[i][5 - i] = 1;
        }
        for (int i = 0; i < 6; i++) {
            for (int j = 0; j < 6; j++) {
                System.out.print(board[i][j] + " ");
            }
            System.out.println();
        }
        System.out.println();
        int[][] temp = new int[6][6];
        for(int i =0; i<6; i++)
            for(int j=0; j<6; j++)
                temp[i][j]=board[i][j];
        for (int i = 0; i < 6; i++) {
            for (int j = 0; j < 6; j++) {
                if (board[i][j] == 1) {
                    if (numOfLiveNeighbours(i, j) < 2 || numOfLiveNeighbours(i, j) >3)
                        temp[i][j] = 0;
                }
                else {
                    if (numOfLiveNeighbours(i, j) == 3)
                        temp[i][j] = 1;
                }
            }
        }
        for(int i =0; i<6; i++)
            for(int j=0; j<6; j++)
                board[i][j]=temp[i][j];
        System.out.println();
        for (int i = 0; i < 6; i++) {
            for (int j = 0; j < 6; j++) {
                System.out.print(board[i][j] + " ");
            }
            System.out.println();
        }
    }
    static int numOfLiveNeighbours(int i, int j) {
        int count = 0;
        if (i > 0 && board[i - 1][j] == 1)
            count++;
        if (i < 5 && board[i + 1][j] == 1)
            count++;
        if (j > 0 && board[i][j - 1] == 1)
            count++;
        if (j < 5 && board[i][j + 1] == 1)
            count++;
        if (i > 0 && j > 0 && board[i-1][j-1] == 1)
            count++;
        if (i < 5 && j > 0 && board[i+1][j-1] == 1)
            count++;
        if (i > 0 && j < 5 && board[i-1][j+1] == 1)
            count++;
        if (i < 5 && j < 5 && board[i+1][j+1] == 1)
            count++;
        return count;
    }
}

Output:
0 0 0 0 0 0
0 1 1 1 1 0
0 1 0 0 1 0
0 1 0 0 1 0
0 1 1 1 1 0
0 0 0 0 0 0

Kartik Patel - 7 years, 1 month ago

Simple Rules → \rightarrow → Surprising Results

2 solutions

Discussions for this problem are now closed

0 pending reports

Simple Rules $\rightarrow$ Surprising Results