Intro
I have been crafting the logic required for the Game of Life. In the last article, I documented how I struggled with life cycles. However, I made some progress recently.
Tests
As I discussed in past articles, I wanted to learn how to implement this system via TDD.
The following tests have been implemented:
[<Test>]
let ``Any live cell with fewer than two live neighbors dies, as if caused by under-population``() =
// Setup
let rowCount = 3
let grid = rowCount |> createGrid
|> setCell { X=2; Y=2; State=Alive }
|> setReaction (2,2)
// Verify
grid |> getStatus (2,2) |> should equal Dead
[<Test>]
let ``Any live cell with two or three live neighbours lives on to the next generation``() =
// Setup
let rowCount = 3
let grid = rowCount |> createGrid
|> setCell { X=1; Y=2; State=Alive }
|> setCell { X=2; Y=2; State=Alive }
|> setCell { X=3; Y=2; State=Alive }
|> setReaction (2,2)
// Verify
grid |> getStatus (2,2) |> should equal Alive
[<Test>]
let ``Any live cell with more than three live neighbours dies, as if by over-population``() =
// Setup
let rowCount = 3
let grid = rowCount |> createGrid
|> setCell { X=1; Y=2; State=Alive }
|> setCell { X=2; Y=2; State=Alive }
|> setCell { X=3; Y=2; State=Alive }
|> setCell { X=3; Y=3; State=Alive }
|> setCell { X=2; Y=1; State=Alive }
|> setReaction (2,2)
// Verify
grid |> getStatus (2,2) |> should equal Dead
[<Test>]
let ``Any dead cell with exactly three live neighbours becomes a live cell, as if by reproduction``() =
// Setup
let rowCount = 3
let grid = rowCount |> createGrid
|> setCell { X=1; Y=2; State=Alive }
|> setCell { X=2; Y=2; State=Dead }
|> setCell { X=3; Y=2; State=Alive }
|> setCell { X=3; Y=3; State=Alive }
|> setReaction (2,2)
// Verify
grid |> getStatus (2,2) |> should equal Alive
Business Logic
I wrote some additional business logic to capture a cell’s neighbors. In addition, I also wrote code to capture a cell’s response to its neighbors.
Neighbors
Each grid block is comprised of nine cells. Thus, I decided to name a cell based on its relative relationship to the original cell that’s being targeted for a response.
Thus, I implemented the following function to get neighboring coordinates:
let getNeighbors (coordinate:int*int) =
let x,y = coordinate
let west = x-1, y
let northWest = x-1, y+1
let north = x, y+1
let northEast = x+1, y+1
let east = x+1, y
let southEast = x+1, y-1
let south = x, y-1
let southWest = x-1, y-1
[west; northWest; north; northEast; east; southEast; south; southWest]
Response
The Game of Life requires that a cell responds to its neighbors based on the state of its neighbors.
The following code was implemented to reflect a cell’s responde to its neighbors:
let setReaction coordinate grid:Map<(int * int), Cell> =
let x,y = coordinate
let count = coordinate |> getNeighbors
|> List.filter (fun coordinate -> grid |> getStatus coordinate = Alive)
|> List.length
match count with
| count when count < 2 || count > 3 -> grid |> setCell { X=x; Y=y; State=Dead }
| 3 -> match grid.TryFind coordinate with
| Some cell -> if cell.State = Dead then
grid |> setCell { cell with State=Alive }
else grid
| None -> failwith "Cell doesn't exists"
| _ -> grid
The full logic is as follows:
type State = Alive | Dead
type Cell = { X:int; Y:int; State:State }
type Response = | Die
| Survive
| Resurect
let isNeighbor cell1 cell2 =
let isAbsNeighbor v1 v2 =
match abs (v1 - v2) with
| 0 | 1 -> true
| _ -> false
let isValueNeighbor v1 v2 =
match v1 >= 0
&& v2 >= 0 with
| true -> isAbsNeighbor v1 v2
| _ -> isAbsNeighbor v2 v1
match cell1.X <> cell2.X
|| cell1.Y <> cell2.Y with
| true -> isValueNeighbor cell1.X cell2.X
&& isValueNeighbor cell1.Y cell2.Y
| _ -> false
let createGrid rowCount =
[for x in 1..rowCount do
for y in 1..rowCount do
yield { X=x; Y=y; State=Dead }
]|> List.map (fun c -> (c.X, c.Y), { X=c.X; Y=c.Y; State=Dead })
|> Map.ofList
let setCell cell (grid:Map<(int * int), Cell>) =
grid |> Map.map (fun k v -> match k with
| c when c = (cell.X, cell.Y) -> { v with State=cell.State }
| _ -> v)
let getStatus coordinate (grid:Map<(int * int), Cell>) =
match grid.TryFind coordinate with
| Some cell -> cell.State
| None -> Dead
let getNeighbors (coordinate:int*int) =
let x,y = coordinate
let west = x-1, y
let northWest = x-1, y+1
let north = x, y+1
let northEast = x+1, y+1
let east = x+1, y
let southEast = x+1, y-1
let south = x, y-1
let southWest = x-1, y-1
[west; northWest; north; northEast; east; southEast; south; southWest]
let setReaction coordinate grid:Map<(int * int), Cell> =
let x,y = coordinate
let count = coordinate |> getNeighbors
|> List.filter (fun coordinate -> grid |> getStatus coordinate = Alive)
|> List.length
match count with
| count when count < 2 || count > 3 -> grid |> setCell { X=x; Y=y; State=Dead }
| 3 -> match grid.TryFind coordinate with
| Some cell -> if cell.State = Dead then
grid |> setCell { cell with State=Alive }
else grid
| None -> failwith "Cell doesn't exists"
| _ -> grid
The full tests is as follows:
[<Test>]
let ``cells sharing x-coordinate are neighbors``() =
// Setup
let cell1 = { X=0; Y=0; State=Dead }
let cell2 = { X=0; Y=1 ; State=Dead }
// Verify
cell1 |> isNeighbor cell2
|> should equal true
[<Test>]
let ``cells sharing y-coordinate are neighbors``() =
// Setup
let cell1 = { X=0; Y=1; State=Dead }
let cell2 = { X=1; Y=1; State=Dead }
cell1 |> isNeighbor cell2
|> should equal true
[<Test>]
let ``cell that's right 1 and down 1 is neighbor``() =
// Setup
let cell1 = { X=0; Y=0; State=Dead }
let cell2 = { X=1; Y=(-1); State=Dead }
// Verify
cell1 |> isNeighbor cell2
|> should equal true
[<Test>]
let ``cell that's right 1 and down-0 is neighbor``() =
// Setup
let cell1 = { X=0; Y=0; State=Dead }
let cell2 = { X=1; Y=0; State=Dead }
// Verify
cell1 |> isNeighbor cell2
|> should equal true
[<Test>]
let ``cell that's right 1 and up 1 is neighbor``() =
// Setup
let cell1 = { X=0; Y=0; State=Dead }
let cell2 = { X=1; Y=1 ; State=Dead }
// Verify
cell1 |> isNeighbor cell2
|> should equal true
[<Test>]
let ``cell that's up 1 is neighbor``() =
// Setup
let cell1 = { X=0; Y=0; State=Dead }
let cell2 = { X=0; Y=1 ; State=Dead }
// Verify
cell1 |> isNeighbor cell2
|> should equal true
[<Test>]
let ``cell that's down 1 is neighbor``() =
// Setup
let cell1 = { X=0; Y=0; State=Dead }
let cell2 = { X=0; Y=(-1); State=Dead }
// Verify
cell1 |> isNeighbor cell2
|> should equal true
[<Test>]
let ``cell that's left 1 and up 1 is neighbor``() =
// Setup
let cell1 = { X=0; Y=0; State=Dead }
let cell2 = { X=(-1); Y=1 ; State=Dead }
// Verify
cell1 |> isNeighbor cell2
|> should equal true
[<Test>]
let ``cell that's left 1 and down 1 is neighbor``() =
// Setup
let cell1 = { X=0; Y=0; State=Dead }
let cell2 = { X=(-1); Y=(-1); State=Dead }
// Verify
cell1 |> isNeighbor cell2
|> should equal true
[<Test>]
let ``far away x-coordinates are not neighbors``() =
// Setup
let cell1 = { X=(-1); Y=0; State=Dead }
let cell2 = { X=(+1); Y=0; State=Dead }
// Verify
cell1 |> isNeighbor cell2
|> should equal false
[<Test>]
let ``far away y-coordinates are not neighbors``() =
// Setup
let cell1 = { X=0; Y=(+1); State=Dead }
let cell2 = { X=0; Y=(-1); State=Dead }
// Verify
cell1 |> isNeighbor cell2
|> should equal false
[<Test>]
let ``far away x,y-coordinates are not neighbors``() =
// Setup
let cell1 = { X=(+1); Y=(+1); State=Dead }
let cell2 = { X=(+1); Y=(-1); State=Dead }
// Verify
cell1 |> isNeighbor cell2
|> should equal false
[<Test>]
let ``cells with same coordinates cannot be neighbors``() =
// Setup
let cell1 = { X=0; Y=0; State=Dead }
let cell2 = { X=0; Y=0; State=Dead }
// Verify
cell1 |> isNeighbor cell2
|> should equal false
[<Test>]
let ``create grid``() =
// Test
let rowCount = 3
let grid = rowCount |> createGrid
// Verify
grid.Count |> should equal 9
[<Test>]
let ``find center``() =
// Setup
let rowCount = 3
let grid = rowCount |> createGrid
let getCoordinate coordinate =
match grid.TryFind coordinate with
| Some coordinate -> true
| None -> false
// Test
let found = getCoordinate (2,2)
// Verify
found |> should equal true
[<Test>]
let ``get status``() =
// Setup
let rowCount = 3
let grid = rowCount |> createGrid
// Test
let center = grid |> getStatus (2,2)
// Verify
center |> should equal Dead
[<Test>]
let ``set cell to alive``() =
// Setup
let rowCount = 3
let target = { X=2; Y=2; State=Alive }
let grid = rowCount |> createGrid
|> setCell target
// Test
let result = grid |> getStatus (2,2)
// Verify
result |> should equal Alive
[<Test>]
let ``get neighbors``() =
// Setup
let rowCount = 3
let grid = rowCount |> createGrid
let center = 2,2
let count = center |> getNeighbors
|> List.length
// Verify
count |> should equal 8
[<Test>]
let ``Any live cell with fewer than two live neighbors dies, as if caused by under-population``() =
// Setup
let rowCount = 3
let grid = rowCount |> createGrid
|> setCell { X=2; Y=2; State=Alive }
|> setReaction (2,2)
// Verify
grid |> getStatus (2,2) |> should equal Dead
[<Test>]
let ``Any live cell with two or three live neighbours lives on to the next generation``() =
// Setup
let rowCount = 3
let grid = rowCount |> createGrid
|> setCell { X=1; Y=2; State=Alive }
|> setCell { X=2; Y=2; State=Alive }
|> setCell { X=3; Y=2; State=Alive }
|> setReaction (2,2)
// Verify
grid |> getStatus (2,2) |> should equal Alive
[<Test>]
let ``Any live cell with more than three live neighbours dies, as if by over-population``() =
// Setup
let rowCount = 3
let grid = rowCount |> createGrid
|> setCell { X=1; Y=2; State=Alive }
|> setCell { X=2; Y=2; State=Alive }
|> setCell { X=3; Y=2; State=Alive }
|> setCell { X=3; Y=3; State=Alive }
|> setCell { X=2; Y=1; State=Alive }
|> setReaction (2,2)
// Verify
grid |> getStatus (2,2) |> should equal Dead
[<Test>]
let ``Any dead cell with exactly three live neighbours becomes a live cell, as if by reproduction``() =
// Setup
let rowCount = 3
let grid = rowCount |> createGrid
|> setCell { X=1; Y=2; State=Alive }
|> setCell { X=2; Y=2; State=Dead }
|> setCell { X=3; Y=2; State=Alive }
|> setCell { X=3; Y=3; State=Alive }
|> setReaction (2,2)
// Verify
grid |> getStatus (2,2) |> should equal Alive
Conclusion
In conclusion, I have been crafting the logic required for the Game of Life. In the last article, I documented how I struggled with life cycles. However, I made some progress recently. I showed how I retrieved neighbors of a cell as well as update a cell’s state in response to it’s neighbors.
Scott Nimrod's Blog 