# First four Project Euler in Scala

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.

• Hmmm 4 questions in 1. Is it still Black Friday somewhere? Or is there a hat-for-that? ;-) – rolfl Dec 15 '14 at 0:13
• @rolfl I thought about that... though it seemed a bit wasteful for four questions for what amounts to one line of code each. – user22048 Dec 15 '14 at 0:16
• 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). – rolfl Dec 15 '14 at 0:18
• Please summarize the challenges in your question. – 200_success Dec 15 '14 at 6:17
• 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). – Landei Dec 15 '14 at 9:30

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.