Beating a dead horse: Project Euler 4

Question

The task

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.

This problem has been reviewed numerous times on this site, and many extraordinary clever solutions has been suggested. I have taken my own stab at the problem, and done it a tad differently. I was mainly wondering if my code is readable and if it has any advantages over the quote on quote standard approach i see many others using.

The standard approach is shown below.

 - for i from 999 to 1
 -     for j from 999 to 1
          if is_palindrome( i*j )
            best = max(old, best)

The basic idea is to iterate over the 3-digit numbers i and j. If the product is a palindrome then check whether it is bigger than the previously found palindrome. There are many speed improvements one could make to the psudo code above (like breaking early or only iterating over numbers divisible by 11). I have implemented these in the code below labeled standard approach.

My thought was even with these improvements it took 160 seconds finding the biggest palindromic product formed by two 8 digit numbers.

Second approach:

for palindromes < limit
    num1, num2 = check(palindrome)
    if num1*num2 > 0
         return num1*num2

Here i iterate over the palindromes starting from biggest to smallest. If the palindromes can be factored into two numbers with n digits we have found the solution. Since we start at the biggest palindrome we can stop once a solution has been found.

I am mainly interested in feedback regarding my method, not the standard one.Is it readable, can one understand what the different help functions do? Also any general feedback on my algorithm / approach would be appreaciated. I think I atleast have followed PEP8.

Standard approach

def is_palindrome(n):
    """Return True if n is a palindrome, False otherwise."""
    s = str(n)
    return s == s[::-1]


def product_lst(n):
    palindrome = max_palindrome = 0
    pair = (0, 0)
    for i in xrange(n - 1, 0, -1):
        "Since all palindromes are divisible by 11, either j or i has to be as well"
        if i % 11 == 0:
            j_max = i
            j_range = xrange(i + 1, 0, -1)
        else:
            j_max = 11 * int(i / 11)
            j_range = xrange(j_max, 0, -11)

        if i * j_max < palindrome:
            break

        for j in j_range:
            product = i * j
            if product < palindrome:
                break
            if is_palindrome(product):
                if product > palindrome:
                    palindrome = product
                    pair = (i, j)
    return (pair, palindrome)

My attempt

from primefac import isprime

def palindrome_product(n):
    "Maximises num1 * num2 = palindrome. Where num1 and num2 has length n."
    palindrome_generator = generate_palindromes(n)
    for palindrome in palindrome_generator:
        num1, num2 = is_product_of_two(palindrome, n)
        if num1 != 0:
            return ((num1, num2), palindrome)


def generate_palindromes(n):
    " Generates palindromes of decreasing order"
    first_half = 10**n - 1
    while first_half > 10**(n - 1) - 1:
        second_half = str(first_half)[::-1]
        palindrome = int(str(first_half) + str(second_half))
        yield palindrome
        first_half -= 1


def is_product_of_two(palindrome, n):
    " Checks wheter the palindrome can be written as a product"
    " of two numbers of length num"
    palindrome //= 11
    "All palindromes are divisible by 11"
    num_1 = num_2 = 0
    if not isprime(palindrome):
        " Generate numbers such that 11*i has length n"
        for i in xrange(10**(n) / 11, 10**(n - 1) / 11, -1):
            " If num2 > 10**n then num2 is no longer a n-digit number"
            if palindrome > i * 10**n:
                break
            if palindrome % i == 0:
                num_1 = i * 11
                num_2 = palindrome / i
                break
    return num_1, num_2

Answer 1

If there are three things that I'd want to improve at the least it's:

1. Don't use strings as comments. Instead use #. Also use docstrings to describe what a function is doing, you seem to do this with strings, so just change them to use """...""".

   "string"
   # Comment
   def fn():
       """Docstring, does this"""
       ...
   

2. You need to stop making variables you use only once. If you use it once, use it straight away. I don't want to figure out how you use a variable to find you only use it once. There's only one exception to this, if it's more readable to use another variable.

3. Try to simplify logic, this is hard, and can take time to figure out. So if you come across a while think 'can this be a for?' If you have a bound in a for to break the for, think 'can this be moved into the for statement?' And probably the hardest to realize, but a good half of palindrome_product's logic is a duplicate of is_product_of_two.

Starting with generate_palindromes.
This should be a for loop. If you ignore the work the while loop is doing and only focus on the looping you should see:

first_half = 10**n - 1
while first_half > 10**(n - 1) - 1:
    ...
    first_half -= 1

This is what for loops were made for!

for first_half in xrange(10**n - 1, 10**(n - 1) - 1, -1):
    ...

This might not seem like much at first, but by having the start, stop and step all in the same place we can now tell what the loop will loop over. This for me and probably others makes the code easier to read, as we now know more about the loop.

As for your inner part, you should change first_half to a string. and then make palindrome without calling str again. This can simply be:

first_half = str(first_half)
yield int(first_half + first_half[::-1])

Personally I think a single letter variable here increases readability. Normally it's recommended against, with very correct reasons, but here I think it's ok.

I'd also make generate_palindromes increase and decrease, this is as if you later need a list of increasing palindromes you can just use this function. This requires another argument, I'd use increase which defaults to False. I'd also move 10 ** n into a variable to increase readability in the ranges.

This would result in:

def generate_palindromes(n, increase=False):
    en = 10 ** n
    en1 = 10 ** (n - 1)
    range_ = xrange(en1, en) if increase else xrange(en - 1, en1 - 1, -1)
    for i in range_:
        i = str(i)
        yield int(i + i[::-1])

This seems good. So I'll move onto is_product_of_two.
First, is says to me it returns a boolean. It does not. If I ask you 'is_that_a_cat' I'd expect a 'yes' or 'no'. I'd not expect the bread of cat. Just like I expect this function to tell me if it is a product of two. Not it's two products.

In this function you don't need num_1 or num_2. Either you return i * 11, palindrome / i or you return 0, 0. Putting a return in a for loop is ok.

With the above you can change you usage of isprime into a guard clause. This is just to reduce the indentation of the for loop by one.

You can move palindrome > i * 10**n into your for loop. If we rearrange it you should get i < palindrome / 10**n. since we know the lowest it can go is 10**(n - 1) / 11 we can just use max to make sure neither of these ever happen.

Using all the above you can get:

def is_product_of_two(palindrome, n):
    palindrome //= 11
    if isprime(palindrome):
        return 0, 0
    # Generate numbers such that 11*i has length n
    for i in xrange(10**n // 11, max(p // 10**n, 10**(n - 1) // 11), -1):
        if palindrome % i == 0:
            return i * 11, palindrome / i
    return 0, 0

Finally I'd merge is_product_of_two into palindrome_product. This is just by replacing return 0, 0 with continue and copying it into the for loop. With a few minor changes like returning (num1, num2), palindrome * 11.

And again I'd use en and en1 to simplify the range.

This can result in:

def palindrome_product(n):
    en = 10 ** n
    en1 = 10 ** (n - 1)
    for p in generate_palindromes(n):
        p //= 11
        if isprime(p):
            continue
        # Generate numbers such that 11*i has length n
        for i in xrange(en // 11, max(p // en, en1 // 11), -1):
            if p % i == 0:
                return (i * 11, p // i), p * 11

I removed most of your comments, as I didn't find them particularly helpful. The one I left is as it has an odd range. And requires a short description of what you done. I also removed your doc-strings as when talking about the code, they get in the way a bit.

But for an example of a multiline-docstring, here's a poor one on the new generate_palindromes function:

def generate_palindromes(n, increase=False):
    """
    Generates palindromes of length 2n.

    Changing increase to True causes the function to yield the smallest numbers first.
    """
    en = 10 ** n
    en1 = 10 ** (n - 1)
    range_ = xrange(en1, en) if increase else xrange(en - 1, en1 - 1, -1)
    for i in range_:
        i = str(i)
        yield int(i + i[::-1])

And it seems like you have no PEP8 errors, I'm not going to run it through a linter to find all your comments. But it's good :)