haskell - Functionally solving problems - Heathrow to London

Ensuing to the discussion that we had on the functionally solving problems that we had before. Where we have Reverse Polish notation calculator, we have yet another problem to solve, which is called Heathrow to London

 

basically the problem is that there are certains means to take from Heathrow to Londo, they start at the initial locatoin at A lane, at node 1, and then it will progress either forward at the same lane, or take a route to another lane. and we know each route has certain weight, the solution is to find the most effective way to travel from Heathrow to London in the shortest path.

 

There is some general guide on how to solve problems with Haskell.

 

 

• Forget Haskell for a minute and think about how we’d solve the problem by hand
• Think about how we’re going to represent our data in Haskell
• Fig Figure out how to operate on that data in Haskell so that we produce at a solution

 

First we will define some data to helps us tackle the problem. 

 

data Section = Section { getA :: Int, getB :: Int, getC :: Int } deriving (Show) 

type RoadSystem = [Section] 

we repsent a group called section, which has three route, one is to A, another to B, and the last is to C (which means goes another route to another lane). 

 

 before this solution, we might have come up some solution which may define data structure as below. 

 

data Node = Node Road Road | EndNode Road

data Road = Road Int Node

 

or even like this , if you prefer to use Maybe data.

 

data Node = Node Road ( Maybe Road )

data Road = Road Int Node

 

Since we have define the datascture to represent the path and the the RoadSystem, we might start to work out some solution, to aid us to do that ,we might define some data that enables us to track the current state and the path we will take along the way. 

 

here are the datas. 

data Label = A | B | C deriving ( Show )

type Path = [( Label , Int )]

 

with that, we may represent the solution by the following. 

 

[(B ,10) ,(C ,30) ,(A ,5) ,(C ,20) ,(B ,2) ,(B ,8)]

 

we might has some helper function, which keeps track the optimal path to A node at section N or the optimal path to B nodes at section N...  Here is the code that helps to find what it is . 

 

roadStep :: (Path, Path) -> Section -> (Path, Path) 

roadStep (pathA, pathB) (Section a b c) =  

    let priceA = sum $ map snd pathA 

        priceB = sum $ map snd pathB 

        forwardPriceToA = priceA + a 

        crossPriceToA = priceB + b + c 

        forwardPriceToB = priceB + b 

        crossPriceToB = priceA + a + c 

        newPathToA = if forwardPriceToA <= crossPriceToA 

                        then (A,a):pathA 

                        else (C,c):(B,b):pathB 

        newPathToB = if forwardPriceToB <= crossPriceToB 

                        then (B,b):pathB 

                        else (C,c):(A,a):pathA 

    in  (newPathToA, newPathToB)

 

with that, we can find the optimal solution by the following.  

<!--[if !supportLineBreakNewLine]-->
<!--[endif]-->

optimalPath :: RoadSystem -> Path 

optimalPath roadSystem =

    let (bestAPath, bestBPath) = foldl roadStep ([],[]) roadSystem 

    in  if sum (map snd bestAPath) <= sum (map snd bestBPath) 

            then reverse bestAPath 

            else reverse bestBPath 

 

and we now need to parse the input and feed that into the optimalPath solution so that it can solve that partical problem.  we create a function called groupOf, which can split the list into groups of the same size.  here is the code that does it. 

 

groupsOf :: Int -> [a] -> [[a]] 

groupsOf 0 _ = undefined 

groupsOf _ [] = [] 

groupsOf n xs = take n xs : groupsOf n (drop n xs) 

 

and it is the main method which does the work .

main = do 

    contents <- getContents 

    let threes = groupsOf 3 (map read $ lines contents) 

        roadSystem = map (\[a,b,c] -> Section a b c) threes 

        path = optimalPath roadSystem 

        pathString = concat $ map (show . fst) path 

        pathPrice = sum $ map snd path 

    putStrLn $ "The best path to take is: " ++ pathString 

    putStrLn $ "The price is: " ++ show pathPrice