Submission #332746

---

Source Code Expand

{-# LANGUAGE OverloadedStrings #-}

import Control.Monad
import Data.List (sort)
import qualified Data.Text as T
import qualified Data.Text.IO as TIO

type RainPeriod = (Int, Int)

main :: IO ()
main = do
    n <- fmap read getLine :: IO Int
    inputLines <- replicateM n getLine
    let rainTimeTuples = fmap (tuplify2 . (fmap timeStringToMinutes) . splitTime) inputLines
    let normalizedRainPeriods = fmap normalize rainTimeTuples
    let mergedRainPeriods = merge normalizedRainPeriods
    let sortedRainPeriods = sort mergedRainPeriods
    let prettyRainPeriods = fmap prettyPeriod sortedRainPeriods
    mapM_ TIO.putStrLn prettyRainPeriods

splitTime :: String -> [String]
splitTime s = [take 4 s, drop 5 s]

prettyPeriod :: RainPeriod -> T.Text
prettyPeriod (rs, re) = prettyTime rs `T.append` T.pack "-" `T.append` prettyTime re

prettyTime :: Int -> T.Text
prettyTime t = T.append hourText minuteText
    where hourText = T.justifyRight 2 '0' $ T.pack $ show (t `div` 60)
          minuteText = T.justifyRight 2 '0' $ T.pack $ show (t `mod` 60)

tuplify2 :: [a] -> (a, a)
tuplify2 [x, y] = (x, y)

-- Turn 1005 -> 10 * 60 + 10 = 610
timeStringToMinutes :: String -> Int
timeStringToMinutes s = hours * 60 + minutes
    where hours = read $ take 2 s
          minutes = read $ drop 2 s

-- fold together overlapping time tuples
merge :: [(Int, Int)] -> [(Int, Int)]
merge = foldl joinTuples []

-- split list into start and first match + rest where a boolean property is
-- true
splitOnFirst :: (a -> Bool) -> [a] -> ([a], [a])
splitOnFirst _ [] = ([], [])
splitOnFirst p (x:xs)
    | p x = ([], x:xs)
    | otherwise = let (befores, afters) = splitOnFirst p xs in (x:befores, afters)

-- join together two overlapping time tuples
joinTuple :: Ord a => (a, a) -> (a, a) -> (a, a)
joinTuple (s1, e1) (s2, e2) = (minimum [s1, s2], maximum [e1, e2])

-- check if two tuples overlap
overlaps :: Ord a => (a, a) -> (a, a) -> Bool
overlaps (s1, e1) (s2, e2)
    | s1 <= s2 && e1 >= e2 = True
    | s2 <= s1 && e2 >= e1 = True
    | s1 >= s2 && s1 <= e2 = True
    | e1 >= s2 && e1 <= e2 = True
    | otherwise = False

-- Find the tuple that overlaps and join the two
joinTuples :: [(Int, Int)] -> (Int, Int) -> [(Int, Int)]
joinTuples [] t = [t]
joinTuples ts t = case splitOnFirst (overlaps t) ts of
    (firstHalf, []) -> t:firstHalf
    (firstHalf, mid:secondHalf) -> joinTuples (firstHalf ++ secondHalf) (joinTuple t mid)

-- Divide by 5, floor the first one, ceiling the second, then multiply back
-- up by 5
normalize :: RainPeriod -> RainPeriod
normalize (s, e) = (peg floor s, peg ceiling e)

peg :: Integral a => (Double -> a) -> a -> a
peg f n = f (fromIntegral n / 5) * 5

Submission Info

Judge Result