current community

your communities

more stack exchange communities

Stack Exchange Inbox Reputation and Badges
tour help
Sign up ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.
up vote 2 down vote favorite
1

I've just written a palindrome generator and would like to know what you think about it.

Especially:

  • code style
  • Is it possible to get the same result without making a special case for 1-digit palindromes?
  • efficiency

#!/usr/bin/env python

def getPalindrome():
    """
        Generator for palindromes.
        Generates palindromes, starting with 0.
        A palindrome is a number which reads the same in both directions.
    """
    # First print all one-digit palindromes
    for i in range(10):
        yield i

    length = 2
    while True:
        # Do the symmetric part
        for i in range(10**(length//2-1), 10**(length//2)):
            a = str(i)
            r = a + a[::-1]
            yield int(r)
        length += 1

        # Do the unsymmetric part
        exponent = (length-1)//2
        for prefix in range(10**(exponent-1), 10**exponent):
            prefix = str(prefix)
            for i in range(10):
                result = prefix + str(i) + prefix[::-1]
                yield int(result)
        length += 1

if __name__ == "__main__":
    palindromGenerator = getPalindrome()
    for i, palindromeNumber in enumerate(palindromGenerator):
        print("%i-th palindrome: %i" % (i, palindromeNumber))
        if i >= 500:
            break
share|improve this question

1 Answer 1

up vote 3 down vote accepted

  1. I'd implement this function like this:

    from itertools import count

def palindromes():
    """Generate numbers that are palindromes in base 10."""
    yield 0
    for digits in count(1):
        first = 10 ** ((digits - 1) // 2)
        for s in map(str, range(first, 10 * first)):
            yield int(s + s[-(digits % 2)-1::-1])

    (In Python 2, you should replace range with xrange and map with itertools.imap.)

    The insight is that instead of building an odd-length palindrome from the parts prefix + middle + xiferp, we can build it as prefix + iferp: that is, with the middle digit being supplied by the last digit of the prefix.

  2. In your main loop, you arrange to generate the first 501 palindromes:

    for i, palindromeNumber in enumerate(palindromGenerator):
    ...
    if i >= 500:
        break

    but it would be simpler to use itertools.islice:

    for i, palindrome in islice(enumerate(palindromeGenerator), 501):
    ...

  3. As for your question about efficiency, it is impossible to answer without knowing the purpose of this code. If all you are going to do is to print the first 501 palindromes, then your code is fine: the runtime will be dominated by printing the output.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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