{-# language FlexibleContexts #-}
import Data.List
import Data.Maybe
import System.Random
import Control.Monad.State
import Text.Printf
import Data.Set (Set)
import qualified Data.Set  as S

type Matrix = [[Bool]]
type Cell = (Int, Int)
type Cluster = Set (Int, Int)

clusters :: Matrix -> [Cluster]
clusters m = unfoldr findCuster cells
  where
    cells = S.fromList [ (i,j) | (r, i) <- zip m [0..]
                               , (x, j) <- zip r [0..], x]

    findCuster s = do
      (p, ps) <- S.minView s
      return $ runState (expand p) ps

    expand p = do
      ns <- state $ extract (neigbours p)
      xs <- mapM expand $ S.elems ns
      return $ S.insert p $ mconcat xs

    extract s1 s2 = (s2 `S.intersection` s1, s2 S.\\ s1)
    neigbours (i,j) = S.fromList [(i-1,j),(i+1,j),(i,j-1),(i,j+1)]
    n = length m

showClusters :: Matrix -> String
showClusters m = unlines [ unwords [ mark (i,j)
                                   | j <- [0..n-1] ]
                         | i <- [0..n-1] ]
  where
    cls = clusters m
    n = length m
    mark c = maybe "." snd $ find (S.member c . fst) $ zip cls syms
    syms = sequence [['a'..'z'] ++ ['A'..'Z']]
------------------------------------------------------------

randomMatrices :: Int -> StdGen -> [Matrix]
randomMatrices n = clipBy n . clipBy n . randoms
  where
    clipBy n = unfoldr (Just . splitAt n)

randomMatrix n = head . randomMatrices n

tests :: Int -> StdGen -> [Int]
tests n = map (length . clusters) . randomMatrices n

task :: Int -> StdGen -> (Int, Double)
task n g = (n, result)
  where
    result = mean $ take 10 $ map density $ tests n g
    density c = fromIntegral c / fromIntegral n**2
    mean lst = sum lst / genericLength lst

main = newStdGen >>= mapM_ (uncurry (printf "%d\t%.5f\n")) . res
  where
    res = mapM task [10,50,100,500]