More fun with Scala

This post is copied over from my internal blog inside IBM, just for posterity after I’ve left. It was first published in February 2011.

I’ve been spending a lot of personal time increasing my knowledge and understanding of Scala. To spur me on I build up an introduction presentation which was presented to the IBM Dublin lab recently:

However, as previously stated, the best way to learn a language is to solve real problems in it, and one vein of problems are mathematical puzzles. I’m not a great mathematician so don’t spend all my time playing with Project Euler or similar, but when somebody posed one on a UK forum I frequent I couldn’t resist having a go in Scala. What’s more bizarre is that the forum is mainly about cars (but then cars and computer geeks sometimes go hand in hand)

Here’s the problem:

Find a 9-digit integer containing only the numbers 1-9 with no duplicates that is exactly divisible by 9.
Now remove the 9th digit to leave an 8-digit integer that is exactly divisible by 8.
Now remove the 8th digit to leave an 7-digit integer that is exactly divisible by 7.
And so on, down to a 1-digit integer that is obviously divisible by 1.

What is the 9-digit number? Is there more than one answer?

The first solution posted was in C# and absolutely unreadable. You can see it on the thread linked above. Then somebody posted a Java based solution that used a little bit of recursion, but was still very imperative. He claimed the “most elegant” solution prize, so I took that as a challenge to see what I could do in Scala.

To begin with I tried to bite off more than I could chew and tried to define a lazy stream of all 9 digit numbers that were divisible by 9. However I was ignoring the restriction that numbers could only consist of the digits 1-9 with no repeated digits. I was also trying to use parts of the language that I didn’t really understand yet.

After an hour or so I switched approach, and took the previously posted Java code and just “Scalafied” it. Then I began to swap out various loops by using higher order functions such as filter, and defining it to use a function implemented with some pattern matching to recursively divide a given number according to the spec. This was all simple enough to do. I hit one snag with the best way to convert an array of Char to an integer, and settled on using an implicit conversion (not strictly necessary as the conversion is only needed once, but I’d not defined one before).

So, here is version 1:

import scala.collection.mutable.Set

object ProblemScala extends Application {

  implicit def charArray2Int(c: Array[Char]): Int = java.lang.String.valueOf(c).toInt

  val digits = Array('1', '2', '3', '4', '5', '6', '7', '8', '9')
  val permutations = Set[Int]()

  def permute(digits: Array[Char], n: Int): Unit = n match {
    case 1 => permutations += digits
    case _ => {
      for(val i <- 0 until n) {
        val j = n - 1
        swap(digits, i, j)
        permute(digits, j)
        swap(digits, i, j)
      } 
    } 
  }

  def swap(digits: Array[Char], i: Int, j: Int): Unit = {
    val c = digits(i)
    digits(i) = digits(j)
    digits(j) = c
  }

  def divisible(n: Int, divisor: Int): Boolean = divisor match {
    case 1 => true
    case _ => n % divisor == 0 && divisible(n / 10, divisor - 1)
  } 

  permute(digits, digits length)
  val result = permutations filter (n => divisible(n, 9))

  result.foreach(i => println("match found: " + i)) 
  println("total match count: " + result.size)
}

The permute and swap functions are used in building a set of all possible 9 digit numbers that can be made up of the digits array contents. This was pretty much a straight copy from the Java code, except I use pattern matching in permute rather than an if/else.

The main difference as mentioned is the divisible function and how that is used in calculating the value of ‘result’. I was quite pleased with that. Overall it read much cleaner than the Java version in my eyes. However I was not happy with this solution. It doesn’t drastically cut down the line length and there’s still too much Java-like stuff going on. It is however a good example of how Scala lets you dip your toes into the water slowly rather than throwing you in at the deep end. Just take your existing code and “Scalafy” the syntax, then start looking for the loops, vals and Units, and start refactoring them out.

Once a days work got out of the way, I started googling around for a better solution to the problem of determining the permutations of the 9 digit numbers. In the meantime, a couple more solutions had been posted in Lua and Python. Both used useful library functions for building permutations, so my thoughts turned to what I might be missing in the Scala libraries. Sadly, there is nothing directly useful in 2.8.1, and many Google results that discuss generic solutions which are quite complex and would turn my solution into an unreadable mess. I did however find reference to the fact that the as yet un-final Scala 2.9.0 does have a SeqLike.permutations function. I set up a new SBT project (more on SBT in another post) using the latest 2.9.0 nightly snapshot and got to work. The result is quite amazing:

object ProblemScala2 extends App {

  def divisible(n: Int, divisor: Int): Boolean = divisor match {
    case 1 => true
    case _ => n % divisor == 0 && divisible(n / 10, divisor - 1)
  }

  "123456789".permutations filter (n => divisible(n.toInt, 9)) foreach(n => println("match found: " + n))
}

The library function allows the String “123456789” to be implicitly converted to a SeqLike when the permutations function is called on it. The result is an Iterator of all permutations. That can then be used as the input of the rest of my first solution. All the cruft code in the first solution to define all the permutations is completely gone and what’s left is an amazingly concise and readable solution. I think it wins the “Most elegant” prize and I’ll be surprised if anybody comes up with something better.

Scala 2.9.0 should be released in the next few months. It is not a major evolution (compared to 2.8) but this is one fun example of how the language and core libraries are getting better and better.

Leave a Reply