Wednesday, 3 February 2010

John Conway's Game of Life in 32 lines of F#

John Conway's Game of Life is a famous example of a simple cellular automaton that produces remarkably diverse results. The game can be implemented in only 32 lines of F# including real-time visualization using Windows Presentation Foundation as follows:

let count (a: _ [,]) x y =
  let m, n = a.GetLength 0, a.GetLength 1
  let mutable c = 0
  for x in x-1..x+1 do
    for y in y-1..y+1 do
      if x>=0 && x<m && y>=0 && y<n && a.[x, y] then
        c <- c + 1
  if a.[x, y] then c-1 else c

let rule (a: _ [,]) x y =
  match a.[x, y], count a x y with
  | true, (2 | 3) | false, 3 -> true
  | _ -> false

open System.Windows
open System.Windows.Media.Imaging

[<System.STAThread>]
do
  let rand = System.Random()
  let n = 256
  let game = Array2D.init n n (fun _ _ -> rand.Next 2 = 0) |> ref
  let image = Controls.Image(Stretch=Media.Stretch.Uniform)
  let format = Media.PixelFormats.Gray8
  let pixel = Array.create (n*n) 0uy
  let update _ =
    game := rule !game |> Array2D.init n n
    for x in 0..n-1 do
      for y in 0..n-1 do
        pixel.[x+y*n] <- if (!game).[x, y] then 255uy else 0uy
    image.Source <-
      BitmapSource.Create(n, n, 1.0, 1.0, format, null, pixel, n)
  Media.CompositionTarget.Rendering.Add update
  Window(Content=image, Title="Game of Life")
  |> (Application()).Run |> ignore

When run, this program produces output like this:

10 comments:

Benjol said...

It would help if you included the references needed to get this working:

#r "System.dll"
#r "System.Windows.Forms.dll"
#r "PresentationFramework.dll"
#r "PresentationCore.dll"
#r "WindowsBase.dll"

marius said...

I have created something similar, that allows you to setup randomly or with the mouse the initial state of the cells, only that it's longer than 32 lines of code. ;) I also have a parallel version of it.

http://mariusbancila.ro/blog/2008/05/08/game-of-life-in-f/

Flying Frog Consultancy Ltd. said...

@Benjol: You don't need the references to System.dll or System.Windows.Forms.dll, just the last three for WPF.

@Marius: Nice!

Jomo said...

Awesome. If running as a script, you can also get rid of the [STAthread] business. This version comes out at 37 lines:

#r "PresentationFramework.dll"
#r "PresentationCore.dll"
#r "WindowsBase.dll"

let count (a: _ [,]) x y =
let m, n = a.GetLength 0, a.GetLength 1
let mutable c = 0
for x in x-1..x+1 do
for y in y-1..y+1 do
if x>=0 && x=0 && y true
| _ -> false

open System.Windows
open System.Windows.Media.Imaging

let rand = System.Random()
let n = 256
let game = Array2D.init n n (fun _ _ -> rand.Next 2 = 0) |> ref
let image = Controls.Image(Stretch=Media.Stretch.Uniform)
let format = Media.PixelFormats.Gray8
let pixel = Array.create (n*n) 0uy
let update _ =
game := rule !game |> Array2D.init n n
for x in 0..n-1 do
for y in 0..n-1 do
pixel.[x+y*n] <- if (!game).[x, y] then 255uy else 0uy
image.Source <-
BitmapSource.Create(n, n, 1.0, 1.0, format, null, pixel, n)
Media.CompositionTarget.Rendering.Add update
let window = Window(Content=image, Title="Game of Life")
window.Visibility <- Visibility.Visible

A Breaking Change said...

I'm getting all kinds of squigglies and offside-rule violations when I paste this code. I have double checked all the indentations, made sure there are no tabs or other junk characters. Really have no clue how to get this to compile at all.

right after first equals sign on let count there is a red squiggly with "Unexpected character ' ' in binding" but there is no space after the equals sign. I get "Possible incorrect indentation" on the "let" on the next line, blue squigglies under the "y" in the nested "for", blue squiggly after the "do" on that line, and it goes on -- a couple more blue squigglies.

A Breaking Change said...

Maddeningly, if I manually keyboard in exactly the same code, I get no squigglies. I wish you could see my Visual-Studio display, here are two blocks of VISUALLY IDENTICAL code, one with squigglies, one without.

So much for the VISUAL part of visual studio . . . where's notepad / emacs / vim -- anything else please and thanks.

Anonymous said...

@A Breaking Change

I have this problem with other kinds of code snippets all the time. What most likely happened is that when you copied the code, some of the quote characters (') got copied as a special character instead of a "regular" quote character. If you use vim or similar and paste in the same code, you can see the discrepancies easily. However, using Microsoft tools, the quotes look extremely similar (if not identical) despite the fact that their ENCODING is different. It has to do with the way the web browser (or whatever other application you might be copying code from) treats the characters. Microsoft products in particular are good at changing regular single quote characters into "left single quote" or "right single quote" or something else depending on the context, as a visual/rendering enhancement.

Hope this helps keep you from going mad :-)

Anonymous said...

EDIT:
I misread your comment the first time...

It's probably not a quotation mark in this case that caused your problem, but its still some special character encoding issue I bet. If copied from the web, sometimes you get strange artifacts where you would normally expect a simple newline, for instance. Again, just paste your code into VIM or Notepad++ or some similar tool to hopefully see the discrepancy.

As for not being able to see the issue in VisualStudio, and I can't speak to that specifically, but I can say that old versions of NetBeans IDE simply fail to render those special characters, so you can't see them in the source, however the COMPILER can see them no problem, and will loudly complain.

Cheers.

Dennis Smith said...

John Conway's game of Life was implemented in 256 characters on a Apple II computer in Applesoft BASIC and published in the September 1985 issue of Nibble magazine as a "One-Liner" contest winner. Granted it is not as sophisticated as this, but it has all of the elements. It allows you to enter the starting pattern then runs until Ctrl C.

Dennis Smith said...

John Conway's game of Life was implemented in 256 characters on a Apple II computer in Applesoft BASIC and published in the September 1985 issue of Nibble magazine as a "One-Liner" contest winner. Granted it is not as sophisticated as this, but it has all of the elements. It allows you to enter the starting pattern then runs until Ctrl C.