Three X eerhT

The fourth task from Project Euler is to find the largest palindrome that is a product of two three-digit numbers. (I’m assuming decimal. 😉 )

Name no one man

The first sub-task is to determine whether the decimal representation of an integer is palindromic. A direct approach yields this:

  def reverseInt(n: Int) = {
    def rev(a: Int, b: Int): Int =
      if (a == 0)
        b
      else
        rev(a / 10, b * 10 + a % 10)
    rev(n, 0)
  }
  def isPalindrome(n: Int) = {
    reverseInt(n) == n
  }

I’m not approaching this by way of string conversion, for three reasons:

  • Nothing in the problem statement involves strings;
  • Expressing the solution in terms of string manipulation doesn’t make the solution significantly easier to understand; and
  • Doing so would be slower.

Now on to the more interesting part.

Seek no monkees

The problem can be solved by searching a two-dimensional space, where each dimension ranges over the three-digit integers. A moment’s thought provides the following additional facts we can use:

  • Multiplication is symmetric, so there’s no need to examine both products of two different numbers (a * b and b * a).
  • The Scala expression 100 to 999 provides the three-digit integers.
  • We can ignore 100 as a candidate, because any multiple of 100 must end in a zero, which isn’t the first digit of any multi-digit decimal number in standard notation.
  • There’s a solution, because 101 × 101 = 10201, which is palindromic. (It’s nice to know that the search function doesn’t need to deal with an empty solution space.)

Going for the obvious, we can construct the products of non-redundant pairs of three-digit numbers, filter the products for palindromes, and capture the maximum of the palindromes:

  def maxOfPalindromes() = {
    (
      for {
        a <- 101 to 999
        b  a max b)
  }

It would be easy to parameterize this for the range to be searched (either by bounds or by number of digits), but I want to focus on the search performance.

Top spot

The version above takes about 152 ms on my laptop, which seems entirely too much time for this small a task. The following diagram shows the search space, as a context for the rest of the post.

search2d.jpg

The names in the diagram describe the state of the search at a given instant:

  • lo and hi — the lower and upper bounds (inclusive) of the range being searched;
  • a and b — the current position in the search space;
  • c — the value at that position (the product of a and b); and
  • x — the largest palindrome found thus far.

In his landmark book, A Discipline of Programming (published 32 years ago!), Edsger Dijkstra stated the “Linear Search Theorem”. I’ll paraphrase it informally for our purposes as:

When searching for the maximum value having some property, examine the values in decreasing order; the first satisfactory value found will be the maximum.

Assuming that we apply this to both a and b, the green area has been examined and the blue area has not. We can express the next state of the search in a decision table (each row’s condition assumes that conditions on all previous rows failed):

Condition Action State changes
next a next b next x
a < lo Search complete
x is the result
n/a
b < a Current row searched,
move to next blue row
a - 1 hi x
c <= x c and rest of this row eliminated,
move to next blue row
a - 1 hi x
isPalindrome(c) c is new max palindrome
(rest of this row is smaller values)
a - 1 hi c
otherwise c eliminated,
continue searching current row
a b - 1 x

The decision table translates directly to a tail-recursive function. I’ll use a bit of scope management to avoid computing c unless it will be used.

  def maxPalindromeIn(lo: Int, hi: Int) = {
    def loop(a: Int, b: Int, x: Int): Int = {
      if (a < lo)
        x
      else if (b < a)
        loop(a - 1, hi, x)
      else {
        val c = a * b
        if (c <= x)
          loop(a - 1, hi, x)
        else if (isPalindrome(c))
          loop(a - 1, hi, c)
        else
          loop(a , b - 1, x)
      }
    }
    loop(hi, hi, 0)
  }
  def maxPalindrome3x3() = maxPalindromeIn(101, 999)

This runs in about 445µs, a speedup factor of well over 300.

I prefer π

Let me round this post off with a few observations.

Performance is not the most important issue. I probably need to state that clearly, having quoted run time so often in this and recent Project Euler posts. I believe that speed, small memory footprint, and any other measure of economy, should be subordinate and subsequent to good design and correctness.

Those who forget history are condemned to repeat it. Over twenty years ago, when the dreaded “G” word was still occasionally heard in polite programming circles, a misguided letter to the editor of the Communications of the ACM attempted to claim that goto was necessary to effective programming and offered a small problem in defense of that claim. Dijkstra’s response addressed the errors and approach of the claim and its “solution”; his demonstration used the idea of the two-dimensional application of the Linear Search theorem.

There are important ideas that transcend programming model. The ideas in A Discipline of Programming are all presented in an imperative style, yet the clarity of design makes the concepts important to FP as well. That book is not an easy read (I worked rather than read through it when I got my copy in 1976) but it rewards the investment richly. David Gries gave a tutorial-style presentation of many of the same core ideas in The Science of Programming. I cannot possibly recommend them highly enough.

Compare and contrast. It’s useful to see how others approach a problem, after you’ve solved it yourself.

My RSS reader is subscribed to the fellow solvers above; many of them have other interesting things to say beyond Project Euler!


Recommended reading:

Advertisements
Trackbacks are closed, but you can post a comment.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: