Mathematical Graphs to Solve Programming Contest Problem

[Jeff Wheeler]

I just learned about graphs (http://en.wikipedia.org/wiki/Graph_(mathematics)) in the context of mathematics, and the Data.Graph (http://hackage.haskell.org/packages/archive/containers/0.2.0.0/doc/html/Data-Graph.html) library in Haskell. So, of course, I had to try solving an old contest problem that this made stupidly easy! :P


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 (http://www.cs.trinity.edu/~mlewis/HSProgComp06/Problems.pdf) (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! :P

[Jeff Wheeler]

And here’s an even simpler solution for problem 9 in the 2005 problem set (http://www.cs.trinity.edu/~mlewis/HSProgComp05/Problems.pdf):


import Data.Graph

import Text.Parsec
import Text.Parsec.String

possibleHoles paths = reachable graph 0
where graph = buildG (0, 5) $ concat $ zipWith (\n ys -> [(n, y) | y <- ys]) [0..] paths

solve = elem 5 . possibleHoles

natural :: Parser Int
natural = many1 digit >>= return.read

parseFile :: Parser [[[Int]]]
parseFile = do n <- natural
newline
count n $ do n <- natural
newline
count n $ do c <- sepEndBy1 natural (char ' ')
newline
return c

main = do contents <- readFile "p9.data"
case (parse parseFile "" contents) of
Left err -> print err
Right a -> print $ map solve a

Try beating that in an imperative language!

[glosrfc]

Here's my CSL solution (that's Common Sense Language) to solving that particular problem:


Enter GAS_STN;
Purchase ROAD_MAP;


Edit: I mean problem 8, of course ;)

[Jeff Wheeler]

Here's my CSL solution (that's Common Sense Language) to solving that particular problem:


Enter GAS_STN;
Purchase ROAD_MAP;


Ah, but you ignored one of the constraints of the problem: you’re lazy! Fortunately, Haskell is one of the few languages that uses lazy evaluation.