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.