Página 1 de 2 12 ÚltimoÚltimo
Resultados 1 al 15 de 17

Hilo: Reto de los patrones

  1. #1
    Registro
    Feb 2010
    Ubicación
    Elementos 5,6,7
    Posts
    2 715
    Nivel
    Grado en Física
    Artículos de blog
    11
    ¡Gracias!
    1 150 (1 030 msgs.)

    Predeterminado 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

    \begin{pmatrix} E_1 & LV_1 & E_2 \\ LH_1 & C & LH_2 \\ E_3 & LV_2 & E_4 \end{pmatrix}

    Las letras representan E=\text{esquina}, \quad LV=\text{lado vertical}, \quad Lh= \text{lado horizontal}, \quad C=\text{.... 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 E consecutivas.
    -No puede haber dos LH consecutivas.
    -No puede haber dos LV consecutivas.


    Por ejemplo \{ E_1 , C , E_3 , LH_2 , E_4 , LH_1\} sería un conjunto válido pero \{ C, E_2 , E_4 , LV_2 \} 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 a las 12:49:40. Razón: Cambiar grupo por conjunto
    k_BN_A \cdot \dst \sum_{k=0}^{\infty} \dfrac{1}{k!} \cdot 50 \cdot 10_{\text{hex}} \cdot \dfrac{2...

  2. #2
    Registro
    Apr 2012
    Ubicación
    Barcelona
    Posts
    72
    Nivel
    Grado en Física
    ¡Gracias!
    18 (16 msgs.)

    Predeterminado 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 P=\frac{n!}{(n-r)!}) 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 a las 15:41:34.
    "Extravaga, hijo mío, extravaga cuanto puedas, que más vale eso que vagar a secas." -Miguel de Unamuno

  3. #3
    Registro
    Nov 2011
    Ubicación
    Barcelona
    Posts
    1 827
    Nivel
    Universidad (Matemáticas)
    Artículos de blog
    6
    ¡Gracias!
    987 (854 msgs.)

    Predeterminado 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.
    \dst\oint_S \vec{E} \cdot \dd \vec{S}=\dst\frac{Q}{\epsilon_0}

  4. #4
    Registro
    Mar 2013
    Posts
    286
    Nivel
    Secundaria
    ¡Gracias!
    122 (109 msgs.)

    Predeterminado 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 a las 16:02:57.
     \left\vert{     \Psi_{UNIVERSE}       }\right>  = \sum \alpha_i   \left\vert{     \Psi_{WORLD_i}...

  5. #5
    Registro
    Mar 2012
    Posts
    10
    Nivel
    Secundaria
    ¡Gracias!
    1 gracias

    Predeterminado 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.

  6. #6
    Registro
    Apr 2012
    Ubicación
    Barcelona
    Posts
    72
    Nivel
    Grado en Física
    ¡Gracias!
    18 (16 msgs.)

    Predeterminado 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

  7. #7
    Registro
    Nov 2011
    Ubicación
    Barcelona
    Posts
    1 827
    Nivel
    Universidad (Matemáticas)
    Artículos de blog
    6
    ¡Gracias!
    987 (854 msgs.)

    Predeterminado Re: Reto de los patrones

    Cita 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 a las 18:02:20.
    \dst\oint_S \vec{E} \cdot \dd \vec{S}=\dst\frac{Q}{\epsilon_0}

  8. #8
    Registro
    Aug 2012
    Ubicación
    Barcelona - Bilbao
    Posts
    129
    Nivel
    Grado en Física
    ¡Gracias!
    41 (41 msgs.)

    Predeterminado 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 a las 18: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

  9. #9
    Registro
    Apr 2012
    Ubicación
    Barcelona
    Posts
    72
    Nivel
    Grado en Física
    ¡Gracias!
    18 (16 msgs.)

    Predeterminado 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

  10. #10
    Registro
    Mar 2013
    Posts
    286
    Nivel
    Secundaria
    ¡Gracias!
    122 (109 msgs.)

    Predeterminado Re: Reto de los patrones

    Cita 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}...

  11. #11
    Registro
    Aug 2012
    Ubicación
    Barcelona - Bilbao
    Posts
    129
    Nivel
    Grado en Física
    ¡Gracias!
    41 (41 msgs.)

    Predeterminado 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

  12. #12
    Registro
    Mar 2013
    Posts
    286
    Nivel
    Secundaria
    ¡Gracias!
    122 (109 msgs.)

    Predeterminado 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}...

  13. #13
    Registro
    Apr 2012
    Ubicación
    Barcelona
    Posts
    72
    Nivel
    Grado en Física
    ¡Gracias!
    18 (16 msgs.)

    Predeterminado 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

  14. #14
    Registro
    Mar 2013
    Posts
    286
    Nivel
    Secundaria
    ¡Gracias!
    122 (109 msgs.)

    Predeterminado Re: Reto de los patrones

    Cita 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 a las 21:54:15.
     \left\vert{     \Psi_{UNIVERSE}       }\right>  = \sum \alpha_i   \left\vert{     \Psi_{WORLD_i}...

  15. 3 usuarios dan las gracias a abuelillo por este mensaje tan útil:

    angel relativamente (26/09/2013),InesIncinerate (26/09/2013),Physicist (27/09/2013)

  16. #15
    Registro
    Apr 2012
    Ubicación
    Barcelona
    Posts
    72
    Nivel
    Grado en Física
    ¡Gracias!
    18 (16 msgs.)

    Predeterminado 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

Página 1 de 2 12 ÚltimoÚltimo

Información del hilo

Usuarios viendo este hilo

Ahora hay 1 usuarios viendo este hilo. (0 miembros y 1 visitantes)

Hilos similares

  1. Globo y copas reto
    Por juang en foro Experimentos caseros
    Respuestas: 1
    Último mensaje: 06/03/2011, 20:39:47
  2. Secundaria Patrones primarios en la separación de pigmentos.
    Por sanzpa5 en foro Química analítica
    Respuestas: 0
    Último mensaje: 29/11/2010, 23:14:52
  3. Patrones de medida
    Por habiles en foro Unidades y análisis dimensional
    Respuestas: 11
    Último mensaje: 23/04/2010, 11:45:07
  4. 1r ciclo ¿Un reto?
    Por KyAlOx en foro Electromagnetismo
    Respuestas: 5
    Último mensaje: 30/06/2008, 22:00:04
  5. 2o ciclo [Ayuda] Acerca de Indexacion de Patrones de Difraccion
    Por c0lo en foro Física avanzada
    Respuestas: 4
    Último mensaje: 20/06/2008, 15:14:02

Etiquetas para este hilo

Permisos de publicación

  • No puedes crear hilos
  • No puedes responder
  • No puedes adjuntar archivos
  • No puedes editar tus mensajes
  •