3
\$\begingroup\$

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.

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
Jamal
35.2k13 gold badges134 silver badges238 bronze badges
asked Oct 28, 2012 at 16:02
\$\endgroup\$
1
  • \$\begingroup\$ As for "most of the time I was battling with getting my types correct" - it's common for beginners. My solution to it was just to keep writing programs until I learned the type system. So don't worry, it's normal. \$\endgroup\$ Commented Nov 8, 2012 at 11:53

2 Answers 2

4
\$\begingroup\$

A good rule of thumb is that you should only ever use foldr when you're really sure that your fold is not an instance of something simpler. In your case, the fold is doing pretty much exactly two things while traversing the pattern list:

  1. Keeping track of the "case index"
  2. Accumulating the result list

The second should be easily recognisable as a map - maybe less obvious is that the first can just be written as a zip with an enumeration:

getResult :: [String] -> (Int, String) -> String
getResult w (count, pattern) =
 "Case #" ++ show count ++ ": " ++ show (numberOfMatches pattern w)
main :: IO ()
main = do
 [...]
 let results = map (getResult knownWords) $ zip [1..n] patterns

Which is much easier to understand than trying to bend the fold to do the right thing.

Also, just as a suggestion, here's main implemented in a more "imperative" (read: monadic) style. After all, Haskell is said to be the best imperative language ever invented, so we can do that proudly:

main :: IO ()
main = do
 [_, d, n] <- fmap (map read . words) getLine
 knownWords <- replicateM d getLine
 forM_ [1..n] $ \count -> do
 pattern <- getLine
 let matches = numberOfMatches pattern knownWords
 putStrLn $ concat ["Case #", show count, ": ", show matches]
answered Oct 29, 2012 at 15:51
\$\endgroup\$
1
  • \$\begingroup\$ Thanks very much - exactly what I need. You can probably see that I was trying to do something similar to your last suggestion, but I couldn't get the types to match. I should pay more attention to Control.Monad as well. I'm glad I learned about replicateM and forM_. I actually know the benefit of the underscore suffix as I used to get [(), (), ()] outputs when using mapM in main instead of mapM_. Thanks for the effort - I appreciate it. \$\endgroup\$ Commented Oct 29, 2012 at 17:22
2
\$\begingroup\$

You can use list length and an operator section to count matches:

numberOfMatches pattern = length . filter (=~ pattern')
 where
 pattern' = replace "(" "[" $ replace ")" "]" pattern
answered Nov 8, 2012 at 16:11
\$\endgroup\$

Your Answer

Draft saved
Draft discarded

Sign up or log in

Sign up using Google
Sign up using Email and Password

Post as a guest

Required, but never shown

Post as a guest

Required, but never shown

By clicking "Post Your Answer", you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.