palindromic numbers in python
Question: Trying to find the largest palindrome that's the product of two three-digit
numbers. Before I look up the infinitely more efficient and - more importantly
- working solution, could you tell me what's wrong with my code? I just keep
getting the empty set.

    
    
    def palindrome():
        n = 100
        m = 100
        palind = []
        while n<=999:
            while m<=999:
                prod = n * m
                if str(prod) == str(prod)[::-1] and prod > palind[0]:
                    palind.pop(0)
                    palind.append(prod)
                return palind
                m = m + 1
            n = n + 1
            return palind
    
    print palindrome()
    


Answer: This shortcuts when it's impossible to return an i*j > the largest recorded
and correctly returns 906609 (note, if you're in python 2, the below would
work for you, but you'd prefer to use `xrange` instead of `range` to avoid
creating unnecessary lists in memory):

    
    
    def palindrome(floor=0, upto=999):
        '''
        return the largest palindrome product for all number from (but not including)
        floor to (and including) upto 
        '''
        start = upto
        largest = None
        for i in range(start, floor, -1): # decreasing from upto
            if i * upto < largest: # if True, impossible for higher product from combo
                break 
            for j in range(start, i-1, -1): # decrease from upto to not including i-1
                product = i*j
                if str(product) == str(product)[::-1]:
                    if product > largest:
                        largest = product
        return largest
    

Usage:

    
    
    >>> palindrome(99,999)
    906609
    >>> palindrome(10,13)
    121
    >>> palindrome(0,10)
    9
    

The short-cutting is important because if given a very large number, it can
take quite a while to return:

    
    
    >>> palindrome(upto=100000000)
    9999000000009999L
    

I also created a generator that hits every single combination from 0 to 999,
and it returns 906609.

    
    
    def palindrome(upto=1000):
        return max(i*j for i in range(upto) for j in range(upto) 
                    if str(i*j) == str(i*j)[::-1])
    

But when running this palindrome as in:

    
    
    >>> palindrome(upto=100000000)
    

The complete search will search all 100000000^2, and take far too long.

I first had written it like this, with the idea that it would short-cut and
avoid iterating over every possible combination, but this is incorrect, it
returns 888888:

    
    
    def palindrome():
        start = 999
        largest = 0
        for i in range(start, 0, -1): # decreasing from 999
            if i * 999 < largest:
                return largest
            for j in range(start, i, -1): # decreasing from 999 to i
                if str(i*j) == str(i*j)[::-1]:
                    largest = i*j
    

It first multiplies 999 times 999, then 998 times 999, then

    
    
    998*998
    997*999
    997*998
    997*997
    ...
    

But the results aren't monotonically decreasing (that is, each result is not
guaranteed to be smaller than the previous.)

