{-# LANGUAGE DuplicateRecordFields, FlexibleInstances, UndecidableInstances, MultiWayIf, RecordWildCards #-} module Main where import Control.Monad --import Data.Array --import Data.Bits import Data.List --import Data.List.Split import Data.Vector (Vector) import qualified Data.Vector as V import Data.Set (Set) import qualified Data.Set as S import Data.Map (Map) import qualified Data.Map as M import qualified Data.Text import Data.Monoid import Data.Traversable import Data.Maybe --import Debug.Trace import System.Environment import System.IO import System.IO.Unsafe -- -- Complete the 'findCheapestPath' function below. -- -- The function is expected to return an INTEGER. -- The function accepts 2D_STRING_ARRAY edges as parameter. -- import Data.Semigroup data Distance = INF | Dist !Int deriving (Eq, Show) instance Num Distance where (+) (Dist x) (Dist y) = Dist (x+y) (+) INF (Dist x) = Dist x (+) (Dist x) INF = Dist x (-) (Dist x) (Dist y) = Dist (x-y) (-) INF (Dist x) = Dist x (-) (Dist x) INF = Dist x data Vertex a = Vertex a Distance deriving (Eq, Show) data Edge a = Edge a a !Int deriving (Eq, Show) data ToPoint a = ToPoint a !Int deriving (Eq, Show) data Graph a = Graph { graphVertices :: [(Vertex a)] -- or Vector (Vertex a) , graphEdges :: Map a [ToPoint a] -- or Set (Edge a) } deriving (Eq, Show) instance (Ord a) => Semigroup (Graph a) where (<>) g1 g2 = Graph (nub $ graphVertices g1 <> graphVertices g2) (M.unionWith (<>) (graphEdges g1) (graphEdges g2)) instance (Ord a) => Monoid (Graph a) where mappend = (<>) mempty = gempty gempty :: Ord a => Graph a gempty = Graph mempty mempty packn :: [[String]] -> Graph Char packn [] = mempty packn (x:xs) = (packn' x) <> (packn xs) packn' :: [String] -> Graph Char packn' [s,e,w] = Graph vertices edges where vertices = [(Vertex (head s) INF), (Vertex (head e) INF)] edges :: Map Char [ToPoint Char] edges = M.fromList [((head s), [ToPoint (head e) (read w :: Int)]),((head e), [ToPoint (head s) (read w :: Int)])] initial :: Eq a => a -> Graph a -> Graph a initial a graph = graph {graphVertices = newVertices} where newVertices = replace (graphVertices graph) (Vertex a INF) (Vertex a $ Dist 0) --(:) (Vertex a (Dist 0)) $ (graphVertices graph) \\ [Vertex a INF] replace :: Eq a => [a] -> a -> a -> [a] replace ls old new = new : (ls \\ [old]) update :: Ord a => Set a -> Graph a -> (Graph a, Set a) update visited graph = (ngraph, nvisited) where oldverts = graphVertices graph nverts = mconcat $ flip fmap (S.toList visited) $ \c -> fmap (\(ToPoint l d) -> Vertex l $ Dist d + (dnum l graph) ) $ filter (\(ToPoint x _) -> S.notMember x visited) $ (graphEdges graph) M.! c ngraph = graph {graphVertices = updateVertices oldverts nverts} nvisited = visited <> ((\(Vertex c _) -> S.singleton c) $ minimum nverts) updateVertices :: Eq a => [Vertex a] -> [Vertex a] -> [Vertex a] updateVertices l1 l2 = flip fmap l1 $ \v@(Vertex c d) -> if hasVert c l2 then findVert c l2 else v findVert :: Eq a => a -> [Vertex a] -> Vertex a findVert a = head . filter (\(Vertex c _) -> c == a) hasVert :: Eq a => a -> [Vertex a] -> Bool hasVert a = not . null . filter (\(Vertex c _) -> c == a) dnum :: Ord a => a -> Graph a -> Distance dnum a graph = dist $ head $ filter (\(Vertex c _) -> c == a) (graphVertices graph) dist :: Vertex a -> Distance dist (Vertex _ d) = d findCheapestPath :: [[String]] -> Int findCheapestPath edges = undefined -- update (S.singleton 'A') $ initial 'A' $ packn edges ---------------------------------------------------------------------------------------------------------------------- lstrip = Data.Text.unpack . Data.Text.stripStart . Data.Text.pack rstrip = Data.Text.unpack . Data.Text.stripEnd . Data.Text.pack readMultipleLinesAsStringArray :: Int -> IO [String] readMultipleLinesAsStringArray 0 = return [] readMultipleLinesAsStringArray n = do line <- getLine rest <- readMultipleLinesAsStringArray(n - 1) return (line : rest) main :: IO() main = do stdout <- getEnv "OUTPUT_PATH" fptr <- openFile stdout WriteMode nTemp <- getLine let n = read $ lstrip $ rstrip nTemp :: Int arrTemp <- readMultipleLinesAsStringArray n let arr = Data.List.map (\x -> Data.List.words $ rstrip x) arrTemp print $ update (S.singleton 'A') $ initial 'A' $ packn arr let result = findCheapestPath arr hPutStrLn fptr $ show result hFlush fptr hClose fptr

{-# LANGUAGE DuplicateRecordFields, FlexibleInstances, UndecidableInstances, MultiWayIf, RecordWildCards #-} module Main where import Control.Monad --import Data.Array --import Data.Bits import Data.List --import Data.List.Split import Data.Vector (Vector) import qualified Data.Vector as V import Data.Set (Set) import qualified Data.Set as S import Data.Map (Map) import qualified Data.Map as M import qualified Data.Text import Data.Monoid import Data.Traversable import Data.Maybe --import Debug.Trace import System.Environment import System.IO import System.IO.Unsafe -- -- Complete the 'findCheapestPath' function below. -- -- The function is expected to return an INTEGER. -- The function accepts 2D_STRING_ARRAY edges as parameter. -- import Data.Semigroup data Distance = INF | Dist !Int deriving (Eq, Show) instance Num Distance where (+) (Dist x) (Dist y) = Dist (x+y) (+) INF (Dist x) = Dist x (+) (Dist x) INF = Dist x (-) (Dist x) (Dist y) = Dist (x-y) (-) INF (Dist x) = Dist x (-) (Dist x) INF = Dist x instance Ord Distance where (<) (Dist x) (Dist y) = x < y (<) INF (Dist x) = True (<) (Dist x) INF = False (<=) x y = (x < y) || (x == y) data Vertex a = Vertex a Distance deriving (Eq, Show) instance Eq a => Ord (Vertex a) where (<) (Vertex _ x) (Vertex _ y) = x < y (<=) (Vertex _ x) (Vertex _ y) = x <= y data Edge a = Edge a a !Int deriving (Eq, Show) data ToPoint a = ToPoint a !Int deriving (Eq, Show) data Graph a = Graph { graphVertices :: [(Vertex a)] -- or Vector (Vertex a) , graphEdges :: Map a [ToPoint a] -- or Set (Edge a) } deriving (Eq, Show) instance (Ord a) => Semigroup (Graph a) where (<>) g1 g2 = Graph (nub $ graphVertices g1 <> graphVertices g2) (M.unionWith (<>) (graphEdges g1) (graphEdges g2)) instance (Ord a) => Monoid (Graph a) where mappend = (<>) mempty = gempty gempty :: Ord a => Graph a gempty = Graph mempty mempty packn :: [[String]] -> Graph Char packn [] = mempty packn (x:xs) = (packn' x) <> (packn xs) packn' :: [String] -> Graph Char packn' [s,e,w] = Graph vertices edges where vertices = [(Vertex (head s) INF), (Vertex (head e) INF)] edges :: Map Char [ToPoint Char] edges = M.fromList [((head s), [ToPoint (head e) (read w :: Int)]),((head e), [ToPoint (head s) (read w :: Int)])] initial :: Eq a => a -> Graph a -> Graph a initial a graph = graph {graphVertices = newVertices} where newVertices = replace (graphVertices graph) (Vertex a INF) (Vertex a $ Dist 0) --(:) (Vertex a (Dist 0)) $ (graphVertices graph) \\ [Vertex a INF] replace :: Eq a => [a] -> a -> a -> [a] replace ls old new = new : (ls \\ [old]) update :: Ord a => Vertex a -> Set a -> Graph a -> (Set a, Graph a) update (Vertex c ol) visited graph = (nvisited, ngraph) where oldverts = graphVertices graph nverts = fmap (\(ToPoint l d) -> Vertex l $ minDistance (dnum l graph) $ Dist d + ol ) $ filter (\(ToPoint x _) -> S.notMember x visited) $ (graphEdges graph) M.! c ngraph = graph {graphVertices = updateVertices oldverts nverts} nvisited = visited <> (S.singleton c) minDistance :: Distance -> Distance -> Distance minDistance INF x = x minDistance x INF = x minDistance x y = min x y minDist :: Ord a => Set a -> Graph a -> Vertex a minDist visited graph = minimum $ filter (\(Vertex c d) -> S.notMember c visited && d /= INF) (graphVertices graph) updateVertices :: Eq a => [Vertex a] -> [Vertex a] -> [Vertex a] updateVertices l1 l2 = flip fmap l1 $ \v@(Vertex c d) -> if hasVert c l2 then findVert c l2 else v findVert :: Eq a => a -> [Vertex a] -> Vertex a findVert a = head . filter (\(Vertex c _) -> c == a) hasVert :: Eq a => a -> [Vertex a] -> Bool hasVert a = not . null . filter (\(Vertex c _) -> c == a) dnum :: Ord a => a -> Graph a -> Distance dnum a graph = dist $ head $ filter (\(Vertex c _) -> c == a) (graphVertices graph) allVisited :: Set a -> Graph a -> Bool allVisited visited graph = (S.size visited) == (length $ graphVertices graph) label :: Vertex a -> a label (Vertex c _) = c dist :: Vertex a -> Distance dist (Vertex _ d) = d findPath :: Ord a => a -> a -> Graph a -> Distance findPath a end graph = go initialGo where initialGo = update (Vertex a (Dist 0)) (mempty) $ initial a $ graph go (s,g) = case update (minDist s g) s g of (s',g') | allVisited s' g' -> dnum end g' | otherwise -> go (s',g') debugFP :: Ord a => a -> a -> Graph a -> Graph a debugFP a end graph = go initialGo where initialGo = update (Vertex a (Dist 0)) (mempty) $ initial a $ graph go (s,g) = case update (minDist s g) s g of (s',g') | allVisited s' g' -> g' | otherwise -> go (s',g') findCheapestPath :: [[String]] -> Int findCheapestPath edges = case findPath 'A' 'H' $ packn edges of INF -> error "No Path Found" (Dist x) -> x ---------------------------------------------------------------------------------------------------------------------- lstrip = Data.Text.unpack . Data.Text.stripStart . Data.Text.pack rstrip = Data.Text.unpack . Data.Text.stripEnd . Data.Text.pack readMultipleLinesAsStringArray :: Int -> IO [String] readMultipleLinesAsStringArray 0 = return [] readMultipleLinesAsStringArray n = do line <- getLine rest <- readMultipleLinesAsStringArray(n - 1) return (line : rest) main :: IO() main = do stdout <- getEnv "OUTPUT_PATH" fptr <- openFile stdout WriteMode nTemp <- getLine let n = read $ lstrip $ rstrip nTemp :: Int arrTemp <- readMultipleLinesAsStringArray n let arr = Data.List.map (\x -> Data.List.words $ rstrip x) arrTemp --print $ (\(s,g) -> update (minDist s g) s g) $ update (Vertex 'A' (Dist 0)) (mempty) $ initial 'A' $ packn arr print $ debugFP 'A' 'H' $ packn arr let result = findCheapestPath arr hPutStrLn fptr $ show result hFlush fptr hClose fptr

{-# LANGUAGE DuplicateRecordFields, FlexibleInstances, UndecidableInstances #-} module Main where import Control.Monad import Data.List import Data.Vector (Vector) import qualified Data.Vector as V import Data.Set (Set) import qualified Data.Set as S import Data.Map (Map) import qualified Data.Map as M import qualified Data.Text import Data.Monoid import Data.Traversable import Data.Maybe import System.Environment import System.IO import Data.Semigroup -- -- Submission by Daniel Grinshpon -- -- | When a distance is unknown, it is set to INF (infinity). When it is known , it is given a number data Distance = INF | Dist !Int deriving (Eq, Show) -- | It's a bit tricky figuring out what to do with INF's in terms of arithmatic, but it's not really important instance Num Distance where (+) (Dist x) (Dist y) = Dist (x+y) (+) INF (Dist x) = Dist x (+) (Dist x) INF = Dist x (-) (Dist x) (Dist y) = Dist (x-y) (-) INF (Dist x) = Dist x (-) (Dist x) INF = Dist x -- | INF's also sort of break the rules when it comes to ordering, but the minDistance function takes care of the case when it could hurt the program instance Ord Distance where (<) (Dist x) (Dist y) = x < y (<) INF (Dist x) = True (<) (Dist x) INF = False (<=) x y = (x < y) || (x == y) -- | A vertex is a node with a label of type a, and a distance data Vertex a = Vertex a Distance deriving (Eq, Show) instance Eq a => Ord (Vertex a) where (<) (Vertex _ x) (Vertex _ y) = x < y (<=) (Vertex _ x) (Vertex _ y) = x <= y data Edge a = Edge a a !Int deriving (Eq, Show) data ToPoint a = ToPoint a !Int deriving (Eq, Show) -- | A graph containing information about the vertices and edges data Graph a = Graph { graphVertices :: [(Vertex a)] -- or Vector/Set (Vertex a) , graphEdges :: Map a [ToPoint a] -- ^ an edge from a to b can be thought of as: key a "toPoint" b } deriving (Eq, Show) instance (Ord a) => Semigroup (Graph a) where (<>) g1 g2 = Graph (nub $ graphVertices g1 <> graphVertices g2) (M.unionWith (<>) (graphEdges g1) (graphEdges g2)) instance (Ord a) => Monoid (Graph a) where mappend = (<>) mempty = gempty -- | empty graph gempty :: Ord a => Graph a gempty = Graph mempty mempty -- | turn a 2d-list of Strings into a Graph packn :: [[String]] -> Graph Char packn [] = mempty packn (x:xs) = (packn' x) <> (packn xs) packn' :: [String] -> Graph Char packn' [s,e,w] = Graph vertices edges where vertices = [(Vertex (head s) INF), (Vertex (head e) INF)] edges :: Map Char [ToPoint Char] edges = M.fromList [((head s), [ToPoint (head e) (read w :: Int)]),((head e), [ToPoint (head s) (read w :: Int)])] initial :: Eq a => a -> Graph a -> Graph a initial a graph = graph {graphVertices = newVertices} where newVertices = replace (graphVertices graph) (Vertex a INF) (Vertex a $ Dist 0) -- | replace an element of a list with a new one replace :: Eq a => [a] -> a -> a -> [a] replace ls old new = new : (ls \\ [old]) -- | Using Dijkstra's algorithm. Given a selected vertex, a set of visited vertices, and the graph, find the distances from the selected vertex to adjacent vertices, then mark it as visited. The new set contains the visited vertices, and the graph contains the vertices with their distances recorded. update :: Ord a => Vertex a -> Set a -> Graph a -> (Set a, Graph a) update (Vertex vlabel vdist) visited graph = (nvisited, ngraph) where oldverts = graphVertices graph nverts = fmap (\(ToPoint tlabel tdist) -> Vertex tlabel $ minDistance (findDist tlabel graph) $ Dist tdist + vdist ) $ filter (\(ToPoint x _) -> S.notMember x visited) $ (graphEdges graph) M.! vlabel ngraph = graph {graphVertices = updateVertices oldverts nverts} nvisited = visited <> (S.singleton vlabel) -- | compare two distances and return the shorter one minDistance :: Distance -> Distance -> Distance minDistance INF x = x minDistance x INF = x minDistance x y = min x y -- | find the vertex in the graph with the smallest distance minDist :: Ord a => Set a -> Graph a -> Vertex a minDist visited graph = minimum $ filter (\(Vertex c d) -> S.notMember c visited && d /= INF) (graphVertices graph) -- | essentially a right-biased union updateVertices :: Eq a => [Vertex a] -> [Vertex a] -> [Vertex a] updateVertices l1 l2 = flip fmap l1 $ \v@(Vertex c d) -> if hasVert c l2 then findVert c l2 else v findVert :: Eq a => a -> [Vertex a] -> Vertex a findVert a = head . filter (\(Vertex c _) -> c == a) hasVert :: Eq a => a -> [Vertex a] -> Bool hasVert a = not . null . filter (\(Vertex label _) -> label == a) -- | given a label a, find the distance of the vertex in the graph with that label findDist :: Ord a => a -> Graph a -> Distance findDist a graph = dist $ findVert a (graphVertices graph) allVisited :: Set a -> Graph a -> Bool allVisited visited graph = (S.size visited) == (length $ graphVertices graph) dist :: Vertex a -> Distance dist (Vertex _ d) = d -- using Dijkstra's algorithm to find the shortest distance between two vertices findPath :: Ord a => a -> a -> Graph a -> Distance findPath start end initialGraph = go initialGo where initialGo = update (Vertex start (Dist 0)) (mempty) $ initial start $ initialGraph go (visited,graph) = case update (minDist visited graph) visited graph of (visited',graph') | allVisited visited' graph' -> findDist end graph' | otherwise -> go (visited',graph') -- findPath but return the graph, for debug purposes debugFP :: Ord a => a -> a -> Graph a -> Graph a debugFP a end graph = go initialGo where initialGo = update (Vertex a (Dist 0)) (mempty) $ initial a $ graph go (s,g) = case update (minDist s g) s g of (s',g') | allVisited s' g' -> g' | otherwise -> go (s',g') findCheapestPath :: [[String]] -> Int findCheapestPath edges = case findPath 'A' 'H' $ packn edges of INF -> error "No Path Found" (Dist x) -> x ---------------------------------------------------------------------------------------------------------------------- lstrip = Data.Text.unpack . Data.Text.stripStart . Data.Text.pack rstrip = Data.Text.unpack . Data.Text.stripEnd . Data.Text.pack readMultipleLinesAsStringArray :: Int -> IO [String] readMultipleLinesAsStringArray 0 = return [] readMultipleLinesAsStringArray n = do line <- getLine rest <- readMultipleLinesAsStringArray(n - 1) return (line : rest) main :: IO() main = do stdout <- getEnv "OUTPUT_PATH" fptr <- openFile stdout WriteMode nTemp <- getLine let n = read $ lstrip $ rstrip nTemp :: Int arrTemp <- readMultipleLinesAsStringArray n let arr = Data.List.map (\x -> Data.List.words $ rstrip x) arrTemp --print $ debugFP 'A' 'H' $ packn arr --for debug purposes let result = findCheapestPath arr hPutStrLn fptr $ show result hFlush fptr hClose fptr