Alien Numbers - how Scala-ish is my solution?

Question

I'm trying to solve an old GCJ. It's a very simple puzzle, but I'm trying to sharpen my Scala-fu.

Basically, you're getting a list of triple number srcLanguage dstLanguage, where number is an integer given in the numeral system of srcLanguage. You should translate it to the numeral system of dstLanguage.

A numeral system is simply a string of all possible digits, in ascending order. The decimal numeral system is represented by 0123456789, the binary numeral system is 01, and the hexadecimal one 0123456789ABCDEF.

For example:

3 0123456789 01 -> 11
3 0123 AB -> BB

Here's how I implemented it in Scala:

case class Langs(num:String,srcLang:String,dstLang:String)
object Langs {def fromLine(line:String):Langs = {
 val ar = line.split(" ");return Langs(ar(0),ar(1),ar(2))}}
object Translate {
 def lang2int(lang:String,num:String):Long = {
 var b = BigDecimal(0)
 val dmap = (lang.toList.zipWithIndex).toMap
 val digitsList = num map dmap
 val valueList = digitsList.reverse.zipWithIndex map (
 x => x._1 -> math.pow(dmap.size,x._2))
 return valueList.map(x=>x._1*x._2).sum.toLong
 }
 def int2lang(lang:String,_num:Long):String = {
 var num = _num
 val dmap = (lang zip (0.toLong to lang.size)).map(_.swap).toMap
 val sb = StringBuilder.newBuilder
 while (num > 0) {
 sb.append(dmap(num % dmap.size))
 num = num/dmap.size
 }
 sb.reverse.toString
 } 
 def lang2lang(l:Langs):String = int2lang(l.dstLang,lang2int(l.srcLang,l.num))
}
object mymain {
 def main(args : Array[String]) : Unit = {
 val s = "A-large-practice"
 val basef = new java.io.FileInputStream("~/Downloads/"+s+".in")
 val f = new java.util.Scanner(basef)
 val out = new java.io.FileWriter(s+".out")
 val n = f.nextInt
 f.nextLine
 for (i <- 1 to n) {
 val nl = f.nextLine
 val l = Langs.fromLine(nl)
 out.write("Case #"+i+": "+Translate.lang2lang(l)+"\n")
 }
 out.close
 }
}

• user unknown: Here is a similar quizzle (codegolf.stackexchange.com/questions/1620/…). It doesn't fit exactly your interface.

Answer 1

• You should definitely use scala.io.Source for File-IO
• I wouldn't consider String splitting a responsibility of a general-purpose class. This should be done in the main loop
• For tuples you can write map{ case (one,two) => ... }, which is often clearer than using x._1 and x._2
• You don't need to write return if it's the last statement of the block
• You can use pattern matching when defining vals: val Array(x, y, z) = line.split(" ")

Here is my attempt:

case class Langs(num:String, srcLang:String, dstLang:String)
object Langs {
 def fromLine(line:String):Langs = {
 val Array(num, srcLang, dstLang) = line.split(" ")
 Langs(num, srcLang, dstLang)
 }
}
object Translate {
 def lang2int(lang:String,num:String):Long = {
 val dmap = lang.toList.zipWithIndex.toMap
 val digitsList = num map dmap
 val valueList = digitsList.reverse.zipWithIndex map {
 case (one, two) => one -> math.pow(dmap.size, two)}
 valueList.map{case (one,two) => one*two}.sum.toLong
 }
 def int2lang(lang:String, num:Long):String = {
 val dmap = (0.toLong to lang.size zip lang).toMap
 Iterator.iterate(num)( _/dmap.size).takeWhile(_ > 0).map(n => 
 dmap(n % dmap.size)).mkString.reverse
 } 
 def lang2lang(l:Langs):String = int2lang(l.dstLang,lang2int(l.srcLang,l.num))
}

Eliminating the while loop isn't that straight-forward, maybe someone else has an idea how to avoid that Iterator train-wreck.

[Edit]

I asked in another forum for a better solution for int2lang, and got this answer:

def int2lang(lang: String, num: Long): String = {
 val dmap = (0L to lang.size) zip lang toMap
 val size = dmap.size
 def loop(num: Long, l: List[Char]): List[Char] =
 if (num == 0) l else loop(num/size, dmap(num%size) :: l)
 loop(num, Nil).mkString
}

The nice thing about this is that the reverse is gone.

• Elazar Leibovich: Thanks! Great input. Few questions: How would I emulate Scanner.readInt with io.Source?
• Elazar Leibovich: (2) Why is the while loop bad? It might be more efficient is definitely clearer, and is only immutable in the function's scope (if a tree falls and nobody heard of it, does it make sound ;-)
• Landei: @Elazar: There is no readInt, usually you call Source.fromFile(...).getLines and work with the Iterator[String]. Strings have already conversion functions, you can simply write "42".toInt.
• Landei: The while loop is not "bad", but you lose the neat advantages of Scala's collections (as mkString). I don't really like my solution either, I have the feeling there must be a better way (especially the takeWhile is confusing, the rest is not so bad)...

Answer 2

My suggestions.

• Take advantage of the fact that Seq[T] is also a function Int => T.
• Use recursion.

Example:

def int2lang(lang:String, num:Long): String = 
 if (num == 0l) "" 
 else int2lang(lang, num / lang.size) + lang(num % lang.size toInt)

If you want to take advantage of tail recursion, use an accumulator:

@scala.annotation.tailrec
def int2lang(lang:String, num:Long, acc: String = ""): String = 
 if (num == 0l) acc
 else int2lang(lang, num / lang.size, lang(num % lang.size toInt) + acc)

But that is suboptimal regarding string concatenation, so you could do this:

@scala.annotation.tailrec
def int2lang(lang:String, num:Long, acc: List[Char] = Nil): String = 
 if (num == 0l) acc.mkString
 else int2lang(lang, num / lang.size, lang(num % lang.size toInt) :: acc)

If you don't like recursion (and tail recursions are very efficiently implemented), use a generic unfold instead of reinventing it:

def unfoldLeft[A, B](seed: B)(f: B => Option[(B, A)]) = {
 def loop(seed: B)(ls: List[A]): List[A] = f(seed) match {
 case Some((b, a)) => loop(b)(a :: ls)
 case None => ls
 }
 loop(seed)(Nil)
}
def int2lang(lang: String, num: Long) = unfoldLeft(num) { n =>
 if (n == 0) None
 else Some((n / lang.size, lang(n % lang.size toInt)))
}.mkString

If you unfold to get the lang, you fold to get the int:

def lang2int(lang: String, num: String) = {
 val lmap = lang.zipWithIndex.toMap
 num.foldLeft(0l) { case (acc, digit) => acc * lang.size + lmap(digit) }
}

Note that I use a Map here because I want T => Int. But since we folded what was unfolded, let's see recursion's converse:

def lang2int(lang: String, num: String) = {
 val lmap = lang.zipWithIndex.toMap
 def recurse(n: String, acc: Long): Long =
 if (n.isEmpty) acc
 else recurse(n substring 1, acc * lang.size + lmap(n(0)))
 recurse(num, 0l)
}

So much for the fun part, let's see the rest. I prefer to turn while loops into iterators, unless performance is critical. So:

for (i <- 1 to n) {
 val nl = f.nextLine
 val l = Langs.fromLine(nl)
 out.write("Case #"+i+": "+Translate.lang2lang(l)+"\n")
}

becomes

val lines = Iterator continually f.nextLine
for ((l, i) <- lines map Langs.fromLine zipWithIndex)
 out.write("Case #"+(i+1)+": "+Translate.lang2lang(l)+"\n")

I could move the map Langs.fromLine to the iterator, making that:

val ns = Iterator continually f.nextLine map Langs.fromLine

or even

val ns = Iterator continually (Langs fromLine f.nextLine)

And if I needed these numbers for more than one use, make it Stream instead of Iterator. Of course, another alternative would be using Source.io, but that's only for lightweight stuff anyway.

Finally, do not use return. A return is an exception of sorts -- it indicates a function will terminate and return its result before its end.

It can also be used inside closures to escape the function that is executing it and return (and exit) the scope in which it was defined.

At any rate, treat a return as something exceptional, and leave it for exceptional situations.

• Elazar Leibovich: Thanks! (1) Can you please fix the code (you used 3 spaces for indentation), (2) "If you don't want recursion, use unfold which uses recursion itself" ;-). Great input, I didn't think about the fact that Seq[T] is actually a function (keep in mind that performance is not guaranteed, it could be a List[T]...), and didn't remember the Iterator.continually.
• Daniel C. Sobral: @Elazar I used 4 spaces for indentation, except for the code that I copy&pasted (foldLeft's definition and the original for loop) and the translation of said loop. Speaking of unfold, the point is that it separates the recursion from the business logic. And, yes, Seq[T] might have a slow apply, but that's not the case of String. :-)
• Elazar Leibovich: you missed just one function def lang2int(lang: String, num: String) copy it to vim, and go / def lang to find it. I don't have edit rights, otherwise I'd fix it myself.
• Daniel C. Sobral: @Elazar Oh, ok, sorry.

Answer 3

I'm kind of new to Scala myself, but I like to think that loops are all-but obsolete. Every time I see one now I think, "A loop - how quaint!"

All the collections have methods you can pass a function to. This approach allows the collection to do various optimizations, particularly for multi-threading that are difficult and time-consuming to program properly on your own. So I'd try to get rid of the for loop and the while loop first.

If you can somehow combine all your processing into one function before passing it to the collection, all the better.

Other people have mentioned a lot of other details making your code more functional, I just think that the loops are the most obvious stylistic element that also affects performance.