1

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.

Improve this question
6
  • 2
    As your code works but you're asking for help improving it, it might be a better fit for Code Review Commented Jul 14, 2022 at 16:39
  • 1
    Would be easier to just iterate over all permutations of the digits 0-9 without 3 and then split them to ABCD and EFGHI Commented Jul 14, 2022 at 16:41
  • What exactly is the code ultimately doing...? Commented Jul 14, 2022 at 16:42
  • You definitely want to use an array here instead of different variables Commented Jul 14, 2022 at 16:44
  • 2
    for a,b,c,d,e,f,g,h,i in itertools.permutations((0,1,2,4,5,6,7,8,9)): could replace all the for loops. Commented Jul 14, 2022 at 16:49

2 Answers 2

Reset to default
6

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

5 Comments

Nice! didn't think the difference will be so big, and I wasn't thinking that the set check is that simple... But why do you do the permutation of the combinations? I couldn't figure that out. Wouldn't work with a simple for perm in permutations("012456789", 4)?
BTW, on closer inspection this is not entirely correct. Converting to set, some digits could be repeated. This is not a problem here, as 4 digits x3 can not produce a 6 digit number, but to be correct you could also compare the combined sorted digits.
@Tomerikoo Thanks for pointing this out, I completely forgot permutations had that parameter!
Did you check the timing again? I would assume that the remove of redundant combinations will improve even more!
@Tomerikoo There were no redundant combinations, since all the digits were unique in the first place. It's just a lot cleaner. The inner loop (before the if) is executed 3024 times either way (as opposed to 362880 times with all permutations).
2

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)
Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.