1067

problem.hs

import Control.Monad
import Data.Tree
import Data.List
import Data.Function (on)

type Path = [String]

splitPath :: String -> Path
splitPath s = unfoldr go s
  where
    go [] = Nothing
    go x = case break (== '\\') x of
             (p, []) -> Just (p, [])
             (p, (_:ps)) -> Just (p, ps)

insertT :: Path -> Forest String -> Forest String
insertT [] f = f
insertT path [] = [unfoldTree go path]
  where
    go [p] = (p, [])
    go (p:ps) = (p, [ps])
insertT path@(p:ps) (t@(Node root forest): rest) =
  if p == root
    then Node root (insertT ps forest) : rest
    else t : insertT path rest


readInput :: IO [Path]
readInput = do
  n <- read `fmap` getLine
  paths <- replicateM n getLine
  return $ map splitPath paths

buildForest :: [Path] -> Forest String
buildForest paths = foldr insertT [] paths

sortForest :: Forest String -> Forest String
sortForest forest = sortBy (compare `on` rootLabel) forest

renderForest :: Forest String -> [String]
renderForest = concatMap (render 0)
  where
    render :: Int -> Tree String -> [String]
    render i t = (replicate i ' ' ++ rootLabel t) : concatMap (render (i+1)) (sortForest (subForest t))

main :: IO ()
main = do
  input <- readInput
  let forest = sortForest $ buildForest input
  -- putStrLn $ drawForest forest
  forM_ (renderForest forest) $ \line ->
      putStrLn line