Conway's Game of life solution in golang

Conway’s Game of life is an interesting problem with a even more interesting solution. In this blog we will look at solving the game of life problem. Since there are solutions which can run infinitely, we will be getting the state of the universe at n^th generation or when the universe is extinct. You can take a look at the solution in github here.

1. Rules

The universe of the Game of Life is is represented as a two dimensional array of (m x n) cells which is wrapped to simulate infinite two dimensional array, each of which is in one of two possible states, alive (1) or dead (0), (or populated and unpopulated, respectively). Every cell interacts with its eight neighbours, which are the cells that are horizontally, vertically, or diagonally adjacent. At each step in time, the following transitions occur:

1. Any live cell with fewer than two live neighbours dies, as if by underpopulation.
2. Any live cell with two or three live neighbours lives on to the next generation.
3. Any live cell with more than three live neighbours dies, as if by overpopulation.
4. Any dead cell with exactly three live neighbours becomes a live cell, as if by reproduction.

The initial pattern constitutes the seed of the system. The first generation is created by applying the above rules simultaneously to every cell in the seed; births and deaths occur simultaneously, and the discrete moment at which this happens is sometimes called a tick. Each generation is a pure function of the preceding one. The rules continue to be applied repeatedly to create further generations.

2. Inputs

1. m and n value of the two dimensional array (universe).
2. Number of generations to run.
3. Number of live cells at zeroth generation or seed of the universe.
4. List of positions (i, j) of the live cells at zeroth generation.

3. Solution

Since the next generation is purely dependent on the previous generation, we need to have two matrices to store the current generation and the next generation. Lets have a look at the code:

func ComputeNextGen(univ [][]int, m, n int) [][]int {
	nextGenUniverse := make([][]int, m)
	for i := range nextGenUniverse {
		nextGenUniverse[i] = make([]int, n)
	}

	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			cnt := getliveAdjacentCellCount(univ, i, j, m, n)
			if univ[i][j] == 1 {
				// Rule number 1 and 3
				if cnt < 2 || cnt > 3 {
					nextGenUniverse[i][j] = 0
				}

				// Rule number 2
				if cnt == 2 || cnt == 3 {
					nextGenUniverse[i][j] = 1
				}
			} else {
				// Rule number 4
				if cnt == 3 {
					nextGenUniverse[i][j] = 1
				}
			}
		}
	}

	return nextGenUniverse
}

As you can see, the current generation universe is represented as univ and the next generation universe is represented as nextGenUniverse. Get the count of adjacent live cells from getliveAdjacentCellCount function. Using the count of adjacent live cells we apply the rules of Game of life and generate the next generation universe. Now lets take a look at getliveAdjacentCellCount function:

func getliveAdjacentCellCount(univ [][]int, i, j, m, n int) int {
	count := 0
	for k := i - 1; k <= i+1; k++ {
		for l := j - 1; l <= j+1; l++ {
			x := k
			y := l
			if x < 0 {
				x = m - 1
			}

			if x > m-1 {
				x = 0
			}

			if y < 0 {
				y = n - 1
			}

			if y > n-1 {
				y = 0
			}

			if x == i && y == j {
				continue
			}

			if univ[x][y] == 1 {
				count++
			}
		}
	}

	return count
}

The above function returns the number of adjacent live cells for the given cell. Since we are wrapping the two dimensional array, we need to handle when a row > m or row < 0 as well as column > n or column < 0. Now lets us look at the main function:

func main() {
	// Size of the universe in m x n
	var m, n int
	fmt.Scanf("%d", &m)
	fmt.Scanf("%d", &n)

	// No of generations to run
	var gen int
	fmt.Scanf("%d", &gen)

	universe := make([][]int, m)
	for i := range universe {
		universe[i] = make([]int, n)
	}

	// Get the initial live cells in the universe
	var liveCellCount int
	fmt.Scanf("%d", &liveCellCount)
	for i := 0; i < liveCellCount; i++ {
		var r, c int
		fmt.Scanf("%d,%d", &r, &c)
		universe[r][c] = 1
	}

	for i := 0; i < gen; i++ {
		universe = ComputeNextGen(universe, m, n)

		extinct := true
		for k := 0; k < m; k++ {
			for l := 0; l < n; l++ {
				if universe[k][l] == 1 {
					extinct = false
					break
				}
			}
		}

		if extinct {
			gen = i + 1
			break
		}
	}

	fmt.Println("Universe for Generation ", gen)
	for k := 0; k < m; k++ {
		for l := 0; l < n; l++ {
			fmt.Printf("%d ", universe[k][l])
		}
		fmt.Printf("\n")
	}
}

We get all the inputs required for the problem m, n of the two dimensional array. Number of generations to run, number of live cells at zeroth generation or seed universe. Then position of the live cell is represented as i,j. Once the zeroth generation universe is generated. We run a for loop of the number of generations to run. If the universe is extinct we print the number of generations it took for the universe to be extinct. Otherwise, we print the status of the universe at n^th generation.