Haskelling the SACO 1

These blog entries is to record my early adventures in Haskell, to advertise the SACO, and show off the awesomeness of Literal Haskell (which means that this entire post can be pasted into a text file and compiled) by documenting my solutions to programming contest problems.


I've finally decided to learn Haskell. For about the third time.

But this time I'm actually doing it.

Since we've just hosted another successful South African Computer Olympiad^[1], I decided to code some Haskell solutions. Looking through the problems, I decided on Living Dead Parrots: I didn't code a check solution before the contest, so it wouldn't be too boring, but it was easy enough that I would spend more time learning the language than figuring out the algorithm. Most importantly, it was an interactive problem^[2], meaning I would be brought face-to-face with the IO monad, a fearful prospect for the novice Haskeller.

Well, it wasn't as scary as I'd feared. By no means.

In short, the problem we're solving is this: the evaluator has an array of N booleans. You can ask it for the number of true values between two indices (inclusive, base one). Less than a hundredth of the booleans are true. There is a limit on the number of queries you can make, but we ignore it, since it is always larger than the number needed by the correct algorithm.

This solution scores 100% (within the C++ time limit, when compiled with GHC), but is probably not the best Haskell ever written. I'd appreciate any advice you can give for improvements. That's why I'm posting, after all.

First, the preliminaries:

> module Main
>     where
>
> import System.IO
>
> rInt :: String -> Int
> rInt = read
>
> flush :: IO ()
> flush = hFlush stdout

Next, the function to query the evaluator. We output "Q a b", and read in an integer. The answer is obviously wrapped in the IO monad.

> query :: Int -> Int -> IO Int
> query a b = do putStrLn ("Q " ++ (show a) ++ " " ++ (show b))
>                flush
>                answer <- getLine
>                return $ rInt answer

I'm not particularly proud of this function, which wraps a value in the IO monad. If it's the right thing to do, there's a library function for it; if it's the wrong thing to do, I shouldn't do it. If you know which it is, leave a comment.

> coerceIO :: a -> IO a
> coerceIO x = do return x

Here comes the meaty part. Search takes a range, and the number of parrots (oh, yes, those booleans represent whether a parrot in a certain cage is pining for the fjords or has kicked the bucket) in that range, and determines where those parrots are.

> search :: Int -> Int -> Int -> IO [Bool]

There are three cases. The first is that the range contains no parrots.

> search start end 0 = coerceIO $ take (end-start+1) (repeat False)

The next case is that the range contains only one element, then we have found the location of a living parrot.

> search start end 1          | start == end  = coerceIO [True]

The interesting case is the remaining one, where we divide the list into two, and recurse.

> search start end numParrots = let middle = (end+start) `div` 2
>                                in do leftNum <- query start middle
>                                      left <- search start middle leftNum
>                                      right <- search (middle+1) end (numParrots-leftNum)
>                                      return (left ++ right)

All that remains is main, which contains my most suspicious use of coerceIO, to bind purely functional variables in a monad: I haven't figured out how to use let in a do.

It first reads a line containing two integers: the size of the parrot array, and the number of questions. We ignore the latter. We then find the number of live parrots in the array, and begin the search. The output format is "A 0 0 0 0 1 0 1 0 1 ...".

> main :: IO ()
> main = do line <- getLine
>           n <- coerceIO $ rInt $ head $ words line
>           numParrots <- query 1 n
>           parrots <- search 1 n numParrots
>           putStrLn $ "A " ++ (unwords $ map (\x -> if x then "1" else "0") parrots)
>           return ()

Notes on Haskell syntax, for non-Haskellers: f $ x is the same as f x, except that it binds more loosely. Its purpose is mostly to eliminate lots of irritating superfluous parentheses. (\x -> y) is an anonymous function mapping x to y

^[1]We now run a parallel contest online: same problems, but open to anyone. You should check it out this time next year. We might also be running the contests from the training camps online (training camps happen about three times a year, starting in February). Unfortunately, Haskell is not one of the supported languages, but after the contests you can download the evaluator programs and test data to score solutions in any language.

^[2]In the SACO, interactive problem solutions communicate through pipes with an evaluator, rather than reading an input file and writing an output file. This allows problems where access to the full dataset is unnecessary, and is either not allowed or too big to be read completely within the time limit.