IndexError in Project Euler attempt

IndexError in Project Euler attempt - Printable Version

+- Python Forum (https://python-forum.io)
+-- Forum: Python Coding (https://python-forum.io/forum-7.html)
+--- Forum: General Coding Help (https://python-forum.io/forum-8.html)
+--- Thread: IndexError in Project Euler attempt (/thread-28855.html)

IndexError in Project Euler attempt - CRISPRmetoopls - Aug-06-2020

Hi everyone!
I'm trying to familiarise myself with maths and CS, so I started doing these little Project Euler challenges.
This is the one I tried to code something to:

"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 get this error message when I try to run it:
"if str(a*b)[n]==str(a*b)[m]:
IndexError: string index out of range"
I realize that either n or m or both become bigger than they should when the program runs, but I'm not sure when/why that happens, since I reset both n and m if the inspected digits turn out not to be the same.

I've been stuck on this problem for days. I would greatly appreciate your help!

a=999
b=999
n=0
m=(len(str(a*b))-1)
while n!=len(str(a*b))-1:
    if str(a*b)[n]==str(a*b)[m]:
        n=n+1  
        m=m-1
    else:
        n=0
        m=(len(str(a*b))-1)
        if len(str(b))==3:
            b=b-1
        else:
            a=a-1
            b=999
    
print(a*b)
print(b)

RE: IndexError in Project Euler attempt - bowlofred - Aug-06-2020

You are subtracting from a and b occasionally. But the problem requires that they are both 3 digit numbers. How do you make sure that is always the case?

12 and 13 seem suspicious to me. It looks like you require b to be 3 digits before subtraction, but not afterward.

Your basic problem seems to be that you are changing a/b and n/m backwards. You're calculating n and m based on a and b. But then you change a or b afterward and hope that the n and m you calculated previously will still be correct. Eventually you hit a case where it isn't.

RE: IndexError in Project Euler attempt - deanhystad - Aug-06-2020

What a fun programming challenge. It is fun just coming up with a solution, but there are many different optimizations that can be tried adding additional challenge. I went from trying 810,000 combinations to 52,115 combinations to 6207 combinations to find the solution.

I think you should restart from scratch and the first thing you solve is to write a test that determines if a number is a palindrome. I wrote mine as a function. That way I could easily try different algorithms and measure how it affected execution time.

Once you get the palindrome test working you need to design an algorithm that tests all possible solutions and reports which combination of numbers produced the highest value palindrome. I am using a for loop. I know the range of three digit numbers so it is easy to specify the range of numbers over which I want to iterate. I don't think it makes much sense converting a number to a string just to count the number of digits. After I got a brute force solution that tests 810,000 combinations of numbers I found some optimizations that eventually reduced that to 6207. The big performance leaps came from analyzing the problem and reducing the range of number I needed to test.

RE: IndexError in Project Euler attempt - perfringo - Aug-10-2020

One approach could be to determine palindrome numbers starting from largest and test for 3-digits factors.

Observation:

- largest product of 3-digits factors is 999 * 999 = 998 001

Largest palindrome can be found by creating it from first three digits:

- 998 899 -> larger than 998 001
- 997 799 -> smaller than 998 001 -> largest palindrome number
- 996 699 -> second largest palindrome number
...
- 100 001 -> smallest 6-digit palindrome number

In Python code it can be something like this:

ceil = 998001
beginning = ceil // 1000         # first three numbers
end = int(str(beginning)[::-1])  # reversed first three numbers

while ceil < int(f'{beginning}{end}'):
    beginning -= 1

# beginning will equal 997 and max palindrome 997 799

Now we know max palindrome and can create descending 6-digit palindrome generator:

palindromes = (int(f'{i}{str(i)[::-1]}') for i in range(beginning, 99, -1))

Now we need to check for 3-digits factors of these palindromes and stop if we found first one.

If not found in range 100 001 .. 997 799 one can look in 5 digits range (100 x 100 = 10 000) using same principle to generate palindromes (just using first two numbers reversing):

five_digits = (int(f'{i}{str(i)[:2][::-1]}') for i in range(99999, 9999, -1))

EDIT: adding simple brute-force 3-digit factors check it will require 91 checks before match (using factorisation for checking probably more efficient):

def check_factors(num):
    for i in range(999, 99, -1):
        factor, reminder = divmod(num, i)
        if factor < 100:
            return False
        if factor < 1000 and reminder == 0:
            return True

for i, palindrome in enumerate(palindromes):
    if check_factors(palindrome):
        print(i, palindrome)
        break

# 91 906609 -> 993 * 913