Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Phone Number Kata
-- Given a list of phone numbers, determine if it is consistent.
-- In a consistent phone list no number is a prefix of another. For example:
-- Bob 91 12 54 26
-- Alice 97 625 992
-- Emergency 911
-- In this case, it is not possible to call Bob because the phone exchange
-- would direct your call to the emergency line as soon as you dialled the
-- first three digits of Bob's phone number. So this list would not be consistent.
-- Rule:
-- A phonelist is consistent if the phonelist contains none of that phonelist's prefixes
isConsistent phonelist = (phonelist`contains`) `noneOf` (phonelist`s` prefixes)
where contains = flip elem
noneOf pred list = not $ any pred list
s = (>>=)
prefixes s = tail $ foldl f [] s
f [] x = [[x]]
f (a:as) x = (a++[x]):a:as
isConsistent :: [String] -> Bool
-- isConsistent ["91125426","97625992", "911"]
-- False
-- isConsistent ["12345", "54321", "99999"]
-- True
module PhoneNumbers where
import Data.List
-- Rule:
-- A phonelist is consistent if the phonelist contains none of that phonelist's prefixes
isConsistent :: [String] -> Bool
isConsistent phonelist = (phonelist`contains`) `noneOf` (phonelist >>= prefixes)
where
contains = flip elem
noneOf pred list = not $ any pred list
-- Generates a list of all prefixes of a String
-- inits "abc" == ["","a","ab","abc"]
-- prefixes "abc" == ["a","ab"]
prefixes = tail . init . inits
-- ["abc", "xyz"] >>= prefixes
-- results in ["a","ab","x","xy"]
-- Which is really mapping prefixes over a phonelist and then flattening it
-- concat $ map prefixes ["abc", "xyz"]
-- In my previous version is aliased '>>=' to 's' to make it read as "a phonelist's prefixes"
@mathiasverraes

This comment has been minimized.

Copy link
Owner Author

@mathiasverraes mathiasverraes commented Sep 30, 2015

Kata Phone Numbers

Given a list of phone numbers, determine if it is consistent. In a consistent phone list no number is a prefix of another. For example:

Bob: 91 12 54 26
Alice: 97 625 992
Emergency: 911

In this case, it is not possible to call Bob because the phone exchange would direct your call to the emergency line as soon as you as dialed the first three digits of Bob’s phone number.

Sample phonebook datasets

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment