Phone Words II.swift

/*:
## Phone Words

Generate a collection of words that can be represented by a given phone number. If a phone number contains the digits `1` or `0` then split up the phone number and find the words for each of the substrings as long as each substring has more than one digit. Non-keypad characters can be ignored. Optionally, filter out words so that only dictionary words are present in the result.

    ╔═════╦═════╦═════╗
    ║  1  ║  2  ║  3  ║
    ║     ║ abc ║ def ║
    ╠═════╬═════╬═════╣
    ║  4  ║  5  ║  6  ║
    ║ ghi ║ jkl ║ mno ║
    ╠═════╬═════╬═════╣
    ║  7  ║  8  ║  9  ║
    ║ pqrs║ tuv ║wxyz ║
    ╠═════╬═════╬═════╣
    ║  *  ║  0  ║  #  ║
    ║     ║     ║     ║
    ╚═════╩═════╩═════╝

Example

`1-8000-356-9377` should return "FLOWERS"
*/

/*:
Some helper code
*/

// /usr/share/dict/words is missing many plurals, ie. "flowers"
//let words = Set(
//    try String(contentsOfFile: "/usr/share/dict/words")
//        .componentsSeparatedByCharactersInSet(
//            NSCharacterSet.newlineCharacterSet()
//    )
//)

// The "words.txt" file below was copied from https://github.com/dwyl/english-words
public let words = Set(
    try! String(contentsOfURL: NSBundle.mainBundle().URLForResource("words-sorted-by-len", withExtension: "txt")!)
        .componentsSeparatedByCharactersInSet(
            NSCharacterSet.newlineCharacterSet()
    )
)

public func isWord(s: String) -> Bool {
    return words.contains(s)
}

extension Int {
    init?(c: Character) {
        guard let i = Int(String(c)) else { return nil }
        self = i
    }
}

func not<T>(pred: T -> Bool)(e: T) -> Bool {
    return !pred(e)
}

func isDigit(c: Character) -> Bool {
    return ("0"..."9").contains(c)
}

/*:
Used for mapping over a collection, replace items in the collection with values keyed by those items.

Example:

    let r = ["a": 1, "b": 12, "c": 144]
    ["a", "b", "c"].flatMap(transform(r))

Using the pipe-forward operator:

    ["a", "b", "c"].flatMap(r |> transform)
*/
func transform<T: Hashable, V>(dict: [T:V])(element: T) -> V? {
    return dict[element]
}

/*:
Pipe-forward operator

`f(x)` can be written as `x |> f`
*/
infix operator |> { precedence 50 associativity left }
public func |> <T,U>(lhs: T, rhs: T -> U) -> U {
    return rhs(lhs)
}

/*:
Protocol representing types that implement `+`
*/
protocol Combinable {
    func +(lhs: Self, rhs: Self) -> Self
}
extension String: Combinable {}

/*:
Return all combinations of elements of pre with elements of suf

Arguments are arrays of `Combinable`.
*/
func permute<T: Combinable>(pre:[T], _ suf: [T]) -> [T] {
    if pre.isEmpty { return suf }
    if suf.isEmpty { return pre }
    return pre.flatMap { p in suf.map { s in p + s } }
}

let keyMap: [Int: [String]] = [
    0: ["0"],
    1: ["1"],
    2: ["a","b","c"],
    3: ["d","e","f"],
    4: ["g","h","i"],
    5: ["j","k","l"],
    6: ["m","n","o"],
    7: ["p","q","r","s"],
    8: ["t","u","v"],
    9: ["w","x","y","z"]
]

/*:
1. Characters of the string
2. Convert each `Character` to an `Int?`
3. Replace each non-nil Int with an array of letters
4. Combine permutations of every element
5. Optionally, filter by a set of valid En-US words
*/
func phoneWords(number: String) -> [String] {
    return number
        .characters                   // 1
        .flatMap(Int.init)            // 2
        .flatMap(keyMap |> transform) // 3
        .reduce([], combine: permute) // 4
        .filter(isWord)               // 5
}

/*:
Similar to `phoneWords(String)` but with a min length
*/
func phoneWords(minLength minLength: Int)(number: String) -> [String] {
    if number.characters.filter(("2"..."9").contains).count >= minLength {
        return phoneWords(number)
    } else {
        return [number]
    }
}

/*:
1. Characters of the string
2. Split at non-digits
3. Convert each sub-array into `String`
4. Replace each `String` with an array of possible phone words
*/
let m = "1-800-3569377"
    .characters                       // 1
    .split(isSeparator: not(isDigit)) // 2
    .map(String.init)                 // 3
    .map(phoneWords(minLength: 2))    // 4

print(m)