Parses a phone number and finds all possible words based on numpad-to-letter mapping and dictionary

phone_number_to_words.scala

trait SolutionDef { self: DictionaryDef with DebugDef =>
  /*
   *  based on the example included:
   *  866-5548 -> tool-kit
   *  the assumption is made that '-' symbol position doesn't matter
   *  and it's not a word divider
   *  e.g. any of those groups of numbers can make up a final sequence of words:
   *  86 65548, 86665 548, 86 655 48, etc.
   *
   *  here is no phone number format specified as every coutry has its own
   *  so for the sake of simplicity any special symbols and non-digits
   *  are ignored (0, 1 too as do not produce output)
   */
  def phoneNumberFilter(str: String): Seq[Char] = str
    .filter(('2' to '9').contains)

  /*
   *  here we can potentially improve by memoizing result for the same tail
   *  For the given phone string (filtered) function returns a sequence of
   *  different variants of words
   */
  def variants(str: Seq[Char]): Seq[Seq[List[String]]] =
    if(str.nonEmpty)
      (1 to str.size).flatMap { i =>
        val number: Long = str.take(i).mkString("").toLong
        val tail = str.drop(i)
        val tailVariants = variants(tail)
        if (tailVariants.isEmpty && tail.nonEmpty) Seq.empty else {
          val wordsOpt: Option[List[String]] = keypadDictionary.get(number)
          //debug(s"$number = ${wordsOpt.getOrElse(Nil).mkString(",")}, tail = $tail, tailvariants = ${tailVariants.mkString(",")}")
          wordsOpt.map(words =>
            if (tail.isEmpty) Seq(Seq(words)) else tailVariants.map(words +: _)
          ).getOrElse(Seq.empty)
        }
      } else Seq.empty

  def solution(phone: String): Seq[List[String]] = {
    val seq = ((variants _) compose phoneNumberFilter).apply(phone)
    val result = seq.flatMap(combinations)
    result
  }

  // return combinations based on given variants for each position
  // e.g. given [[1,2], [3,4]] returns [[1,3], [1,4], [2,3], [2,4]]
  def combinations(seq: Seq[List[String]]): Seq[List[String]] = {
    seq.headOption.map { head: List[String] =>
      val tail: Seq[List[String]] = seq.tail
      val tailCombinations: Seq[List[String]] = combinations(tail)
      debug(head.mkString(","))
      if (tailCombinations.isEmpty) head.map{w => List(w)}
      else head.flatMap(word => tailCombinations.map(word :: _))
    }.getOrElse(Seq.empty)
  }

}

trait DebugDef {

  def debug(s: String): Unit = {
    val depth = new Throwable().getStackTrace().length
    println(s"DEBUG-$depth: $s")
  }
}
trait NoDebug extends DebugDef {
  override def debug(s: String) = () 
}

trait DictionaryDef { self: DebugDef =>
  val dictionary: Seq[String]

  // (2 to 9) zip ('a' to 'z').grouped(3).toList
  lazy val keypad2Letters: Map[Int, List[Char]] = Map(
    0 -> Nil, 1 -> Nil,
    2 -> List('a', 'b', 'c'),
    3 -> List('d', 'e', 'f'),
    4 -> List('g', 'h', 'i'),
    5 -> List('j', 'k', 'l'),
    6 -> List('m', 'n', 'o'),
    7 -> List('p', 'q', 'r', 's'),
    8 -> List('t', 'u', 'v'),
    9 -> List('w', 'x', 'y', 'z')
  )
  lazy val reverseKeypad: Map[Char, Int] = keypad2Letters.toList
    .flatMap {  case (numb, chars) => chars.map(_ -> numb) }
    .toMap

  /*
   *  words which cannot be interpreted into keypad sequence are skipped
   *  (non a-zA-Z)
   *  lowercase included
   */
  lazy val keypadDictionary: Map[Long, List[String]] =
    dictionary.map { word =>
      val mappedOpts = word.toLowerCase().map(reverseKeypad.get)
      if (mappedOpts.contains(None)) {
        debug(s"couldn't parse $word")
        None
      } else {
        val numb = mappedOpts.flatten.toList.decimal
        Some(numb -> word)
      }
    }.flatten.groupBy(_._1).toMap.mapValues(_.map(_._2).toList)

  implicit class ListIntDecimal(l: List[Int]) {
    def decimal: Long = l.foldLeft[Long](0l) { case (a, b) => 10l * a + b }
  }
}

/**
  * The complexity of the provided solution is O(M) + O(2^n)
  * where M is size of the dictionary and n is the length of the phone number.
  *
  * Memory footprint relative to the size of the dictionary supplied. (<1mb for default dict)
  * If we are in a really bad situation of limited memory - then we still can write
  * transformed dictionary to database/disk and provided algorithm still works
  * 
  * complexity can be simplified down to n^3 I think although
  * as phone number cannot be more then ~12 long
  */
object Solution extends App {

  val linuxWordsDictionary = scala.io.Source
    .fromURL("https://users.cs.duke.edu/~ola/ap/linuxwords")
    .mkString
    .split("\n")

  val solver = new SolutionDef with DictionaryDef with NoDebug {
    override val dictionary = linuxWordsDictionary
  }
  
  if (args.length == 0) {
    println("please, specify phone number as an input argument")
  } else if (args(0).length >= 15) {
    println("phone number is too long")
  } else {
    val phoneStr = args(0)
    //println(s"solving for phone number = ${solver.phoneNumberFilter(phoneStr)}")
    val result = solver.solution(phoneStr)
    println(result.map(_.mkString("-")).mkString("\n"))
  }


}

object SolutionSpecs extends App {

  val test = new SolutionDef with DictionaryDef with DebugDef {
    val dictionary = List("foo", "bar", "emo")
  }
  // reverse keypad should be valid
  assert(test.reverseKeypad('h') == 4)
  assert(test.reverseKeypad('z') == 9)
  assert(test.reverseKeypad('s') == 7)

  // keypad dictionary should be valid
  assert(test.keypadDictionary(366l).contains("foo"))
  assert(test.keypadDictionary(366l).contains("emo"))
  assert(test.keypadDictionary(227l).contains("bar"))

  // combinations should return valid result
  val words = List(List("foo", "bar"), List("fo", "ba"))
  assert(test.combinations(words).contains(List("foo", "fo")))
  assert(test.combinations(words).contains(List("bar", "ba")))

  val result = test.solution("366227")
  assert(result.contains(List("foo", "bar")))

  val resultWith01 = test.solution("01366227")
  assert(result.size == resultWith01.size)
}