Какова Энтропия Точечной Системы Пароля Android?

Это только частичный ответ. Единственными соответствующими стартовыми точками являются 1, 2 и 5. Для точек 1 и 2 можно сгенерировать шаблон, эквивалентный началу с любой из других точек (кроме 5) с помощью простого поворотного преобразования. Это означает, что если можно перечислить все детали, начинающиеся с 1 и 2, то можно считать все детали, начинающиеся с любого числа, кроме 5, умножив их на 4.

Траектории, начинающиеся с 5 - это другой случай. Вы можете считать их все, считая все пути, которые начинаются с 5->1 и 5->2 и умножаются на 4, так как можно сгенерировать все остальные возможные пути простым вращением с помощью трансформации.

Таким образом, способ перечислить пути будет...

(Все пути, начинающиеся с 1 + все пути, начинающиеся с 2 + все пути, начинающиеся с 5->1 + все пути, начинающиеся с 5->2) * 4

Опять же, система нумерации, для удобства:

1  2  3
4  5  6
7  8  9

Для этого первого хода:

От 1 -> 2, 4, 5, 6 и 8 доступны.

Из 2 -> 1, 3, 4, 5, 6, 7 и 9 доступны (в основном просто не 8 или сам по себе).

Из 5 -> 1, 2, 3, 4, 6, 7, 8 и 9 доступны.

Для ходов после этого становится действительно интересно.

Например, 1537 - действующий пароль. 1539 - нет.

Здесь кратко изложены правила:

Ни одна точка не может быть частью пути дважды. Если точка не является частью пути и точно пересекается переходом, она становится частью пути между точкой источника и точкой назначения.

Вот несколько примеров путей:

• 2->3->1->8 допускается.
• 1->3->2->5 не разрешен, потому что 2 не является частью пути, когда 1->3 проходит точно через 2, поэтому путь становится 1->2->3->5 независимо от того, хотите вы этого или нет.
• 1->2->3->7 не разрешено, потому что 3->7 пересекается с 5 и 5 еще не является частью пути.
• 1->5->3->7 разрешено. 5 игнорируется в 3->7, потому что он уже является частью пути.

Эта программа:

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)

Генерирует ответ 389112.

Она также подтверждает мои предыдущие интуиции:

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