Project Euler 4 The Functional Way

Question

I'm learning Scala (and functional programming). Is there a better way to solve Euler problem 4 than either of these two solutions.

Euler 4

I like this array comprehension solution, but it wastes so much space.

def isPal(n: Int): Boolean = {
  val sN = n + ""
  sN == sN.reverse
}
def euler4Iter: Int = {
  var largestPal = 0
  for (i <- 100 to 1000; j <- i to 1000) {
    if (i * j > largestPal && isPal(i*j)) {
      largestPal = i*j
    }
  }
  largestPal
}
def euler4ArrayCompre: Int = {
  (for(i <- 100 to 1000; j <- i to 1000 if isPal(i*j)) yield i*j).max
}

Answer 1

Inefficiencies

Your iteration is wasteful for several reasons

1. You generate every product of two 3-digit numbers, which will not be reaped until the calculation is finished.
2. You start at the lowest end of a large range, when the desired result is clearly going to be near the top end.
3. You keep iterating after the largest number has been found
4. You are iterating over nearly twice as many results as you need to, because of duplicate products

Just to prove the final point:

scala> (for (i <- 100 to 999; j <- i to 999) yield (i * j)).size
res0: Int = 405450

(for (i <- 100 to 999; j <- i to 999) yield (i * j)).sorted.distinct.size
res1: Int = 227521

for (i <- 100 to 999; j <- i to 999 if i * j == 100000) yield (i, j)
res2: scala.collection.immutable.IndexedSeq[(Int, Int)] = Vector((125,800), (160,625), (200,500), (250,400))

Improvements

The first point can easily be addressed with iterators, since you only need to traverse each range once. As to the others...

You could look for a way to start at the top of the range and work down, in such a way that each iteration tests the next lowest product of two 3-digitnumbers. If you could think of a way to do that recursively, you could safely return as soon as you found a palindromic number. But consider this:

1. There are only 999 6-digit palindromic numbers
2. It is trivial to generate a sequence of them in descending order
3. Testing a decreasing sequence of potential divisors, starting at 999, can be abandoned as soon as palindrome / divisor > 999
4. The search can stop as soon as palindrome % divisor == 0

As long as the target number is near the top of the range (which of course it will be), working backwards like this will involve much fewer operations, which makes this cheaper even with the higher cost of modulo division.

Here's a simple attempt:

def ps = for (i <- Iterator.from(9, -1) take 9;
              j <- Iterator.from(9, -1) take 10;
              k <- Iterator.from(9, -1) take 10;)
              yield (i + 10 * j + 100 * k + 1000 * k + 10000 * j + 100000 * i)

ps find {p =>
  Iterator.from(999, -1) take 900 takeWhile (p / _ < 1000) exists (p % _ == 0)
}

If you are not happy that this only looks at the 6-digit palindromes and worry that the highest palindrome might be in the 5-digit range, laziness means that it is cheap to append 5-digit palindromes to the 6-digit iterator:

// Lazily generate all 999 palindromic 6-digit numbers in reverse order
def ps6 = for ((i <- Iterator.from(9, -1) take 9;
                j <- Iterator.from(9, -1) take 10;
                k <- Iterator.from(9, -1) take 10)
              yield (i + 10 * j + 100 * k + 1000 * k + 10000 * j + 100000 * i)

// Even more lazy generation of the 5-digit palindromes
def ps5 = ps6 map (i => (i / 1000) * 100 + i % 100)

// Put them together.  Iterator ++ is lazy
def ps = (ps6 dropWhile (_ > 999 * 999)) ++ (ps5 takeWhile (_ > 9999))

There are ways to do this without modulo arithmetic and/or even fewer iterations. While my simple solution addresses the first 3 inefficiencies I listed, it is iterating rather more than is needed (mitigated significantly by working down from the top). Maybe you can improve on this from here.