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: automata, bonsai, cellular, code, conway, game, Haskell, kata, life, praxis, programming
