Commits

Lucian Brănescu-Mihăilă committed 26ba559

Complete paths program.

Comments (0)

Files changed (2)

+50
+10
+30
+5
+90
+20
+40
+2
+25
+10
+8
+0
-#!/usr/bin/runkaskell
+#!/usr/bin/runhaskell
 
 data Node = Node Road (Maybe Road)
 data Road = Road Int Node
 type Path = [(Label, Int)]
 
 optimalPath :: RoadSystem -> Path
+optimalPath system =
+    let (bestAPath, bestBPath) = foldl roadStep ([], []) system
+    in if sum (map snd bestAPath) <= sum (map snd bestBPath)
+        then reverse bestAPath
+        else reverse bestBPath
+
+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)
+
+
+groupsOf :: Int -> [a] -> [[a]]
+groupsOf 0 _ = undefined
+groupsOf _ [] = []
+groupsOf n xs = take n xs : groupsOf n (drop n xs)
+
+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