[Tutor] Fwd: Re: largest palindrome number

[Chris Fuller]

I played around with this puzzle a bit.  I made a palindrome function a bit 
like Bob's, only i iterated through the string (stopping at the first mismatch) 
instead of doing the whole thing at once.

The rest of the code is even more amenable to speedups.  The first thing I saw 
was the outer "i" loop can start at 100, rather than one.  I also saw that 
using PNum = max(palindrome(i*j), PNum) would replace a half dozen lines in 
the first try.  But I discarded this approach.  I figured it would be much 
faster to work backwards from 999*999, stopping at the first palindrome that 
was the product of two three digit numbers.

This code is quite terse, and uses some advanced features (generator 
functions, shortcutting), but I'll try to explain it.


n = 999*999

while True:
   if palindrome(n) and \
      any( (100<=i<1000 and 100<=n/i<1000 for i in \
         (j for j in range(1,1+int(n**.5)) if n%j==0))):
      break
   else:
      n -= 1

print n

The inner "j" loop simply finds factors of n (n**.5 is the square root of n); 
the outer loop checks to see if the factor and its complementary factor are 
three digit numbers.  The generator expressions (like list comprehensions, but 
bounded by parentheses) only calculate one true/false check on a single factor 
at a time.  The any() built-in function returns as soon as it encounters are 
true value, so a lot of computation is avoided versus checking all the factors 
and their three-digit status.

A note on the "if palindrome(n) and \" line.  Python (and C. and most 
languages) will stop computing through and and statement if the first 
expression is false, and likewise for an or statement if the first statement is 
true.  This is the same way any() and all() work, only these functions can 
operate on iterators of arbitrary length.  So by putting the less 
computationally intensive palindrome check first, a few more cpu cycles are 
saved.

I got around an order of magnitude speedup with this code.

Cheers