# Prison Transport

# Prison Transport

dzmitry75 + 0 comments My implementation in Scala fails time constraint on case 9. I can use mutable structures (e.g. Java collections, that Scala supports as is) to achieve much better performance but IMHO this is

*not*what functional programming is used for. Maybe I'm wrong here, though...

Widget + 0 comments To get the last test case (9) to work, I had to basically copy/paste the fgl library into the box:

{-# OPTIONS_GHC -O3 -threaded #-} import qualified Data.IntMap as IM import qualified Data.IntMap.Strict as IMS import qualified Data.Tree as T import Data.List(foldl') newtype Graph = Graph (IM.IntMap (IM.IntMap (), IM.IntMap ())) instance Show Graph where showsPrec d g = showParen (d > 10) $ showString "mkGraph " . shows (labNodes g) . showString " " . shows (labEdges g) mkGraph vs es = insEdges es $ Graph $ IM.fromList $ zip vs (repeat (IM.empty, IM.empty)) insEdges es g = foldl' insEdge g es insEdge (Graph g) (v, w) = g' `seq` Graph g' where g' = IM.adjust addP w $ IM.adjust addS v g addS (ps, ss) = (ps, IM.insert w () ss) addP (ps, ss) = (IM.insert v () ps, ss) labNodes (Graph g) = IM.keys g labEdges (Graph g) = do (node, (_, ss)) <- IM.toList g (next, _) <- IM.toList ss return (node, next) components :: Graph -> [[Int]] components = map T.flatten . (fixNodes xdff) fixNodes f g = f (labNodes g) g xdff vs g = fst (xdf vs g) xdf :: [Int] -> Graph -> ([T.Tree Int], Graph) xdf [] g = ([], g) xdf _ (Graph g) | IM.null g = ([], Graph g) xdf (v:vs) g = case match v g of (Nothing, g1) -> xdf vs g1 (Just (ps, node, ss), g1) -> (T.Node node ts:ts', g3) where (ts , g2) = xdf (ps ++ ss) g1 (ts', g3) = xdf vs g2 where match node (Graph g) = case IM.lookup node g of Nothing -> (Nothing, Graph g) Just (p, s) -> let !g1 = IM.delete node g !p' = IM.delete node p !s' = IM.delete node s !g2 = clearPred g1 node s' !g3 = clearSucc g2 node p' in (Just (IM.keys p', node, IM.keys s), Graph g3) clearSucc g v = IMS.differenceWith clearSucc' g clearSucc' (ps, ss) _ = Just (ps, IM.delete v ss) clearPred g v = IMS.differenceWith clearPred' g clearPred' (ps, ss) _ = Just (IM.delete v ps, ss) transportCost n links = sum $ map (ceiling . sqrt . fromIntegral . length) $ components $ mkGraph n links main = do n <- read <$> getLine _ <- getLine links <- pairUp . words <$> getContents print $ transportCost [1..n] links where pairUp [] = [] pairUp (x:[]) = [] pairUp (x:y:xs) = (read x, read y) : pairUp xs

wizard2none + 0 comments Clojure. Worked easily enough using the union-find source code from here (code credit to Jordan Lewis)

przemek_kwiecien + 0 comments Hi guys! In my opinion, some test case data are not following common sense rule. How many hands have inmate? Rather not more than 2. So how many pairs can inmate create - in my opinion also 2. But in TC3 data points that inmate 22 is cuffed with 5 other inmates! Cuffing directly one person to 5 other is rather impossible. If I am correct description should be rephrased or some test cases changed.

PK

egoek + 0 comments So I have this, which compiles and runs fine locally:

import Data.Graph import Control.Monad groupSizes :: Graph -> [Int] groupSizes g = map (\x -> length x) (components g) cost :: Int -> Int cost x = head [c | c <- [1..], c * c >= x] group :: [String] -> [(Int, Int)] group input = map (\x -> (read (head x), read (last x))) (map words input) main = do n <- getLine m <- getLine pairs <- replicateM (read m) getLine let groups = group pairs prisoners = buildG (1, read n) groups tcost = map cost (groupSizes prisoners) putStrLn $ show $ sum tcost

However I get error: Couldn't match type ‘Tree Vertex’ with ‘[a0]’ when i run it in the buffer. I'm a Haskell beginner and not sure what to make of this. Can I not import Data.Graph or what?

nkrim + 2 comments Is anyone else having trouble getting the last test to pass in-time w/ Haskell. All the other tests pass very quickly and then the last one always times-out by a large margin, and I've tried using many differnet datatypes and setups and it's always the same.

Ido_Schwartzman + 0 comments I'm using Scala but I had a similar problem, until I've implemented the ranked union-find data structure - surprisingly enough, you don't even need the path compression to make it work fast enough - I'm assuming Haskell will give you similar results, as I've only used pure immutable structures. Read the Wikipedia article about disjoint sets - it has everything you need - it's simpler than it looks at first.

maqusss + 0 comments me too. Im using Data.Set datatype

cbrghostrider + 2 comments Where can I find a good Union-Find library for Haskell?

abhiranjan + 0 comments Hi, you can write it yourself :)

Ido_Schwartzman + 0 comments Just implement what you find in Wikipedia about ranked union find - you don't even need the path compression part, which seems to be counter-productive in pure functional implementations.

quick_dudley + 1 comment Where it says "Only one group of inmates can be transported per bus": for the purposes of this rule are single inmates considered to be groups of 1 or are we allowed to put all the single inmates on the same bus?

abhiranjan + 0 comments They are group of 1.

No more comments

Sort 8 Discussions, By:

Please Login in order to post a comment