Conway's Game of Life
(Challenge added 635 days ago.)
I, for one, welcome our new cellular automaton overlords.
The Problem
Conway's Game of Life is played on an infinite two-dimensional grid of cells, with each cell either being alive or dead. The game starts with a grid which has a number of alive cells. In each generation, cells are born and cells die depending on the number of neighbours a cell has. A cell's neighbours are the cells which are immediately vertically, horizontally or diagionally adjacent to it. These are the rules which are applied :
- A cell dies of loneliness if it has one or zero neighbours.
- A cell dies of overcrowding if it has four or more neighbours.
- A new cell is born if it has exactly three neighbours.
- An alive cell with exactly two or three neighbours survives to the next generation.
Let's take the following, very simple example :
o ooo o
After one generation, we have the following grid :
ooo o o ooo
This 2nd generation was arrived at because the following rules were applied :
- The center cell died because it had four neighbours.
- Each of the outlying cells in the cross had exactly three cells so they continued to live.
- The four cells which are now at the corners of the square came to life because they had exactly three neighbours.
- None of the other surrounding dead cells in the first generation came to live since they only had a maximum of one neighbour.
Note that all of these rules were applied at the same time - The center cell died at exactly the same time that the 4 dead cells came to life.
More Information
- A grid representing the first generation of cells, along with the number of generations your program should apply to that grid, will be given to your program on stdin. You should print the resulting grid, after that number of generations have been applied, to stdout.
- The format of the input given to your program is as follows. The first line will be the number of generations followed by a newline. The following lines will be the grid of cells. A space represents a dead cell, and an '
o' (Lowercase letter O) represents an alive cell. Lines may have trailing spaces removed, and each line is terminated by a newline. - Since the game is meant to be played on an infinite grid and an infinite grid cannot be displayed, when printing the resulting grid, you should align the top-most cell at the top and the left-most cell at the far left. You will then have however many rows and columns you need fit all live cells. Each line should have trailing spaces stripped, and each line should be separated by a single newline.
- Your program will be executed seven times for each submission. It will need to pass all seven runs for it to be deemed successful.
- Wikipedia's Conway's Game of Life page might be useful and is full of background information about the topic.
Examples
As mentioned above, your program will be run seven times. The first four times, you will receive the same input. You can see that input, and the expected output, below :
- Run 1 - 5x5, 30 generations.
- Run 2 - Gliders, 201 generations.
- Run 3 - Diehard, 99 generations.
- Run 4 - Spaceship and block, 100 generations.
For the remaining three runs, you will receive random input. The number of generations will be between 5 and 50 inclusive, and the width and height of the grid will be between 5 and 25 inclusive. Click here to see an example of the random input and the output it should produce. Reload the page to see more random examples.
Note that, given a random grid, it is perfectly possible that all the cells will die within the number of generations you should apply. If this is the case, your program should print nothing.
Thanks
Many thanks to flagitious for suggesting and submitting this challenge!