SPOJ

There is a website that provides an online programming contest called the Sphere Online Judge. We would like to gather together a bunch of haskellers and wipe other languages off the map :)

Solution to TEST

TEST description: the input consists of one number per line, the program should echo each number until "42" is reached, at which point the program should exit.

main = mapM_ putStrLn . takeWhile (/="42") . lines =<< getContents

Solution to INTEST

INTEST description: the first line of input contains two numbers: n and k. The input then consists of n lines of numbers. The output of the program should be the count of the numbers which are divisible by k.

Prior to the installation of GHC 6.6.1, it was quite difficult, if not impossible, to pass this demonstration. This solution shows a simple, reasonably efficient manner of using the new ByteString library to achieve acceptable times.

import Data.List (unfoldr)
import qualified Data.ByteString.Char8 as SS

divisibleBy :: Int -> Int -> Bool
a `divisibleBy` n = a `rem` n == 0

readInt1 :: SS.ByteString -> Maybe (Int, SS.ByteString)
readInt1 cs = do
  (n, cs') <- SS.readInt cs
  return (n, SS.tail cs')

main = do
  cs <- SS.getContents  -- This is the only line of I/O
  let n:k:ns = unfoldr readInt1 cs
      count  = length $ filter (`divisibleBy` k) ns
  print count

Techniques for dealing with problems efficiently

This section accumulates some earned wisdom about writing Haskell programs which overcome some of the technical obstacles in SPOJ. These are not spoilers, hopefully, but useful tips in general about auxiliary issues.

I/O

SPOJ has finally installed the GHC version 6.6.1. This makes the new, alternative I/O module available: Data.ByteString. Hopefully, it will be possible to find solutions for many more problems -- which could not be solved efficiently in the past because of mundane issues like I/O.

ByteStrings come in two varieties: Strict (default), and Lazy. Strict ByteStrings, in brief, are implemented by a foreign pointer to a block of memory which is filled by low level operations. The ByteString data type points to this memory region and also contains two Ints which track relative position and length. This means that many operations on ByteStrings can re-use memory and merely manipulate the two Ints.

Data.ByteString.Lazy is a layer on top which provides the ByteString API, but now the data is only read in chunks of Strict ByteStrings when necessary.

Don Stewart and others have put a great deal of excellent work into the library to ensure that the high-level interface will be optimized into efficient code. However, it may behoove you to inspect the source code for yourself, which is quite accessible and available in the GHC repository under libraries/base/Data/.

For SPOJ purposes, the most common operation is reading some kind of list of Ints. The code for INTEST above demonstrates one simple way to take advantage of ByteString. Using a similar technique may suffice for many problems. However, there are more advanced possibilities which could offer improvements in some cases.

todo

Arrays

todo

Garbage Collection

todo