Google Code Jam in Scala : Speaking in Tounges

Part One of the series "let's solve Google Code Jam problems in Scala, without ever using the keyword var".

The first problem for the 2012 qualification round gives you the task of "implement a monoalphabetic substitution cipher if you have access to sufficient plaintext/ciphertext". At the bottom of the problem description you have a nice seed data, which you can put in a map:

val stringMap = Map(
  "ejp mysljylc kd kxveddknmc re jsicpdrysi"
         -> "our language is impossible to understand",
  "rbcpc ypc rtcsra dkh wyfrepkym veddknkmkrkcd"
         -> "there are twenty six factorial possibilities",
  "de kr kd eoya kw aej tysr re ujdr lkgc jv"
         -> "so it is okay if you want to just give up"
)

This is a string-to-string map. But you need a character-to-character map. Converting to that is easy, you just have to know some facts about the scala collections:

1. every map can be seen as a sequence of (key,value) pairs - you can iterate over them
2. a string is also a Seq[Char], and as such, it has a zip method. So if you zip two strings together, you get a sequence of character pairs
3. the reverse of (1), thus if you have a sequence of (key,value) pairs, you can create a map

val charMap = for(
    (keyString,valueString) <- stringMap;
    (key,value) <- keyString zip valueString)
  yield (key,value)

Since stringMap is of type Map[String,String], due to the clever scala mapping system, the type of charMap will be Map[Char,Char].
Now we can create our cipher decode function, and test it out. For this, I'm giving you a few different solutions, that are equivalent, as the differences are only syntactic sugar:

def decode(s:String) = for(c<-s) yield charMap(c)
def decode(s:String) = s.map(c=>charMap(c))
def decode(s:String) = s.map(charMap(_))
println(decode("rbcpc ypc rtcsra dkh wyfrepkym veddknkmkrkcd"))
"there are twenty six factorial possibilities"

Before you download the first input file to solve, you might ask one question: "I know map throws an exception for unknown keys. What if the sample we have so far doesn't cover all letters of the alphabet?" Good question. Let's ask our code for the answer! Again the extremely versatile collection classes come to the rescue:

1. you can use the magic keyword "to" to create a NumericRange, and it works for all numeric types, including Char
2. basically every collection has a toSet method, that creates an immutable set
3. sets have a substitution operation "--" that can remove from a set anything that can be iterated over
4. maps have methods to get the keys and the values as Iterables

val alphabet = ('a' to 'z').toSet
println(alphabet -- charMap.keys)
Set(q, z)
println(alphabet -- charMap.values)
Set(q, z)

Oops, there are two characters that don't have a mapping. Fortunately, if you read the beggining of the problem, there are some hints...