Что такое Entropy Android Dot Password System?

Ответ 1

Это лишь частичный ответ. Единственными актуальными стартовыми точками являются 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

Ответ 2

Ключ должен заметить, что после того, как вы посетили любые две точки, вы можете достичь любой другой точки, которую вы желаете, не перемещаясь по какой-либо точке, которую вы еще не посетили. Поэтому, как только вы выбираете две стартовые точки (по порядку), вы можете выбрать остальную часть своего пароля по своему желанию в любом порядке. (Это связано с тем, что "рыцарские ходы" разрешены, по крайней мере, согласно странице, которую вы связали)

Таким образом, исключая "стартовые две" точки, количество оставшихся 2-7-значных символов равно 7P2 + 7P3 + 7P4 + 7P5 + 7P6 + 7P7. Есть 56 потенциальных стартовых двузначных головок, потому что есть 5 ходов, которые вы можете сделать из любой угловой точки, 7 из любой граничной точки и 8 из центральной точки. Таким образом, общее количество шаблонов разблокировки будет 56 * (7P2 + 7P3 + 7P4 + 7P5 + 7P6 + 7P7) = 766 752.

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

Ответ 3

Хорошо, так что сначала позвольте мне начать с того, чтобы сказать, что всезнающий кажется правильным. Что мы можем сделать с математикой. Я согласен с ним, когда он скажет, что действительно есть только 3 случая. 1,2 и 5.

OP хочет какую-то элегантную формулу подсчета, которая, как я сомневаюсь, существует для такой проблемы. Когда вы используете все 9 точек, вы находите гамильтоновские пути, которые, если бы это был полный график, очень легко подсчитать (это не так). Поскольку каждый из трех случаев уникален, вы собираетесь перечислить все из них, чтобы найти общее количество путей.

Посмотрим на первый случай, начиная с угла. У вас есть четыре варианта для угла, тогда у вас есть 5 вариантов для следующего квадрата. Теперь вы быстро увидите, что наша формула расширяется довольно быстро, потому что у нас есть 5 вариантов, и мы должны разделить эти 5 вариантов на 2 набора.

Перемещение на средний квадрат, будет иметь одинаковые варианты, независимо от того, к какой из них вы переходите. В отличие от перехода на 5, что даст нам еще много вариантов, уже наша формула:

4 * (4 * (6) + 1 * (7))

Затем мы должны разбить 6 и 7 вариантов на другие группы. Если мы перейдем к боковому квадрату, то теперь мы можем перейти на два боковых квадрата, три угла и один средний квадрат. Тогда наша формула будет следующей:

4 * (4 * (2 * (5) + 3 * (3) + 1 * (7)) + 1 * (7))

Тогда мы должны начать решение, если бы мы перешли на средний квадрат, и я остановлюсь здесь. Поиск гамильтоновых путей является NP-полным, хотя мы просто подсчитываем их. Но здесь нет никаких свойств, которые мы можем использовать для элегантного решения. Это проблема теории графов, и она включает в себя грубое принуждение решения, как это было ранее сделано Omnifarious.

Я попытаюсь объяснить, почему вы интуитивно ошибаетесь, вы говорите, что:

"Я знаю, что решение этого кроется в Discrete Math, в частности, Permutations Without Repetition. Если ваш ответ не использует перестановки или комбинации, вы ошибаетесь".

К сожалению, вы этого не знаете, потому что вы не знаете формулы (если вы не можете показать мне строгое неконструктивное доказательство). Дело в том, что перестановка или комбинация означает, что когда у вас есть n элементов, вы можете выбрать любой элемент на любой итерации. Теперь вы можете установить ограничения на количество элементов, которые вы можете выбрать, и на какие предметы вы можете выбрать на определенных итерациях. Но то, что вы не можете сделать и ожидаете элегантного решения, - это выбор определенных предметов, влияющих на то, какие предметы вы можете выбрать дальше. Это именно то, что делает этот вопрос, и почему нет какой-либо хорошей формулы, использующей комбинации и перестановки.

Короче формула, которую вы ищете, не существует, но Omnifarious нашел правильный ответ.

Ответ 4

Omnifarious был определенно точным в своем размещении - есть 389 112 комбинаций. Я опубликовал ОГРОМНУЮ вещь о всем процессе определения этого алгоритма, а также текстовый файл, в котором перечислены все отдельные комбо из длины 1-9 (что, по-видимому, возможно, из того, что я мог рассказать на телефоне моей подруги). Ссылка на этот контент такова: http://bit.ly/hEHcBJ

Ответ 5

Я не знаю, все ли по-прежнему заботятся, но это проблема подсчета пути в графе. Есть 9 узлов, поэтому создайте матрицу 9 x 9 (каждая строка имеет значение от node, каждый столбец a до node). Если node n подключается к node m, установите (n, m) и (m, n) как 1. Сделайте это для всех подключений. Оставьте остальные ноль. Это называется матрицей смежности. Поднимите эту матрицу на число строк в шаблоне и добавьте все записи. Это число перестановок. Если кто-то заботится, я отправлю код python (на моем телефоне или я бы опубликовал его сейчас)

import numpy as np
paths = [[1,3,4],[2,3,4,5],[4,5],[4,6,7],[5,6,7,8],[7,8],[7],[8],[]]
m = [[0 for i in range(0,len(paths))] for j in range(0,len(paths))]

for i in range(0,len(paths)):
    for j in paths[i]:
        m[i][j] = 1
        m[j][i] = 1

for row in m:
    print row

[0, 1, 0, 1, 1, 0, 0, 0, 0]
[1, 0, 1, 1, 1, 1, 0, 0, 0]
[0, 1, 0, 0, 1, 1, 0, 0, 0]
[1, 1, 0, 0, 1, 0, 1, 1, 0]
[1, 1, 1, 1, 0, 1, 1, 1, 1]
[0, 1, 1, 0, 1, 0, 0, 1, 1]
[0, 0, 0, 1, 1, 0, 0, 1, 0]
[0, 0, 0, 1, 1, 1, 1, 0, 1]
[0, 0, 0, 0, 1, 1, 0, 1, 0]

adj = np.matrix(m)

adj.sum()
40

(adj**2).sum()
200

(adj**6).sum()
107648

Мои ответы не соответствуют тем, которые были даны другими людьми выше, поэтому я также написал симуляцию обхода графика для рассматриваемого графа. Ответы моделирования (из-за выхлопа) соответствуют ответам из расчета матрицы смежности. Я также разработал первые два (один край и два края) вручную и получил те же ответы (40 и 200). Обратите внимание, что я предполагаю, что вы можете повторно посетить одну и ту же вершину (например, 1- > 2- > 1- > 2...).

Мой график:

0 - 1 - 2
| X | X |
3 - 4 - 5
| X | X |
6 - 7 - 8

Ответ 6

edit: Нет, я ошибаюсь. График изменяется, потому что, в то время как в целом такие вещи, как 1 → 3, не разрешены (сначала вам нужно пройти через 2), вы можете делать такие вещи, как 2 → 5 → 1 → 3: 1 → 3 становится доступным, так как 2 уже используется в пути.

Я написал программу для учета этого и получил тот же 389,112, что и Omnifarious (и тогда я понял, что моя программа делает то же самое, что и его).

Мне стало интересно: я уверен, что это 139,880. Как сказал Джим, это может быть смоделировано графиком. Подведение матрицы смежности к мощности не работает, потому что оно подсчитывает пути с повторами, но вы можете просто BFS через график:

nodes = range(1, 10)

edges = {
    1: [2, 6, 5, 8, 4],
    2: [1, 4, 7, 5, 9, 6, 3],
    3: [2, 4, 5, 8, 6],
    4: [1, 2, 3, 5, 9, 8, 7],
    5: [1, 2, 3, 4, 6, 7, 8, 9],
    6: [3, 2, 1, 5, 7, 8, 9],
    7: [4, 2, 5, 6, 8],
    8: [7, 4, 1, 5, 3, 6, 9],
    9: [8, 4, 5, 2, 6],
}

def num_paths(length):
    q = deque([node] for node in nodes)
    paths = []
    while q:
        path = q.popleft()
        if len(path) == length:
            paths.append(path)
            continue
        for node in edges[path[-1]]:
            if node not in path:
                q.append(path + [node])
    return len(paths)

А затем просто добавьте количество путей длиной 4, 5, 6, 7, 8 и 9.

>>> sum(num_paths(i) for i in range(4, 10))
139880