Marius Bancila’s Blog

The Game of Life is a cellular automaton devised by the John Horton Conway in 1970. It is the best-known example of a cellular automaton. It consists of a collection of cells which, based on a few mathematical rules, can live, die or multiply. Depending on the initial conditions, the cells form various patterns throughout the course of the game.

Here you can learn more about the game:

• Game of Life
• Game of Life on Wikipedia

I decided to implement this in F#. With all the code involving the user interface, it was nearly 300 lines of code. Pretty neat!

Using the game

The life’s arena can take several sizes:

• Tiny: 15 x 10
• Small: 30 x 20
• Medium: 60 x 40
• Large: 120 x 80
• Huge: 150 x 100

The size can be changed from the Game > Size menu.

The following commands are available from the menu:

• Reset (Ctrl + R): Resets the game, all cells die
• Randomize (Ctrl + G): Randomly initialize alive cells
• Start/Stop (Ctrl + B): Starts or stops continuos creation of new generations
• Step (Ctrl + N): Creates a new generation of cells

In addition the followin commands are available from the File menu:

• Save (Ctrl + S): saves game to a bitmap file called gameolife_.bmp; this file is created in the working folder
• Save As… (Ctrl + Shift + S): saves the game to a file, giving you the possibility to chose the location and format (bmp, jpg, gif and png)

Note: The state of the game can be changed (killing cells, making others alive) simply by clicking with the mouse on the game panel.

Implementation in F#

Some comments on the implementation of the game. For more have a look at the code.

I defined two records, one called Cell and one called World. The cell reprezents a cell and has a flag called Alive (which is self explanatory), and World represents the ‘arena of life’, containing a matrix of Cells.

type Cell =
 { Alive : bool;}

type World =
 { Width : int;
   Height : int;
   Cells: Cell[,];}

Various arena sizes are defined in a descriminated union and the mapping between that and values for width and height are done in this function:

type GameSize =
   | Tiny
   | Small
   | Medium
   | Large
   | Huge

let sizeMapping (size:GameSize) =
   match size with
   | Tiny -> (15,10)
   | Small -> (30, 20)
   | Medium -> (60, 40)
   | Large -> (120, 80)
   | Huge -> (150, 100)

A next generation of cells is computed based on the rules of the game. For each cell the number of alived neighbors is computed and then the state of the cell is changes (if necessary).

let nextGeneration (world:World) =
   let alive = {new Cell with Alive = true}
   let dead = {new Cell with Alive = false}
   let newcells = Array2.create world.Width world.Height dead
   for i = 0 to world.Width - 1 do
      for j = 0 to world.Height - 1 do
         let ncount = neighbors world j i
         match world.Cells.(i,j).Alive with
         | true -> if ncount = 2 || ncount = 3 then newcells.(i,j) <- alive
                   else newcells.(i,j) <- dead
         | _ -> if ncount = 3 then newcells.(i,j) <- alive
                  else newcells.(i,j) <- dead
      done
   done
   { world with Cells = newcells}

For computing the number of neighbors, I considered 9 cases:

• cell is one of the four corners
• cell is on one of the four edges (not a corner)
• cell is anywhere else in the matrix

Depending on this position a list of neighbors is created and folded to compute the number of alive neighboring cells.

let sum (neighbors:Cell list) =
   neighbors |> List.fold_left (fun sum x -> if x.Alive then sum+1 else sum) 0

let neighbors (world:World) row col =
   match row, col with
   | _,_ when row = 0 && col = 0 -> sum [world.Cells.(1,0);world.Cells.(1,1);world.Cells.(0,1)]
   | _,_ when row = 0 && col = world.Width-1 -> sum [world.Cells.(world.Width-2,0);world.Cells.(world.Width-2,1);world.Cells.(world.Width-1,1)]
   | _,_ when row = world.Height-1 && col = 0 -> sum [world.Cells.(0, world.Height-2);world.Cells.(1, world.Height-2);world.Cells.(1,world.Height-1)]
   | _,_ when row = world.Height-1 && col = world.Width-1 -> sum [world.Cells.(world.Width-1, world.Height-2);world.Cells.(world.Width-2, world.Height-2);world.Cells.(world.Width-2,world.Height-1)]
   | _,_ when row = 0 && col > 0 && col < world.Width-1 -> sum [world.Cells.(col-1,0);world.Cells.(col-1,1);world.Cells.(col,1);world.Cells.(col+1,1);world.Cells.(col+1,0);]
   | _,_ when row = world.Height-1 && col > 0 && col < world.Width-1 -> sum [world.Cells.(col-1,row);world.Cells.(col-1,row-1);world.Cells.(col,row-1);world.Cells.(col+1,row-1);world.Cells.(col+1,row);]
   | _,_ when col = 0 && row > 0 && row < world.Height-1 -> sum [world.Cells.(0,row-1);world.Cells.(1,row-1);world.Cells.(1,row);world.Cells.(1,row+1);world.Cells.(0,row+1);]
   | _,_ when col = world.Width-1 && row > 0 && row < world.Height-1 -> sum [world.Cells.(col,row-1);world.Cells.(col-1,row-1);world.Cells.(col-1,row);world.Cells.(col-1,row+1);world.Cells.(col,row+1);]
   | _,_ -> sum [world.Cells.(col-1,row-1);world.Cells.(col,row-1);world.Cells.(col+1,row-1);world.Cells.(col+1,row);world.Cells.(col+1,row+1);world.Cells.(col,row+1);world.Cells.(col-1,row+1);world.Cells.(col-1,row);]

The rest is basically user interface code. But I made a parallel version of the game, when then computation of the next generation of cells is parallelized with the Parallel FX framework. Here is how the function looks.

let nextGeneration (world:World) =
   let alive = {new Cell with Alive = true}
   let dead = {new Cell with Alive = false}
   let newcells = Array2.create world.Width world.Height dead
   Parallel.For(0, world.Width, (fun i ->
      for j = 0 to world.Height - 1 do
         let ncount = neighbors world j i
         match world.Cells.(i,j).Alive with
         | true -> if ncount = 2 || ncount = 3 then newcells.(i,j) <- alive
                   else newcells.(i,j) <- dead
         | _ -> if ncount = 3 then newcells.(i,j) <- alive
                  else newcells.(i,j) <- dead
      done
   ))
   { world with Cells = newcells}

Source code

Here are the available downloads

• un-parallelized version, GameOfLife.zip
• parallelized version, GameOfLife.Parallel.zip

automata, F#, gameoflife, parallel Hits for this post: 15889 .

Finally I managed to scan some printed pictures from Seattle. During the party at the Experience Music Project, some of us had some fun on stage. Here is the proof of performing “We Will Rock You” on stage. From left to right, ovidiucucu, gstercken, Marc G, me, VictorN and Brad.

And this time VictorN, Marc G and myself.

We had a lot of fun!

Hits for this post: 18110 .

In this post I’ll show some F# constructs, all put together in a simple application that modifies file names that match a criteria. This would be an application that is started from a console with the following command line options:

filesmod.exe -f < folder > [-r] -p < pattern > [-pre < prefix >] [-suf < suffix >]
  -f < folder>   specifies the folder where the files are located
  -r            indicates that the specified folder should be parsed
                recursively
  -p < pattern>  indicates a pattern used for filtering files
  -pre < prefix> indicats a prefix to the added to all files
                that match the criteria
  -suf < suffix> indicats a suffix to the added to all files
                that match the criteria

Reading command line

The command line arguments can be retrieved using the Environment class from the .NET framework. This class has a static method called GetCommandLineArgs() that returns a list of the passed arguments.
We can define a type that contains all the parsed arguments.

type CommandOptions =
    { mutable Folder : string;
      mutable Recursive : bool;
      mutable Pattern : string;
      mutable Prefix : string;
      mutable Suffix : string;}

This mutable record can be instantiated, and the value can be mutated while parsing the arguments. This is how you instantiate it:

   let cmdops =
      { new CommandOptions
        with Folder = String.Empty
        and Recursive = false
        and Pattern = String.Empty
        and Prefix = String.Empty
        and Suffix = String.Empty }

Parsing the command line arguments can be done with pattern matching. This is the equivalent of switches in C+/C#/Java, only more powerful.
Basically, I’m checking each argument, and if it’s a flag in the command line (-f, -r, -p, -pre, -sub) I take the next argument and put it in the appropriate property of the record.

   try
      let args = Environment.GetCommandLineArgs()
      for i = 0 to args.Length-1 do
         match args.(i) with
            | "-f" when i+1 <= args.Length-1 -> cmdops.Folder <- args.(i+1)
            | "-r" -> cmdops.Recursive <- true
            | "-p" when i+1 <= args.Length-1 -> cmdops.Pattern <- args.(i+1)
            | "-pre" when i+1 <= args.Length-1 -> cmdops.Prefix <- args.(i+1)
            | "-suf" when i+1 <= args.Length-1 -> cmdops.Suffix <- args.(i+1)
            | _ -> ()
      done
   with e -> printfn "%s" e.Message

There are two things you could notice here. The first is the try … with block that makes sure any possible exception is caught.
The second is the quarding the rules with the contidion that the current argument is not the last one in the list. (-f should be followed by a folder, -suf by a suffix, etc.)
You can see what in the when statement:

when i+1 <= args.Length-1

Getting the files in a directory

We can get all files in a folder, using the following algorithm:

• get all the files in the current folder
• get all the sub-folders in the current folder and for each of them apply the algorithm again

That is spelled "recursion"!. Our function should take several arguments: the path of a folder, a pattern for mathing filenames and a flag indicating whether sub-folders should be parsed or not.

let rec allFiles dir pattern r =
    seq
        { for file in Directory.GetFiles(dir, pattern) do
            yield file
          if r then
            for subdir in Directory.GetDirectories(dir) do
                for file in allFiles subdir pattern r do
                    yield file }

The above function is recursive and returns a sequence of file names. Sequences are lazy, which means that successive elements are computed and returned on demand, when they are needed.
That is the opposite of a list or array, whose elements are created at once. The keyword 'yield' here is used to return a new value as the sequence is iterated.

Processing the files

To process the files, we simply iterate over the sequence of files from the specified folder, match it against the provided parttern, and if there is a match, apply the prefix and/or suffix transformation.

   for name in (allFiles cmdops.Folder "*.*" cmdops.Recursive) do
      let file = new FileInfo(name)
      if(Regex.IsMatch(file.Name, cmdops.Pattern, RegexOptions.Singleline)) then
        let filename = file.Name.Substring(0, file.Name.LastIndexOf('.'))
        let newname = file.Directory.FullName+"\\"+cmdops.Prefix+filename+cmdops.Suffix+file.Extension
        System.IO.File.Move(file.FullName, newname)
        printfn "%s -> %s" file.FullName newname
   done

Well, I have two cores on my machine, and since the Parallel FX framework is available, I like to use it. So here is the parallel version of that:

       try
          Parallel.ForEach(allFiles cmdops.Folder "*.*" cmdops.Recursive, fun name ->
             let file = new FileInfo(name)
             if(Regex.IsMatch(file.Name, cmdops.Pattern, RegexOptions.Singleline)) then
                let filename = file.Name.Substring(0, file.Name.LastIndexOf('.'))
                let newname = file.Directory.FullName+"\\"+cmdops.Prefix+filename+cmdops.Suffix+file.Extension
                System.IO.File.Move(file.FullName, newname)
                printfn "%s -> %s" file.FullName newname)
       with e -> printfn "%s" e.InnerException.Message

The provided (via command line) pattern is a regular expression. Initially, the folder is checked for all files and then these files are matched against this regular expression.

As I was saying in a previous post, if you use PFX, you have to add a reference to the System.threading.dll assembly, which requires a reference to the System.Core.dll assembly.
That should be specified at the project's propertyes.

-r C:\WINDOWS\assembly\GAC_MSIL\System.Core\3.5.0.0__b77a5c561934e089\System.Core.dll -r "C:\Program Files\Microsoft Parallel Extensions Dec07 CTP\System.Threading.dll"

Putting all together

All that put together looks like this:

#light

open System
open System.IO
open System.Text.RegularExpressions

open System.Threading

let rec allFiles dir pattern r =
    seq
        { for file in Directory.GetFiles(dir, pattern) do
            yield file
          if r then
            for subdir in Directory.GetDirectories(dir) do
                for file in allFiles subdir pattern r do
                    yield file }

let showUsage() =
    printfn "filesmod.exe -f < folder > [-r] -p < pattern > [-pre < prefix >] [-suf < suffix >]"
    printfn "  -f < folder >\tspecifies the folder where the files are located"
    printfn "  -r\t\tindicates that the specified folder should be parsed\n\t\trecursively"
    printfn "  -p < pattern >\tindicates a pattern used for filtering files"
    printfn "  -pre < prefix >\tindicats a prefix to the added to all files\n\t\tthat match the criteria"
    printfn "  -suf < suffix >\tindicats a suffix to the added to all files\n\t\tthat match the criteria"

type CommandOptions =
    { mutable Folder : string;
      mutable Recursive : bool;
      mutable Pattern : string;
      mutable Prefix : string;
      mutable Suffix : string;}

let main()=
   let cmdops =
      { new CommandOptions
        with Folder = String.Empty
        and Recursive = false
        and Pattern = String.Empty
        and Prefix = String.Empty
        and Suffix = String.Empty }

   try
      let args = Environment.GetCommandLineArgs()
      for i = 0 to args.Length-1 do
         match args.(i) with
            | "-f" when i+1 <= args.Length-1 -> cmdops.Folder <- args.(i+1)
            | "-r" -> cmdops.Recursive <- true
            | "-p" when i+1 <= args.Length-1 -> cmdops.Pattern <- args.(i+1)
            | "-pre" when i+1 <= args.Length-1 -> cmdops.Prefix <- args.(i+1)
            | "-suf" when i+1 <= args.Length-1 -> cmdops.Suffix <- args.(i+1)
            | _ -> ()
      done
   with e -> printfn "%s" e.Message

   if ((String.IsNullOrEmpty(cmdops.Prefix) && String.IsNullOrEmpty(cmdops.Suffix)) ||
        String.IsNullOrEmpty(cmdops.Pattern) ||
        String.IsNullOrEmpty(cmdops.Folder)) then
        showUsage()
   else
       try
          Parallel.ForEach(allFiles cmdops.Folder "*.*" cmdops.Recursive, fun name ->
             let file = new FileInfo(name)
             if(Regex.IsMatch(file.Name, cmdops.Pattern, RegexOptions.Singleline)) then
                let filename = file.Name.Substring(0, file.Name.LastIndexOf('.'))
                let newname = file.Directory.FullName+"\\"+cmdops.Prefix+filename+cmdops.Suffix+file.Extension
                System.IO.File.Move(file.FullName, newname)
                printfn "%s -> %s" file.FullName newname)
       with e -> printfn "%s" e.InnerException.Message

   Console.WriteLine("Press any key to continue...")
   Console.ReadKey()

main()

Of course, the options available in this application (on file name changes) are pretty limited, but that can be extended at will.

files, parallel, pattern, record, recursive, regex Hits for this post: 17294 .