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):

enter image description here

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

• JanDotNet: Thanks for the great review! 1.) Your board with the console colors looks really nice ;) 2.) You are absolutely right about the bug with using the state of the updated board to calculating the new state (what a beginner's mistake)... ;). 3) You are using some cool features that i didn't know (e.g. array initializations like[| for x in 1..size -> alive |] or the ignore function)
• JanDotNet: You can replace the large nested if else statement in function indexToNewState with a shorter version by determining newState first. (let newState = ...; Array.set newBoard idx newState; if state <> newState then updateCell idx newState; state <> newState)
• JanDotNet: Is there a special reason why you are using Array.tryFind in combination with match result with... instead of Array.exists in combination with if result then updater nextBoard? (e.g. does it help the compiler recognizing tail recursion?)
• user73941: @JanDotNet: As for the ugly if statements you are completely right. I knew it was ugle, but I didn't have the time to rethink it properly. As for tryFind vs. exists: exists is much nicer - no good reason for my choice. I took the freedom to update my code with your suggestions.
• user110704: instead of board |> Array.iteri (fun i ch -> updateCell i ch) why not just board |> Array.iteri (updateCell)?

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.

• user110704: let me leave a few comments:
• user110704: 1. let rnd = new Random(10) <- sequence will begin with the same value
• user110704: 2. Array.set ar ind x can be rewritten as ar.[ind] <- , well, it can be useful for type inference.
• JanDotNet: Thanks for your feedback! List.zip combines the n'th element of list A with the n'th element of list A. However, my custom combine function combines each element of list A with each element of list B. Therefore it's not the same IMHO (Or do you have special trick in mind? ;))
• JanDotNet: The other tips are helpful... I really like functional programming - but it needs a lot of rethinking. So, thanks for helping :)