Generating Phone Words in Swift

Question

I've been playing around with some basic algorithms in Swift. Here I am trying to generate phone words, words which can be mapped from phone numbers using the characters under each digit. I was trying to use map/filter etc.. as much as possible, do you think the result ended up being more readable or less?

First step, getting the word list ready.

The built-in words file "/usr/share/dict/words" can be used. But it seems to be missing plurals like "flowers".

The "words.txt" file used below can be found at dwyl/english-words.

If you are pasting this into a playground then it's best to put this part in the "Sources" directory so it doesn't get evaluated every time

let words = Set(
    try! String(contentsOfURL: NSBundle.mainBundle().URLForResource("words", withExtension: "txt")!)
        .componentsSeparatedByCharactersInSet(
            NSCharacterSet.newlineCharacterSet()
    )
)

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

Next, the mapping of keys to characters (array of one-letter strings).

let phoneKeyMap: [Character: [String]] = [
    "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"]
]

Some helper functions. These aren't really necessary but I think it makes the last bit of code more readable.

func isPhoneKeyMappable(c: Character) -> Bool {
    return ("2"..."9").contains(String(c))
}

func hasMoreThanOne<T: CollectionType>(c: T) -> Bool {
    return c.count > 1
}

func filterWith<T: CollectionType>(pred: T.Generator.Element -> Bool)(c: T) -> [T.Generator.Element] {
    return c.filter(pred)
}

Generate phone words recursively

1. handle empty string
2. handle non keypad characters
3. termination condition
4. recursively build words
5. combine words with all characters for cur key

This function expects the passed-in string to have characters "2"..."9".

func phoneWords(s: String) -> [String] {
    guard let n = s.characters.first else { return [] } // 1
    guard let px = phoneKeyMap[n] else { return [] } // 2
    if s.characters.count == 1 { return px } // 3
    let sx = phoneWords(String(s.characters.dropFirst())) // 4
    return px.flatMap { p in sx.map { s in p + s } } // 5
}

Generate phone words for the phone number 1-800-FLOWERS

1. split the phone number at "1" and "0"
2. filter out digits that are not 2-9
3. filter out single-digit words
4. convert each collection of Character into a String
5. convert each string into a collection of words based on keypad
6. filter out non-engligh words based on a word dictionary

Finally:

"1-800-356-9377".characters
    .split { ("0"..."1").contains(String($0)) } // 1
    .map(filterWith(isPhoneKeyMappable)) // 2
    .filter(hasMoreThanOne) // 3
    .map(String.init) // 4
    .map(phoneWords) // 5
    .map(filterWith(isWord)) // 6

Edit

I've made some changes, I think this is an improvement. A quick outline of the changes:

1. Made the key mapping [Int: [String]] instead of [Character: [String]]. The original version ended up breaking the input into characters then turning them into strings then breaking them back out into characters. This could have just been an array of type [[String]] but I like the fact that dictionary returns an optional when subscripted.
2. Removed isPhoneKeyMappable. The key mapping handles this by removing nils (via flatMap) when converting from digits to array of String.
3. Added some helper methods, renamed other.
4. phoneWords has been replaced with a more general permute function which simply returns all the permutations of the subarray items.

Here is the updated code (not including the words list which hasn't changed):

/*:
This solution involves using a map of `Int` to `String` arrays. `String` arrays are used instead of just strings since we have to split each string into characters and convert back to `String` for concatenation anyway. This could be done as an array since the key is an `Int`, but using a map gives us added safety by returning optionals when subscripting.
*/

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"]
]

/*:
Generate permutations

1. handle empty string
2. termination condition
3. recursively generate permutations on smaller inputs
4. combine prefixes with each result from recursive permutation
*/
func permute(parts: [[String]]) -> [String] {
    guard let prefixes = parts.first else { return [] } // 1
    if parts.count == 1 { return prefixes } // 2
    let sx = permute(Array(parts.dropFirst(1))) // 3
    return prefixes.flatMap { p in sx.map { s in p + s } }
}

/*:
Some helper functions to make things more readable later
*/
func hasMoreThanOne<T: CollectionType>(c: T) -> Bool {
    return c.count > 1
}

func filter<T: CollectionType>(pred: T.Generator.Element -> Bool)(c: T) -> [T.Generator.Element] {
    return c.filter(pred)
}

func flatMap<T: CollectionType, V>(transform: T.Generator.Element -> V?)(c: T) -> [V] {
    return c.flatMap(transform)
}

func transform<T: Hashable, V>(dict: [T:V])(element: T) -> V? {
    return dict[element]
}

infix operator |> { precedence 50 associativity left }

public func |> <T,U>(lhs: T, rhs: T -> U) -> U {
    return rhs(lhs)
}

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

extension CollectionType where Generator.Element : Equatable {
    public func split(separators: Self.Generator.Element...) -> [Self.SubSequence] {
        return self.split(isSeparator: separators.contains)
    }
}

/*:
Generate phone words for the phone number `1-800-FLOWERS`

1. break the string down into an array of `Character`
2. convert each `Character` into an `Int`
3. split into subarrays of `Int`
4. replace each digit with a list of characters
5. filter out single-digit subarrays
6. generate permutations
7. filter out non-engligh words
*/
let mnemonics = "1-800-356-9377"
    .characters                          // 1
    .flatMap(Int.init)                   // 2
    .split(1, 0)                         // 3
    .map(keyMap |> transform |> flatMap) // 4
    .filter(hasMoreThanOne)              // 5
    .map(permute)                        // 6
    .map(isWord |> filter)               // 7

print(mnemonics) // [["flowers"]]

Answer 1

Here is my version, It Would need, some kind of isWord function to make it useful

You may find it easier to read it from the bottom up

The use of an enum improves readability a bit and makes it easy to change. I think the performance would be the same so the main difference between the solutions is the coding style, which is a matter of preference.

I have not handled the nonnumeric character in the phone number and leave it up to the caller of the routine to remove them. This concentrates on the core functionality.

My solution is agnostic to how many characters if any are mapped to the number which makes it robust.

enum Dialpad : Int {
  case zero ,one ,two ,three ,four ,five ,six ,seven ,eight ,nine

  var letters : [String] {
    switch self {
    case .zero,.one:
      return []
    case .two:
      return ["a","b","c"]
    case .three:
      return ["d","e","f"]
    case .four:
      return ["g","h","i"]
    case .five:
      return ["j","k","l"]
    case .six:
      return ["m","n","o"]
    case .seven:
      return ["p","q","r","s"]
    case .eight:
      return ["t","u","v"]
    case .nine:
      return ["w","x","y","z"]
    }
  }
}
// recursive function which takes in arrays of characters || strings
// and spits out the combinations example ["A","B"],["C","D"] -> ["AC","AD","BC","DE"]
// the output is n*m
func comboArray(_ arrays:[[String]], n:Int,set:inout Set<String>) {
  if n >= arrays.count { return }
  let array = arrays[n]
  if set.isEmpty {
    set = Set(array)
  } else {
    set.forEach { (c1) in
      array.forEach({ (c2) in
        set.insert(c1+c2)
      })
      if !array.isEmpty {
        set.remove(c1)
      }
    }
  }
  comboArray(arrays, n: n+1, set: &set)

}
// takes in a number and maps it to the letters on a phone dialpad
func dialPadLetters(number:Int) -> Set<String> {
  let stringNumber = String(number)
  var arrayLetter : [Array<String>] = []
  for c in stringNumber {
    let n = Int(String(c))! // back to a number it is safe to force unwrap
    let letters = Dialpad(rawValue: n)!.letters
    arrayLetter.append(letters)
  }
  var mySet : Set<String> = []
  comboArray(arrayLetter, n: 0, set: &mySet)
  return mySet
}

let theSet = dialPadLetters(number: 1234)

print(" theset \(theSet)")