Anuncio

Colapsar
No hay ningún anuncio todavía.

Reto de los patrones

Colapsar
X
Colapsar
 
  • Página de 2
  • Filtro
  • Hora
  • Mostrar
Borrar todo
nuevos mensajes
Anterior 1 2 template Siguiente
  • #1

    Divulgación Reto de los patrones

    Saludos compañeros,
    Hace un tiempo se me ocurrió un reto matemático que personalmente aún no he conseguido sacar. Por ello me gustaría compartirlo por aquí, a ver si alguien tiene el suficiente ingenio para resolverlo o por contra concluimos que no es en absoluto trivial.
    El problema es el que sigue. Todos habréis tenido o visto algún smartphone que para desbloquearlo hay que insertar un patrón. Este patrón se basa en lo siguiente: Tenemos una cuadrícula de 9 puntos que voy a representar con la siguiente matriz


    Las letras representan . Buscamos todos los conjuntos de elementos distintos que se puedan formar y que satisfagan ciertas condiciones:

    -Los conjuntos son desde 4 elementos hasta 9.
    -Sí importa el orden de los elementos.
    -No puede repetirse ningún elemento.
    -No puede haber dos consecutivas.
    -No puede haber dos consecutivas.
    -No puede haber dos consecutivas.


    Por ejemplo sería un conjunto válido pero no lo sería por tener dos esquinas consecutivas.

    Tras estar un buen rato haciendo cuentas me sale (y espero no haberme equivocado en ningún número) que hay un total de 1408 conjuntos de 4 elementos. No obstante hice las cuentas un poco "a la vieja" como se dice, y no encontré ningún patrón general para poder calcular los conjuntos de más elementos que naturalmente es una burrada calcular a pelo.


    ¿Alguien se anima a pensarlo?

    Todo surgió de mi pregunta de cuán seguro es dicho método de bloqueo para móviles
    Última edición por angel relativamente; 23/09/2013, 13:49:40. Motivo: Cambiar grupo por conjunto
    [TEX=null]k_BN_A \cdot \dst \sum_{k=0}^{\infty} \dfrac{1}{k!} \cdot 50 \cdot 10_{\text{hex}} \cdot \dfrac{2\pi}{\omega} \cdot \sqrt{-1} \cdot \dfrac{\dd x} {\dd t } \cdot \boxed{^{16}_8\text{X}}[/TEX]
    Etiquetas: combinatoria, estadística, ingenio, matemáticas
  • #2
    Re: Reto de los patrones

    Yo también dividí esa pantalla en los mismos grupos, vértice, pared vertical, pared horizontal y centro, y vi que tenían en común la matriz de elementos a los que podían acceder en caso de no existir ningún movimiento previo.

    Así, usando una notación de subíndices del 0 al 8 (de izquierda a derecha), esta era:
    Para los vértices: [1,3,4,5,7]
    Para los LV: [0,1,2,4,6,7,8]
    Para los LH: [0,2,3,4,5,6,8]
    Para el centro: [0,1,2,3,5,6,7,8]

    Se me ocurrió también que los posibles caminos que podía tomar el patrón podían subdividirse en: vías que el patrón siempre puede tomar, y vías que solo puede tomar en función del camino ya recorrido.

    He intentado crear un programa que tenga en cuenta las premisas que explicitas, pero con mis precarios conocimientos de programación (y para rematar solo sé hacerlo en Java), solo he logrado escribir un armatoste que lleva 4 bucles inscritos y que me devuelve las permutaciones iniciales (sin condiciones restrictivas y según la fórmula ) ligeeeramente modificadas , cuando creo que tendrían que reducirse bastante, a poco más de la mitad, teniendo en cuenta todas las "normas" dependientes de la posición de cada punto.

    Además investigué un poco y descubrí que también es legal ir de un punto a su simétrico (tanto en horizontal y en vertical como en diagonal), pasando de nuevo por el punto intermedio pero sin que este se vuelva a seleccionar, cosa que lo complica de nuevo (así por ejemplo, sería legal hacer la combinación {1,4,5,3}. Es la historia de nunca acabar...
    Última edición por InesIncinerate; 23/09/2013, 16:41:34.
    "Extravaga, hijo mío, extravaga cuanto puedas, que más vale eso que vagar a secas." -Miguel de Unamuno

    Comentario

    • #3
      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.

      Comentario

      • #4
        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:

        Código:
        #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;
}
        Última edición por abuelillo; 23/09/2013, 17:02:57.
        \left\vert{ \Psi_{UNIVERSE} }\right> = \sum \alpha_i \left\vert{ \Psi_{WORLD_i} }\right> \text{ } \hspace{3 mm} \sum \left\vert{} \alpha_i \right\vert{}^2 = 1

        Comentario

        • #5
          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.

          Comentario

          • #6
            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 ).
            "Extravaga, hijo mío, extravaga cuanto puedas, que más vale eso que vagar a secas." -Miguel de Unamuno

            Comentario

            • #7
              Re: Reto de los patrones

              Escrito por InesIncinerate Ver mensaje
              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.
              Última edición por Weip; 23/09/2013, 19:02:20.

              Comentario

              • #8
                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
                Última edición por Physicist; 23/09/2013, 19:05:32.
                Y Dios dijo: \vec{\nabla} \cdot \vec{E} = \frac{\rho}{\epsilon_0} ; \vec{\nabla} \cdot \vec{B} = 0 ; \vec{\nabla} \times \vec{E} = -\frac{\partial \vec{B}}{\partial t } ; \vec{\nabla} \times \vec{B} = \mu_0\vec J + \mu_0 \epsilon_0 \frac{\partial \vec{E}}{\partial t } ...y se hizo la luz

                Comentario

                • #9
                  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/
                  "Extravaga, hijo mío, extravaga cuanto puedas, que más vale eso que vagar a secas." -Miguel de Unamuno

                  Comentario

                  • #10
                    Re: Reto de los patrones

                    Escrito por InesIncinerate Ver mensaje
                    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.
                    \left\vert{ \Psi_{UNIVERSE} }\right> = \sum \alpha_i \left\vert{ \Psi_{WORLD_i} }\right> \text{ } \hspace{3 mm} \sum \left\vert{} \alpha_i \right\vert{}^2 = 1

                    Comentario

                    • #11
                      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
                      Y Dios dijo: \vec{\nabla} \cdot \vec{E} = \frac{\rho}{\epsilon_0} ; \vec{\nabla} \cdot \vec{B} = 0 ; \vec{\nabla} \times \vec{E} = -\frac{\partial \vec{B}}{\partial t } ; \vec{\nabla} \times \vec{B} = \mu_0\vec J + \mu_0 \epsilon_0 \frac{\partial \vec{E}}{\partial t } ...y se hizo la luz

                      Comentario

                      • #12
                        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


                        Código:
                        /* 
 * 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; 
}
                        \left\vert{ \Psi_{UNIVERSE} }\right> = \sum \alpha_i \left\vert{ \Psi_{WORLD_i} }\right> \text{ } \hspace{3 mm} \sum \left\vert{} \alpha_i \right\vert{}^2 = 1

                        Comentario

                        • #13
                          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.
                          "Extravaga, hijo mío, extravaga cuanto puedas, que más vale eso que vagar a secas." -Miguel de Unamuno

                          Comentario

                          • #14
                            Re: Reto de los patrones

                            Escrito por InesIncinerate Ver mensaje
                            ¡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:

                            Código:
                            // 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
                            Última edición por abuelillo; 25/09/2013, 22:54:15.
                            \left\vert{ \Psi_{UNIVERSE} }\right> = \sum \alpha_i \left\vert{ \Psi_{WORLD_i} }\right> \text{ } \hspace{3 mm} \sum \left\vert{} \alpha_i \right\vert{}^2 = 1
                            • 3 gracias

                            Comentario

                            • #15
                              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í .
                              "Extravaga, hijo mío, extravaga cuanto puedas, que más vale eso que vagar a secas." -Miguel de Unamuno

                              Comentario

                              Anterior 1 2 template Siguiente

                              Contenido relacionado

                              Colapsar
                              Trabajando...
                              X