# Mathematical Graphs to Solve Programming Contest Problem

**URL:** <https://forum.kirupa.com/t/mathematical-graphs-to-solve-programming-contest-problem/277994>\
**Category:** open source\
**Created:** [December 19, 2008, 8:36pm UTC](https://forum.kirupa.com/t/mathematical-graphs-to-solve-programming-contest-problem/277994 "2008-12-19T20:36:56Z")\
**Posts on this page:** 1\
**Page:** 1

<div class="post-metadata">

**Author:** ![Jeff\_Wheeler](https://avatars.discourse-cdn.com/v4/letter/j/59ef9b/32.png) [@Jeff\_Wheeler](https://forum.kirupa.com/u/Jeff_Wheeler)\
**Post date:** [December 19, 2008, 8:36pm UTC](https://forum.kirupa.com/t/mathematical-graphs-to-solve-programming-contest-problem/277994/1 "2008-12-19T20:36:56Z")

</div>

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](http://en.wikipedia.org/wiki/Graph_(mathematics)) library in Haskell. So, of course, I had to try solving an old contest problem that this made stupidly easy! 😛

```auto
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! 😛