Android (sistema operativo): ¿Cuántas combinaciones tiene el desbloqueo de puntos de Android 9?

En realidad, los gráficos de conectividad de Dirk, Anders y Greg son incorrectos.

No solo los nodos están conectados por adyacencia y movimientos de caballeros; También pueden conectarse a través de 2 pasos a lo largo de una línea, o un salto de clavija, si el punto medio ya está en uso. Eso significa que la conectividad cambia según los puntos que ya se hayan utilizado.

Entonces, por ejemplo, si los nodos están etiquetados como

1 2 3

entonces (1 2 3), (2 1 3), (2 3 1), (3 2 1) podrían ser válidos. (Tenga en cuenta que todos estos son demasiado cortos, ya que la longitud mínima es de 4 puntos).

La salida del siguiente código es:

Secuencias por longitud: [0, 0, 0, 0, 1624, 7152, 26016, 72912, 140704, 140704]
Número total de secuencias: 389112

min_seq_length = 4

def Medio (a, b):
“” “Devuelve el nodo entre a y b si hay uno, o Ninguno.” “”
if (a + b)% 2! = 0:
regresar Ninguno
medio = (a + b) / 2
si mid == 5:
volver a mediados
si a% 3 == b% 3:
volver a mediados
if (a-1) / 3 == (b-1) / 3:
volver a mediados
regresar Ninguno

def NextValid (base):
“” “Genera movimientos válidos j + 1 dada una secuencia de movimientos 1..j.” “”
si len (base)> = 9:
regreso
si len (base) == 0:
para i en xrange (1,10):
rendimiento i
regreso
para i en xrange (1,10):
si no en la base:
mid = Middle (i, base [-1])
si mid es None o mid en la base:
rendimiento i

def Secuencias (base):
“” “Generador para secuencias válidas de movimientos” “”
if len (base)> = min_seq_length:
lista de rendimiento (base)
para n en NextValid (base):
para s en Secuencias (base + [n]):
rendimiento m

seqs_of_length = [0] * 10

para seq en Secuencias ([]):
seqs_of_length [len (seq)] + = 1
print ‘Secuencias por longitud:’, seqs_of_length
print ‘Número total de secuencias:’, suma (seqs_of_length)

Tenía una manera ingenua de resolver este problema. Eso es por fuerza bruta.
Estoy usando el código python.

La idea es modelar los puntos 3 x 3 como un gráfico, luego explorar todas las formas posibles en que se pueden conectar 4 (o cualquier número <= 9) nodos. Cualquier nodo no debe explorarse dos veces. Luego creamos un gráfico especial que denota los nodos no accesibles de cada nodo como se muestra a continuación:

  non_adj_intermediate = {1: {3: 2, 7: 4, 9: 5}, 
 						  2: {8: 5}, 
 						  3: {1: 2, 7: 5, 9: 6}, 
 						  4: {6: 5},
 						  5: {},
 						  6: {4: 5},
 						  7: {1: 4, 3: 5, 9: 8},
 						  8: {2: 5},
 						  9: {1: 5, 3: 6, 7: 8}}

Este non_adj_intermediate describe que el nodo 1 no puede alcanzar el nodo 3 porque el nodo 2 está bloqueando su camino. El nodo 1 no puede alcanzar el nodo 7 porque el nodo 4 está bloqueando. El nodo 1 no puede alcanzar el nodo 9 porque el nodo 5 está bloqueando. Y así sucesivamente para el resto de los nodos.

Entonces, para calcular la combinación, aplicamos la fuerza bruta y no exploraremos los nodos que no se pueden alcanzar (es decir, se excluyen aquellos que no se pueden alcanzar).

Código completo:

  NUM_DOTS = 0
 PCOUNT = 0
 conteo de def (pgraph, used_list, current_node):
     NUM_DOTS globales, PCOUNT
     si current_node en used_list:                  
         regreso
     más:                                         
         used_list.append (current_node)            
         if len (used_list) == NUM_DOTS:            
             PCOUNT = PCOUNT + 1                   
             used_list.remove (current_node)       
             regreso
         para nodos en rango (1,10):               
             if nodos en used_list:
                 continuar
             non_adj = pgraph [current_node]         
             si nodos en non_adj.keys () y non_adj [nodos] no en used_list:
                 continuar                                                  
             contando (pgraph, used_list, nodos)     
         used_list.remove (current_node)              
         regreso
                
 non_adj_intermediate = {1: {3: 2, 7: 4, 9: 5},        
                          2: {8: 5},                   
                          3: {1: 2, 7: 5, 9: 6},         
                          4: {6: 5},
                          5: {},
                          6: {4: 5},
                          7: {1: 4, 3: 5, 9: 8},
                          8: {2: 5},
                          9: {1: 5, 3: 6, 7: 8}}

 node_used_for_pattern = []    
                    
 para pattern_dot en el rango (1,10):                    
     NUM_DOTS = patrón_dot
     para w en rango (1,10):                         
         contando (non_adj_intermediate, node_used_for_pattern, w)
     imprime "Patrón total para", NUM_DOTS, "el punto es:", PCOUNT
     node_used_for_pattern = []                     
     PCOUNT = 0

Salida:
El patrón total para 1 punto es: 9
El patrón total para 2 puntos es: 56
El patrón total para 3 puntos es: 320
El patrón total para 4 puntos es: 1624
El patrón total para 5 puntos es: 7152
El patrón total para 6 puntos es: 26016
El patrón total para 7 puntos es: 72912
El patrón total para 8 puntos es: 140704
El patrón total para 9 puntos es: 140704

La respuesta es 389112.

He escrito un código en C. Imprimirá todos los patrones posibles con el número total de patrones al final. Mi solución es bastante simple.

Utilicé el concepto de teoría de gráficos (primera búsqueda de profundidad) donde cada punto en la pantalla de bloqueo es un nodo. Supongamos que cada punto en la pantalla de bloqueo está conectado con todos los otros puntos. Entonces, hay un total de 9c2 = 36 aristas. Ahora suponga que se encuentra en cualquier punto de la pantalla de bloqueo. Primero marcamos el punto como visitado. Desde este punto solo puede saltar a los puntos que tienen las siguientes propiedades:

1. No hay puntos no visitados en la línea recta que une los dos puntos.

2. El punto al que vamos a saltar debe estar sin visitar

Proceder de la misma manera; Después de buscar a través de todos los patrones posibles desde este punto cuando dejamos el punto (es decir, nos movemos al punto o nodo principal), marcamos el punto como no visitado.

Así visitamos a través de todos los patrones posibles.

NOTA: solo consideramos patrones que tienen al menos 4 puntos conectados, es decir, la longitud mínima debe ser 3.

Aquí está el código …

  #include 
  int total_pattern = 0;
  void print_pattern (int stack [9], int pivot) {
 	 int i;
 	 printf ("\ n ---------- \ n");
 	 para (i = 0; i ", stack [i]);
 	 printf ("% d", stack [pivot]);
  }
 int check_integer (float x) {
 	 if (! ((float) (int) xx)) devuelve 1;
 	 devuelve 0;
  }
  // Para verificar si hay alguna no visitada
  // punto entre los puntos en la recta 
  // línea que une los puntos
  int check_path (int nodo1, int nodo2, int visitado [9]) {
  flotante node1_x, node1_y, node2_x, node2_y, x, y;
    nodo1_x = (int) ((nodo1-1) / 3);
    nodo2_x = (int) ((nodo2-1) / 3);
    nodo1_y = (int) ((nodo1-1)% 3);
    nodo2_y = (int) ((nodo2-1)% 3);
 		 y = (nodo2_y + nodo1_y) / 2;
 		 x = (nodo2_x + nodo1_x) / 2;
 	 if (check_integer (y) && check_integer (x)) {
 		 if (! visitó [(int) (3 * x + y)]) devuelve 0;
 	 }
 	 retorno 1;
  }
  // profundidad primera búsqueda
  patrón vacío (int nodo, int visitado [9], int longitud, int stack [9]) {
 	 int i;
 	 pila [++ longitud] = nodo;
 	 if (longitud> = 3) {
 		 patrón_total ++;
 		 print_pattern (pila, longitud);
 	 }
 	 visitado [nodo-1] = 1;
 	 para (i = 1; i <= 9; i ++) {
 		 if (i! = nodo) {
 			 if (! (visitado [i-1]) && check_path (nodo, i, visitado)) {
 				 patrón (i, visitado, longitud, pila);
 			 }
 		 }
 	 }
 	 visitado [nodo-1] = 0;
  }
  vacío principal(){
 	 int i, j, k, visitado [9], stack [9];
 	 k = 1;
 	 printf ("Pantalla de bloqueo:");
 	 para (i = 0; i <3; i ++) {
 		 printf ("\ n");
 		 para (j = 0; j <3; j ++) printf ("% d", k ++);
 	 }
 	 for (i = 0; i <9; i ++) visitó [i] = 0;
 	 para el patrón (i = 1; i <= 9; i ++) (i, visitado, -1, pila);
 	 printf ("\ n Patrones totales:% d", patrón_total);
  }

Si no desea imprimir todos los patrones posibles (porque va a ocupar un lugar enorme) simplemente coloque la línea 35 como un comentario (//) o simplemente elimine la línea ... La salida será solo el número total de patrones. 389112

El Android impone estas condiciones en los patrones:

• Cada patrón debe conectar al menos cuatro puntos.
• Los puntos en el patrón deben ser distintos.
• Si el segmento de línea que conecta dos puntos consecutivos en el patrón pasa a través de otros puntos, los otros puntos deben haber estado previamente en el patrón.

En estas condiciones, puede crear 389112 patrones distintos , como se calcula con el siguiente programa C ++:

Representación del patrón de la siguiente manera,

0 1 2

3 4 5

6 7 8

  #include 
 #include 
 
 usando el espacio de nombres estándar;
 
 void Gen (int x, vector  v, long long int & ctr, int * visitado)
 {
	 bandera int, l;
 
	 visitado [x] = 1;
	 v.push_back (x);
	 l = v.size ();
 
	 // Para verificar si el segmento de línea que conecta dos puntos consecutivos en el patrón pasa por otros puntos, entonces los otros puntos deben haber estado previamente en el patrón
	 // Para verificar la validez del último elemento insertado en el vector.
	 bandera = 1;
  	 si (l> 1)
  	 {
    	 if (v [l-2] == 0 && v [l-1] == 2 && visitado [1] == 0)
        	 bandera = 0;

         if (v [l-2] == 0 && v [l-1] == 6 && visitado [3] == 0)
         	 bandera = 0;
         if (v [l-2] == 0 && v [l-1] == 8 && visitado [4] == 0)
         	 bandera = 0;
 
         if (v [l-2] == 2 && v [l-1] == 0 && visitado [1] == 0)
         	 bandera = 0;
 
         if (v [l-2] == 2 && v [l-1] == 6 && visitado [4] == 0)
         	 bandera = 0;
 
         if (v [l-2] == 2 && v [l-1] == 8 && visitado [5] == 0)
         	 bandera = 0;
 
         if (v [l-2] == 6 && v [l-1] == 0 && visitado [3] == 0)
        	 bandera = 0;
 
         if (v [l-2] == 6 && v [l-1] == 2 && visitado [4] == 0)
        	 bandera = 0;
 
         if (v [l-2] == 6 && v [l-1] == 8 && visitado [7] == 0)
        	 bandera = 0;
 
         if (v [l-2] == 8 && v [l-1] == 2 && visitado [5] == 0)
        	 bandera = 0;
 
         if (v [l-2] == 8 && v [l-1] == 0 && visitado [4] == 0)
        	 bandera = 0;
 
         if (v [l-2] == 8 && v [l-1] == 6 && visitado [7] == 0)
        	 bandera = 0;
 
         if (v [l-2] == 1 && v [l-1] == 7 && visitado [4] == 0)
        	 bandera = 0;
 
         if (v [l-2] == 7 && v [l-1] == 1 && visitado [4] == 0)
        	 bandera = 0;
 
         if (v [l-2] == 3 && v [l-1] == 5 && visitado [4] == 0)
        	 bandera = 0;
 
         if (v [l-2] == 5 && v [l-1] == 3 && visitado [4] == 0)
        	 bandera = 0;
     }
 
	 si (bandera == 1)
     {
    	 // Para verificar si longitud> = 4
    	 si (l> 3)
         {
			 // Vector válido que representa la secuencia del patrón de bloqueo
        	 ctr ++;

			 / *
			 // Bucle para imprimir los patrones de bloqueo válidos
        	 cout << ctr << ":";
        	 para (int i = 0; i  V;  // vector para almacenar una secuencia de patrón válida
	 largo largo int ctr;  // Para mantener el recuento de patrones de bloqueo válidos.
 
	 // Inicialización de la matriz visitada
	 para (int i = 0; i <9; i ++)
		 visitado [i] = 0;
	 // Inicialización de la variable de contador
	 ctr = 0;
 
	 // Comenzando desde el primer punto como yo
	 para (int i = 0; i <9; i ++)
	 {
		 Gen (i, V, ctr, visitado);
	 }
 
	 //salida
	 cout << ctr << endl;

  	 devuelve 0;
 }

( EDITAR : Gracias a Yoyo Zhou por señalar una falla en este modelo: Anders tiene el resultado final de la discusión en la nueva versión de su respuesta).

Me gustó la respuesta de Haskell en Anders, pero la pantalla de desbloqueo de Android (al menos en mi teléfono con Froyo) es aún más permisiva de lo que él suponía. De hecho, también es posible seguir un punto con un punto alejado de un caballero, sin haber tocado ningún otro punto. El número de patrones disponibles se convierte en 766752.

Es fácil demostrar el movimiento del caballero si lo hace lentamente, solo manténgase alejado del disco oscuro alrededor de cada punto cercano.

Por otro lado, si hago un movimiento de torre o de alfil de longitud 2, se llena en el punto intermedio como si lo hubiera tocado. (Con la retroalimentación táctil, está claro que en realidad no toqué el punto, por lo que no creo que un toque más hábil haga posible evitar esto). Así que esos son los únicos movimientos no disponibles.

Esta variante del código de Anders calcula el resultado:

 import qualified Data.Set as S import Control.Monad(guard) points = [(row, col) | row <- [0..2], col <- [0..2]] adjacentButtons (x, y) = do (x', y') <- points guard $ 1 `elem` [abs $ x' - x, abs $ y' - y] return (x', y') extensions pattern = map (: pattern) . S.toList $ S.difference (S.fromList $ adjacentButtons =<< pattern) (S.fromList pattern) search pattern found = foldr search (pattern : found) $ extensions pattern valid pattern = length pattern >= 4 main = print . length . filter valid . foldr search [] $ map (:[]) points 

Esto se compara con el número de patrones de longitud> = 4 que puede hacer desde 9 puntos sin restricciones a las que puede llegar desde donde:

  > suma.  soltar 4 $ scanl (*) 1 [9,8..1]
 985824

de hecho, exactamente 2/9 de esa clase de patrones no están disponibles.

Sin embargo, la respuesta de Anders es un mejor límite superior sobre cuántos patrones podrían ser prácticos de usar: descubro que el movimiento del caballero toma demasiada atención cuando solo quiero desbloquear mi teléfono.

La respuesta es 389112, ya he escrito un pequeño artículo para explicar cómo obtuve el resultado. Número de posibilidades en el patrón de código de Android – Amine KABAB – Medio

Los patrones deben seguir estas condiciones:

1. Cada patrón debe conectar al menos 4 puntos
2. Todos los puntos deben ser únicos o distintos.
3. Si el segmento de línea que conecta dos puntos consecutivos en el patrón pasa a través de otros puntos, los otros puntos deben haber estado previamente en el patrón.

Según lo calculado por el programa Haskell, puede crear 389112 patrones distintos para la condición mencionada anteriormente.

Este número es confirmado por Adam J. Aviv, Katherine Gibson, Evan Mossop, Matt Blaze, Jonathan M. Smith, “Ataques de manchas en pantallas táctiles de teléfonos inteligentes”, en Proc. 4th USENIX WOOT , 9 de agosto de 2010, págs. 1-7:

¡Probé esto en python y el código es el siguiente!

La solución es: 389112

Deje que la configuración de la matriz sea

[matemáticas] 0 1 2 [/ matemáticas]

[matemáticas] 3 4 5 [/ matemáticas]

[matemáticas] 6 7 8 [/ matemáticas]

Los movimientos que no son válidos son:

• Patrones compuestos por menos de 4 puntos.
• Movimientos adyacentes saltando un nodo. (por ejemplo: no puede pasar de 0 a 2 si no se ha visitado 1)

Nota: El movimiento del caballero es válido ya que podemos alcanzar cuidadosamente un nodo sin tocar ningún otro nodo. (p. ej .: pasar de 0 a 5 sin tocar ningún otro nodo).

  # Patrones de desbloqueo de Android
 cuenta = 0
 visitado = [Falso] * 9
 # not_reachable asigna 2 puntos (A y B) a otro punto (C) como 
 # eso, la ruta directa A a B puede existir si C ha sido visitado. 
 not_reachable = {'02': 1, '06 ': 3, '08': 4, '17 ': 4, '26': 4, '28 ': 5, '35': 4, '68 ': 7 }
 def android_lock (current_position):
     recuento global
     global visitado
     visitado [current_position] = True
     para new_position en rango (0,9):
         si no se visita [new_position] y valid_move (current_position, new_position):
             android_lock (nueva_posición)
     si suma (visitado)> = 4: cuenta + = 1
     visitado [current_position] = False  
 def valid_move (a, b):
     global no accesible
     índice = str (min (a, b)) + str (max (a, b))
     si el índice está en no accesible y no visitado [no accesible [índice]]:
         falso retorno
     más:
         volver verdadero
 para start_position en rango (0,9):
     android_lock (start_position)
 imprimir (contar)

La complejidad espacial es O (N).

La complejidad del tiempo es O (N!) (¡Necesito una aclaración sobre este!)

Si un movimiento a lo largo de la horizontal o vertical se considera 1 unidad, el patrón más corto que usa todos los puntos es 8 unidades. El patrón más largo (distancia del dedo) es> 17, sqrt (2) + 7 * sqrt (5). Este es el resultado de 7 movimientos de caballeros y una diagonal corta. Esto es incómodo y máximamente regular (casi una estrella). Entonces, ¿qué patrón tiene menos simetría (inversiones mínimas y reflejos mínimos) con mayor longitud? Creo que eso sería lo más seguro.
Por cierto: desearía que los puntos pudieran ser reutilizados. El número de combinaciones aumentaría a 9 ^ 9, o 1000 veces el gráfico actual. ¿Y por qué la longitud del punto debe limitarse a solo 9? por ejemplo, 31415926536 podría ser agradable (numerado de l a r, de t a abajo desde la parte superior izquierda).

Hice una IU rápida y sucia que visualiza las diferentes permutaciones disponibles: http://daniellereya.github.io/an …

Puedes ver el código real en github.

También forcé la respuesta con una búsqueda recursiva y encontré una respuesta más grande, 487272. El algoritmo es simple: probarlo todo. Lo cité aquí abajo. No encontré ningún error en mi código (pero no soy muy hábil con c ++). Perdón por el error gramatical, no soy inglés.

#include
#include
usando el espacio de nombres estándar;

combo int; //mostrador

investigación nula (int Ipoints / * número de puntos ya ocupados * /, bool Icheck [9] / * matriz de puntos * /, int Ilast / * último punto tomado * /,
int Icomboval / * representación de combinación, solo para fines de impresión * /, int deep / * número de iteraciones, solo para fines de impresión * /)
{

// int numcall = 0; //DEPURAR

for (int i = 0; i <9; i ++) // Controlando cada punto libre en busca de una forma válida de continuar
if (marque [i] == false)
{
// Solo por seguridad, haciendo frente a cada variable en una nueva variable. No sé cómo funciona c ++ pero lo haré funcionar
puntos int = puntos I;
int last = Ilast;
int comboval = Icomboval;
cheque de bool [9];
para (int j = 0; j <9; j ++)
check [j] = Icheck [j];

int e1, e2;
int medio = -1;
e1 = i; e2 = último; // Control de saltos de doble
if (e1 == 0 && e2 == 2) medio = 1;
if (e1 == 3 && e2 == 5) medio = 4;
if (e1 == 6 && e2 == 8) medio = 7;
if (e1 == 0 && e2 == 6) medio = 3;
if (e1 == 1 && e2 == 7) medio = 4;
if (e1 == 2 && e2 == 8) medio = 5;
if (e1 == 0 && e2 == 8) medio = 4;
if (e1 == 6 && e2 == 2) medio = 4;

e2 = i; e1 = último; // en ambos sentidos
if (e1 == 0 && e2 == 2) medio = 1;
if (e1 == 3 && e2 == 5) medio = 4;
if (e1 == 6 && e2 == 8) medio = 7;
if (e1 == 0 && e2 == 6) medio = 3;
if (e1 == 1 && e2 == 7) medio = 4;
if (e1 == 2 && e2 == 8) medio = 5;
if (e1 == 0 && e2 == 8) medio = 4;
if (e1 == 6 && e2 == 2) medio = 4;

if ((middle! = -1) &&! (marque [middle])) {
marcar [medio] = verdadero;
puntos ++; // agregando puntos medios
comboval * = 10;
comboval + = medio;
}

marque [i] = verdadero;
puntos ++; // obtener el punto

comboval * = 10;
comboval + = i + 1;

si (puntos> 3)
{
combo ++; // cada iteración sobre puntos de árbol es un combo válido

// Si quieres verlos a todos, ten cuidado porque imprimirlos es realmente lento:
// cout << "Combinación n." << combo << "encontrado:" << comboval << ", puntos" << puntos << "con" << profundo << "iteraciones \ n";
}

if (puntos> 9) // Solo seguro, apagado de emergencia,
{salida (1); }

investigación (puntos, verificación, i, comboval, profundo + 1); / * Recursivo, ¡aquí está el verdadero programa! * /

// numcall ++; //DEPURAR
}

// cout << "Ended" << deep << ", con" << numcall << "subs llamados \ n"; // Solo para propósitos de depuración, elimine con todo // DEPURAR }

int main ()
{
combo = 0; // no inicial sabe combo
tablero de ajedrez bool [9];
para (int i = 0; i <9; i ++) tablero de ajedrez [i] = falso; // patrón inicial en blanco

research (0 / * no se toma ningún punto * /, tablero de damas, -1 / * solo un valor inútil * /, 0 / * combo en blanco * /, 1 / * es la primera iteración * /); // ¡busquemos!

cout << "\ n";
cout << "Y la respuesta es ..." << combo << "\ n"; //fuera char ans = ‘\ 0’;
while (ans == ‘\ 0’)
{ //a la espera
cin >> ans;
}

devuelve 0;
}

La forcé brutalmente y la respuesta (como otros mencionaron) fue 389112:
Aquí está el código C ++:
Ubuntu Pastebin
pero tengo una pregunta:
¿Es posible calcular esto usando combinatoria?

aqui esta la respuesta

¿Cómo haces un patrón del número 6?