sierpinski.hs

vertices :: Integer -> Integer -> Integer -> [(Integer, Integer)]
vertices 1 w h = [(quot (w+1) 2, h)]
vertices n w h = foldl (\acc v -> acc ++ [((fst v) - dx, snd v), (fst v, (snd v) - dy), ((fst v) + dx, snd v)]) [] p
               where p = vertices (n-1) w h
                     dx = quot (w+1) (2^n)
                     dy = quot h (2^(n-1))

inrange :: Integer -> Integer -> Integer -> Bool
inrange 0 x y = abs (x - 32) < y
inrange n x y = inrange (n-1) x y && (foldl (\acc v -> acc && (not (abs (x-(fst v)) <= (snd v) - y && (snd v) - y < dy))) True verts)
              where verts = vertices n 63 32
                    dy = quot 32 (2^n)

sierpinski :: Integer -> Integer -> String
sierpinski n y = concat $ map (ascii . (\x -> inrange n x y)) $ [1..63]
               where ascii True  = "1"
                     ascii False = "_"

sierpinskiTriangle :: Integer -> [String]
sierpinskiTriangle n = map (\r -> sierpinski n r) [1..32]

main :: IO ()
main = do
         n <- getLine
         putStr $ unlines $ sierpinskiTriangle ((read :: String -> Integer) $ n)