Pytanie Co to jest Entropy systemu Dot Password systemu Android?


Ile permutacje systemu logowania Dot Dot są możliwe? Wiem, że rozwiązanie tego problemu polega w szczególności na dyskretnej matematyce Permutacje bez powtórzeń, Jeśli twoja odpowiedź nie używa permutacji lub kombinacji, jesteś niepoprawny.

Długość haseł wynosi od 4 do 9 punktów. Łącznie 9 kropek do zaimportowania. więc moje początkowe równanie to:

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

Wiem jednak, że to równanie jest niekompletne, ponieważ nie bierze pod uwagę wszystkich reguł. Każda kropka jest odrębna z powodu pozycji, więc jeśli przypiszesz numer do każdej kropki, wykonaj następujące czynności:

123
456
789

Hasło "1397" jest niemożliwe, jeśli spróbujesz użyć tego hasła, w rzeczywistości wprowadzisz "1236987", ponieważ liczby pośrednie są automatycznie wybierane. Należy utworzyć inne równanie, aby uwzględnić te ograniczenia, a następnie odejść od mojego równania nPr powyżej.

To połączyć ma świetny film o kimś, kto używa loginu android. Bardziej szczegółowo omawia zasady. Matematyka na tej stronie jest całkowicie błędna, nie jest nawet bliski prawdziwemu rozwiązaniu.


21
2018-01-22 21:27


pochodzenie


Uważam, że 1397 nie jest właściwie niemożliwy, po prostu bardzo podchwytliwy. - Omnifarious
Nie, po prostu próbowałem grać z własnym telefonem. To jest niemożliwe. Wybierze kropkę, nawet jeśli ostrożnie ją przejmiesz. - Omnifarious
Interesujący problem. Ponieważ nie mam telefonu z Androidem, jedno pytanie o zasady: możesz przejść przez już używaną kropkę, ale czy to ma wpływ na hasło? na przykład są 1254, 12514, 125124 i 125214 wszystkie uważane są za odrębne hasła, czy są one takie same (skoro wszystkie z nich trafiły 1254 po raz pierwszy w tej samej kolejności)? - Tyler McHenry
Nic nie wiem o systemie Android, ale to pytanie wydaje się takie fajne! : P - Alix Axel
Wydaje się to być pytaniem o projekt Eulera. Kocham to. - Emily


Odpowiedzi:


To tylko częściowa odpowiedź. Jedynymi odpowiednimi punktami początkowymi są 1, 2 i 5. Dla kropek 1 i 2 można wygenerować wzorzec równoważny rozpoczynaniu się od dowolnego innego punktu (innego niż 5) za pomocą prostej transformacji rotacji. Oznacza to, że jeśli możesz wyliczyć wszystkie wzorce zaczynające się od 1 i 2, możesz policzyć wszystkie wzorce rozpoczynające się od dowolnej liczby innej niż 5, mnożąc przez 4.

Ścieżki rozpoczynające się od 5 to inny przypadek. Możesz policzyć wszystkie, licząc wszystkie ścieżki zaczynające się od 5> 1 i 5-> 2 i mnożąc przez 4, ponieważ znowu możesz wygenerować wszystkie inne możliwe ścieżki dzięki prostej transformacji rotacji.

Tak więc sposobem na wyliczenie ścieżek byłoby ...

(Wszystkie ścieżki zaczynają się od 1 + wszystkie ścieżki zaczynające się od 2 + wszystkie ścieżki zaczynające się od 5> 1 + wszystkie ścieżki zaczynające się od 5> 2) * 4

Ponownie, system numerowania, dla łatwego odniesienia:

1  2  3
4  5  6
7  8  9

Do tego pierwszego ruchu:

Od 1 -> 2, 4, 5, 6 i 8 są dostępne.

Od 2 -> 1, 3, 4, 5, 6, 7 i 9 są dostępne (w zasadzie po prostu nie 8 lub siebie).

Od 5 -> 1, 2, 3, 4, 6, 7, 8 i 9 są dostępne.

Do ruchów po tym robi się naprawdę interesująco.

Na przykład 1537 jest prawidłowym hasłem. 1539 nie jest.

Tutaj zwięźle, są zasady:

Żadna kropka nie może być częścią ścieżki dwukrotnie. Jeśli kropka nie jest częścią ścieżki i jest dokładnie przekreślona przez przejście, staje się częścią ścieżki między kropką źródłową a kropką docelową.

Oto kilka przykładowych ścieżek:

  • 2-> 3-> 1-> 8 jest dozwolone.
  • 1-> 3-> 2-> 5 jest niedozwolone, ponieważ 2 nie jest częścią ścieżki, gdy 1-> 3 idzie dokładnie powyżej 2, więc ścieżka zmienia się w 1-> 2-> 3-> 5, czy chcesz albo nie.
  • 1-> 2-> 3-> 7 jest niedozwolone, ponieważ 3-> 7 krzyżyków powyżej 5 i 5 nie jest już częścią ścieżki.
  • 1-> 5-> 3-> 7 jest dozwolone. 5 jest ignorowane w 3-> 7, ponieważ jest już częścią ścieżki.

Ten 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)

Generuje odpowiedź 389112.

Potwierdza również moje wcześniejsze intuicje:

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

19
2018-01-22 21:53



wow koleś, dobra edycja. - rook


Kluczem do sukcesu jest zauważenie, że po odwiedzeniu dowolnych dwóch kropek, możesz dotrzeć do dowolnej innej kropki, której pragniesz, bez poruszania się po kropce, której jeszcze nie odwiedziłeś. Po wybraniu dwóch początkowych kropek (w kolejności) możesz dowolnie wybrać resztę swojego hasła w dowolnej kolejności. (Dzieje się tak, ponieważ "ruchy rycerskie" są dozwolone, przynajmniej według strony, którą połączyłeś)

Zatem, z wyłączeniem "początkowych dwóch" kropek, liczba pozostałych 2-7-cyfrowych ogonów wynosi 7P2 + 7P3 + 7P4 + 7P5 + 7P6 + 7P7. Istnieje 56 potencjalnych początkowych dwucyfrowych głowic, ponieważ można wykonać 5 ruchów z dowolnej kropki narożnej, 7 z dowolnej kropki krawędzi i 8 z środkowej kropki. Łączna liczba wzorów odblokowania wynosiłaby 56 * (7P2 + 7P3 + 7P4 + 7P5 + 7P6 + 7P7) = 766 752.

Jeśli jest źle, to prawdopodobnie dlatego, że brakuje mi wiedzy na temat zasad tego systemu.


3
2018-01-22 22:34



Myślę, że jesteś na dobrej drodze. Będę musiał poświęcić trochę czasu, aby zweryfikować to nieco lepiej. Czy ktoś inny może to zweryfikować? - rook
Jeśli odwiedzasz kropki 1 i 8, nie możesz odwiedzić kropki 2, więc Twoje założenie nie jest poprawne. Ponadto, jeśli odwiedzasz kropki 2 i 7, nie możesz wtedy odwiedzać kropek 1, 3 lub kropki 9. Nie jesteś nawet poprawny po 3 kropkach. Jeśli odwiedzasz 123, nie możesz odwiedzić 7. - Omnifarious
Wtedy nie mogę zrozumieć reguł, ponieważ zgodnie z twoim stwierdzeniem w komentarzach do pytania, sekwencja 182 jest równoważna sekwencji 1812, która jest legalna. Podobnie 271 = 2721, 273 = 2723, 1237 = 12327. Jeśli to nie jest poprawne, daj mi znać, jaka reguła temu zapobiega. - Tyler McHenry
1812 nie jest legalne. System obraca każdy ruch z 8 na 2 w ruch z 8 na 5 na 2, jeśli 5 nie jest już częścią ścieżki. - Omnifarious
Aby wyjaśnić - 1812 nie jest legalne, ponieważ jest dokładnie równoznaczne z 182 (powtórki kropek, które są już częścią ścieżki są całkowicie ignorowane), co nie jest legalne. System obraca każdy ruch z 8-> 2 na ruch dwuczęściowy z 8-> 5-> 2, jeśli 5 nie jest już częścią ścieżki. Gdy 5 znajdzie się na ścieżce, 8-> 2 staje się możliwym przejściem. - Omnifarious


Okay, więc na początek pozwól mi zacząć od stwierdzenia, że ​​wszystko wydaje się poprawne. Co możemy zrobić z matematyką? Zgadzam się z nim, kiedy mówi, że rzeczywiście są tylko 3 sprawy, którymi należy się zająć. 1,2 i 5.

OP chce jakiejś eleganckiej formuły liczenia, która jest wątpliwa w przypadku takiego problemu. Kiedy użyjesz wszystkich 9 punktów, znajdziesz ścieżki Hamiltona, co jeśli byłby to kompletny wykres, bardzo łatwo byłoby policzyć (nie jest). Ponieważ każdy z tych trzech przypadków jest unikalny, będziesz musiał wyliczyć wszystkie z nich, aby znaleźć całkowitą liczbę ścieżek.

Rzućmy okiem na pierwszy przypadek, zaczynając od rogu. Masz cztery możliwości wyboru narożnika, a następnie masz 5 możliwości wyboru następnego kwadratu. Teraz szybko zauważysz, że nasza formuła rozwija się dość szybko, ponieważ mamy 5 możliwości i musimy podzielić te 5 opcji na 2 zestawy.

Przejście na środkowy kwadrat boczny będzie miało te same wybory, bez względu na to, do którego się przeniesiesz. W przeciwieństwie do przenoszenia do 5, co da nam znacznie więcej opcji, nasza formuła już jest:

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

Następnie musimy podzielić opcje 6 i 7 na kolejne grupy. Jeśli przejdziemy do kwadratu bocznego, możemy teraz przejść do dwóch kwadratów bocznych, trzech rogów i jednego środkowego kwadratu. Nasza formuła staje się wtedy:

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

Potem musimy zacząć rozwiązywać, jeśli przeniosłyśmy się na środkowy kwadrat, a ja zamierzam się tu zatrzymać. Znalezienie ścieżek Hamiltona jest NP-zupełne, chociaż je po prostu liczymy. Ale nie ma tu żadnych właściwości, które moglibyśmy wykorzystać, aby uzyskać eleganckie rozwiązanie. To problem teorii grafów, który polega na brutalnym forsowaniu rozwiązania, tak jak to miało miejsce wcześniej w przypadku programu Omnifarious.

Spróbuję wyjaśnić, dlaczego intuicja jest zła, mówisz tak:

"Wiem na pewno, że rozwiązanie tego leży w dyskretnej matematyce, w szczególności Permutations Without Repetition, Jeśli twoja odpowiedź nie używa permutacji lub kombinacji, jesteś niepoprawny."

Niestety nie znasz tego faktu, ponieważ nie znasz formuły (chyba że możesz pokazać mi rygorystyczny, nie-konstruktywny dowód). Faktem jest, że permutacja lub kombinacja oznacza, że ​​gdy masz n pozycji, możesz wybrać dowolny przedmiot w dowolnej iteracji. Teraz możesz nakładać ograniczenia na liczbę przedmiotów, które możesz wybrać i na jakie przedmioty możesz wybrać w określonych iteracjach. Ale czego nie możesz zrobić i oczekiwać eleganckiego rozwiązania, to sprawienie, że niektóre przedmioty wpływają na to, które przedmioty możesz wybrać. I właśnie to robi to pytanie i dlaczego nie ma jakiejś fajnej formuły z wykorzystaniem kombinacji i permutacji.

W skrócie, formuła, której szukasz, nie istnieje, ale Omnifarious znalazł poprawną odpowiedź.


2
2018-01-25 06:37



Dziękuję Ci. Byłem prawie pewien, że nie było tak naprawdę możliwe wymyślenie łatwej formuły i wiedziałem, że to dlatego, że wybory były ważne, zmieniły się w zależności od wyborów, które wybrałeś wcześniej, ale nie wiedziałem, jak jasno to wyrazić. Wyraziłeś to dość wyraźnie. - Omnifarious


Omnifarious był zdecydowanie dokładny w swoim wpisie - istnieje 389.112 kombinacji. Wysłałem OGROMNĄ informację o całym procesie określania tego algorytmu, wraz z plikiem tekstowym zawierającym listę wszystkich kombinacji od 1 do 9 długości (co wydaje się możliwe, z tego, co mogłem powiedzieć na telefonie mojej dziewczyny). Link do tej treści jest następujący: http://bit.ly/hEHcBJ


2
2018-01-22 23:11





Nie wiem, czy ktoś jeszcze się tym przejmuje, ale jest to problem z liczeniem ścieżek wykresu. Jest 9 węzłów, więc utwórz macierz 9 x 9 (każdy wiersz jest z węzła, każda kolumna od A do węzła). Jeśli węzeł n łączy się z węzłem m, ustaw (n, m) i (m, n) oba na 1. Zrób to dla wszystkich połączeń. Zostaw resztę na zero. Nazywa się to macierzą sąsiedztwa. Podnieś tę macierz do liczby linii we wzorze i dodaj wszystkie wpisy. Jest to liczba permutacji. Jeśli komuś zależy, wyślę trochę kodu Pythona (na moim telefonie lub po jego opublikowaniu)

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

Moje odpowiedzi nie pasują do tych podanych przez inne osoby powyżej, więc napisałem również symulację trajektorii wykresu dla danego wykresu. Odpowiedzi symulacji (z powodu wydechu) odpowiadają odpowiedziom z obliczeń macierzy sąsiedztwa. Ja również opracowałem dwie pierwsze (jedna krawędź i dwie krawędzie) ręcznie i otrzymałem te same odpowiedzi (40 i 200). Zauważ, że zakładam, że możesz wielokrotnie odwiedzać ten sam wierzchołek (tj. 1-> 2-> 1-> 2 ...).

Mój wykres:

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

1
2018-01-06 05:15



+1 tak, patrzę na to. - rook
Teraz gra z moim telefonem i zdałem sobie sprawę, że dozwolone są także 0-> 5, itp. (Mój wykres jest nieprawidłowy). Mój komputer jest wyłączony i wyjeżdżam z miasta na weekend, więc nie mogę tego naprawić. Po prostu zaktualizuj listę ścieżek dla rzeczywistych dozwolonych ścieżek. Matematyka wciąż jest poprawna. - Jim
Grając z moim telefonem, odkryłem, że ścieżki w stylu 1-> 2-> 1 nie są dozwolone. Więc nie jest to dokładne przejście przez wykres, ponieważ wykres zmienia się podczas przejścia. Mimo to nadal można go obliczyć za pomocą matryc. Zależy od dokładnych reguł (nigdy wcześniej nie miał droida) - Jim
Wskrzeszanie tego: Nie musimy myśleć o tym, że wykres się zmienia: interesują nas tylko ścieżki, a nie spacery. Zobacz moją odpowiedź. - Alec
Ach, wykres robi zmień, ponieważ rzeczy takie jak 1 -> 4 -> 0 -> 2 są dozwolone (normalnie nie możesz przeskoczyć z 0 na 2, ale teraz możemy, ponieważ 1 jest już używany). - Alec


edytować: Nie, jestem w błędzie. Wykres zmienia się, ponieważ w ogólności rzeczy takie jak 1 -> 3 są niedozwolone (musisz przejść przez 2 pierwsze), ty mogą wykonaj czynności 2 -> 5 -> 1 -> 3: 1 -> 3 krawędzi staje się dostępne, ponieważ 2 zostały już użyte w ścieżce.

Napisałem program do tego celu i otrzymałem te same 389,112, co Omnifarious (i wtedy zrozumiałem, że mój program robi to samo, co jego).

Zaciekawiło mnie to: dość pewny, że to 139,880. Tak jak powiedział Jim, można to modelować za pomocą wykresu. Podnoszenie macierzy sąsiedztwa do mocy nie działa, ponieważ zlicza ścieżki z powtórzeniami, ale możesz po prostu BFS przez wykres:

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)

A następnie po prostu dodaj liczbę ścieżek o długości 4, 5, 6, 7, 8 i 9.

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


1
2018-02-07 06:26