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

In summary, the code uses recursion to check all palindromes up to a certain size, but it crashes if the palindrome is too large.
  • #1
mslate
2
0
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?


Code:
# 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
 
Last edited by a moderator:
Technology news on Phys.org
  • #2
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.
 
  • #3
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.

Code:
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.
 
Last edited:
  • #4
Thank you for the concise answer and style advice--your code certainly looks nicer :) I'll take the looping advice to heart
 
  • #5
You are not supposed to give out full solutions to Project Euler problems. Please remove it.
 
  • #6
Amanheis said:
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" [Broken].

It's a trivial problem anyway...
 
Last edited by a moderator:
  • #7
vcxp said:
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.
 
  • #8
uart said:
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

Code:
"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.
 
  • #9
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 :
Code:
function IsPalindrome(n : integer) : boolean;
var s : string;
 begin
  str(n,s);
  IsPalindrome := s = ReverseString(s)
 end;
 
Last edited:

1. What is recursion in Python?

Recursion in Python is a programming technique in which a function calls itself repeatedly until a base case is reached. This allows for solving complex problems by breaking them down into smaller, simpler versions of the same problem.

2. How do you write a recursive function in Python?

To write a recursive function in Python, you need to define a base case that will stop the function from calling itself, and a recursive case that will call the function with a smaller input until the base case is reached. You also need to make sure that the recursive case will eventually reach the base case to avoid an infinite loop.

3. What are the advantages of using recursion in Python?

Using recursion in Python can make code more concise and elegant, and it allows for solving complex problems that would be difficult to solve with iterative approaches. It can also help with code reuse, as a recursive function can be called multiple times within the same program.

4. What are some common mistakes when using recursion in Python?

Some common mistakes when using recursion in Python include not defining a base case or defining a base case that is never reached, which can lead to infinite loops. Another mistake is not considering the space complexity, as recursive functions can use a lot of memory if not implemented correctly.

5. Can all problems be solved using recursion in Python?

No, not all problems can be solved using recursion in Python. Some problems may be better suited for iterative approaches or may not have a natural recursive solution. It is important to evaluate the problem and determine the most efficient approach before using recursion.

Similar threads

  • Programming and Computer Science
2
Replies
55
Views
4K
  • Programming and Computer Science
Replies
2
Views
727
  • Programming and Computer Science
Replies
3
Views
1K
  • Programming and Computer Science
Replies
2
Views
730
  • Programming and Computer Science
2
Replies
43
Views
3K
  • Programming and Computer Science
Replies
1
Views
748
  • Programming and Computer Science
Replies
1
Views
2K
  • Programming and Computer Science
Replies
22
Views
633
  • Programming and Computer Science
Replies
19
Views
2K
  • Programming and Computer Science
Replies
4
Views
4K
Back
Top