public
Created

  • Download Gist
gistfile1.txt
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78
> module Main where
>
> import Data.List (sort)
 
I don't need to know anything about the precise positions of the Wire's
end points, all that is important is the relative positions (the problem
states that only 2 wires cross at one point, so I don't have to worry about
the angles of the wires).
 
Given the wire that is lowest on the left building, I know that another wire
cannot cross it if both of that wire's endpoints are higher up the building.
Given this is the lowest wire on the left, I already know the other wire's
left position will be higher, so I only need to consider whether the right
position is higher (no crossing), or lower (crossing).
 
I sort the wires based on their position on the left building, and recurse, so
that I am always considering the wire lowest on the left building, and count
the number of crossing wires.
 
As we are only considering right positions, we don't actually need the left
positions after sorting, so we discard them.
 
If there are no wires, there are no crossings, so the base case is zero.
 
I haveb't used a data type for Wires, preferring a simple pair - maybe this
is me trying to do scheme in haskell.
 
> ropeIntranet :: (Ord a) => [(a,a)] -> Int
> ropeIntranet wires = countCrossings $ map snd (sort wires)
 
> countCrossings :: (Ord a) => [a] -> Int
> countCrossings (x:xs) = length (filter (< x) xs) + countCrossings xs
> countCrossings [] = 0
 
Now we come to the "hard part": dealing with reading a simple file format.
This took me about 10 times as long as solving the problem.
 
I've chosen to stay out of IO as much as possible, and just deal with one
big string. There are almost certainly better ways to do this. Enlighten me!
 
Start simply - given a string like "1 10", I need to turn it into a pair of
Ints.
 
> strToTuple :: String -> (Int, Int)
> strToTuple str = (read (xs !! 0), read (xs !! 1)) where xs = words str
 
I follow the problem, using the first line in a case as the number of wires and
taking that many more lines from the string, converting them and getting a
result for that case from ropeIntranet.
> executeIt :: [String] -> [Int]
> executeIt (x:xs) = let i = (read x) in
> (ropeIntranet (map strToTuple (take i xs))) : executeIt (drop i xs)
> executeIt [] = []
 
Give everything an index, so we can output the case number. I couldn't
find anything equivilent to Ruby's each_with_index method.
> addIndexes :: [a] -> [(Int, a)]
> addIndexes a = zip [1..(length a)] a
 
Format the result as wanted.
 
> formatResult :: (Int, Int) -> String
> formatResult (i, result) = concat ["Case #", (show i), ": ", (show result)]
 
The main IO loop which reads from stdin and writes to stdout.
 
> main :: IO ()
> main = do
I don't care about the total number of cases, so I discard the first line.
> _ <- getLine
> str <- getContents
 
Output the results. mapM_ seems an odd name.
 
> mapM_ (putStrLn . formatResult) ((addIndexes . executeIt . lines) str)

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.