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

Question

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

Answer 1

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.