I've successfully solved the Alien Languages problem for Google Code Jam in Haskell:
The algorithm is trivial - turn the patterns into regular expressions and see how many of the known words match these expressions.
But - this has taken me far longer than I expected it to, and most of the time I was battling with getting my types correct. Which leaves me wondering whether there is something wrong with my understanding of Functional programming.
Anyway here is my code:
module Main where -- http://code.google.com/codejam/contest/90101/dashboard#s=p0 -- Input and output with standard redirection operators -- Unless otherwise indicated, all modules used are either bundled with -- the Haskell Platform (http://hackage.haskell.org/platform/) or available -- as a separate download from Hackage (http://hackage.haskell.org/). import Data.List import Text.Regex.Posix import Data.String.Utils numberOfMatches :: String -> [String] -> Int numberOfMatches pattern = foldl' matches 0 where matches acc word = if word =~ pattern' :: Bool then acc + 1 else acc pattern' = replace "(" "[" $ replace ")" "]" pattern getResult :: String -> ([String], Int, [String]) -> ([String], Int, [String]) getResult pattern (w, count, accum) = (w, count - 1, res : accum) where res = "Case #" ++ show count ++ ": " ++ show (numberOfMatches pattern w) main :: IO () main = do (header:xs) <- fmap lines getContents -- IO is a Functor. let [_, d, n] = map read $ words header let knownWords = take d xs let patterns = drop d xs let (_, _, results) = foldr getResult (knownWords, n, ) patterns mapM_ putStrLn results
Which, for a test input of:
3 5 4 abc bca dac dbc cba (ab)(bc)(ca) abc (abc)(abc)(abc) (zyx)bc
Yields the results:
Case #1: 2 Case #2: 1 Case #3: 3 Case #4: 0
I'd appreciate any comments.