Python- Nested for loops not working as expected

Question

I'm fairly new to Python and trying out the Project Euler challenges. I'm currently having trouble getting a nested for loop to work properly. My code looks like this:

def palindrome():
    for i in range(999,317,-1):
        for a in range(999,317,-1):
            s = str(i*a)
            if s[0] == s[5] and s[1] == s[4] and s[2] == s[3]:
               return(s)
print(palindrome())

The point of the program is to find the largest possible palindrome that is the product of two three digit numbers. When I run this program, I consistently get the answer 580085. It is a palindrome, but I know it's the wrong answer.

Concrete Questions:

Am I using/nesting for loops improperly in some way?
Is there a way to search for palindromes without using the two loops?

your second for loop could be changed to for a in range(i,317,-1): and instead of returning you could add all the palindromes to a list and get the largest after both for loops — depperm
– depperm, Commented Dec 22, 2016 at 19:52
@depperm better store one largest palindrome and if larger found change to the new one. — Yevhen Kuzmovych
– Yevhen Kuzmovych, Commented Dec 22, 2016 at 19:53
def isPalindrome(number): return True if str(number) == ''.join(reversed(str(number))) else False — Shijo
– Shijo, Commented Dec 22, 2016 at 19:59
@depperm I rewrote the program to append to a list. It now creates a list of palindromes with 580085 being the first value. Two questions: 1. Why did my original code stop after finding the first value? and also, 2. Why does it seem as thought the results are in a random order? — Luke
– Luke, Commented Dec 22, 2016 at 20:02
it stopped after finding the first value because you were returning the value right away. The random order is because of the range you are using, I'd look at the answers below which have good examples and explanations on how to do what you want — depperm
– depperm, Commented Dec 22, 2016 at 20:03

Yevhen Kuzmovych · Accepted Answer · 2016-12-22 19:59:33Z

4

Try this:

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

or more readable way:

def palindrome():
     largest = 0
     for i in range(999, 317, -1):
         for j in range(i, 317, -1):
             if str(i*j) == str(i*j)[::-1] and i*j > largest:
                 largest = i*j
     return largest

answered Dec 22, 2016 at 19:59

Yevhen Kuzmovych

12.3k8 gold badges32 silver badges54 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Will · Accepted Answer · 2016-12-22 20:05:16Z

4

You're pretty close. Your code is returning the first palindrome it finds, you want to find all palindromes, and only return the largest one. Try something like:

def palindrome():
    largest = 0
    for i in range(999,317,-1):
        for a in range(999,317,-1):
            s = str(i*a)
            if s[0] == s[5] and s[1] == s[4] and s[2] == s[3]:
               if int(s) > largest:
                   largest = int(s)  # <-- don't return, just set s aside and keep checking
    return largest

edited Dec 22, 2016 at 20:05

answered Dec 22, 2016 at 20:00

Will

4,4696 gold badges35 silver badges52 bronze badges

3 Comments

depperm Over a year ago

changing 999 to i in the second for loop would make this algorithm slightly faster by not checking the same product twice

Luke Over a year ago

Thanks so much! Sorry I can't upvote yet. Would I be correct in saying the mistake was placing the return inside the for loop?

Will Over a year ago

@LukeWeller Yes, and it's a pretty common mistake to return when only half the criteria are met. Declaring a variable to return right at the beginning of a function and assigning to it can sometimes help me remember not to return until all loops are complete.

Prune · Accepted Answer · 2016-12-22 20:01:10Z

That's the first palindrome you found; it's not the largest you'll find. The loops work as documented: at first, i=999, and you'll work your way from 999*999 down to 999*317. Then you'll go back to the outer loop, set i=998, and start over from a=999. Note that your first unique product, 998*998, is significantly larger than two iterations earlier, 999*317.

One way to solve this is to save the largest palindrome you've found so far, and only print the result when you've gone through them all ... or stop early when k*k < largest.

Another way is to change your looping parameters so that you work from the largest products on down.

elldur · Accepted Answer · 2016-12-22 20:03:37Z

At the moment your code terminates at the FIRST palindrome it finds, For example it might terminate at 999*400. However a larger palindrome might be found at 900 * 800 for example (theses values wont but you get the idea).

To fix this you can do this:

def palindrome(x, y):
    lis = [] # Contains the palindromes
    for i in range(x,317,-1):
        for a in range(y,317,-1):
            s = str(i*a)
            if s[0] == s[5] and s[1] == s[4] and s[2] == s[3]:
               lis.append(i*a)

    # Finding largest palindrome
    largest = 0
    for i in range(0, len(lis)):
        if lis[i] > largest:
            largest = lis[i]
    return largest

print(palindrome(999, 999))

This returns the value: 906609 Not only that but you can modify this code to give you the list of all the palindromes it can find.

Collectives™ on Stack Overflow

Python- Nested for loops not working as expected

4 Answers 4

Comments

3 Comments

Comments

Comments

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

Comments

3 Comments

Comments

Comments

Related