# [GCJ] How scala-ish is my solution?

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 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
}
}
``````
-
Here is a similar quizzle (codegolf.stackexchange.com/questions/1620/…). It doesn't fit exactly your interface. –  user unknown Jun 4 '11 at 2:44

• 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.

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.

-
Thanks! Great input. Few questions: How would I emulate `Scanner.readInt` with `io.Source`? –  Elazar Leibovich May 20 '11 at 15:27
(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 ;-) –  Elazar Leibovich May 20 '11 at 15:34
@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 May 20 '11 at 21:33
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)... –  Landei May 20 '11 at 21:42

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.

-
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. –  Elazar Leibovich Jun 2 '11 at 9:29
@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`. :-) –  Daniel C. Sobral Jun 2 '11 at 12:18
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. –  Elazar Leibovich Jun 2 '11 at 16:49
@Elazar Oh, ok, sorry. –  Daniel C. Sobral Jun 2 '11 at 18:44