Posts Tagged ‘sierpinski’

Programming Praxis – Cellular Automata

May 15, 2009

Today‚Äôs Programming Praxis problem is about cellular automata. Let’s dive in.

As usual, our imports:

import Data.Bits
import Data.List

Programming Praxis’ author uses ones and zeros to represent on and off cells. That works, but you run the risk of accidentally having another number somewhere and crashing your program. We Haskell programmers like our type safety, so we’re going to use booleans. First we need a function to get the successor of a group of cells:

successor :: Int -> [Bool] -> Bool
successor r bs = testBit r . sum $
                 zipWith (shiftL . fromEnum) (reverse bs) [0..]

Using that, we can generate the next row as follows:

nextRow :: Int -> [Bool] -> [Bool]
nextRow r xs = map (successor r) . take (length xs) . transpose .
               take 3 . iterate (drop 1) $ [head xs] ++ xs ++ [last xs]

Since lists of booleans are not that easy to read, let’s use spaces and Xs.

displayRow :: [Bool] -> String
displayRow = intersperse ' ' . map (\b -> if b then 'X' else ' ')

Each run starts with one active cell and simply consists of repeating nextRow as often as needed.

cells :: Int -> Int -> [String]
cells r h = map displayRow . take (h + 1) . iterate (nextRow r) $
            replicate h False ++ [True] ++ replicate h False

And finally we test out program. Let’s make a lovely Sierpinski triangle:

main :: IO ()
main = mapM_ putStrLn $ cells 82 15

Done. 10 lines of code. Not bad.