# Prison Transport

# Prison Transport

- EG
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.

- P
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.

- MM
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 :)

- P
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.

- JL
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 4 Discussions, By:

Please Login in order to post a comment