Monday, September 08, 2008

Scala ArrayStack

I had not done any Project Euler problems for awhile, so I decided to solve one yesterday. I was also planning on attending the next BASE meeting, so I wanted to brush up my Scala. Thus it was time to solve Problem #47 in Scala.

The solution got me a little more familiar with some of the data structures available in scala.collection.mutable. In particular I needed a structure to hold a list of factors. I decided that ArrayStack was the best choice. Here is my solution:


package probs
import scala.collection.mutable.ArrayStack

object Euler47 {
def main(args : Array[String]) : Unit = {
val start = System.nanoTime
solve(4)
val duration = System.nanoTime - start
println("duration=" + duration/1000000.0)
}

def solve(n:Int):Unit = {
var i = 2
while (i > 0){
var j = i
while (j<i+n && numFactors(j) ==n){
j += 1
}
if (j-i == n){
val msg = (i until j).foldLeft(""){(x,y) => x + y + " "}
println(msg)
return
}
i += 1
}
}

def numFactors(n:Int):Int = {
var factors = new ArrayStack[Int]
var i=2
var m = n
while (i <= m/i){
while (m % i ==0){
if (factors.size ==0 || i != factors.peek){
factors += i
}
m /= i
}
i += 1
}
if (m != 1){
factors += m
}
factors.size
}
}

I was very pleased with the performance, solving the problem in about 0.4 seconds on my MacBook. I saw a similar, but not as good Java solution on the message boards that ran in 1.5 seconds. That solution added all of the factors repeated times and then had to loop through them again to get rid of duplicates. I ran it on my MacBook and it ran in 1.1 seconds. Even when I "fixed" it, it still took about one second. I am sure I could have done a lot of work to it and got it as fast as Scala, but why bother.

No comments:

Post a Comment