What is the Python syntax for checking if a number is a palindrome?

[mslate]

I'm doing the http://projecteuler.net/" problems for garbages and giggles, and was working on problem 4 which requires finding the largest number palindrome (e.g. 10301, 54345) that is the product of two 3-digit numbers.

Below is my code, and I'm pretty sure Python will reproduce the error that I'm getting if you try it. I'm using recursion to search backwards from the product of 999 x 999, stopping at 100 x 100. I'm not very familiar with Python or programming, but I suspect that the problem's arising from the recursive calls spinning out of control and taking up too much memory. Any ideas?

# Project Euler no. 4
# Find the largest palindrome made from the product of two 3-digit numbers


def checkPalindrome(num1,num2):
	prod=str(num1*num2)
	i=0
	l=len(prod)

	print num1, num2
	# prevents infinite loop by stopping recursion beyond checking 3-digit numbers
	if (len(str(num1))!=3 | len(str(num2))!=3):
		return 0,0

	# even
	if l%2==0:
		while (1):
			if prod[i]!=prod[-i-1]:
				a1,b1=checkPalindrome(num1,num2-1)
				prod1=a1*b1
				a2,b2=checkPalindrome(num1-1,num2-1)
				prod2=a2*b2
				return (a1,b1) if prod1 > prod2 else (a2,b2)
			if i==l/2:				# checked palindrome w/o error--is a palindrome
				return num1, num2
			i+=1
	else: #odd
		while (1):
			if prod[i]!=prod[-i-1]:
				a1,b1 = checkPalindrome(num1,num2-1)
				prod1 = a1 * b1
				a2,b2 = checkPalindrome(num1-1,num2-1)
				prod2 = a2 * b2
				return (a1,b1) if prod1 > prod2 else (a2,b2)
			if i > l/2:    	# checked palindrome w/o error--is a palindrome
				return num1, num2
			i+=1
	return 0,0

if __name__=="__main__":
	a=999
	b=999
	
	print "Checking palindrome for 3-digit products..."
	num1,num2=checkPalindrome(a,b)

	print "The largest palindrome made from the product of two 3-digit" \
		" numbers is %d and results from the product of " \
		"%d and %d" % num1*num2, num1, num2

 

[vcxp]

I've got an event to attend in ~10 minutes, but I'll look at your code when I get home.

It's worth noting, however, that Python doesn't handle recursion well (at least, as far as I remember; I've since started using Haskell and Scheme). This isn't surprising, given Guido's hostility to functional programming (IIRC, he dislikes lambda expressions and map/reduce/filter, so it doesn't surprise me that he'd prefer imperative looping over recursion).

That being said, I got your program to stop displaying an error about recursion depth (check out sys.setrecursiondepth(); the default value is 1000), but when I did something else broke (one of your string indices was out of range). I'm skeptical about the approach used here anyway, but I can't say for sure without looking at it some more.

Hang tight, and I'll get back to you a little later today.

 

[vcxp]

I hacked this up in about 5 minutes. It's a 15 line solution that takes about 1-1.5 seconds. It attempts no optimization or anything, but it's easy to read and runs fast enough.

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

def euler_four():
    highest = 1
    for x in xrange(100, 1000):
        for y in xrange(100, 1000):
            if is_palindrome(x*y) and x*y > highest:
                highest = x * y
    return highest

def main():
    print euler_four()

main()

Tips for your code:

- Recursion is not your friend in Python. Use a loop.
- while(1) is disgusting. Don't do that unless you absolutely have to. Remember that in Python, if you're going to do that, True == 1, and while(True) is a lot easier to read. But you really shouldn't have to do this all that often.
- You can check all n digit products by checking in the range [10^(n-1), 10^n) (for a product, you obviously have to loop this twice). Using a string is nasty and makes your code harder to read.
- Your two while loops contain code that is exactly the same. You could probably use a function to abstract something here.
- If you find yourself writing "# prevents infinite loop by stopping recursion beyond checking 3-digit numbers", then that should tell you something is wrong. 99.99999999% of the time, you should have a clear idea of what range of values you need to loop over. That is, you can easily set a boundary for this problem and check within that (as I explained above) without having to use an infinite loop.

If you have any questions, or feel that I made a mistake (I probably did), please let me know.

EDIT: Code inside spoiler tags does not work.

 

[mslate]

Thank you for the concise answer and style advice--your code certainly looks nicer :) I'll take the looping advice to heart

 

[Amanheis]

You are not supposed to give out full solutions to Project Euler problems. Please remove it.

 

[vcxp]

You are not supposed to give out full solutions to Project Euler problems. Please remove it.

Tell that to http://en.wikipedia.org/wiki/Project_Euler" .

It's a trivial problem anyway...

 

[uart]

It's a trivial problem anyway...

Agreed!

I've got one simple question about the Python code though. For most part Python seems quite readable (a bit like Pascal/Delphi which I'm very familiar with), but one piece of syntax strikes me as a bit odd. Could someone please explain the syntax of the code that apparently implements string reversal, "str(n)[::-1]".

Thanks.

 

[vcxp]

Agreed!

I've got one simple question about the Python code though. For most part Python seems quite readable (a bit like Pascal/Delphi which I'm very familiar with), but one piece of syntax strikes me as a bit odd. Could someone please explain the syntax of the code that apparently implements string reversal, "str(n)[::-1]".

Thanks.

str() is called in order to convert the number we passed, "n", to a string. To reference a particular element of a string, we use [] just like we would with a char* in C. However, Python's string index is a little more fancy, and the "[::-1]" reverses the string for us. So the entire line just compares the string of the original number to the string of the original number, reversed. If they're equal, it returns True, and otherwise it returns False.

As for how the index itself works (i.e., what [::-1] actually means), think of the index like so:

[a : b : c]

To get an element "a", we would use myString[a] for short. To get multiple elements within a slice of the string, we'd use myString[a:b]. If we want to pull items in a sequence and skip a fixed number of elements, we would use myString[a:b:c]. We can omit parts of this index to get default values. If we omit a, b and c, we get the whole string. If we just add a c element to the index, we get every cth element of the original string. So, if we wanted every other letter of the string "abcde", we'd do

"abcde"[::2]

which returns the string "ace". So putting this all together, we pass a value of -1 for our "c" part of the index, which tells Python to walk through the string backwards (as you might guess, calling a string with myString[::1] just returns the original string, so making -1 the reverse just makes the notational logical and convenient).

Hope that helps.

 

[uart]

Thanks vcxp, yes I figured out the "str(n)" part it was really just the [::-1] part that baffled me. Your post explains it perfectly. So there is really a lot of string handling syntax effectively built into the index notation.

In Pascal or Delphi the corresponding code would be :

function IsPalindrome(n : integer) : boolean;
var s : string;
 begin
  str(n,s);
  IsPalindrome := s = ReverseString(s)
 end;