Could someone share a clean version of the Coder class from Odersky's keynote at Scala Days 2011?

Question

Martin Odersky delivered the keynote at Scala Days 2011. In it he presented an impressive solution to the famous phone number phrase encoder problem used in Lutz Prechelt's "An Empirical Comparison of Seven Programming Languages" article in IEEE Computer 33. I tried to take the code from the PDF, but the result was full of non-breaking spaces, which are hard to get rid of.

Also, there are some odd things in the solution given, like types explicitly mentioned when they could have been inferred, and a Map with List[String] values being given a default value of 0. And it's just a class; it's not executable.

Does anyone have a ready-to-go, cleaned up version of that exemplary code?

The keynote video and slides are available here:

http://days2011.scala-lang.org/node/138/270

Answer 1

Here is a cleaned up version of the Coder class, along with a CoderTest class that you execute like so, the first argument being the phone number to encode and the rest being words in the dictionary:

$ scala CoderTest 7225276257 let us see if scala rocks is in the output
Set(scala rocks)

This output says that for the phone number and dictionary given, the only encoding found is the pair of words "scala rocks".

Here's the test driver:

object CoderTest extends App {
  val digits::words = args.toList
  println( new Coder(words) translate digits )
}

And here's the Coder class itself. I've changed some of the identifiers and comments to make them clearer to myself.

class Coder( words: List[String] ) {

  // In this code "num" means a string of digits, e.g. "834921".

  val digitToLetters = Map(
    '2' -> "ABC", '3' -> "DEF" , '4' -> "GHI", '5' -> "JKL",
    '6' -> "MNO", '7' -> "PQRS", '8' -> "TUV", '9' -> "WXYZ"
  )

  // Invert digitToLetters to give a map from chars 'A'..'Z' to '2'..'9'.
  val letterToDigit =
    for ( (digit,itsLetters) <- digitToLetters; letter <- itsLetters )
      yield ( letter -> digit ) 

  // Maps a word to the digit string it can represent.
  def wordToNum( word: String ) = word.toUpperCase map letterToDigit 

  // Map from digit string to words in our dictionary that represent it.
  // e.g. 5282 -> List( Java, Kata, Lava, ... )
  val numToWords = ( words groupBy wordToNum ) withDefaultValue List()

  // Maps a digit string to all phrases (lists of dictionary words)
  // that represent it.
  def numToPhrases( num: String ): Set[ List[String] ] =
    if ( num.isEmpty )
      Set( List() )
    else (
      for { splitPoint <- 1 to num.length
            word   <- numToWords  ( num take splitPoint )
            phrase <- numToPhrases( num drop splitPoint )
      } yield word::phrase
    ).toSet

  // Maps a number to the set of all word phrases that can represent it.
  def translate( num: String ) = numToPhrases(num) map ( _ mkString " " ) 

}

Remember, though, that it is actually a good idea to specify the return types of methods which form part of a public API. And now you can use splitAt to do the take and drop in one go.