Return to Revisions

Desired Feedback

I'm looking for feedback regarding ways this could be: more concise/clean, more idiomatic Haskell, or if there are algorithmic/mathematical tricks I missed that could further simplify the computation.

Problem Description

The input is read in line by line from stdin.

Input Format

The first line contains an integer, T, denoting the number of test cases. The subsequent lines describe T test cases, and the input for each test case is as follows:

The first line contains an integer, N, the number of (x,y) pairs in the test case. The N subsequent lines each contain two space-separated integers describing the respective x and y values for each ordered pair.

Constraints

1 ≤ T ≤ 51 ≤ T ≤ 5

2 ≤ 2 ≤ N ≤ 100 ≤ 100

0 ≤ x, y ≤ 5000 ≤ x, y ≤ 500

x and y are both integers.

Output Format

On a new line for each test case, print YES if the set of ordered pairs represent a valid function, or NO if they do not.

Sample Input

2
3
1 1
2 2
3 3
4
1 2
2 4
3 6
4 8

Sample Output

YES
YES

Full problem statement: https://www.hackerrank.com/contests/lambda-calculi-march-2016/challenges/functions-or-not

Code

import System.IO (readLn, getLine)
import Control.Monad (replicateM, mapM_, liftM)
import Data.List (nub)
import qualified Data.Map.Strict as M
data YesNo = YES | NO deriving Show
boolToYesNo :: Bool -> YesNo
boolToYesNo x = if x then YES else NO
readInt :: IO Int
readInt = readLn
tuplefy :: [a] -> (a, a)
tuplefy xs = case xs of [a, b] -> (a, b)
 _ -> error "each item must consist of 2 values."
readPair :: [String] -> [(Int, Int)]
readPair = map $ tuplefy . map (read :: String -> Int) . words
getPairs :: Int -> IO [String]
getPairs = flip replicateM getLine
readTestCase :: Int -> IO [(Int, Int)]
readTestCase = fmap readPair . getPairs
 
readTestCases :: Int -> IO [[(Int, Int)]]
readTestCases = flip replicateM $ readInt >>= readTestCase
printAnswers :: Show a => [a] -> IO ()
printAnswers = mapM_ print
isSingletonSet :: Eq b => [b] -> Bool
isSingletonSet xs = case nub xs of [x] -> True
 _ -> False
listToMultiMap :: (Ord k, Eq k, Eq v) => [(k, v)] -> M.Map k [v]
listToMultiMap ((k, v):vs) = toMap (M.fromList [(k, [v])]) vs
 where toMap m xs = case xs of [] -> m
 (k0, v0):ys ->
 case M.lookup k0 m of Nothing -> toMap (M.insert k0 [v0] m) ys
 Just v0s -> toMap (M.insert k0 (v0:v0s) m) ys
functionOrNot :: [(Int, Int)] -> YesNo
functionOrNot tuples = boolToYesNo $ foldl1 (&&) $ M.elems $ M.map isSingletonSet $ listToMultiMap tuples
main :: IO ()
main = getAnswers >>= printAnswers
 where getAnswers = (liftM . map) functionOrNot $ readInt >>= readTestCases