Project Euler problem 92 in Scala, square digit chains

Question

Here is a summary of the problem: "A number chain is created by continuously adding the square of the digits in a number to form a new number until it has been seen before... How many starting numbers below ten million will arrive at 89?" The site also gives an example at https://projecteuler.net/problem=92.

I have a solution which arrives at the correct answer but takes ~24 seconds on my computer to complete. I used an array to record as true the index of each value which resolves to 89 through the chain described above. I used an array so that updating and checking values would take constant time. I believed that recording all numbers that resolved to 89 would save time so that the checkAll function could avoid redundant calls of chain for these values.

However, I tested this assumption and wrote a version in which chain would simply recurse until resolving to true or false without recording the chain, so that checkAll would check every single value from 1 until 10 million but perhaps save time from not recording values. Despite the change, this version took almost the exact same amount of time, although at least it's more concise.

For the above reason I now suspect that the chain of method calls used to produce the next variable in the chain function is the main bottleneck, but I am not sure whether this is possible to implement in a faster way.

object euler92 {
  def main(args: Array[String]): Unit = {
    val t0 = System.nanoTime()

    val blank = new Array[Boolean](10000000)
    def chain(number: Int, links: List[Int] = List()): Unit = {
      val next = number.toString.toList.map(_.toString).map(_.toInt).map(x => x * x).sum
      if (next == 89) for (i <- number :: links) blank(i) = true
       else if (next == 1) ()
      else {
        chain(next, number :: links)
      }
    }
    def checkAll(num: Int, counter: Int = 0): Unit = {
      if (num == 10000000) println("Answer: " + counter)
      else if (blank(num) == true) checkAll(num + 1, counter + 1)
      else {
        chain(num)
        if (blank(num) == true) checkAll(num + 1, counter + 1)
        else checkAll(num + 1, counter)
      }
    }
    checkAll(1)

    val t1 = System.nanoTime()
    println("Elapsed time: " + (t1 - t0) + " ns")
  }
}

Here is the implementation without an array:

def chain(number: Int, links: List[Int] = List()): Boolean = {
      val next = number.toString.toList.map(_.toString).map(_.toInt).map(x => x * x).sum
      if (next == 89) true
      else if (next == 1) false
      else {
        chain(next, number :: links)
      }
    }

def checkAll(num: Int, counter: Int = 0): Unit = {
  if (num == 10000000) println("Answer: " + counter)
  else {
    val ans = chain(num)
    if (ans) checkAll(num + 1, counter + 1)
    else checkAll(num + 1, counter)
  }
}
checkAll(1)

I am hoping for insight on how to improve the performance of this solution.

Answer 1

Let's start off with your code to convert to the sum of digits.

number.toString.toList.map(_.toString).map(_.toInt).map(x => x * x).sum

First of all, a String can already be treated as List[Char], so that toList is unnecessary. Also, instead of converting from Char to String to Int, you can just call asDigit. And while we're at it, let's stuff that in a function, so that we know what's going on when we call that line. After all that, the line looks like:

def sumSquareDigits(number: Int): Int = number.toString.map(_.asDigit).map(x => x*x).sum

Now, you had the right idea in creating a hash. However, as an array of Booleans it's hard to tell what's been set and what hasn't. For now, let's start with a HashMap, since it's the most obvious construct for a cache. If it were too slow you could worry more about optimization, but at least on my computer it's sufficient to solve it. This has the added advantage of not needing to cache values that aren't repeated. Instead of needing to fill in 10,000,000 integers (I don't have that kind of spare RAM), it only ends up needing to cache 495 values. Additionally, since we're using the cache inductively, we should prepopulate the cache with our base case:

val cache = scala.collection.mutable.HashMap[Int,Int](1->1,89->89)

Now, we want to see whether a value converges to 1 or 89. We can do this by recursively calling the hash on the sumSquareDigits defined above until we get an answer, placing the results of any new stuff into the cache. We'll use a helper function just for simplicity:

def addValueToCache(number: Int) =
{
  val converged = getConvergedValue(number)
  cache.put(number,converged)
  converged
}
def getConvergedValue(number: Int) = cache.getOrElse(sumSquareDigit(x), addValueToCache(sumSquareDigit(x))

And now we just need to check which values converge to 89,

def checkAll(max: Int): Int= 
  (1 until max).map(getConvergedValue).filter(_ == 89).size

then call it from main!

def main(args: Array[String]): Unit =
{
  println("Answer: "+checkAll(10000000))
}

Notice how using if statements for flow control is entirely unnecessary here. Functional programming style tends to do flow control with monadic operations (filter, map, flatMap, flatten, etc...) or pattern matching. If you're trying to stick to a functional style, when you see a lot of nested if statements you should be wondering if there's a better way to do it.

Answer 2

This is not an answer, but too long to be a comment.

You are testing too much. Among the numbers below 10000000 the largest sum of squares is produced by 9999999, and it is a mere 7*81 = 567. The entire range of [0, 10000000) maps into [0, 567]. There is no reason to check anything beyond it. (The second round shrinks it even more, to 3*81 = 243, but I don't think it would make any difference).

I am not fluent enough (or at all) in Scala, so I cannot pinpoint inefficiencies in your code. However, an indiscriminate use of recursion makes me nervous. And of course the 10M strong array with no clear access pattern is not very cache friendly.

Answer 3

There are at least two ways you can increase the efficiency of your calculation of next.

So right now you are doing:

val next = number.toString.toList.map(_.toString).map(_.toInt).map(x => x * x).sum

More efficient ways to do the same thing:

(1) The following reduces the runtime of your program to ~50% of what it was:

val next = number.toString.map(i => (i - '0') * (i - '0')).sum

Or if you prefer could be written as:

val next = number.toString.map(i => i.asDigit * i.asDigit).sum

(2) And perhaps a more readable version that results in a speedup of ~20%:

val next = number.toString.map(_.asDigit).map(i => i * i).sum

Answer 4

Scala's Set collection is a much more concise way to test for element repetition.

The idiomatic FP Scala way would be to use an immutable Set and create a new instance every time it's updated.

def goodChain(x:Int, old:Set[Int]=Set()):Boolean =
  if (x == 89) true
  else if (old(x)) false
  else goodChain(x.toString.map{d => val dgt = d.asDigit; dgt*dgt}.sum, old+x)

(2 until 10000000).count(goodChain(_))  //res0: Int = 8581146

But since you're looking for a performance enhancement, reusing a mutable Set will probably be a bit faster.

val oldx = collection.mutable.Set.empty[Int]

def fastChain(x:Int): Boolean =
  if (x == 89)      {oldx.clear; true}
  else if (oldx(x)) {oldx.clear; false}
  else {
    oldx(x) = true
    fastChain(x.toString.map{d => val dgt = d.asDigit; dgt*dgt}.sum)
  }

2 until 10000000 count fastChain  //res1: Int = 8581146

Of course doing all that multiplication is redundant and unnecessary.

val oldx = collection.mutable.Set.empty[Int]
val sqr = Map('0'->0, '1'->1, '2'->4, '3'->9, '4'->16
             ,'5'->25, '6'->36, '7'->49, '8'->64, '9'->81)

def fasterChain(x:Int): Boolean =
  if (x == 89)      {oldx.clear; true}
  else if (oldx(x)) {oldx.clear; false}
  else {
    oldx(x) = true
    fasterChain(x.toString.foldLeft(0)(_ + sqr(_)))
  }

2 until 10000000 count fasterChain  //res2: Int = 8581146