Project Euler #4 - Largest Palindrome Product

Question

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)

whenever a product or combination or permutation is mentioned, i'd check itertools first — dm03514
– dm03514, Commented Sep 29, 2013 at 1:16

Gareth Rees · Accepted Answer · 2013-09-27 09:19:44Z

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.

SylvainD · Accepted Answer · 2013-09-29 22:49:24Z

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

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. — SylvainD
– SylvainD, Commented Sep 26, 2013 at 23:43
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 — blueberryfields
– blueberryfields, Commented Sep 27, 2013 at 4:40

Stack Exchange Network

Project Euler #4 - Largest Palindrome Product

2 Answers 2

You must log in to answer this question.

Hot Network Questions

Project Euler #4 - Largest Palindrome Product

2 Answers 2

You must log in to answer this question.

Related

Hot Network Questions