security - termodinamica - ¿Cuál es la entropía del sistema de contraseña de punto de Android?
entropico (6)
La clave es notar que una vez que haya visitado dos puntos, puede alcanzar cualquier otro punto que desee sin moverse a través de ningún punto que no haya visitado. Entonces, una vez que eliges dos puntos de inicio (en orden), puedes elegir el resto de tu contraseña a voluntad, en el orden que desees. (Esto se debe a que se permiten "movimientos de caballero", al menos de acuerdo con la página que vinculó)
Entonces, excluyendo los puntos ''iniciales'', el número de colas restantes de 2 a 7 dígitos es 7P2 + 7P3 + 7P4 + 7P5 + 7P6 + 7P7. Hay 56 posibles cabezas iniciales de dos dígitos porque hay 5 movimientos que puedes hacer desde cualquier punto de la esquina, 7 desde cualquier punto de borde y 8 desde el punto central. Entonces, el número total de patrones de desbloqueo sería 56 * (7P2 + 7P3 + 7P4 + 7P5 + 7P6 + 7P7) = 766 752.
Si esto está mal, es probable que sea porque me falta algún conocimiento de las reglas de este sistema.
¿Cuántas permutaciones del sistema de inicio de sesión de dot de androides son posibles? Sé de hecho que la solución a esto radica en Matemáticas Discretas, específicamente Permutaciones Sin Repetición . Si su respuesta no usa permutaciones o combinaciones, usted es incorrecta.
La longitud de las contraseñas está entre 4 y 9 puntos, sin embargo, hay un total de 9 puntos para permutar. entonces mi ecuación inicial es:
9P4+9P5+9P6+9P7+9P8+9P9
Sin embargo, sé que esta ecuación es incompleta porque no toma en consideración todas las reglas. Cada punto es distinto debido a su posición, por lo que si asigna un número a cada punto de la siguiente manera:
123
456
789
La contraseña "1397" es imposible. Si intenta utilizar esta contraseña, de hecho habrá ingresado en "1236987" porque los números intermedios se seleccionan automáticamente. Se necesita crear otra ecuación para tener en cuenta estas limitaciones y luego restar de mi ecuación nPr anterior.
Este enlace tiene un gran video de alguien que usa el inicio de sesión de Android. También entra en mayor detalle en las reglas. La matemática en esa página es completamente incorrecta, ni siquiera está cerca de una solución real.
Esta es solo una respuesta parcial. Los únicos puntos de inicio relevantes son 1, 2 y 5. Para los puntos 1 y 2, puede generar un patrón equivalente al inicio en cualquiera de los otros puntos (distintos de 5) con una transformación de rotación simple. Esto significa que si puede enumerar todos los patrones que comienzan en 1 y 2, puede contar todos los patrones comenzando en cualquier número que no sea 5 multiplicando por 4.
Las rutas que comienzan en 5 son un caso diferente. Puede contarlos todos contando todas las rutas que comienzan con 5-> 1 y 5-> 2 y multiplicando por 4, ya que de nuevo puede generar todas las otras rutas posibles con una transformación de rotación simple.
Entonces, una manera de enumerar los caminos sería ...
(Todas las rutas empiezan en 1 + todas las rutas comenzando en 2 + todas las rutas comenzando con 5-> 1 + todas las rutas comenzando con 5-> 2) * 4
De nuevo, el sistema de numeración, para una referencia fácil:
1 2 3
4 5 6
7 8 9
Para este primer movimiento:
Desde 1 -> 2, 4, 5, 6 y 8 son accesibles.
Desde 2 -> 1, 3, 4, 5, 6, 7 y 9 son accesibles (básicamente no solo 8 o sí mismo).
Desde 5 -> 1, 2, 3, 4, 6, 7, 8 y 9 son accesibles.
Para movimientos después de eso se vuelve realmente interesante.
Por ejemplo, 1537 es una contraseña válida. 1539 no es.
Aquí de manera sucinta, son las reglas:
Ningún punto puede ser parte del camino dos veces. Si un punto no es parte de la ruta y está exactamente cruzado por una transición, se convierte en parte de la ruta entre el punto de origen y el punto de destino.
Aquí hay algunas rutas de muestra:
- 2-> 3-> 1-> 8 está permitido.
- 1-> 3-> 2-> 5 no está permitido porque 2 no forma parte de la ruta cuando 1> 3 va exactamente por encima de 2, por lo que la ruta se convierte en 1-> 2-> 3-> 5 si lo desea o no.
- 1-> 2-> 3-> 7 no está permitido porque 3-> 7 cruza más de 5 y 5 ya no es parte de la ruta.
- 1-> 5-> 3-> 7 está permitido. 5 se ignora en 3-> 7 porque ya es parte de la ruta.
Este programa:
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)
Genera una respuesta de 389112.
También valida mis intuiciones previas:
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
De acuerdo, entonces primero déjenme comenzar diciendo que omnifarious parece ser correcto. ¿Qué podemos hacer con las matemáticas? Estoy de acuerdo con él cuando dice que, de hecho, solo hay 3 casos de los que preocuparse. 1,2 y 5.
El OP quiere algún tipo de fórmula de conteo elegante, que dudo que exista para un problema como este. Cuando utilizas los 9 puntos, estás encontrando caminos hamiltonianos, que si fuera un gráfico completo sería muy fácil de contar (no lo es). Debido a que cada uno de los tres casos es único, enumerará a través de todos ellos para encontrar el número total de rutas.
Echemos un vistazo al primer caso, comenzando en una esquina. Tienes cuatro opciones para una esquina, luego tienes 5 opciones para tu siguiente casilla. Ahora verá rápidamente que nuestra fórmula se expande bastante rápido, porque tenemos 5 opciones y tenemos que dividir esas 5 opciones en 2 conjuntos.
Al mudarse a un cuadrado del lado medio, tendrá las mismas opciones, independientemente de a cuál se dirija. A diferencia de pasar a 5, que nos dará muchas más opciones, ya nuestra fórmula es:
4 * (4 * (6) + 1 * (7))
Luego tenemos que dividir las opciones 6 y 7 en otros grupos. Si nos movemos a un cuadrado lateral, entonces podemos movernos a dos cuadrados laterales, tres esquinas y un cuadrado medio. Nuestra fórmula se convierte en:
4 * (4 * (2 * (5) + 3 * (3) + 1 * (7)) + 1 * (7))
Entonces tenemos que empezar a resolver si nos hubiéramos movido al cuadro del medio y voy a parar aquí. Encontrar caminos hamiltonianos es NP completo, aunque solo los estamos contando. Pero no hay propiedades aquí que podamos aprovechar para una solución elegante. Es un problema de teoría de grafos y es uno que involucra la fuerza bruta forzando la solución, como lo ha hecho previamente Omnifarious.
Trataré de explicar por qué tu intuición es incorrecta, dices eso:
"Sé de hecho que la solución a esto radica en Matemáticas discretas, específicamente Permutaciones sin repetición, si su respuesta no utiliza permutaciones o combinaciones, usted es incorrecta".
Desafortunadamente, no se sabe esto de hecho, porque no se conoce una fórmula (a menos que pueda mostrarme una prueba rigurosa no constructiva). El hecho es que una permutación o una combinación significa que cuando tienes n elementos, puedes elegir cualquier elemento en cualquier iteración. Ahora puedes poner restricciones sobre la cantidad de elementos que puedes elegir y sobre los elementos que puedes elegir en ciertas iteraciones. Pero lo que no puede hacer y esperar una solución elegante es hacer que elegir determinados artículos afecte a los artículos que puede elegir a continuación. Que es exactamente lo que esta pregunta está haciendo y por qué no hay una buena fórmula que use combinaciones y permutaciones.
En resumen, la fórmula que estás buscando no existe, pero Omnifarious encontró la respuesta correcta.
Omnifarious fue definitivamente preciso en su publicación: hay 389.112 combinaciones. Publiqué mucho sobre todo el proceso de determinación de este algoritmo, junto con un archivo de texto que enumera cada combinación de 1-9 de longitud (lo que parece posible, por lo que pude decir en el teléfono de mi novia). El enlace a este contenido es este: http://bit.ly/hEHcBJ
No sé si a alguien le importa, pero este es un problema de conteo de gráficos. Hay 9 nodos, por lo tanto, cree una matriz de 9 x 9 (cada fila es un nodo, cada columna un nodo). Si el nodo n se conecta al nodo m, configure (n, m) y (m, n) ambos en 1. Haga esto para todas las conexiones. Deje el resto en cero. Esto se llama matriz de adyacencia. Levante esta matriz al número de líneas en el patrón y agregue todas las entradas. Este es el número de permutaciones. Si a alguien le importa, publicaré un código de Python (en mi teléfono o lo publicaría ahora)
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
Mis respuestas no coinciden con las de otras personas, por lo que también escribí una simulación de cruce transversal para el gráfico en cuestión. Las respuestas de la simulación (debido al escape) coinciden con las respuestas del cálculo de la matriz de adyacencia. También resolví los dos primeros (un borde y dos bordes) a mano y obtuve las mismas respuestas (40 y 200). Tenga en cuenta que asumo que puede visitar el mismo vértice repetidamente (es decir, 1-> 2-> 1-> 2 ...).
Mi gráfica
0 - 1 - 2
| X | X |
3 - 4 - 5
| X | X |
6 - 7 - 8
editar : No, estoy equivocado. El gráfico cambia, porque aunque en general cosas como 1 -> 3 no están permitidas (primero debe pasar por 2), puede hacer cosas como 2 -> 5 -> 1 -> 3: El 1 -> 3 bordes está disponible ya que 2 ya se utilizó en la ruta.
Escribí un programa para dar cuenta de eso y recibí los mismos 389.112 como Omnifarious (y entonces me di cuenta de que mi programa estaba haciendo lo mismo que el suyo).
Me dio curiosidad por esto: bastante seguro de que es 139,880. Como dijo Jim, esto se puede modelar mediante un gráfico. Elevar una matriz de adyacencia a una potencia no funciona porque cuenta las rutas con repeticiones, pero solo puede BFS a través del gráfico:
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)
Y luego solo agregue el número de rutas de longitudes 4, 5, 6, 7, 8 y 9.
>>> sum(num_paths(i) for i in range(4, 10))
139880