Solution for puzzle 3d x 1d = 2d x 2d in Python

I wanted to resolve the puzzle from this link using Python 3. It works and gives me the correct value but I would like to know if it is possible to resolve this problem with a few lines or how I can improve/optimize my code.

import time
start = time.time()
max=0
gx=0
gy=0
gi=0
gj=0

for i in range(999,99,-1):
    for j in range(9,0,-1):
        mul=i*j

        for x in range(99,9,-1):
            for y in range(99,9,-1):
                mul2=x*y

                if mul==mul2:
                    if mul>max:
                        gx=x
                        gy=y
                        gi=i
                        gj=j
                        max=mul

print ("i: " + str(gi))
print ("j: " + str(gj))
print ("x: " + str(gx))
print ("y: " + str(gy))
print ("max: " + str(max))                      
end = time.time()
print (end - start)

And this is the result:

i: 992
j: 9
x: 96
y: 93
max: 8928
17.678768157958984

Style

Python has a style guide called PEP8. It is definitly worth a read. Among the few things you could do to make your code more pythonic : spacing around operators. Also, you should try to avoid giving your variables the same name as builtins. Furthermore, you can assign all variables in one go if it corresponds to a single logical operation (as in "saving the best result found so far"). Finally, you can remove explicit conversion when printing :

import time
start = time.time()
maxi, gx, gy, gi, gj = 0, 0, 0, 0, 0

for i in range(999, 99, -1):
    for j in range(9, 0, -1):
        mul = i * j

        for x in range(99, 9, -1):
            for y in range(99, 9, -1):
                mul2 = x*y

                if mul == mul2:
                    if mul > maxi:
                        maxi, gx, gy, gi, gj = mul, x, y, i, j

print("i: ", gi)
print("j: ", gj)
print("x: ", gx)
print("y: ", gy)
print("max: ", maxi)
end = time.time()
print(end - start

Algorithm

For each i, j, it only makes sense to check if it can be written under the form _ _ * _ _ if it is bigger than the current best value.

for i in range(999, 99, -1):
    for j in range(9, 0, -1):
        mul = i * j

        if mul > maxi:
            for x in range(99, 9, -1):
                for y in range(99, 9, -1):
                    mul2 = x*y
                    if mul == mul2:
                            maxi, gx, gy, gi, gj = mul, x, y, i, j

This makes your code go roughly 500 times faster.

From this point, it is hard to make things actually faster but let's try.

Once you have mul, to find 2 divisors under of 2 digits, you don't need have two loops : one is enough and then you check if the number actually divides mul and if the result has 2 digits.

if mul > maxi:
        for x in range(99, 9, -1):
            y, r = divmod(mul, x)
            if r == 0 and 10 <= y < 100:
                axi, gx, gy, gi, gj = mul, x, y, i, j

Once you have it, you can break because it will only find the same solution.

if mul > maxi:
        for x in range(99, 9, -1):
            y, r = divmod(mul, x)
            if r == 0 and 10 <= y < 100:
                maxi, gx, gy, gi, gj = mul, x, y, i, j
                break

Similarly, you can break out of the j loop when mul <= maxi because mul goes decreasing.

for i in range(999, 99, -1):
    for j in range(9, 0, -1):
        mul = i * j

        if mul <= maxi:
            break
        else:
            for x in range(99, 9, -1):
                y, r = divmod(mul, x)
                if r == 0 and 10 <= y < 100:
                    maxi, gx, gy, gi, gj = mul, x, y, i, j
                    break

Also, in the x loop, it doesn't make sense anymore to do backward.

for i in range(999, 99, -1):
    for j in range(9, 0, -1):
        mul = i * j
        if mul <= maxi:
            break
        else:
            for x in range(10, 100):
                y, r = divmod(mul, x)
                if r == 0 and 10 <= y < 100:
                    maxi, gx, gy, gi, gj = mul, x, y, i, j
                    print(maxi)
                    break

This seems to be roughly 10 000 times faster than it used to be.

StackExchange Code Review Q#79092, answer score: 4