## Introduction

The Conway Game of Life is a simulation of a cell population. It was developed by the mathematician John Horton Conway in 1970. This simulation is a classic example of a cellular automaton.

The algorithm for the Conway Game of Life is widely known because it has been adopted and used in various applications. For instance, it has been employed to simulate the spread of a virus, the evolution of a bacterial colony, the behavior of an ant colony, and the movements of crowds.

## Implementation

``````
(* Conway Game of Life *)

let get g x y =
try g.(x).(y)
with _ -> 0

let neighbourhood g x y =
(get g (x-1) (y-1)) +
(get g (x-1) (y  )) +
(get g (x-1) (y+1)) +
(get g (x  ) (y-1)) +
(get g (x  ) (y+1)) +
(get g (x+1) (y-1)) +
(get g (x+1) (y  )) +
(get g (x+1) (y+1))

let next_cell g x y =
let n = neighbourhood g x y in
match g.(x).(y), n with
| 1, 0 | 1, 1                      -> 0  (* lonely *)
| 1, 4 | 1, 5 | 1, 6 | 1, 7 | 1, 8 -> 0  (* overcrowded *)
| 1, 2 | 1, 3                      -> 1  (* lives *)
| 0, 3                             -> 1  (* get birth *)
| _ (* 0, (0|1|2|4|5|6|7|8) *)     -> 0  (* barren *)

let copy g = Array.map Array.copy g

let next g =
let width = Array.length g
and height = Array.length g.(0)
and new_g = copy g in
for x = 0 to pred width do
for y = 0 to pred height do
new_g.(x).(y) <- (next_cell g x y)
done
done;
(new_g)

let print g =
let width = Array.length g
and height = Array.length g.(0) in
for x = 0 to pred width do
for y = 0 to pred height do
if g.(x).(y) = 0
then print_char '.'
else print_char 'o'
done;
print_newline ()
done

``````

The algorithm defines the following functions:

• `get`: A helper function that returns the value of a cell within a two-dimensional array. The arguments `x` and `y` represent the indices of the location of a cell.
• `neighbourhood`: A function that calculates the total number of living neighbors around a cell whose location is defined by the arguments `x` and `y`.
• `next_cell`: A function that determines the state of a cell based on its current state and the total number of living neighbors. This function applies the rules of the Conway Game of Life.
• `copy`: A function that creates and returns a copy of a two-dimensional array.
• `next`: A function that advances the simulation by one generation. This function returns a new two-dimensional array containing the next generation of cells.
• `print`: A function that prints the state of the cell population to the console.

## Step-by-step Explanation

1. `get` defines a helper function that takes a two-dimensional array `g` and two indices `x` and `y` and returns the value of the cell at position `(x, y)` in the array, or 0 if it is outside the array bounds.
2. `neighbourhood` calculates the total number of living neighbors around a cell whose location is defined by the arguments `x` and `y`. It does this by summing the values of the eight cells immediately surrounding the given cell, obtained through the `get` function.
3. `next_cell` determines the state of a cell in the next generation of the simulation, applying the rules of the Conway Game of Life. It takes two arguments, a two-dimensional array `g` and two indices `x` and `y`, corresponding to the location of the cell in question. It calculates the number of living neighbors using the `neighbourhood` function, and returns the updated state of the cell in the next generation.
4. `copy` creates a new two-dimensional array `new_g` that is a copy of the input two-dimensional array `g`, by using the `Array.map` function to apply the `Array.copy` function to each row of `g`.
5. `next` applies the `next_cell` function to each cell of the two-dimensional array `g`, creating a new two-dimensional array `new_g` that represents the state of the cell population in the next generation. It does this by looping over each element in the array and setting the corresponding value in `new_g` to the value returned by `next_cell`.
6. `print` takes a two-dimensional array `g` representing the cell population and prints its state to the console. It does this by printing a single character for each cell, representing whether it is alive or dead.

## Complexity Analysis

• `get`: This function is a constant-time operation. It just checks if the indices are within bounds and returns the value of a specific position in the two-dimensional array. Thus, the complexity of the function is O(1).
• `neighbourhood`: This function calculates the sum of the eight neighboring cellsâ€™ values. It does this by accessing eight cells, which is a constant-time operation. Thus the complexity of the function is O(1).
• `next_cell`: This function implements the set of rules that dictate whether the cell should change its state, based on the value of its neighbors and its current state. The function only performs a constant number of operations - at most, two if statements and one simple arithmetic addition. As a result, its time complexity is also O(1).
• `copy`: This function iterates through the input two-dimensional array, and creates a copy of every element using the `Array.copy` method. Thus, the function has a time complexity of O(nm), where n and m are the dimensions of the input array.
• `next`: This function iterates over every element in the input two-dimensional array and sets the corresponding value in the new array by calling `next_cell`. This involves iterating over every row of the array `g`, and then iterating over every element of each row. Thus, the time complexity of this function is O(nm) where n and m are the dimensions of the input arrays.
• `print`: This function iterates through every element in the input two-dimensional array and then prints a corresponding string to the console. It also has a time complexity of O(nm) where n and m are the dimensions of the input arrays.