[GCJ] 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
  }
}

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.

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.

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.