Using combinatorics in Python to list 4-digit passcodes

Question

I came across this interesting article about why using 3 unique numbers for a 4-digit passcode is the most secure: (LINK)

The math involved is pretty straightforward - if you have to guess a phone's 4-digit passcode based on the smudges left on the screen, then:

4 smudges indicates that there are 4 unique numbers in the passcode. Since each of them must be used at least once, then we have 4! = 24 possible passcodes.

With 3 distinct numbers, the passcode becomes a little more secure. Since there are three smudges, one number is repeated - but we don't know which one. So accounting for multiplicity, we get (4!/2!) x 3 = 36 possible passcodes.

Similarly, with 2 distinct numbers, we get 14 possible passcodes.

My question is, is there any way I can "prove" the above in Python? A way to justify that 3 numbers gives the most secure passcode, with Python code, probably something that lists out all possible passcodes if you give it some numbers? I was thinking about using itertools, with itertools.permutations as a starting point, but then I found that Python has a combinatorics module, which may be a far more elegant way. Would someone be kind enough to show me how to use it? I'm reading the documentation right now but some syntax is escaping me.

Answer 1

There is no combinatorics module in the standard distribution, but this is easy to do regardless. For example,

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

That prints:

(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

The search space is very small (len(num_smudges)**4, which as at most 4**4 = 256), so no point to doing anything fancier ;-)

How it works: it generates all possible (product) 4-tuples (repeat=4) containing the passed-in sequence of smudged numbers. So for [1, 8], it generates all 2**4 = len(smudged_numbers)**4 = 16 possibilities for a 4-tuple containing nothing but 1's and 8's.

Converting a raw possibility to a set then tells us how many (len) different numbers appear in the raw 4-tuple. We only want those containing all the smudged numbers. That's all there is to it. In the [1, 8] case, this step only weeds out 2 of the 16 raw 4-tuples: (1, 1, 1, 1) and (8, 8, 8, 8).

Answer 2

My try with the permutations method in the itertools module.

I have added the shuffle method from the random module to generate more random tries from normal crackers. (To try your luck you would never go serially would you?!) But, if you want the serial tries method, you can just remove the shuffle(codes_to_try) line.

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.

Note - You may play around with the function if you like int & not str. PS - I have kept the code self-explanatory, but you can always comment & ask something you don't understand.