3
\$\begingroup\$

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
\$\endgroup\$
4
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.