What is the Entropy of Android's Dot Password System?

Question

How many permutations of the androids dot login system are possible? I know for a fact the solution to this lies in Discrete Math, specifically Permutations Without Repetition, If your answer doesn't use permutations or combinations you are incorrect.

The length of passwords is between 4 and 9 dots, There are a total of 9 dots to permute though. so my initial equation is:

9P4+9P5+9P6+9P7+9P8+9P9 

However, I know this equation is incomplete because it does not take into consideration all of the rules. Each dot is distinct because of is position so if you assign a number to each dot as follows:

123 456 789 

The password "1397" is impossible, if you attempt to use this password you will in fact have entered in "1236987" because the numbers in-between are automatically selected. Another equation needs to be created to account for these limitations and then subtract off from my nPr equation above.

This link has a great video of someone using the android login. It also goes into greater detail into the rules. The math on that page is completely incorrect, he is not even close to a real solution.

Answer 1

This is only a partial answer. The only relevant starting dots are 1, 2, and 5. For dots 1 and 2, you can generate a pattern equivalent to starting at any of the other dots (other than 5) with a simple rotation transformation. This means if you can enumerate all the patterns starting at 1 and 2 you can count all the patterns starting at any number other than 5 by multiplying by 4.

The paths starting at 5 are a different case. You can count all of them by counting all the paths that start with 5->1 and 5->2 and multiplying by 4 since you again can generate all the other possible paths with a simple rotation transformation.

So, a way to enumerate the paths would be...

(All paths starting at 1 + all paths starting at 2 + all paths starting with 5->1 + all paths starting with 5->2) * 4

Again, the numbering system, for easy reference:

1  2  3 4  5  6 7  8  9 

For this first move:

From 1 -> 2, 4, 5, 6 and 8 are accessible.

From 2 -> 1, 3, 4, 5, 6, 7, and 9 are accessible (basically just not 8 or itself).

From 5 -> 1, 2, 3, 4, 6, 7, 8, and 9 are accessible.

For moves after that it gets really interesting.

For example, 1537 is a valid password. 1539 is not.

Here succinctly, are the rules:

No dot may be part of the path twice. If a dot is not part of the path and it is exactly crossed over by a transition, it becomes part of the path between the source dot and destination dot.

Here are some sample paths:

• 2->3->1->8 is allowed.
• 1->3->2->5 is not allowed because 2 is not part of the path when 1->3 goes exactly over 2, so the path becomes 1->2->3->5 whether you want it to or not.
• 1->2->3->7 is not allowed because 3->7 crosses over 5 and 5 is not already part of the path.
• 1->5->3->7 is allowed. 5 is ignored in 3->7 because it is already part of the path.

This program:

class LockPattern(object):     def __init__(self, *args):         if (len(args) == 1) and hasattr(args[0], '__iter__'):             args = tuple(args[0])         if len(args) > 9:             raise TypeError("A LockPattern may have at most 9 elements.")         self._pattern = ()         for move in args:             if not self.isValidNextStep(move):                 raise TypeError("%r is not a valid lock sequence." % (args,))             else:                 self._pattern = self._pattern + (move,)     def __len__(self):         return len(self._pattern)     def __iter__(self):         return iter(self._pattern)     def isValidNextStep(self, nextdot):         nextdot = int(nextdot)         if (nextdot < 1) or (nextdot > 9):             raise ValueError("A lock sequence may only contain values from 1 "                              "to 9 and %d isn't." % (nextdot,))         if len(self._pattern) <= 0:             return True # Any dot is valid for the first dot         if len(self._pattern) >= 9:             return False         if nextdot in self._pattern:             return False # No dot may be visited twice         prevdot = self._pattern[-1]         dotpair = tuple(sorted((prevdot, nextdot)))         if dotpair == (1,3):             return 2 in self._pattern         if dotpair == (1,7):             return 4 in self._pattern         if dotpair in ((1,9),(2,8),(3,7),(4,6)):             return 5 in self._pattern         if dotpair == (3,9):             return 6 in self._pattern         if dotpair == (7,9):             return 8 in self._pattern         return True     def isValidLockSequence(self):         return 4 <= len(self)     def newSequenceAddDot(self, nextdot):         if not self.isValidNextStep(nextdot):             raise ValueError("%d is not a valid next dot for the sequence." % (nextdot,))         newseq = LockPattern()         newseq._pattern = self._pattern + (nextdot,)         return newseq  def genAllPatterns(starting = LockPattern()):     if starting.isValidLockSequence():         yield starting     for dot in xrange(1,10):         if starting.isValidNextStep(dot):             for result in genAllPatterns(starting.newSequenceAddDot(dot)):                 yield result  print reduce(lambda x, p: x+1, genAllPatterns(), 0) 

Generates an answer of 389112.

It also validates my previous intuitions:

lsts = tuple(((p, list(genAllPatterns(LockPattern(p)))) for p in ((1,), (2,), (5,1), (5,2)))) [(x[0], len(x[1])) for x in lsts] -> [((1,), 38042), ((2,), 43176), ((5, 1), 7352), ((5, 2), 8708)] sum((len(x[1]) for x in lsts) -> 97278 97278 * 4 -> 389112 

Answer 2

The key is to notice that once you have visited any two dots, you can reach any other dot that you desire without moving through any dot that you have not already visited. So once you pick two starting dots (in order), then you can choose the rest of your password at will, in any order you wish. (This is because "knight's moves" are allowed, at least according to the page you linked)

So, excluding the 'starting two' dots, the number of remaining 2-7 digit tails are 7P2 + 7P3 + 7P4 + 7P5 + 7P6 + 7P7. There are 56 potential starting two-digit heads because there are 5 moves you can make from any corner dot, 7 from any edge dot, and 8 from the center dot. So the total number of unlocking patterns would be 56 * (7P2 + 7P3 + 7P4 + 7P5 + 7P6 + 7P7) = 766 752.

If this is wrong, it's probably because I am missing some knowledge of the rules of this system.