To avoid redundancy, however, we only show the implementation for the sparse representation in this article.įigure 7 shows the implementation of the sparse representation. In any case, we implemented both representations so as to provide a performance baseline. In our case, a sparse representation has the advantage, seeing as it requires less memory (since most cells will be dead) and allows us to iterate through the set of living cells only (since dead cells do not have direct effect on their neighbours).
All these living cells are aggregated in a dictionary structure. Each living cell is represented by its position (int, int) on the grid. The position of a cell on the grid is defined by its position in the matrix.Ī sparse representation in which only living cells are encoded. The dead cells are represented by a zero (or false) and the alive cells are represented by a 1 (or true). There are two possible ways to represent a state:Ī dense representation in which all the cells are encoded in a width*height matrix. Let’s assume a simple initial state where only 3 cells are alive: left cell, middle cell, and right cell. 3) In all other cases, the cell becomes (or remains) dead. 2) A living cell with two or three living neighbours remains alive. The game takes place on a two-dimensional finite or infinite grid whose cells can take two distinct states: “alive” or “dead”.Īt each stage, the evolution of a cell is entirely determined by its current state and the state of its eight neighbours as follows:ġ) A dead cell with exactly three living neighbours becomes alive. The game of life is a game in the mathematical sense rather than a playable game. Despite very simple rules, the game of life is Turing-complete and deterministic. Conway in the 1970s and is probably, the best known of all cellular automata. The game of life is a cellular automaton imagined by John H. We chose these two languages because they represent two of the most used programming paradigms, imperative (Python) and functional (Haskell), and because of the relative ease they provide in writing expressive and understandable code. In the third section, we compare the performance and elegance of our implementations. The second section will provide the implementation details in Python and Haskell for the game of life. The first section will be focused on giving an explanation of the rules of the game as well as examples of how it is played/defined. The code is provided on both of our GitHub profiles: Joseph94m, Michel-Haber. I say ‘we’ because this time I am joined by my friend and colleague Michel Haber. In this article we explain and provide an implementation for “The Game of Life”. (Previous one: From Scratch: Bayesian Inference, Markov Chain Monte Carlo and Metropolis Hastings, in python)
Hello everyone and welcome to the second article in the “From Scratch” series.