First four Project Euler in Scala

Question

I was working on teaching myself some Scala and decided to tackle some Project Euler problems. The first four of these turned out to be one liners.

/* Find the sum of all the multiples of 3 or 5 below 1000 */
object Problem1 extends App {
 println((1 to 999).filter((i: Int) => i % 3 == 0 || i % 5 == 0).sum)
}

/* By considering the terms in the Fibonacci sequence whose values do not
 exceed four million, find the sum of the even-valued terms. */
object Problem2 extends App {
 def fib: Stream[Long] = {
 def tail(h: Long, n: Long): Stream[Long] = h #:: tail(n, h+n)
 tail(0,1)
 }
 println(fib.takeWhile(_ < 4000000).filter(_ % 2 == 0).sum)
}

/* What is the largest prime factor of the number 600851475143? */
object Problem3 extends App {
 val v = BigInt("600851475143")
 val z = BigInt(0)
 println(PrimeSeq.ps.takeWhile{p => v.>(BigInt(p).pow(2))}.filter(v.%(_) == z).max)
}

/* Find the largest palindrome made from the product of two 3-digit numbers. */
object Problem4 extends App {
 def isPalindrome (a:Int) : Boolean = {
 a.toString.equals(a.toString.reverse)
 }
 println((100 to 999).map { rangeIdx => (rangeIdx to 999).map{ i => i * rangeIdx}.map{ x => if(isPalindrome(x)) x else 0}.max }.max)
}

PrimeSeq is in a separate object because I expect that I'll be using it again in the future and is included here for completeness. The code itself is from this StackOverflow question and isn't code I wrote.

object PrimeSeq {
 lazy val ps: Stream[Int] = 2 #:: Stream.from(3).filter(i =>
 ps.takeWhile{j => j * j <= i}.forall{ k => i % k > 0})
}

I am most interested in the idiomatic corrections of the Scala code, though other parts will be of interesting too.

• rolfl: Hmmm 4 questions in 1. Is it still Black Friday somewhere? Or is there a hat-for-that? ;-)
• user22048: @rolfl I thought about that... though it seemed a bit wasteful for four questions for what amounts to one line of code each.
• rolfl: I'm inclined to let it go through as 1 question. The code volume is small, and the only person who really suffers is you (with reduced votes in total).
• 200_success: Please summarize the challenges in your question.
• Landei: Your PrimeSeq will be very inefficient for bigger primes, as it performs worse than the sieve of Eratosthenes. See cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf for a good explanation and implementation (the Haskell code there can be written pretty much the same way in Scala).

Answer 1

You should avoid the natural tendency in Scala to make everything a one-liner. It hinders the readability and maintainability of the code. I don't think it's much of a problem in the first two, but the third and fourth solutions seem a bit cryptic. In most cases the compiler will collapse your more verbose collection of defs down to the same result as your one-liner, but the multiple defs are easier to grok for humans.

I can simplify Problem4 with filter and flatten to reduce the lists without resorting to use of '0' as a placeholder for "not to be considered".

println( (100 to 999).map(x=>(x to 999).map(_*x).filter(isPalindrome)).flatten.max)

But it still reads better to me if not so composed.

For example:

 def products = (100 to 999).map(x=>(x to 999).map(_*x)).flatten
 def palProducts = products.filter(isPalindrome)
 println( palProducts.max )

Even that combines too much in products, I think. For-comprehension can make it more readable even without separate defs:

 def palProducts = 
 for { a <- (100 to 999)
 b <- ( a to 999)
 c = a*b
 if (isPalindrome(c)) } yield c
 println( palProducts.max )

Also, you should add @tailrec annotations to code which is reliant on being tail-recursive, only to prevent them becoming non-tailrec through some accidental change in the future. This is a minor quibble in these small examples, but it will become more important in larger projects.