Solution to ACM Finals, 2001, Problem A: Airport Configuration.

> import Array
> import List(sort)

> newtype Parser a = Parser (ReadS a)
> toReadS (Parser r) = r
> parse :: Read a => Parser a
> parse = Parser reads
> instance Monad Parser where
>   return x = Parser (\s -> [(x,s)])
>   (Parser r) >>= g = Parser (\s -> do {(a,s') <- r s; toReadS (g a) s'})
>   fail _ = Parser (\s -> [])

From a configuration, we can compute distances.
  a = array of arrival gates (note a[1] means which gate receives city 1)
  d = array of departure gates (ditto)
  s = "from" city
  t = "to" city
  distance = walking distance when transferring from s to t

> distance (a,d) (s,t) = abs (a!s - d!t) + 1

From traffic data and a configuration, we can compute load.
  traffic = [((source, dest), passengers)]
  c = (a,d)

> load traffic c = sum (map load' traffic)
>   where
>   load' ((s,t),p) = distance c (s,t) * p


> main = do n <- readLn
>           if n == 0 then return () else
>              do traffic <- readTraffic n
>                 configs <- readConfigs n
>                 let (c,i) = unzip configs
>                     loads = map (load traffic) c
>                     answer = sort (zip loads i)
>                 putStrLn "Configuration  Load"
>                 mapM_ (putStrLn . printer) answer
>                 main

> printer (l,i) = showi ++ "          " ++ show l
>   where
>   s = show i
>   showi = replicate (5 - length s) ' ' ++ s


Input traffic data.
  n = number of cities
  return [((source, dest), passengers)]

> readTraffic 0 = return []
> readTraffic n = do l <- getLine
>                    let [(t,_)] = (toReadS r) l
>                    more <- readTraffic (n-1)
>                    return (t ++ more)
>   where
>   r = do i <- parse
>          k <- parse
>          sequence (replicate k (do j <- parse
>                                    n <- parse
>                                    return ((i,j),n) ))

Input configurations.
  n = number of cities.
  return [((arrival array, departure array), config id)]

> readConfigs n = do id <- readLn
>                    if id==0 then return [] else
>                       do a <- readarray
>                          d <- readarray
>                          more <- readConfigs n
>                          return $ ((a,d),id) : more
>   where
>   readarray = do l <- getLine
>                  let [(s,_)] = toReadS (sequence $ replicate n parse) l
>                      a = array (1,n) (zip s [1..])
>                  return a