2
\$\begingroup\$

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

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

How would you improve the following code?

I'm looking specifically for:

  • performance optimizations
  • ways to shorten the code
  • more "pythonic" ways to write it

   def is_palindrome(num):
        return str(num) == str(num)[::-1]        
    def fn(n):
        max_palindrome = 1
        for x in range(n,1,-1):
            if x * n < max_palindrome: 
                break
            for y in range(n,x-1,-1):
                if is_palindrome(x*y) and x*y > max_palindrome:
                    max_palindrome = x*y
                elif x * y < max_palindrome:
                    break
        return max_palindrome

    print fn(999)
\$\endgroup\$
1
  • 1
    \$\begingroup\$ whenever a product or combination or permutation is mentioned, i'd check itertools first \$\endgroup\$
    – dm03514
    Sep 29, 2013 at 1:16

2 Answers 2

3
\$\begingroup\$

The function is_palindrome converts num to a string twice. You might consider:

def is_palindrome(n):
   """Return True if n is a palindrome; False otherwise."""
   s = str(n)
   return s == s[::-1]

And then for the main loop I would write:

from itertools import product
max(x * y for x, y in product(range(1000), repeat=2) if is_palindrome(x * y))

This runs in less than a second so I think it is not worth putting lots of effort into optimizing it.

\$\endgroup\$
1
\$\begingroup\$

It looks good to me.

You could break from the inner loop even if x*y == max to avoid 1) an additional useless iteration 2) checking if it is a palindrome. Also it would remove some code testing the value of the product.

I think you could change the limits of the inner loop to consider only y smaller or equal to x. If you do so, you can break out of the outer loop if x*x < max.

Edit :

Some more details. My second optimisation tips is not a really a good tip, it's not a bad tip neither.

Here is the function before and after taking my second comment into action. Also, some more basic code has been added for benchmarking purposes.

def fn(n):
    itx,ity = 0, 0
    max_palindrome = 1
    for x in range(n,1,-1):
        itx+=1
        if x * n < max_palindrome:
            break
        for y in range(n,x-1,-1):
            ity+=1
            if is_palindrome(x*y) and x*y > max_palindrome:
                max_palindrome = x*y
            elif x * y < max_palindrome:
                break
    print "1", n,itx,ity,max_palindrome
    return max_palindrome

def fn2(n):
    itx,ity = 0, 0
    max_palindrome = 1
    for x in range(n,1,-1):
        itx+=1
        if x * x <= max_palindrome:
            break
        for y in range(x,1,-1):
            ity+=1
            if x*y <= max_palindrome:
                break
            if is_palindrome(x*y):
                max_palindrome = x*y
                break
    print "2", n,itx,ity,max_palindrome
    return max_palindrome

Now, when running the following tests :

for n in [99,999,9999,99999,999999]:
    assert fn(n) == fn2(n)

fn is sometimes in a pretty epic way, sometimes just worse...

fn n      itx    ity result
1 99       10     38 9009
2 99        6     29 9009
1 999      93   3242 906609
2 999      48   6201 906609
1 9999    100   4853 99000099
2 9999     51   2549 99000099
1 99999   339  50952 9966006699
2 99999   171 984030 9966006699
1 999999 1000 498503 999000000999
2 999999  501 250499 999000000999
\$\endgroup\$
10
  • 1
    \$\begingroup\$ are you sure the second optimization is correct? \$\endgroup\$ Sep 26, 2013 at 22:33
  • \$\begingroup\$ Assuming x goes from n to 0 and y goes from x to 0, I think we have the following property: 1) for a given x, xy is decreasing 2) if xx <= max, xy <= xx <= max. \$\endgroup\$
    – SylvainD
    Sep 26, 2013 at 23:43
  • \$\begingroup\$ y is in the range [n..x-1]. yx > xx for y > x \$\endgroup\$ Sep 27, 2013 at 1:11
  • 1
    \$\begingroup\$ that's a change which leads to an incorrect algorithm (as written above, it would miss some of the larger palindromes, including the correct solution). It would be an effective optimization if i was writing an algorithm looking for the smallest palindrome, though \$\endgroup\$ Sep 27, 2013 at 4:40
  • 1
    \$\begingroup\$ I've added more details about what I had in mind. \$\endgroup\$
    – SylvainD
    Sep 29, 2013 at 22:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.