Mathematical Graphs to Solve Programming Contest Problem

talk open source
1

I just learned about graphs in the context of mathematics, and the [url=http://hackage.haskell.org/packages/archive/containers/0.2.0.0/doc/html/Data-Graph.html]Data.Graph library in Haskell. So, of course, I had to try solving an old contest problem that this made stupidly easy! :stuck_out_tongue:

import Control.Arrow
import Control.Monad

import Data.List
import Data.Graph
import Data.Maybe

import Text.Parsec
import Text.Parsec.String

cities :: [(String, String)] -> [String]
cities [] = []
cities ((a, b):xs) = a : b : cities xs

solve :: (String, [(String, String)], [String]) -> [Bool]
solve (start, highways, destinations) = map ((path graph $ findV start) . findV) destinations
  where graph = buildG (0, length verts) (map (findV *** findV) highways)
        verts = cities highways
        findV = fromMaybe (-1) . flip elemIndex verts

name :: Parser String
name = manyTill anyChar space

num :: Parser Int
num = do xs <- many1 digit
         return (read xs)

parseFile :: Parser (String, [(String, String)], [String])
parseFile = do start <- name
               hc <- num
               newline
               highways <- count hc $ do h <- name
                                         a <- name
                                         b <- name
                                         return (a, b)
               dc <- num
               newline
               destinations <- count dc name
               return (start, highways, destinations)

main = do contents <- readFile "p8.data"
          case parse parseFile "" contents of
            Left err -> print err
            Right a  -> do forM (solve a) $ \b -> putStrLn $ if b then "Just go a ways over there."
                                                                  else "You can't get there from here."
                           return ()

It solves problem 8 from this problem set (PDF warning) for the Trinity contest, 2006.

Only the first two functions, cities and solve are needed to solve the problem; the rest of the file just reads in and parses the data and then prints it out.

I challenge anybody who thinks they have a more concise language to try making solve/cities shorter! :stuck_out_tongue: