# 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.