Problem 4 [Language]: Find the largest palindrome made from the product of two 3-digit numbers.

[eloots]

In the Algorithm section of this problem, I showed a re-factored solution using case classes in the return value of a method. What's this about?

Well... one of the nice things about Scala (certainly compared to Java) is that we're not limited to using primitive data types as return types. Sure, in the case of Java, one can return an object that contains whatever you like, but it's a hassle to get stuff in and out...

Back to the problem. You may have written method's in Scala that return things like (String, Int, Int) or List[Set[Int], Int, Int]].

Convenient and certainly very cool, but you probably know the feeling that, when pick your code where you left it the other day, you have little clue about what the meaning of each field is. For example, what are the two Int in (String, Int, Int)? The age and number of children respectively perhaps? Or the other way around?

Let's get back to the palindrome problem and look at the signature of method largestPalindrome

def largestPalindrome(n: Long, range: Long =  100, pRange: Long = 0): (Long, Long, Long)

We can't tell that the Long values correspond to the Palindrome, and the first and second Palindrome divider respectively. We can of course add documentation, (which we should), but there's something missing...

Instead, let's use case classes and reap all their benefits.

We start by defining a new case class that matches this use-case:

case class PalindromeAndDividers(palindrome: Long, divider1: Long, divider2: Long)

The original version of largestPalindrome:

def largestPalindrome(n: Long, range: Long =  100, pRange: Long = 0): (Long, Long, Long) = {
      val candidatesNewXPrev = for {
        nNew  <- n - pRange until n - range  by -1
        nPrev <- n          until n - pRange by -1
        posPalindrome = (nNew * nPrev).toString
        if posPalindrome == posPalindrome.reverse
      } yield (posPalindrome.toLong, nNew, nPrev)

      val candidatesNewXNew = for {
        nNew  <- n - pRange until n - range by -1
        nNew2 <- nNew       until n - range by -1
        posPalindrome = (nNew * nNew2).toString
        if posPalindrome == posPalindrome.reverse
      } yield (posPalindrome.toLong, nNew2, nNew)

      val interm = (candidatesNewXPrev ++ candidatesNewXNew)
                                .sortBy { case (num, _, _) => -num }

      if (interm.isEmpty) {
        largestPalindrome(n, range + 100, range)
      } else interm.head
    }

can be re-written as follows:

def largestPalindrome(n: Long, range: Long =  100, pRange: Long = 0): PalindromeAndDividers = {
      val candidatesNewXPrev = for {
        nNew  <- n - pRange until n - range  by -1
        nPrev <- n          until n - pRange by -1
        posPalindrome = (nNew * nPrev).toString
        if posPalindrome == posPalindrome.reverse
      } yield PalindromeAndDividers(posPalindrome.toLong, nNew, nPrev)

      val candidatesNewXNew = for {
        nNew  <- n - pRange until n - range by -1
        nNew2 <- nNew       until n - range by -1
        posPalindrome = (nNew * nNew2).toString
        if posPalindrome == posPalindrome.reverse
      } yield PalindromeAndDividers(posPalindrome.toLong, nNew2, nNew)

      val palindromes = (candidatesNewXPrev ++ candidatesNewXNew)
                                .sortBy { palAndDivs => - palAndDivs.palindrome }

      if (palindromes.isEmpty) {
        largestPalindrome(n, range + 100, range)
      } else palindromes.head
    }

In the two for comprehensions, instead of yielding a 3-element Tuple, we yield a PalindromeAndDividers case class instance. As a consequence, we end-up with sequences with elements of that type. When performing the sorting using sortBy we have a wealth of options to achieve our (sorting) goal.

We can do as in the code above: select field palindrome on the case class instance, or use any of the following forms using pattern matching:

val palindromes = (candidatesNewXPrev ++ candidatesNewXNew)
                                .sortBy { case PalindromeAndDividers(num, _, _) => -num }

or:

val palindromes = (candidatesNewXPrev ++ candidatesNewXNew)
                                .sortBy { case palAndDivs  @ PalindromeAndDividers(_, _, _) => - palAndDivs.palindrome }

or, in a very brief form:

val palindromes = (candidatesNewXPrev ++ candidatesNewXNew)
                                .sortBy { - _.palindrome }

Does coding in this way incur a performance penalty? No - it's the compiler who's doing all the hard work for you - you just get the readability...

In this explanation, we showed the utilization of using case classes as method return types inside methods. The real benefit comes when you start using the power of Pattern matching on values returned from methods elsewhere in your code...