Geek Answers Handbook

Using combinatorics in Python to enumerate four-digit passwords

I came across this interesting article about why using 3 unique numbers for a 4-digit access code is the safest: (LINK)

The math used is pretty simple - if you need to guess the phone 4-digit access code based on the spots remaining on the screen, then:

4 spots indicate that the password has 4 unique numbers. Since each of them must be used at least once, we have 4! = 24possible passwords.

With 3 different numbers, the access code becomes a bit more secure. Since there are three spots, one number is repeated, but we do not know which one. Thus, given the multiplicity, we get the (4!/2!) x 3 = 36possible passwords.

Similarly, with 2 different numbers, we get 14 possible codes.

My question is: is there a way to β€œprove” above in Python? A way to justify that 3 numbers gives the most secure access code with a Python code, maybe something that lists all the possible access codes if you give it some numbers? I thought about using itertools, with itertools.permutationsas a starting point, but then I discovered that Python has a combinatorial module that can be much more elegant. Would someone be kind to show me how to use it? I am reading the documentation right now, but some syntax eludes me.

+4
source share
2

combinatorics, . ,

def guess(smudged_numbers):
    from itertools import product
    num_smudges = len(smudged_numbers)
    for raw in product(smudged_numbers, repeat=4):
        if len(set(raw)) == num_smudges:
            yield raw

count = 0
for nums in guess([1, 8]):
    print nums
    count += 1
print "total", count

:

(1, 1, 1, 8)
(1, 1, 8, 1)
(1, 1, 8, 8)
(1, 8, 1, 1)
(1, 8, 1, 8)
(1, 8, 8, 1)
(1, 8, 8, 8)
(8, 1, 1, 1)
(8, 1, 1, 8)
(8, 1, 8, 1)
(8, 1, 8, 8)
(8, 8, 1, 1)
(8, 8, 1, 8)
(8, 8, 8, 1)
total 14

(len(num_smudges)**4, , , 4 ** 4 = 256), , -)

: (product) 4-tuples (repeat=4), . , [1, 8] 2 ** 4 = len(smudged_numbers)**4= 16 4-, 1 8.

set , (len) 4-. , . , . [1, 8] 2 16 4-: (1, 1, 1, 1) (8, 8, 8, 8).

+4

permutations itertools.

shuffle random, . ( , , ?) , shuffle(codes_to_try).

from itertools import combinations, permutations
from random import randint, shuffle

def crack_the_code(smudges, actual_code):
    """ Takes a list of digit strings (smudges) & generates all possible
    permutations of it (4 digits long). It then compares the actual given
    code & returns the index of it in the generated list, which basically
    becomes the number of tries.
    """
    attempts_to_crack = 0
    no_smudges = len(smudges)

    if no_smudges == 3:
        all_codes = ["".join(digits)
                     for repeated_num in smudges
                     for digits in permutations([repeated_num]+smudges)
                     ]
        all_codes = list(set(all_codes)) # remove duplicates
    elif no_smudges == 4:
        all_codes = ["".join(digits)
                     for digits in permutations(smudges)
                     ]
    else:
        print "Smudges aren't 3 or 4"
        raise ValueError

    shuffle(all_codes)
    return all_codes.index(actual_code)

print crack_the_code(["1","2","3"],"1232")
# above prints random values between 0 & 35 inclusive.

. , int, str. PS - , , .

+1

More articles:


All Articles