Why does this simple Python script reveal the incorrect answer?

Question

I'm again working on Project Euler, this time problem #4. The point of this script is to find the largest palindromic product of two three digit numbers. I thought it was fairly straightforward to solve, but I'm getting an answer that is too low. More specifically, I am getting 580085, and the answer is 906609.

Could someone tell me what about this is incorrect?

#!/usr/bin/env python
# encoding: utf-8
"""
P4.py

Created by Andrew Levenson on 2010-06-29.
Copyright (c) 2010 __MyCompanyName__. All rights reserved.
"""

import sys
import os


def main():
    for x in range(100, 1000):
        for y in range(100, 1000):
            z = str( x * y )
            s = str( z[::-1] ) # Reverse z
            if z == s:
                t = z
    print t


if __name__ == '__main__':
    main()

Answer 1

Your code doesn't make sure it prints the largest product, since there could later be a smaller product which replaces it. To fix it, initialize t to zero, and replace your condition with

if z==s and int(z)>t:
    t = int(z)

Or equivalently,

if z==s:
    t = max(t,int(z))

Edit: Fixed int/string issues above. It's a bit cleaner to avoid the conversion to string and back to int like this though:

def isPalindrome(x):
    s = str(x)
    return s == s[::-1]

t = 0
for x in range(100, 1000):
    for y in range(100, 1000):
        z = x * y
        if isPalindrome(z) and z > t:
            t = z
print t

Answer 2

The problem is to find the largest palindrome. You have nothing here to find the largest, simply the last. You assumed the last one would be the largest, but that isn't so because you are examining the entire ZxZ square of possibilities.

For example, you are considering 200*101 after you've considered 101*999.

Answer 3

You need to add a check if the one you found is larger than the one you already have.

Answer 4

Because of the way you're using the 2 for loops you're going to get the number with the largest x value, not the largest product.

906609 = 993 * 913

Then x keeps incrementing and the next palindrome is:

580085 = 995 * 583

You need a variable to keep track of the largest palindrome you've found.

def main():
    largest = 0
    for x in range(100, 1000):
        for y in range(100, 1000):
            z = str( x * y )
            s = str( z[::-1] ) # Reverse z
            if z == s:
                t = int(z)
                if t > largest:
                    largest = t
    print largest

Answer 5

Here's a tricky but correct way to do it in a single expression...:

def main():
  print max(p for x in range(100, 1000) for y in range(x, 1000)
              for p in (x * y,) if str(p) == str(p)[::-1])

The tricky part is the single-item for p clause which plays the role of an assignment (just to stop recomputing that product several times;-).

Note that the accepted answer is wrong (as are several others), because it looks for the string "max", which is different from the int max -- try running it, and you'll see!-)

Answer 6

I'll add that you can save yourself some time in this test. All 6 digit palindromes must be divisible by 11. Therefore at least one of the factors must be divisible by 11.