Posts Tagged ‘life’

Programming Praxis – A Dozen Lines Of Code

January 24, 2012

In today’s Programming Praxis exercise, our goal is to make any program we want, as long as it’s cool and it fits within 12 lines of code. I decided to make an implementation of Conway’s Game of Life: it’s interesting, it’s visual, it’s Turing complete… how much cooler can you get? Let’s get started, shall we?

First, some imports. I’m not counting these as lines of code since to me a line of code is something that can contain a bug.

import qualified Data.List.Key as K
import qualified Data.Map as M

First we define the rule that the game of life is based on: cells stay alive if they have 2 or 3 neighbors, and they become alive if they have 3 neighbors.

rule (cy,cx) m = elem ns $ if alive (cy,cx) then [2,3] else [3] where
    ns = sum [1 | y <- [-1..1], x <- [-1..1], (y,x) /= (0,0), alive (cy+y,cx+x)]
    alive c = M.lookup c m == Just 'x'

We calculate the next generation of a grid by determining the rectangle that holds the active cells, adding a one-cell border (since that’s the furthest influence distance) and calculating the new state for each cell in the resulting rectangle.

step m = if null on then M.empty else M.fromList
    [((y,x),if rule (y,x) m then 'x' else '.') | y <- range fst, x <- range snd]
    where on = M.keys $ M.filter (== 'x') m
          range f = [minimum (map f on) - 1..maximum (map f on) + 1]

Next, we need some functions to load and show a generation:

load s = M.fromList [((y,x),c) | (y,l)<-zip [0..] $ lines s, (x,c)<-zip [0..] l]

display = mapM_ (putStrLn . map snd) . ([] 🙂 . K.group (fst . fst) . M.assocs

The program reads the input from a text file that holds the starting situation, e.g.

.....
.xxx.
.x...
..x..
.....

and then prints all of the subsequent generations until the pattern stabilizes, i.e. it finds two subsequent identical generations.

main = mapM_ (display . snd) . takeWhile (uncurry (/=)) .
    (\l -> zip l $ tail l) . iterate step . load =<< readFile "life.txt"

And that’s it. A cool little program that’s even one line under our budget of 12.

Programming Praxis – Conway’s game of life

May 11, 2010

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......