Monday, January 9, 2012

Project Euler Problem 8 in Scala

This is 8 in a series.  The previous post is at, Project Euler Problem 5 in Scala. 

So we saw problem 6 solved with a 'one-liner'.  Then we moved on to problem 7 and I had to have a while loop and control variables, which really disappointed me. Problem 8, however, was not only satisfying, but allowed me to explore even more features of Scala.  

Before I get into the actual problem, I want to comment on my language progress.  My 'native tongue' so-to-speak, is Java.  I use Java at work and have for 12 years. I expect it will be paying the bills for years to come.  We can debate the merits of Java as a language, and I'm sure every one reading this has an opinion about it, good or bad.  Regardless of opinion, I am most productive in Java.  Period.  Why?  Because I have used it so much, and am so familiar with the syntax and libraries that the language 'gets out of the way'.  I don't have to think about anything but what the code is intending to do.  This makes me very productive.  I'm finding that its taking a little longer to get to the point where I feel like the language has stepped back with Scala.  Part of it is the rather verbose API documentation, which, just seems to tell me too much and doesn't allow me to get right to 'how do I use this'.  Part of it is that Scala has a lot more power and expressiveness than Java, and that takes more time to learn.  At any rate, my Scala skills are slowing improving.  

Now, on to Problem 8:

Find the greatest product of five consecutive digits in the 1000-digit number.
 This problem is pretty straight forward.  Iterate the string literal and multiply sets of 5 numbers together.  Find the largest of those numbers and return it.  Now, in Java, this would take a couple of for loops, a String, possibly a string buffer, some variables to store the results, and an ugly System.out.println....

Not so in Scala.  The Collections facilities actually allowed me to solve this in one line, without any mutable state.  No, really, I mean it.  Check this out:

object Problem8 {
  def main(args: Array[String]): Unit = {
    val totalDigits = """[omitted the big string literal here, but you can add it back if you want to run the code...]"""
    println((for (i <- 5 to totalDigits.length()) yield totalDigits slice (i - 5, i)) collect {
      case i =>
        i.foldLeft(1)((product: Int, nextChar) => {
          (nextChar asDigit) * product
    } max)

Okay, its a 'one-liner' but there is a lot going on there.  Let's deconstruct the statement.  First, we see that everything is wrapped in a 'println', which is nice shorthand in Scala for System.out.println.  The second thing we see is that the result of the statement 'max' is what will be printed.  max is a collection function.  A couple of things to note.  Since max takes no arguments, we drop the '()'.  Since Scala can infer its a method call, we can even omit the '.'.  Now let's look at the rest of the code, shall we?

Let's go back to the beginning of the statement.  We are using the 'for' comprehension.  To be honest, the 'for' comprehension in Scala is much more powerful than the 'for' loop in other languages I've used.  You can see, we are going to iterate 5 to the length of the string.  For each iteration, we are going to yield the slice if i-5 and i.  slice is a nice string operator in Scala.  Essentially, we're getting 5 characters.  In turn we are going to collect the results of folding (There's that foldLeft again....) the 5 character Sequence.  The result of all of these will be a Sequence of Int values, on which we call 'max' function.

Boy, that was a mouthful.  It was cool, though, wasn't it?  It took a few minutes for me to weed through the API and figure out the syntax for this, but in the end, it is a succinct and stateless solution....

On to the next one...


  1. I also did the euler 8 in scala 2.9

    here's mine

    def getMaxproductSuccint(pList : List[Int]) : Int ={
    val groups = pList.sliding(5).toList.par => x.product).par.max

    pList = the list of integers read from file etc...

    here is the code

    def getNumbers(filename : String) : List[Int] = {

    val file = fromFile(filename)
    val lines = file.getLines
    var list : List[Int] = Nil
    val zero = '0'.toInt

    for(line <- lines){
    list = list :::> x.toInt - zero).toList

  2. renghen,

    Another interesting solution. I like the use of 'sliding' in your solution. It seems the Scala collections API's are much more complete than those in Java. I keep learning about more functions that are truly helpful in everyday programming.

    Thanks for sharing.