Welcome to Project Lovelace! We're still in early development so there are still tons of bugs to find and improvements to make. If you have any suggestions, complaints, or comments please let us know on Discourse, Discord, or GitHub!

Game of life

You will learn about: cellular automata and 2D arrays.

A cellular automaton is a model used to simulate a wide variety of systems in science. We'll look at one that's supposed to simulate life itself, Conway's Game of Life. You have a two-dimensional rectangular grid of square cells, each of which can be either alive or dead. Each cell interacts with its eight nearest neighbors and evolves according to the following rules:

  1. A live cell with less than two live neighbours dies (due to underpopulation).
  2. A live cell with two or three live neighbours continues to live.
  3. A live cell with more than three live neighbours dies (due to overpopulation).
  4. A dead cell with exactly three live neighbours becomes a live cell (due to reproduction).

To deal with the finite size of the grid we'll impose periodic (or toroidal) boundary conditions, that is, to treat the left and right edges of the grid to be stitched together so that moving across the right boundary returns you to the left boundary (and we will do the same with the top and bottom edges).


A bunch of still life patterns that do not change shape under the evolution rules, and some oscillator patterns that flip between the same patterns again and again.
A glider gun pattern that generate gliders, which are spaceship patterns that move across the grid. In this case, the gliders go down the bottom of the grid and reappear at the top due to the periodic boundary conditions. After the gliders go through the right boundary they reappear on the left and destroy the glider gun that created them.

Given an initial configuration for the grid, run the Game of Life simulation for $N$ time steps (also an input) and return the state of the grid.

Input: A 2D integer array representing the grid where the dead cells are represnted by 0's and the alive cells are 1's, and a number of time steps $N$ to run the Game of Life for.

Output: A 2D array representing the state of the grid after $N$ time steps.

Example

Input number of time steps: 1 Input initial grid: 000000000000000000000000000000000000 011000001100000000000000000000000000 011000010010000000000001110001110000 000000001010000011100000000000000000 000000000100000000000100001010000100 000110000000000000000100001010000100 001001000001000000000100001010000100 000110000010100000000001110001110000 000000000001000011100000000000000000 000000000000000111000001110001110000 011000000000000000000100001010000100 011000000000000000000100001010000100 000110000000000000000100001010000100 000110000000000000000000000000000000 000000000000000000000001110001110000 000000000000000000000000000000000000 000000000000000000000000000000000000 Output final grid: 000000000000000000000000000000000000 000000000000000000000000100000100000 000000000000000001000000100000100000 000000000000000001000000110001100000 000000000000000001000000000000000000 000000000000000000001110011011001110 000000000000000000000010101010101000 000000000000000001000000110001100000 000000000000000100100000000000000000 000000000000000100100000110001100000 011000000000000010000010101010101000 010000000000000000001110011011001110 000010000000000000000000000000000000 000110000000000000000000110001100000 000000000000000000000000100000100000 000000000000000000000000100000100000 000000000000000000000000000000000000
 Difficulty  Timesink
 Function game_of_life(board, steps)

You must be logged in to view your submissions.

Notes

  • There is a Numberphile video where John Conway himself talks about how he invented the Game of Life!
  • There are many interesting patterns: puffer trains,
  • Since the Game of Life is Turing complete, you can actually make a digital clock pattern and even an attempt to build a working version of Tetris!
  • LifeWiki has tons more information on the Game of Life, cool patterns, and the latest news (people are still discovering completely new patterns in 2018).

Let us know what you think about this problem! Was it too hard? Difficult to understand? Also feel free to discuss the problem, ask questions, and post cool stuff on Discourse. You should be able see a discussion thread below. Would be nice if you don't post solutions in there but if you do then please organize and document your code well so others can learn from it.