-
Notifications
You must be signed in to change notification settings - Fork 139
Conway's Game of Life
An implementation of Conway's Game of Life.
This uses the same approach as the APL version.
/ To run type: dfix brd
amd: {.[x;(_((^x)-^y)%2)+!:'^y;:;y]} / Amend and center
pnt: {|/y=\:x#!*/x} / Generate pentominoes
fpt: pnt[3 3;1 2 3 4 7] / F-pentomino
gld: pnt[3 3;1 5 6 7 8] / Glider
brd: amd[5 7#0;fpt] / Board with fpt centered
brd2: amd[20 20#0;fpt] / Larger board with fpt
brd3: amd[20 20#0;gld] / Glider centered
life: {|/(1;x)&3 4=\:+/,/2{-1 0 1!'\:x}/x}
disp: {`0:".#"[a:life x],"\n";a} / Display with chars
dfix: disp/ / Display until fixed point is reached
To calculate the next generation we must first determine how many living neighbours a cell has. The neighbours of a cell are all cells that are horizontally, vertically and diagonally adjacent. Based on the neighbour count one of the following rules is applied to each cell:
- Any live cell with fewer than two live neighbours dies, as if caused by under-population.
- Any live cell with two or three live neighbours lives on to the next generation.
- Any live cell with more than three live neighbours dies, as if by overcrowding.
- Any dead cell with exactly three live neighbours becomes a live cell, as if by reproduction.
An example 4 by 4 grid is used to demonstrate the calculations. Zero indicates a dead cell and one a living cell:
grid: |/5 6 10=\:4 4#!16
0 0 0 0 0 1 1 0 0 0 1 0 0 0 0 0 |
Rotating the grid by one place in each vertical direction and summing the resulting arrays gives the vertical neighbour count of each cell:
vert: 1 -1!\:grid
| Up | Down |
|---|---|
0 1 1 0 0 0 1 0 0 0 0 0 0 0 0 0 |
0 0 0 0 0 0 0 0 0 1 1 0 0 0 1 0 |
vcount: +/vert
0 1 1 0 0 0 1 0 0 1 1 0 0 0 1 0 |
The grid is then rotated by one in each horizontal direction:
horiz: 1 -1!'\:grid
| Left | Right |
|---|---|
0 0 0 0 1 1 0 0 0 1 0 0 0 0 0 0 |
0 0 0 0 0 0 1 1 0 0 1 0 0 0 0 0 |
The result of summing the horizontally rotated grids is the horizontal neighbour count of each cell:
hcount: +/horiz
0 0 0 0 1 1 1 1 0 1 0 1 0 0 0 0 |
A cell on a diagonal from another cell must also be counted as a neighbour. A diagonally rotated grid is produced by rotating the already rotated grids in a direction perpendicular to their original rotation direction i.e. If a grid was rotated vertically it is rotated horizontally.
diag: 1 -1!'\:horiz
| Left | Right | |
|---|---|---|
| Up |
1 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 |
0 0 1 1 0 0 0 1 0 0 0 0 0 0 0 0 |
| Down |
0 0 0 0 0 0 0 0 1 0 0 0 1 1 0 0 |
0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 1 |
Summing the resulting grids gives us the diagonal neighbour count of each cell:
dcount: +/,/diag
1 1 1 1 0 1 0 1 1 1 1 1 0 1 0 1 |
Finally, adding up the individual neighbour counts gives us the total neighbour count for each cell. The original grid is also added to give living cells a neighbour count one greater than their true neighbour count, this will be useful later in calculating the next generation:
neigh: hcount+vcount+dcount+grid
| grid | True Count | Count + grid |
|---|---|---|
0 0 0 0 0 1 1 0 0 0 1 0 0 0 0 0 |
1 2 2 1 1 2 2 2 1 3 2 2 0 1 1 1 |
1 2 2 1 1 3 3 2 1 3 3 2 0 1 1 1 |
After calculating the neighbour count for each cell the next generation of life may be produced using the four rules. A living cell with two or three neighbours lives on and a dead cell with three neighbours is brought to life, any other cell remains dead or dies.
The calculated neighbour count for living cells is one greater than their true count, this means that to determine which cells will live on or become alive it is enough to select cells that have a neighbour count of 3 and cells that have a neighbour count of 4 and exist on the original grid.
check: 3 4=\:neigh
| 3 | 4 |
|---|---|
0 0 0 0 0 1 1 0 0 1 1 0 0 0 0 0 |
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 |
Checking if the cells with neighbour count 4 exist on the original grid:
four: grid&check[1]
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 |
Combining the results of the two checks above to form the next generation:
gen: check[0]|four
0 0 0 0 0 1 1 0 0 1 1 0 0 0 0 0 |