Project Euler #4 "Largest Palindrome product" in Python

Question

Given

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.

Solution

import time
def reverse(num):
 dreverse = 0
 while (num > 0):
 dreverse = dreverse * 10 + num % 10
 num /= 10
 return dreverse
def is_palindrome(num):
 if (num < 0):
 raise ValueError('Non-negative integers only')
 return num == reverse(num)
def main():
 largest_palindrome = 0
 lower = 999
 while lower >= 100:
 upper = 999
 while upper >= lower:
 if upper * lower <= largest_palindrome:
 break
 if is_palindrome(upper * lower):
 largest_palindrome = upper * lower
 upper -= 1
 lower -= 1
 return largest_palindrome
start_time = time.time()
print main()
print("--- %s seconds ---" % (time.time() - start_time))
o/p: 906609
--- 0.0150721073151 seconds --- 

I am including timing metric from now on. This solution seems \$O(N^2)\$. Can I improve it further?

Answer 1

You are recomputing the product upper * lower three times:

 while upper >= lower:
 if upper * lower <= largest_palindrome:
 break
 if is_palindrome(upper * lower):
 largest_palindrome = upper * lower

You should save it in a variable:

 while upper >= lower:
 product = upper*lower
 if product <= largest_palindrome:
 break
 if is_palindrome(product):
 largest_palindrome = product

Also, how about this version of is_palindrome:

def is_palindrome(n):
 s = str(n)
 return (s == s[::-1])

Update

Replace your loops with for and xrange:

largest = 0
for lower in xrange(999,99,-1):
 for upper in xrange(999,lower-1,-1):
 ...

It makes the intent of your code a lot clearer, and it is easier to correctly write the loop.

(The following is note quite right)

(削除) Finally, if upper*lower <= largest_palindrome, you actually return from the function:

 if upper * lower <= largest_palindrome:
 return largest_palindrome

The return will essentially break out of both while loops. Using just break will only break out of the inner loop. Of course, the remaining cases will execute very quickly since they will only last one iteration of the inner loop, but it is still a good optimization to know about. (削除ここまで)

• CodeYogi: No, I don't want to use tricks here return (s == s[::-1]). Thanks!
• Dan: How is this a trick? s == s[::-1]evaluates true if s is equal to the reverse of s, and evaluates false if it isn't. This is exactly what a palindrome is. That's actually exactly what your code already does, but this does it in a more concise manner.
• spyr03: @ARedHerring An explanation of how it works might be more convincing. CodeYogi The "trick" is that s[::-1] iterates from the end of the variable to the start. It what the division and mod code does, but it is easier to read
• Jaime: The suggestion to replace break with return has faulty logic, I'm afraid, e.g. if the product of lower = 500, upper = 501 is the first smaller than largest_palindrome, we still need to check lower = 499, upper = 999, which is about 2x larger.
• ErikR: yeah - you're right about that. Let me see if I can find a way to iterate where you can return early.

Answer 2

I am going to suggest a solution that is 20x less perfomant than yours, because Python was really made to optimize programmer's time, not execution time. It should be noted that my solution is still under a second of execution time.

---

def is_palindrome(string):
 return string == ''.join(reversed(string))

A number is just a kind of string, so I wrote a more general (and, yes, slower) function to check for palindromes. The number should be converted to string before being passed in to the function.

The main body of this program is really close to natural langauge, it is just:

print(max(i * j for i in range(500, 999) for j in range(500, 999) 
 if is_palindrome(i * j)))

it uses a generator expression, so the usage of memory is O(1) and the time complexity is O(N^2) as in your solution.

Almost all the time is spent in the is_palindrome function, using your function would make this as fast as your solution.

• Peter Schneider: Just to be pythonic isn't an excuse for not using the best algorithm. In your variant, you have to evaluate is_palindrome() for every value. CodeYogi and user5402 break out of the inner loop as soon as lower*upper is less then the currently known best value. This reduces the number of calls to is_palindrome down by a factor of 66. Also, in my eyes is s==s[::-1] much more readable.
• Caridorc: @PeterSchneider indeed, this is just an alternate way that preferes a slower algoritmh for simplicity of implementation, it is different but by no means better
• CodeYogi: @Caridorc I agree with @peter that in the same of being pythonic we are really writing less efficient code. This is my real experience. If we can improve the performance then why the hell we use slower techniques in the name of readablilty? Or there should be strict disclaimer for python learners Learn at your own risk because you won't pass any coding competitions . A code is beautiful when it runs not when its dead.
• Caridorc: @CodeYogi You are raising an interesting point, Should a code be 20x slower just to be more readable? Yes and no, and the answer changes from case to case