Programming Praxis – Conway’s game of life

With the author of Programming Praxis currently hospitalized, I’ll be posting some programming exercises in his stead until he’s recovered.

Conway’s game of life is the most well-known example of cellular automata. It consists of a 2D grid where each cell is either alive or dead. Alive cells stay alive if they have 2 or 3 alive neighbors, otherwise they die. Dead cells become alive when they have 3 alive neighbors. Other rule variations exist, but Conway’s version is the most commonly used one. These simple rules result in a lot of complexity. In fact, the game of life is equivalent to a universal Turing machine.

Theoretically, Conway’s game of life takes place on an infinite grid, but for practical reasons the size of the grid is often limited, with cells beyond the edges being assumed dead.

In today’s exercise, your task is to write an algorithm that takes a starting situation and can produce an arbitrary number of subsequent generations. When you are finished, you are welcome to read a suggested solution below, or to post your own solution or discuss the exercise in the comments below (to post code, put it between [code][/code] tags).

 
 

First, some imports.

import Data.List.Split
import qualified Data.Map as M

Cells stay/become alive if they have 3 neighbors, or 2 if they’re already alive. Anything else dies.

rule :: (Num a) => Char -> a -> Bool
rule c n = c == 'x' && n == 2 || n == 3

Since the algorithm needs to check a cell’s neighbors, we need to know what they are.

neighbours :: (Int, Int) -> [(Int, Int)]
neighbours (y,x) = [(y', x') | y' <- [y-1..y+1], x' <- [x-1..x+1],
                               (y', x') /= (y, x)]

We will need a way to load the starting situation.

load :: String -> M.Map (Int, Int) Char
load = M.fromList . concat . zipWith (\y -> zipWith (\x c ->
           ((y, x), c)) [1..]) [1..] . lines

To obtain the next generation, we just apply the rule to every cell.

next :: M.Map (Int, Int) Char -> M.Map (Int, Int) Char
next b = M.mapWithKey (\k a -> if rule a . length .
             filter (\p -> M.findWithDefault '.' p b == 'x') $
             neighbours k then 'x' else '.') b

Next, we need a function to show a generation in a more readable format.

display :: M.Map (Int, Int) Char -> String
display b = unlines . chunk (snd . fst $ M.findMax b) $ M.elems b

And, finally, something to show multiple subsequent generations.

run :: Int -> M.Map (Int, Int) Char -> IO ()
run n = mapM_ (putStrLn . display) . take n . iterate next

Let’s test to see if everything’s working correctly.

main :: IO ()
main = run 10 $ load ".........\n\
                     \.xx......\n\
                     \.xx..xxx.\n\
                     \.....x...\n\
                     \......x..\n\
                     \..x......\n\
                     \..x......\n\
                     \..x......"

If you implemented everything correctly, the last generation should look like this:

.....xx..
....x..x.
.....xx..
.........
..xx.....
.x..x....
.x.x.....
..x......

Tags: , , , , , , , , , ,

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


Follow

Get every new post delivered to your Inbox.

Join 35 other followers

%d bloggers like this: