---------------------------------------------------------------------------
-- Programm zu Uebungsblatt 1                                            --
-- Parallelitaet in funktionalen Sprachen, WS 2002/03                    --
---------------------------------------------------------------------------

{-
(a) Was macht das Programm?
    Vervollstaendigen Sie die Kommentare!

(b) Wo sind unabhaengige Programmteile, die parallel ausgefuehrt
    werden koennten?

    Stellen Sie Regeln zum Auffinden von Parallelitaet in funktionalen
    Programmen auf!
-}
main :: IO () 
main =  putStr (concat (map find hidden))

-- find:
---------------------------------------------------------------------------
find :: [Char] -> String
find word = word ++ " " ++ (concat dirs) ++ "\n"
  where dirs = map snd (forw ++ back)

        forw = filter (any (contains word) . fst)
               [(r,"right "), (d,"down "), (dl,"downleft "), (ul,"upleft ")]
        back = filter (any (contains drow) . fst)
               [(r,"left "), (d,"up "), (dl,"upright "), (ul,"downright ")]
        drow = reverse word

        r  = grid
        d  = transpose grid
        dl = diagonals grid
        ul = diagonals (reverse grid)

-- transpose:
---------------------------------------------------------------------------
transpose :: [[a]] -> [[a]]
transpose []             = []
transpose ([] : xss)     = transpose xss
transpose ((x:xs) : xss) = (x : [h | (h:t) <- xss]) :
                           transpose (xs : [t | (h:t) <- xss])

-- diagonals: -- zipinit:
---------------------------------------------------------------------------
diagonals [r]    = map (:[]) r
diagonals (r:rs) = zipinit r ([]:diagonals rs)

zipinit []     ys     = ys
zipinit (x:xs) (y:ys) = (x : y) : zipinit xs ys

-- contains:
-- prefix:
-- suffixes:
---------------------------------------------------------------------------
contains xs ys = any (prefix xs) (suffixes ys)

suffixes [] = []
suffixes xs = xs : suffixes (tail xs)

prefix []     ys     = True
prefix xs     []     = False
prefix (x:xs) (y:ys) = x == y && prefix xs ys

---------------------------------------------------------------------------
grid = [['Y', 'I', 'O', 'M', 'R', 'E', 'S', 'K', 'S', 'T'],
        ['A', 'E', 'H', 'Y', 'G', 'E', 'H', 'E', 'D', 'W'],
        ['Z', 'F', 'I', 'A', 'C', 'N', 'I', 'T', 'I', 'A'],
        ['N', 'T', 'O', 'C', 'O', 'M', 'V', 'O', 'O', 'R'],
        ['E', 'R', 'D', 'L', 'O', 'C', 'E', 'N', 'S', 'M'],
        ['Z', 'O', 'U', 'R', 'P', 'S', 'R', 'N', 'D', 'A'],
        ['O', 'Y', 'A', 'S', 'M', 'O', 'Y', 'E', 'D', 'L'],
        ['R', 'N', 'D', 'E', 'N', 'L', 'O', 'A', 'I', 'T'],
        ['F', 'I', 'W', 'I', 'N', 'T', 'E', 'R', 'R', 'C'],
        ['F', 'E', 'Z', 'E', 'E', 'R', 'F', 'T', 'F', 'I'],
        ['I', 'I', 'D', 'T', 'P', 'H', 'U', 'B', 'R', 'L'],
        ['C', 'N', 'O', 'H', 'S', 'G', 'E', 'I', 'O', 'N'],
        ['E', 'G', 'M', 'O', 'P', 'S', 'T', 'A', 'S', 'O'],
        ['T', 'G', 'F', 'F', 'C', 'I', 'S', 'H', 'T', 'H'],
        ['O', 'T', 'B', 'C', 'S', 'S', 'N', 'O', 'W', 'I']]

hidden = ["COSY", "SOFT", "WINTER", "SHIVER", "FROZEN", "SNOW",
          "WARM", "HEAT", "COLD", "FREEZE", "FROST", "ICE" ]