13
\$\begingroup\$

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.

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

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy