Created
June 25, 2016 19:40
-
-
Save lonnelars/567a0c4b45767b4fa9c2d5b2ef6ceaa1 to your computer and use it in GitHub Desktop.
Solution in haskell for the phone list problem from open.kattis.com
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import Control.Monad (replicateM) | |
data Tree a = EmptyTree | Node a [Tree a] deriving (Show, Eq) | |
label :: Tree a -> a | |
label (Node a _) = a | |
subforest :: Tree Char -> [Tree Char] | |
subforest (Node _ subforest) = subforest | |
countLeaves :: Tree Char -> Int | |
countLeaves t = | |
if (subforest t) == [] | |
then 1 | |
else sum $ map countLeaves (subforest t) | |
insertForest :: String -> [Tree Char] -> [Tree Char] | |
insertForest "" forest = forest | |
insertForest (d:ds) [] = [Node d (insertForest ds [])] | |
insertForest number@(d:ds) (t:ts) = | |
if d == label t | |
then (Node (label t) (insertForest ds (subforest t))):ts | |
else t:(insertForest number ts) | |
insertNumbers :: [String] -> [Tree Char] -> [Tree Char] | |
insertNumbers [] forest = forest | |
insertNumbers (n:ns) forest = insertNumbers ns (insertForest n forest) | |
performTestCase :: IO String | |
performTestCase = do | |
numberOfLines <- getLine | |
numbers <- replicateM (read numberOfLines) getLine | |
let forest = insertNumbers numbers [] | |
let count = sum $ map countLeaves forest | |
if count == length numbers then return "YES" else return "NO" | |
main = do | |
testCases <- getLine | |
testResults <- replicateM (read testCases) performTestCase | |
mapM putStrLn testResults |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment