Compact game of life implementation

Question

I am learning F# and implemented Conway's Game of Life as an exercise (There are also other implementations on CodeReview). I have tried to forget all my object-oriented background and practice "functional thinking".

Any feedback is welcome, especially related to alternative (more functional) solutions.

open System

[<EntryPoint>]
let main argv = 

    let rows = 30
    let columns = 30    
    let size = rows*columns

    let combine listX listY = [
        for x in listX do
        for y in listY do
        yield x, y ]

    let createRandomBoard =
        let rnd = new Random(10)
        [1..size] 
        |> List.map (fun x -> if rnd.NextDouble() < 0.2 then 1 else 0) 
        |> List.toArray

    let board = createRandomBoard

    let toBoardLine (line : int[]) : string =
        line |> Array.fold (fun agg i -> agg + (if i = 1 then "X" else ".")) ""        

    let drawBoard () =
        [0..rows-1] 
        |> List.iter (fun y -> printfn "%A" (board.[y*rows..y*rows+columns-1] |> toBoardLine))               

    let indexToCoordinates index = (index % columns + 1, index / columns + 1)
    let coordinatesToIndex (x, y) = (y - 1) * columns + (x - 1)

    let getLivingNeighboursCount idx =
        let x, y = indexToCoordinates idx
        let (minX, maxX) = (if x = 1 then columns else x - 1), (if x = columns then 1 else x + 1)
        let (minY, maxY) = (if y = 1 then rows else y - 1), (if y = rows then 1 else y + 1)
        combine [minX; x; maxX] [minY; y; maxY]
        |> List.filter (fun com -> com <> (x,y))
        |> List.map coordinatesToIndex 
        |> List.map (fun x -> board.[x]) 
        |> List.sum

    let indexToNewState idx =
        let state = board.[idx]
        let livingNeigbours = getLivingNeighboursCount idx
        (if livingNeigbours = 3 || (livingNeigbours = 2 && state = 1) then 1 else 0)

    let updateState () =
        [0..size-1]
        |> List.iter (fun idx -> (Array.set board idx (indexToNewState idx)))

    while true do
        Console.Clear();
        updateState ()
        drawBoard ()
        System.Threading.Thread.Sleep(200);

    Console.ReadLine()
    0

Answer 1

With only a couple of hours ahead of you in my experience with F#, I find the essence of your code fairly functional, although the graphic output is hard to grasp as it has a lot of flicker.

Below find a gentle review of your code with improvements (or at least another way to do the things) and inline comments. I've tried to improve the graphic output by using colors and a distinct update of the cells only when they change.

let playGOL rows columns =
    let mutable doContinue = true
    let size = rows*columns

    let alive = ConsoleColor.Green // Console colors as cell values instead of int/strings
    let dead = ConsoleColor.Red

    let combine listX listY = [
        for x in listX do
            for y in listY do
                yield x, y ]

    let board = // create the board directly
        let rnd = new Random()
        [| for x in 1..size -> if rnd.NextDouble() < 0.2 then alive else dead |] // Initialize the array directly instead of iterate over a list then converted to array

    let indexToCoordinates index = index % columns + 1, index / columns + 1  // No need for parentheses
    let coordinatesToIndex (x, y) = (y - 1) * columns + (x - 1)

    // Instead of using chars I use background colors 
    let updateCell cellIndex state =
        let x, y = indexToCoordinates cellIndex
        Console.CursorLeft <- x
        Console.CursorTop <- y
        Console.BackgroundColor <- state
        printf " "        
        Console.BackgroundColor <- ConsoleColor.Black    
        doContinue <- true

    let drawBoard () =
        board |> Array.iteri (fun i ch -> updateCell i ch) // Iterate over the board itself instead of a list

    let getLivingNeighboursCount idx =
        let x, y = indexToCoordinates idx
        let minX, maxX = (if x = 1 then columns else x - 1), (if x = columns then 1 else x + 1)
        let minY, maxY = (if y = 1 then rows else y - 1), (if y = rows then 1 else y + 1)
        combine [minX; x; maxX] [minY; y; maxY]
        |> List.filter (fun com -> com <> (x,y))
        |> List.map (fun x -> board.[coordinatesToIndex x]) // Map directly from coordinates to value
        |> List.sumBy (fun x -> if x = alive then 1 else 0)

    let indexToNewState idx =
        let state = board.[idx]
        let livingNeighbours = getLivingNeighboursCount idx

        if livingNeighbours = 3 || livingNeighbours = 2 && state = alive then 
                if state <> alive then updateCell idx alive // Instead of opdating the whole board just update the changed cell
                alive 
            else 
                if state <> dead then updateCell idx dead // Instead of opdating the whole board just update the changed cell
                dead

    let updateState () =
        doContinue <- false
        board |> Array.iteri (fun idx state -> (Array.set board idx (indexToNewState idx)))  // Use the board itself to iterate over

    drawBoard()
    while doContinue do
        updateState ()
        System.Threading.Thread.Sleep(100);

    Console.ReadLine() |> ignore

let go() =
    let size = 40
    Console.WindowHeight <- size + 5
    Console.WindowWidth <- size + 5
    playGOL size size

---

That said I think both solutions suffer from a generation problem (I'm not a GOL-expert so I may be wrong):

As the image shows getLivingNeighboursCount() checks against two different generations because the board cells are successively updated through the calls to Array.set in updateState() resulting in a false new state. The solution is to create a new board per generation and recursively check those while creating the next generation board:

let playGOL rows columns =
    let size = rows*columns

    let alive = ConsoleColor.Green // Console colors as cell values instead of int/strings
    let dead = ConsoleColor.Red

    let combine listX listY = [
        for x in listX do
            for y in listY do
                yield x, y ]

    let indexToCoordinates index = index % columns + 1, index / columns + 1  // No need for parentheses
    let coordinatesToIndex (x, y) = (y - 1) * columns + (x - 1)

    // Instead of using chars I use background colors 
    let updateCell cellIndex state =
        let x, y = indexToCoordinates cellIndex
        Console.CursorLeft <- x
        Console.CursorTop <- y
        Console.BackgroundColor <- state
        printf " "        
        Console.BackgroundColor <- ConsoleColor.Black    

    let drawBoard board =
        board |> Array.iteri (fun i ch -> updateCell i ch) // Iterate over the board itself instead of a list

    let getLivingNeighboursCount idx (board: ConsoleColor[]) =
        let x, y = indexToCoordinates idx
        let minX, maxX = (if x = 1 then columns else x - 1), (if x = columns then 1 else x + 1)
        let minY, maxY = (if y = 1 then rows else y - 1), (if y = rows then 1 else y + 1)
        combine [minX; x; maxX] [minY; y; maxY]
        |> List.filter (fun com -> com <> (x,y))
        |> List.map (fun x -> board.[coordinatesToIndex x]) // Map directly from coordinates to value
        |> List.sumBy (fun x -> if x = alive then 1 else 0)

// Replaced according to JanDotNet's comments
//            let indexToNewState idx (oldBoard: ConsoleColor[]) newBoard =
//            let state = oldBoard.[idx]
//            let livingNeighbours = oldBoard |> getLivingNeighboursCount idx
//    
//            if livingNeighbours = 3 || livingNeighbours = 2 && state = alive then 
//                Array.set newBoard idx alive
//                if state <> alive then 
//                    updateCell idx alive // Instead of opdating the whole board just update the changed cell
//                    true
//                else
//                    false
//            else 
//                Array.set newBoard idx dead
//                if state <> dead then 
//                    updateCell idx dead // Instead of opdating the whole board just update the changed cell
//                    true
//                else
//                    false
//    
//        let updateState (board: ConsoleColor[]) =
//            let rec updater bdr =
//                System.Threading.Thread.Sleep(100);
//                let nextBoard = [| for x in 1..size -> alive |]
//                let allResults = bdr |> Array.mapi (fun idx state -> indexToNewState idx bdr nextBoard)
//                let result = allResults |> Array.tryFind (fun res -> res)
//                match result with
//                | Some(true) -> updater nextBoard
//                | _ -> ignore
//            updater board


    let indexToNewState idx (oldBoard: ConsoleColor[]) newBoard =
        let state = oldBoard.[idx]
        let livingNeighbours = oldBoard |> getLivingNeighboursCount idx

        let newState = if livingNeighbours = 3 || livingNeighbours = 2 && state = alive then alive else dead
        Array.set newBoard idx newState
        if newState <> state then
            updateCell idx newState
            true
        else
            false

    let updateState (board: ConsoleColor[]) =
        let rec updater bdr =
            System.Threading.Thread.Sleep(100);
            let nextBoard = [| for x in 1..size -> alive |]
            let result = bdr |> Array.mapi (fun idx state -> indexToNewState idx bdr nextBoard) |> Array.exists (fun res -> res)
            match result with
            | false -> ignore
            | true -> updater nextBoard
        updater board

    let board = // create the board directly
        let rnd = new Random(10)
        [| for x in 1..size -> if rnd.NextDouble() < 0.2 then alive else dead |] // Initialize the array directly instead of iterate over a list then converted to array

    drawBoard board
    updateState board |> ignore

    Console.ReadLine() |> ignore

let go() =
    let size = 30
    Console.WindowHeight <- size + 5
    Console.WindowWidth <- size + 5
    playGOL size size

Answer 2

Some remarks :

• your combine function is in fact List.zip, you might want to explore the Array and List sections of the standard library, they are full of very useful functions that will speed-up your development.

• createRandomBoard is not a function and thus will always be the same array (arrays being mutable, you might come across some unwanted side effects if you use it twice in the same code). It could be rewritten using Array.init :

  let createRandomBoard () =
     let rnd = new Random(10)
     Array.init size (fun _ -> if rnd.NextDouble() < 0.2 then 1 else 0)
  

• you are using '0' and '1' to model your two states, why not booleans ? It would eliminate the need for some tests.

• Array.set ar ind x can be rewritten as ar.[ind] <- x (but, as Foggy Finder said, you would lose some type inference if ar has not been identified as an array before)

• forms such as :

  [1..n] |> List.iter f
  

  are indeed functional but inefficient and, I believe, not as readable as using a loop. F# is especially powerful because it is a hybrid language (and not a purely functional one) : don't hesitate to leverage arrays and loops when it makes sense.