The fourth task from Project Euler is to find the largest palindrome that is a product of two threedigit numbers. (I’m assuming decimal. ðŸ˜‰ )
Name no one man
The first subtask 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 twodimensional space, where each dimension ranges over the threedigit 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
andb * a
).  The Scala expression
100 to 999
provides the threedigit 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 multidigit 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 nonredundant pairs of threedigit 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.
The names in the diagram describe the state of the search at a given instant:
lo
andhi
— the lower and upper bounds (inclusive) of the range being searched;a
andb
— the current position in the search space;c
— the value at that position (the product ofa
andb
); andx
— 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 completex 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 tailrecursive 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 twodimensional 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 tutorialstyle 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.
 The Haskell web site has Haskell solutions to the Project Euler problems; another site offers Pythonbased solutions of the first several. However, these sites have very little explanation of the solution or design strategy (my focus).
 You can register at Project Euler to track your own progress, and read the comments posted by others when you’ve completed a problem. (Comments are closed for the earlier problems.)
 Russ Gray (Basildon Coder) is working through the problems in a variety of languages and posting on his experiences. His discussion of the first problem is what tipped me over the edge into this series.
 Dianne Marsh (a friend from Java Posse Roundup) is also doing Project Euler problems in Scala. Apparently she’s roped in collegues from SRT: Bill Wagner in C#, Darrell Hawley in Python, Marina Fedner in Ruby, and Anne Marsan in Matlab.
 I’m also aware of a partial set of solutions in F# by Chris Smith
My RSS reader is subscribed to the fellow solvers above; many of them have other interesting things to say beyond Project Euler!
Recommended reading:
 A Discipline of Programming (PrenticeHall Series in Automatic Computation)
 The Science of Programming (Monographs in Computer Science)