Project Euler #4 with python. What;s wrong with my code?

Question

I am trying to do project euler problem 4 using python. The problem statement goes like this:

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.

I wrote down a solution for it:

s=0
x=100
y=100
list=[]
z=x*y
def palindrome():
    while z>=1:
        s=s*10+z%10
        z=z/10
        if z==s:
            list.append(z)
while x<=999:
    while y<=999:
        palindrome()
        y=y+1
    x=x+1
    y=100
print list

It ended up giving an error along the lines of 'z referenced beyond assignment'.

I searched for a solution to this error before finally deciding to use the syntax 'global' to bypass this error.

s=0
x=100
y=100
list=[]
z=x*y
def palindrome():
    global z
    global s
    global x
    global y
    global list
    while z>=1:
        s=s*10+z%10
        z=z/10
        if z==s:
            list.append(z)
while x<=999:
    while y<=999:
        palindrome()
        y=y+1
    x=x+1
    y=100
print list

Now it doesn't give an error, but it gives an empty list as output. I tried to debug the code by inserting print statements in between. The loops appear to work fine, as 'x' and 'y' print all the values they are supposed to. However, I get an empty list as an output to the print list command and 'z' does not apparently change values and is stuck at 100000 despite me using while loops to change the values of x and y.

I am at a loss on how to proceed from here.

Answer 1

The error you got was probably:

UnboundLocalError: local variable 'z' referenced before assignment

This means that z was not defined, at least not within the palindrome() function. Your solution of adding the global keyword is technically correct. However, as others have pointed out already, use of globals makes the code hard to follow.

It's not clear to me what palindrome() is supposed to do. Is it supposed to check if a number is a palindrome? Generate palindrome numbers? To fix this problem, you should think about structuring your code. There are many ways to do this, of course, and with time you will find your own style.

My advice, then, is to think about how you would solve this in general. If you don't know the solution, coding won't help you. Sometimes, when solving problems like this one, I write functions without declaring their bodies. You can do this top-down or bottom-up, both work. For example:

def is_palindrome(n):
    """ Check if n is a palindrome number. """
    pass

def multiples_of_3_digits():
    """ Return all numbers that are the product of two 3-digit numbers ."""
    pass

def main():
    print max(n for n in multiples_of_3_digits() if is_palindrome(n))

This way you can focus on solving the problem, then on the actual coding. Maybe you will add helper functions or realize you can solve the problem in a more efficient way, but it's a start. Good luck!

Answer 2

min=100
max=999
max_palindrome = 0
for a in range(min,max + 1):
    for b in range(a + 1, max + 1):
        prod = a*b
        if prod > max_palindrome and str(prod)==(str(prod)[::-1]):
            max_palindrome = prod
print max_palindrome

Here we are only concerned with the maximum palindrome, and so we don’t spend any time storing other palindromes once they are known to be non-maximum. Also, the if statement first checks if the given product is larger than the maximum known palindrome before using the string cast and list slice to check whether or not the number is even a palindrome. This should speed up our code a bit since the greater than comparison will often fail, regardless of whether the product in question is a palindrome. When we run this, we get the following.

906609

Alternate Way:

I would discourage you to use the global variables because of the reasons pointed out by others. I would also like you to refer to Andre's approach as it will teach you to organize yourself. In this approach too I will be using 2 functions is_palindrome(num) [to check if the number is palindrome or not] and find_max_palindrome [to find the largest palindrome]

def is_palindrome(num):
    reversed = 0
    original = num

    if num < 10:
        return True
    if num % 10 == 0:
        return False

    while num >= 1:
        reversed = (reversed * 10) + (num % 10)
        num = num/10

    if original == reversed:
        return True
    else:
        return False

def find_max_palindrome():
    max_palindrome = 0
    a = 999
    b = 999
    prod = 0

    while a > 99:
        b = 999
        while b >= a:
            prod = a*b
            if prod > max_palindrome and is_palindrome(prod):
                max_palindrome = prod
            b = b -1
        a = a - 1

    return max_palindrome

print find_max_palindrome()