CODEWITHSUNDEEP
python
jolrael
jolrael

Reputation: 46

Simplify multiple nested loop

for a math riddle i wrote that python program to bruteforce the solutions. ABCD * 3 = EFGHI with each ABCDEFGHI different from each other (and 3 of course).

#   Game looking like : ****
#                       X   3
#                     = *****
# with each * diferent from others and is in interval [0-9] except 3 (as the last * being imposed)


import time
t1 = time.time()
occurence = 0
for a in range(0,10):
    if a == 3 : continue    
    tn = time.time()
    delta = tn - t1
    # each number should be different so a,b,c,d,e,f,g,h,i are
    # each one and unique number in [0-9] excluding 3    
    for b in range(0,10):
        if a == b or b == 3 : continue
        
        for c in range(0,10):
            if a == c or b ==c or c == 3 : continue
            for d in range(0,10):
                if d==a or d==b or d==c or d == 3 : continue
                for e in range(0,10):
                    if e==a or e==b or e==c or e==d or e == 3: continue
                    for f in range(0,10):
                        if f ==a or f==b or f==c or f==d or f==e or f == 3: continue
                        for g in range(0,10):
                            if g ==a or g==b or g==c or g==d or g==e or g==f or g == 3: continue
                            for h in range(0,10):
                                if h ==a or h==b or h==c or h==d or h==e or h==f or h==g or h == 3: continue
                                for i in range(0,10):
                                    if i == a or i==b or i==c or i==d or i==e or i==f or i==g or i==h  or i == 3: continue
                                    first = 1000*a + 100*b + 10*c + d
                                    result = 10000*e + 1000*f + 100*g + 10*h + i
                                    if (first *3 == result):
                                        #on a un gagnant
                                        occurence +=1
                                        print(first, "* 3 =", result)
                                        t2 = time.time()
print(occurence, "positiv results")
print(t2-t1, "seconds")

I'm pretty sure this code could have been way lighter using list and that's why i post today.

Upvotes: 1

Views: 129

Answers (2)

tobias_k
tobias_k

Reputation: 82899

Besides using permutations, you do not need to test all the permutations for all the nine digits at all. Instead, get all combinations for the first four digits, then the permutations of those (or, as pointed out in comments, use permutations with optional r parameter), and check if that together with 3x that number is a permutation of all the allowed digits.

from itertools import permutations

digits = list("012456789")
for perm in permutations(digits, r=4):
    first = int(''.join(perm))
    second = first * 3
    if sorted(f"{first}{second}") == digits:
        print(f"{first} * 3 = {second}")

(Edit: Using permutations with r=4 and sorted instead of set to check for duplicate digits, although that should not be an issue here.)

For me, this reduces the running time from ~1.06 seconds (your original code) or 0.21 seconds (using permutations, but all) down to 0.007 seconds.

Upvotes: 6

Tomerikoo
Tomerikoo

Reputation: 19414

Create all permutations of the 9 numbers, split them to your two operands and check the condition:

from itertools import permutations

digits = "012456789"

for perm in permutations(digits):
    abcd = int(''.join(perm[:4]))
    efghi = int(''.join(perm[4:]))
    if abcd * 3 == efghi:
        print(abcd, efghi)

Upvotes: 2

Related Questions