Phone List challenge

Question

To learn Haskell, I've been going at this challenge, which is to check a list of phone numbers to ensure that no number is a prefix of another. However, my code is way too slow. I am really new to Haskell so I don't know what to look for in performance optimization.

I have generated a sample input which takes 5s (uncompiled via runhaskell) on my machine. What can I do to speed this up?

main = do
    content <- getContents
    let 
        allLines = lines content
        caseCount = read (head allLines) :: Int
        cases = tail allLines
    putStr $ unlines $ map toYesNo (processCases cases caseCount)

toYesNo b 
    | b = "YES"
    | otherwise = "NO"

processCases :: [[Char]] -> Int -> [Bool]
processCases [] num = []
processCases cases 0 = []
processCases cases remaining =
    let 
        caseLines = read (head cases) :: Int
        current = take caseLines (tail cases)
    in (if (checkListConsistency current) then True else False)
        : (processCases (drop (caseLines+1) cases) (remaining-1))

checkListConsistency :: [[Char]] -> Bool
checkListConsistency [] = True
checkListConsistency list =
    let
        number = head list
        rest = tail list
    in if checkNumberConsistency number rest
        then checkListConsistency rest
        else False

checkNumberConsistency :: [Char] -> [[Char]] -> Bool
checkNumberConsistency number [] = True
checkNumberConsistency number list =
    foldr (&&) True (map (checkNumberConsistencyVsNumber number) list)

checkNumberConsistencyVsNumber :: [Char] -> [Char] -> Bool
checkNumberConsistencyVsNumber number number2 =
    let
        numberLength = length number
        number2Length = length number2
    in if numberLength > number2Length 
        then notStartsWith number number2
        else notStartsWith number2 number

notStartsWith _ [] = False
notStartsWith [] _ = True
notStartsWith (hl:tl) (hs:ts) 
        | hl == hs = notStartsWith tl ts
        | otherwise = True

Answer 1

Inlining very short expressions

It is better to avoid the in dialect when the expression is really short, checkNumberConsistencyVsNumber can be written in a much shorter manner

checkNumberConsistencyVsNumber :: [Char] -> [Char] -> Bool
checkNumberConsistencyVsNumber number number2
        | length number > length number2 = notStartsWith number number2
        | otherwise = notStartsWith number2 number

Types everywhere

It is very good that your code is mostly typed, I would finish the job giving types to main and toYesNo:

main :: IO()
toYesNo :: Bool -> [Char]

Use built-ins

Built-ins make the code faster, shorter and easier, for example the below line would benefit from all

foldr (&&) True (map (checkNumberConsistencyVsNumber number) list)

Be sure to use -O2

That is to compile with ghc -O2 phone.hs for automatically faster code

Answer 2

Performance

Your program is slow because you check each number against all subsequent numbers. For a fully consistent phone book with n entries, that's O(n²).

A better strategy would be to sort each phone book first. Then you only need to check consecutive pairs. If one number is a prefix of another, then the prefix will appear just before the longer number. That's O(n log n) for the sorting, plus O(n) for the checking, which is O(n log n) in total.

Looping

The infrastructure for handling test cases is clumsy.

One problem stems for the fact that you slurp up all the input into one list right away, with content <- getContents followed by allLines = lines content. As a result processCases has to take a list of those lines as input, and parcel them out using drop (caseLines+1) cases. A further complication is that allLines contains non-homogeneous data: the first line specifies the number of test cases, the first line within each test case specifies the size of that test case, and all other lines contain phone numbers. You're basically doing I/O by dissecting the list, and you would be better off doing real I/O.

processCases performs a countdown using its second parameter. It would be better to have a processCase function instead, which is called n times. You can't make that improvement, though, given the way all the input has been slurped up into one list.

Style

• For readability, maintainability, and performance, declare the types of all functions. You missed toYesNo and main. Instead of [[Char]], use [String], which is easier to understand.
• Avoid function names like checkSomething, which sound more imperative than functional. For example, isListConsistent would be a better name than checkListConsistency.
• Take advantage of standard library functions — use Google and Hoogle. For example, notStartsWith is just ((not.).isPrefixOf).

• Simplify predicate tests on a list. checkNumberConsistency can be

  checkNumberConsistency :: String -> [String] -> Bool
  checkNumberConsistency n ns = all (checkNumberConsistencyVsNumber n) ns
  

• Avoid if … then … else. There is usually a better alternative. For example, (if (checkListConsistency current) then True else False) is just checkListConsistency current. Your checkListConsistency function can be simplified:

  checkListConsistency :: [String] -> Bool
  checkListConsistency [] = True
  checkListConsistency (n:ns) = (checkNumberConsistency n ns) && (checkListConsistency ns)
  

Suggested solution

import Control.Monad (replicateM, replicateM_)
import Data.List (isPrefixOf, sort)

isConsistentPhoneList :: [String] -> Bool
isConsistentPhoneList numbers = not $ any (uncurry isPrefixOf) consecutivePairs
  where
    sortedNumbers = sort numbers
    consecutivePairs = zip sortedNumbers $ tail sortedNumbers

yesNo :: Bool -> String
yesNo True = "YES"
yesNo False = "NO"

processCase :: IO ()
processCase = do
  caseSize <- readLn
  inputs <- replicateM caseSize getLine
  putStrLn $ (yesNo . isConsistentPhoneList) inputs

main :: IO ()
main = do
  caseCount <- readLn
  replicateM_ caseCount processCase

Answer 3

Using the isPrefixOffunction from Data.List

The Data.Listpackage has a a function called isPrefixOf, which can be used to build a single isValidPhoneLstfunction, like this:

isValidPhoneLst :: [String] -> String
isValidPhoneLst [] = "YES"
isValidPhoneLst [p] = "YES"
isValidPhoneLst (h:t) = 
    case any (==True) [isPrefixOf h a || isPrefixOf a h | a <- t] of
        True -> "NO"
        _ -> isValidPhoneLst t

Simplifying your mainfunction with replicateM and mapM_

The replicateM function performs an action n times, gathering the results. It can be used to build a list of only the test cases that you need. As for printing the results, you can use the mapM_ function to print the results of the isValidPhoneLstfunction applied to the test cases, like this:

import Control.Monad(replicateM)
import Data.List(isPrefixOf)

main :: IO ()
main = do
    nTestCases <- readLn
    tests <- replicateM nTestCases $ do
        testCaseSize <- readLn
        replicateM testCaseSize getLine
    mapM_ (putStrLn . isValidPhoneLst) tests

isValidPhoneLst :: [String] -> String
isValidPhoneLst [] = "YES"
isValidPhoneLst [p] = "YES"
isValidPhoneLst (h:t) = 
    case any (==True) [isPrefixOf h a || isPrefixOf a h | a <- t] of
        True -> "NO"
        _ -> isValidPhoneLst t

Using the test case you provided, the main program ran in 349 Milliseconds, compiled without any optimizations.

On Kattis

I've made a kattis account and after submitting this solution I also got Time Limit Exceed. I wish they would provide more information to us users, such as websites like Hackerrank do.