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

[samdebacker]

A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 x 99.

Task: Find the largest palindrome made from the product of two 3-digit numbers.

Note: The stated problem can be solved for numbers with a larger number of digits.

For example, for 5 digit numbers, the largest palindrome is 9966006699 = 99681 * 99979 and this solution can be determined programmatically in under a second. In fact, it is possible to calculate the value of these palindrome for the product of two numbers up-to 8 digits in around 5 seconds.

Finding the right strategy for finding a fast solution is not straightforward. Use experiments to find a good strategy. The 'fast' solution doesn't require tons of math...

[samdebacker]

Thank you Eric for adding this interesting problem!

A first solution was just to use nested loops to calculate the product and keeping track of the max.

But loops are dull, why not 'flatMap that shit'? So I came to this bit awkward flatMapped solution. It is basically the same as the nested loops, but by flatMap/map-ing over the Ranges.

Flatmap is cool, and can be written like a for-comprehension. For-comprehensions are just syntactic sugar for flatMap/map/filter combinations. It uses generators (<-) over the Ranges, local variable definitions (=) and a filter expression (if). And in this case also a dirty trick to set the max variable in the closure when we find a better max. I'm rather curious if most of you consider this OK or rather NOT DONE?

To get to the 8-digits in 5 seconds solution, make the following observation in the product table:

i * j	999	998	997	996	...
999	998001
998	997002	996004
997	996003	995006	994009
996	995004	994008	993012	992016
...

The nested loops solutions from before calculated the products in this table from top to bottom from left to right, but you can find another order that generates the biggest product first and works it way down...

999 * 999,
998 * 999,
998 * 998, 997 * 999,
997 * 998, 996 * 999,
997 * 997, 996 * 998, 995 * 999,
996 * 997, 995 * 998, 994 * 999, 
...

Using nested loops and stopping once the first palindromic product is found, you get to the fast solution. Actually it is an 8-digits in 7 seconds solution, but I leave it as an 'UOVT' to transform it so you no longer need p = i * j but can derive p by doing some additions/subtractions. I'm pretty sure it will result in a real 8-digits in 5 seconds solution.

[eloots]

You're a genius ! I have over quite some time, found a number of solutions using different approaches, but had never spotted the pattern that allows the calculation of products to generate results that are monotonously descending... Next, your implementation (the last one) using a mutable variable is difficult to beat in terms of performance.

I managed to come up with implementation of your algorithm in pure FP:

object PalinSamdrome {
  val N = 9999999

  val N2 = (N * N).toString

  val palindrome =
    if (N2 == N2.reverse) (N * N, N, N)
    else {
      (Iterator.from(N, -1)
        .map { n => (n-1, n) }
        .flatMap { case (n1, n2) =>
          (0L to 1) flatMap { deltaOne =>
            (0L to N - n2 + deltaOne) map { d2 => (n1 - d2, n2 - deltaOne + d2) } }
      })
        .map { case (n1, n2) => (n1 * n2, n1, n2) }
        .find { case (palindromeCandidate, _, _) =>
          palindromeCandidate.toString == palindromeCandidate.toString.reverse }
    }
}

The reason for the line if (N2 == N2.reverse) (N * N, N, N) is that the code in the else clause generates all the required numbers, except the N * N.

Time to find the 8 digit numbers that have the greatest palindromic product is about 9 seconds on my Mac.

For the case of seven digits:

Some((99956644665999,9997647,9998017)) - 1478999 µs

I will submit another solution that I found when I have time.

[samdebacker]

Thanks Eric, I was thinking about how to make a flatMap/map/... solution given the fact that you need to terminate early and you don't want to generate all possible products first? The Iterator-find combination just does that trick for you! And just for the sake of it, here a (scary) adaptation of your solution with for-comprehension.

[mverbist]

@ Sam
Indeed, my solution was very similar to yours (for comprehension)

(for {i <- (1 to 999); j <- (1 to 999)} yield i*j).filter(isPalindrome(_)).max

[eloots]

I posted some solutions that I came up with over time. The one that I originally started with used the brute force technique like shown by Michel Verbist (with one optimization to avoid doing every possible multiplication twice - e.g. 789 * 934 = 934 * 789:

(for {
   i <- (999 to 1 by -1)
   j <- (i to 1 by -1)
 } yield i*j
).filter(isPalindrome(_)).max

A first minor improvement was to limit the range of numbers over which to perform the multiplications. In fact, I thought that there might exist numbers that, if squared, generate a palindrome. If the range of numbers (1 to 999 in the problem) contains 1 or more of such numbers, then we pick the largest one and the corresponding palindrome specialNumber. For the stated problem, this number is 836, which, if squared, generates the palindrome 698896.

Now, the above code can be rewritten as:

(for {
   i <- (999 to 836 by -1)
   j <- (i to 698896 / i by -1)
 } yield i*j
).filter(isPalindrome(_)).max

In the original case, we do 499,500 multiplications, whereas here, we only do 25,449: a reduction by a factor of almost 20.

Of course we first have to find this special number (836) but we can do this with a linear search like as follows:

val specialNumber = Iterator.from(999, -1) find( x => isPalindrome(x * x) )

The code in my solution dates from quite a while ago and is different from what I show above. It demonstrates that experience will improve your code ;-).

Another solution I came up with uses another approach. It looks at all possible palindromic numbers, in reverse order, that can potentially generated from the base number (999). It then calculates all divisors below or equal to the base number and checks if the result of the division of the palindrome by the divisors is lower than the base number. If such a number is found, the problem has a solution.

Even though this seems far-fetched, it actually works, and is much faster than the previous method.

The code is in "eloots-2 - search by starting from palindromes"

Finally, there's my fastest solution in "eloots-3 - search in more optimal way". The solution found by Sam is really the fastest one, but this one comes pretty close. What is does is to apply a brute force search on a limited range of numbers (999 ... 900 in the sample code). If it doesn't find a palindrome in this range, it extends the range by another 100, but does't recalculate what's already been calculated. If the original range van N1 and it is extended with a additional range N2, the brute force search is performed on all N1 x N2 and N2 x N1. This process is repeated recursively until a solution is found. Using this method, the largest palindrome that can be generated from two 8 digit numbers can be found in about 5 seconds.

The last piece of code, "eloots-3a - same as eloots-3 but refactored" is the same as "eloots-3" but rewritten to illustrate the utilization of case classes specify method return types. More on that in the Language thread of this problem.

[eloots]

Just discovered how to close an issue ... and how to re-open it :-)

[eloots]

This post is in follow-up of yesterday's (January 8, 2015) Project Euler hacking session. Due to a lack of time, I couldn't present everything I had prepared.

As can be seen from the different solutions that were posted for this problem, there are many possible approaches. One of them was posted by Sam and the idea behind it was that, based on an observation he made, it is possible to generate products of numbers that are monotonically decreasing. Finding the largest possible palindrome then becomes a trivial problem: one just needs to scan the list of products and check if a number is a palindrome. The first one found then is the solution to the problem.

Here's the code that generates these numbers (note that it generates the products except for start * start):

val start = 999
val products =
  for {
    n2 <- Iterator.from(start.toInt, -1)
    n1 = n2 - 1
    deltaOne <- 0L to 1
    d2 <- 0L to (start - n2 + deltaOne)
    i = n1 - d2
    j = n2 - deltaOne + d2
  }  yield i * j

products is an Iterator[Long].

What we can do now is to derive another Iterator that contains tuples of subsequent values in the Iterator of products:

val productsM1 = products.drop(1)
val prodTuples = products zip productsM1

If the generated products are monotonically decreasing, every tuple in the Iterator should have a value in its first element that is greater or equal to the value in its second element.

So, the following check should return None if products is monotonically decreasing:

prodTuples find { case (n1, n2) => n1 < n2 }

but, unfortunately, it doesn't as shown in the following REPL session:

scala> val start = 999
start: Int = 999

scala> :pas
// Entering paste mode (ctrl-D to finish)

val products =
  for {
    n2 <- Iterator.from(start.toInt, -1)
    n1 = n2 - 1
    deltaOne <- 0L to 1
    d2 <- 0L to (start - n2 + deltaOne)
    i = n1 - d2
    j = n2 - deltaOne + d2
  }  yield i * j

// Exiting paste mode, now interpreting.

products: Iterator[Long] = non-empty iterator

scala> val productsM1 = products.drop(1)
productsM1: Iterator[Long] = non-empty iterator

scala> val prodTuples = products zip productsM1
prodTuples: Iterator[(Long, Long)] = non-empty iterator

scala> prodTuples find { case (n1, n2) => n1 < n2 }
res0: Option[(Long, Long)] = Some((934065,934122))

scala> prodTuples find { case (n1, n2) => n1 < n2 }
res1: Option[(Long, Long)] = Some((930069,930260))

scala> prodTuples find { case (n1, n2) => n1 < n2 }
res2: Option[(Long, Long)] = Some((926073,926406))

As a side note, it's interesting to see that, even though this implementation of the solution has a fundamental problem, it still comes up with a correct solution in most cases. This is most probably because of the way palindromic numbers are distributed which reduces the chance of hitting a problem.

There is an important remark to be made regarding Iterators; as can be seen in the REPL session above, an Iterator is mutable; in essence it has two key operators defined on it: next and hasNext. Calling next returns the next element (if any) on the Iterator. That element is now no longer on the Iterator.