Reto de los patrones

[angel relativamente]

Re: ¿Cuántos patrones de desbloqueo del teléfono se pueden crear?

Hace tiempo se planteó por aquí el reto de los patrones, y algún usuario consiguió descifrarlo.
La verdad sorprende las "pocas" combinaciones que hay, en comparación por ejemplo con contraseñas alfanuméricas

[Alriga]

¿Cuántos patrones de desbloqueo del teléfono se pueden crear?

¿Os habíais peguntado alguna vez cuántos patrones distintos de desbloqueo del teléfono se pueden crear? En este vídeo explican cómo calcular cuántos patrones de desbloqueo diferentes existen en los teléfonos Android, si se aplican las siguientes reglas:

• Como mínimo hay que conectar 4 números
• Todos los números que se conectan son distintos
• Si una línea pasa sobre un número intermedio, ese punto debe haber sido ya conectado anteriormente

La cifra que da el vídeo, 389.112 patrones distintos, es difícil de calcular y se puede ver que coincide con la cifra que dan en Smudge Attacks on Smartphone Touch Screens en donde confiesan en la página 2 que lo han calculado a fuerza bruta: "Due to the complexity of the intermediate contact point restriction, we calculated this result via brute force methods"

Y el que quiera ver las 389.112 posibilidades distintas, aquí las tiene todas:

Saludos.

[InesIncinerate]

Re: Reto de los patrones

Completísimo, ¡muchas gracias! Lo intentaré una vez más y si me falla algo ya vendré a quejarme por aquí .

[abuelillo]

Re: Reto de los patrones

¡Impresionante! No entiendo ni papa del código en C pero desde luego los resultados avalan tu método, enhorabuena . ¿Crees que podrías hacer una traducción rapidilla al cristiano? Tengo el programa empezado en Java y, ya por cuestión de orgullo, nada me gustaría más que acabarlo.

Lo cierto es que es mas dificil de explicar que de hacer, a ver si se entiende, he etiquetado los 9 puntos posibles de la siguiente forma:
0 1 2
3 4 5
6 7 8
A partir de aqui he definido una matriz bidimensional de 9x9: cada elemento i,j de la matriz guarda el punto intermedio entre los puntos i,j.
Por ejemplo en el elemento 0,8 de la matriz se guarda el valor 4, que es el punto que esta entre los puntos 0 y 8.
Si los puntos son directamente adyacentes, o no son adyacentes pero definen un movimiento del tipo que hace el caballo en el ajedrez, se guarda un valor especial para indicar que no hay ningun punto entre esos dos.
Por ejemplo entre 0,1 no hay puntos intermedios asi que en la matriz se puede guardar el valor -1.
O para los puntos 2,6 tambien se guarda el valor -1 porque aunque en principio no son adyacentas, segun las reglas de movimiento "topologicamente" si lo son, ya que se corresponden con un movimiento tipo caballo de ajedrez que no tienen restricciones.

Despues todo el trabajo lo hace una funcion recursiva a la que se le pasa un punto inicial y recorre todos los demas puntos comprobando si el movimiento es valido, si es valido se llama recursivamente asi misma para evaluar el siguiente salto.
Intentare poner un pseudocodigo generico, porque la implementacion en C se me hace dificil de explicar, porque uso mascaras de bits para implementar la lista de puntos ya usados y otras cosas que son muy especificas de C y de lenguajes de bajo nivel.

En realidad en el pseudocodigo que voy a poner, en lugar de recorrer siempre todos los puntos, podria definirse un parametro nuevo en la funcion que guardase "la lista de puntos que aun no se han usado" y recorrer solo los puntos de esa lista, pero como en C no hay variables de tipo lista faciles de manipular no lo he implementado asi, ya que haria el codigo muchismo mas largo.

No se si sera suficiente para entenderlo, espero que si:

// Identificacion de los puntos
// 0 1 2
// 3 4 5
// 6 7 8

DEFINIR matriz_movimientos[9,9]
DONDE cada elemento matriz_movimientos[j,k] VALE:
-1  =>  Si los puntos j,k son topologicamente adyacentes
o
Entre 0 y 9 => Identificando el punto que hay entre los puntos j y k

// Parametros de la funcion:
// punto_origen  = punto inicial del salto, posibles valores 0 a 9
// puntos_ya_usados = lista con los puntos que ya han sido utilizados
// saltos_pendientes = numero de saltos pendientes de realizar

FUNCION CalcularRecursivo( punto_origen, puntos_ya_usados,  saltos_pendientes)

  SI saltos pendientes=0 ENTONCES
     //Ya no hay que buscar mas saltos, porque ya tenemos una secuencia completa
     //por ejemplo si se estaban buscando los patrones de longitud 4, este ya seria la quinta llamada recursiva, no hay que seguir evaluando puntos
    RETORNAR 1
  SINO
    // la variable "contar" va contando los patrones validos que se van localizando
    contar = 0
    DESDE punto_destino=0 HASTA 9 
        SI (punto_destino NO ESTA EN LA LISTA puntos_ya_usados) Y
          (
             (matriz_movimientos[punto_origen,punto_destino] = -1 ) O 
             (matriz_movimientos[punto_origen,punto_destino] ESTA EN LA LISTA puntos_ya_usados)
          )
        ENTONCES
             contar = contar + CalcularRecursivo( punto_destino, puntos_ya_usados + punto_destino, saltos_pendientes-1 )
        FIN SI
    FIN DESDE
    RETORNAR contar
  FIN SI
FIN FUNCION

// Llamar a esta funcion en lugar de a CalcularRecursivo
// tamaño_patron = longitud del pin del que queremos calcular el numero de combinaciones posibles

FUNCION Calcular(tamaño_patron)
  contar = 0
  DESDE punto_origen=0 HASTA 9 
    contar = contar + CalcularRecursivo( punto_origen, punto_origen, tamaño_patron)
  FIN DESDE
  RETORNAR contar
FIN FUNCION

[InesIncinerate]

Re: Reto de los patrones

¡Impresionante! No entiendo ni papa del código en C pero desde luego los resultados avalan tu método, enhorabuena . ¿Crees que podrías hacer una traducción rapidilla al cristiano? Tengo el programa empezado en Java y, ya por cuestión de orgullo, nada me gustaría más que acabarlo.

[abuelillo]

Re: Reto de los patrones

Usando las reglas completas, me sale el mismo resultado que el ya expuesto en un post previo:

PinSize: 4 PinCount: 1624
PinSize: 5 PinCount: 7152
PinSize: 6 PinCount: 26016
PinSize: 7 PinCount: 72912
PinSize: 8 PinCount: 140704
PinSize: 9 PinCount: 140704
PinCount Total: 389112

/* 
 * Android unlocking patterns, calculate the number of combinations
 * P0 P1 P2  
 * P3 P4 P5 
 * P6 P7 P8
 */

#include <stdio.h>

#define P0 0x001
#define P1 0x002
#define P2 0x004
#define P3 0x008
#define P4 0x010
#define P5 0x020
#define P6 0x040
#define P7 0x080
#define P8 0x100
#define OO 0xFFF 

const int moves[9][9] = {
  //P0 P1 P2 P3 P4 P5 P6 P7 P8
  { OO,OO,P1,OO,OO,OO,P3,OO,P4 }, // P0
  { OO,OO,OO,OO,OO,OO,OO,P4,OO }, // P1
  { P1,OO,OO,OO,OO,OO,P4,OO,P5 }, // P2
  { OO,OO,OO,OO,OO,P4,OO,OO,OO }, // P3
  { OO,OO,OO,OO,OO,OO,OO,OO,OO }, // P4
  { OO,OO,OO,P4,OO,OO,OO,OO,OO }, // P5
  { P3,OO,P4,OO,OO,OO,OO,OO,P7 }, // P6
  { OO,P4,OO,OO,OO,OO,OO,OO,OO }, // P7
  { P4,OO,P5,OO,OO,OO,P7,OO,OO }, // P8
};

#define calc_android_unlock_patterns(pinsize) realcalc(4, 0x800, pinsize)
int realcalc(int point, int used_points, int pincount)
{
  int i, mi, count;
  if (pincount==0) return 1;
  count= 0;
  for(i=0,mi=1; i<9; i++,mi<<=1) 
    if ( !(mi&used_points) && moves[point][i]&used_points )
      count+= realcalc( i, used_points|mi, pincount-1 );
  return count; 
}
 
int main(void)
{
  int i, count, total= 0;
  for(i=4; i<=9; i++)  {
    count= calc_android_unlock_patterns(i);
    printf("PinSize: %d PinCount: %d\n", i, count);
    total+= count;
  }
  printf("PinCount Total: %d\n",total);
  return 0; 
}

[Physicist]

Re: Reto de los patrones

Según las planteadas aqui si lo es, porque ya has seleccionado el centro una vez, así que ahora puedes pasar por encima

[abuelillo]

Re: Reto de los patrones

Y para ampliar la información, aquí está el link original: http://beust.com/weblog/2008/09/17/a...cking-pattern/

Por lo que veo las reglas explicadas en esa pagina son distintas a las planteadas por angel.
Por ejemplo la combinacion: { LV2, C, LH1, LH2 } no es valida segun las reglas planteadas aqui, pero si es legal segun las reglas de esa pagina.

[InesIncinerate]

Re: Reto de los patrones

Y para ampliar la información, aquí está el link original: http://beust.com/weblog/2008/09/17/a...cking-pattern/

[Physicist]

Re: Reto de los patrones

Muy Buenas!

Los resultados más fiables hasta ahora son:

4 dots: 1624 solutions
5 dots: 7152 solutions
6 dots: 26016 solutions
7 dots: 72912 solutions
8 dots: 140704 solutions
9 dots: 140704 solutions
Total: 389112

Tiene sentido que los dos últimos sean los mismo porque solo queda un punto y habrá que elegirlo si o si

[Weip]

Re: Reto de los patrones

abuelillo, yo no sabría detectar ningún error en el código, pero sé que el resultado correcto es algo mayor, aunque muy muy similar a ése, pues buscando los movimientos posibles llegué a encontrar la solución al problema corroborada por varios usuarios de smartphones que realizaron sus programas independientemente. Lo que no vi es el procedimiento por el que llegaron a ella (tampoco quería hacerlo ).

¿Podrías poner aquí los resultados, si los tienes o si te acuerdas? Es que así no iremos tan perdidos.

[InesIncinerate]

Re: Reto de los patrones

abuelillo, yo no sabría detectar ningún error en el código, pero sé que el resultado correcto es algo mayor, aunque muy muy similar a ése, pues buscando los movimientos posibles llegué a encontrar la solución al problema corroborada por varios usuarios de smartphones que realizaron sus programas independientemente. Lo que no vi es el procedimiento por el que llegaron a ella (tampoco quería hacerlo ).

[l3m0n]

Re: Reto de los patrones

Como a los matemáticos nos gusta tocar las narices aquí las voy a tocar

Este problema aún tiene más gracia, ya que sí que se pueden cumplir las 3 condiciones últimas que pones para la creación de un conjunto (camino) válido.

Utilizaré la notación que has usado tu para no confundirnos.
Las tres últimas condiciones básicamente se resumen en dicho de forma vulgar, que no se pueden unir dos nodos en linia recta sí tienen uno entre medio. Pero esto sólo se cumple cuando el nodo que está en el medio no ha sido préviamente seleccionado, si para hacer el patrón que estamos haciendo ya hemos seleccionado ese nodo entonces sí que podemos "pasar por encima".

Bueno, voy a ver si me dedico un ratillo a pensarlo, porque hacerlo a fuerza bruta me parece muy cutre y quiero ver si hay algún método que no sea ese . Cuando digo cutre quiero decir que para mí, la fuerza bruta siempre tiene que ser la última alternativa, esperamos que no lo sea para este problema.

[abuelillo]

Re: Reto de los patrones

Como son pocas combinaciones, he probado a resolverlo numericamente a base de fuerza bruta, me sale este resultado:

Pin Size: 1 Pin Count: 9
Pin Size: 2 Pin Count: 56
Pin Size: 3 Pin Count: 304
Pin Size: 4 Pin Count: 1400
Pin Size: 5 Pin Count: 5328
Pin Size: 6 Pin Count: 16032
Pin Size: 7 Pin Count: 35328
Pin Size: 8 Pin Count: 49536
Pin Size: 9 Pin Count: 32256

Lo he hecho en un ratin con una forma algo chapucera y sin muchas comprobaciones, asi que no estoy seguro si esta bien,
la unica comprobacion que he hecho es confirmar que sin el filtro que elimina las combinaciones invalidas da correctamente el numero de Variaciones de
9 elementos tomados de n en n (siendo n =1..9)
Adjunto el codigo en C por si alguien detecta algun error, hubiera sido mas entendible en un lenguaje de mas alto nivel y sin usar mascaras de bits, pero era lo que tenia a mano en ese momento:

#include <stdio.h>


#define E1  0x0001
#define E2  0x0002
#define E3  0x0004
#define E4  0x0008
#define V1  0x0010
#define V2  0x0020
#define H1  0x0040
#define H2  0x0080
#define CC  0x0100
#define ELEMENTS_COUNT 9
#define ELEMENTS_MASK  0x1FF  // E1|E2|E3 ...


const int filter[] =
{
  E1 | E2 | E3 | E4,
  E1 | E2 | E3 | E4,
  E1 | E2 | E3 | E4,
  E1 | E2 | E3 | E4,
  V1 | V2,
  V1 | V2,
  H1 | H2,
  H1 | H2,
  0
};


int count;


void rcalc(int max, int elements, int mask)
{
  int i,mi;
  for(i=0,mi=1; i<ELEMENTS_COUNT; i++,mi<<=1) 
    if ( (mi&elements) && !(mi&mask)) {
    if (max>0)
      rcalc( max-1, elements^mi, filter[i] );
    else
      count++;
    }
}


int calc(size)
{
 count= 0; 
 rcalc(size-1,ELEMENTS_MASK,0); 
 return count; 
}
 
int main(void)
{
 int i;
 for(i=1; i<=9; i++) 
   printf("Pin Size: %d Pin Count: %d\n", i, calc(i));
 return 0;
}

[Weip]

Re: Reto de los patrones

Anda, yo hace tiempo también intenté hacer cosas parecidas a las vuestras. En concreto quería saber el número de caminos (los conjuntos que dice Ángel) necesarios en 4 etapas para ir de un punto a otro (bueno quería hacer de 9 pero era muy cansado hacerlo). Lo que hice es sacar la matriz de adyacencia M e ir multiplicando matrices hasta encontrar M^4. Hay muchísimas combinaciones, pero al final no lo comparé con las de una contraseña... Igual me vuelvo a poner con este tema, pero creo que no es nada trivial.