How do I transform the state of specific elements within a collection that's always changing?

Question

How do I transform the state of specific elements within a collection that's always changing?

I'm trying to make the following test pass:

[<Test>]
let ``Any live cell with fewer than two live neighbors dies, as if caused by under-population``() =
    // Setup
    let rowCount = 3
    let result = rowCount |> createGrid
                          |> cycle
                          |> cycle
                          |> getStatus (2,2)
    // Verify
    result |> should equal Dead

The first cycle will result in the center cell being alive:

[<Test>]
let ``center cell is the first to live``() =
    // Setup
    let rowCount = 3
    let result = rowCount |> createGrid
                          |> cycle 
                          |> getStatus (2,2)
    // Verify
    result |> should equal Alive

However, the second cycle should apply the rules to each cell within the grid of cells.

This is where I am stuck. Specifically, I do not know of an appropriate approach for transforming a grid each time the state of one of the cells within the grid changes.

Consider the following code:

let cycle (grid:Map<(int * int), Cell>) =

    let isBeginnng = grid |> Map.forall (fun _ cell -> cell.State = Dead)
    match isBeginnng with
    | true  ->  grid |> setCell { X=2; Y=2; State=Alive }
    | false ->  grid // ?? idk

Hence, each time a cell changes state other cells will react by also changing state.

As a result, I find myself spinning my wheels.

The full code is here:

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 cycle (grid:Map<(int * int), Cell>) =

    let isBeginnng = grid |> Map.forall (fun _ cell -> cell.State = Dead)
    match isBeginnng with
    | true  ->  grid |> setCell { X=2; Y=2; State=Alive }
    | false ->  grid // ??

Answer 1

To extend the previous answer a bit on the conceptual level: It may be useful to think about this in smaller pieces (i.e., functions). Thus, how would you update a single cell, given the current state of the grid and a coordinate? For the rule from your test, you would need to look at the neighbours of that coordinate (i.e., use getNeighbors), find out their status (getStatus), collect only those that are alive (List.filter) and then count them (List.length) and make a decision based on that. If you string all of that together, you obtain the following function:

let cycleOneCell grid coord cell =
    let aliveNeighbours = 
        getNeighbors coord
        |> List.filter (fun n -> getStatus n grid = Alive)
    if List.length aliveNeighbours < 2 then
        { cell with State = Dead }
    else
        cell

Now you know how to update one cell. Now your task is to apply this update to all cells, which is a Map, i.e., you would use Map.map. I'll leave that part of your homework to you :-)

Answer 2

I think you use Map.map here to create a new Map every time you want to change the data. After all, Map is immutable. If you want a mutable collection, you should use a Dictionary. But first let's get a function that lets us update the state given a Cell's state and the state of its neighbors. Here's a simple one that makes it so that your cell always dies.

let update (cell:Cell) (neighborState:State list) = 
    match cell.State with
    | Alive -> {cell with State = Dead}
    | Dead -> {cell with State = Dead}

Then we want to update the pattern match of your cycle function to iterate through the grid, get the status of the neighbors of every grid location, and then update it appropriately with the previous update function.

let cycle (grid:Map<(int * int), Cell>) =

    let isBeginnng = grid |> Map.forall (fun _ cell -> cell.State = Dead)
    match isBeginnng with
    | true  ->  grid |> setCell { X=2; Y=2; State=Alive }
    | false ->  grid |> Map.map (fun location cell -> location
                                                        |>getNeighbors 
                                                        |> List.map ( fun neighbor -> getStatus neighbor grid)
                                                        |> update cell
                                                        )

This will create a new grid with the new updated values based on the function how you want to update. Since this looks to be the game of life, you can program in the rules for that through changing the update function to calculate the # of aliveNeighbors in the neighborState list and then using some if statements.

Note also that your getNeighbors function has a bug with the edges of the grid because for example getNeighbors (2,1) returns [(1, 1); (1, 2); (2, 2); (3, 2); (3, 1); (3, 0); (2, 0); (1, 0)], of which (3, 0); (2, 0); (1, 0) are not valid grid positions.

Edit: Never mind your getStatus function actually already accounts for that, I'm dumb.