CODEWITHSUNDEEP
python
Luke
Luke

Reputation: 87

Python- Nested for loops not working as expected

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:

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

Upvotes: 2

Views: 1884

Answers (4)

Will
Will

Reputation: 4469

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

Upvotes: 4

elldur
elldur

Reputation: 2103

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.

Upvotes: 2

Prune
Prune

Reputation: 77847

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.

Upvotes: 2

Yevhen Kuzmovych
Yevhen Kuzmovych

Reputation: 12140

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

Upvotes: 4

Related Questions