Digamos que viste a tu amigo ingresar su contraseña en su teléfono Android. No recuerdas cómo hicieron el patrón, pero recuerdas cómo se ve el patrón. Siendo el amigo preocupado que eres, quieres saber qué tan segura es su contraseña. Su trabajo es calcular todas las formas en que se puede hacer un patrón particular.

Cómo funcionan los patrones de Android

Los patrones se dibujan en una cuadrícula de nodos 3x3. En un patrón, se visita una serie de nodos sin levantar el dedo de la pantalla. Cada nodo que visitan está conectado al nodo anterior por un borde. Hay dos reglas a tener en cuenta.

• No puede visitar ningún nodo más de una vez

• Un borde no puede pasar a través de un nodo no visitado

Tenga en cuenta que, aunque generalmente es muy difícil de realizar y, por lo tanto, no es muy común en combinaciones reales de bloqueo de Android, es posible moverse como un Caballero . Es decir, es posible moverse de un lado a una esquina no adyacente o al revés. Aquí hay dos ejemplos de patrones que emplean tal movimiento:

Aquí hay un Gif animado de lo que se está realizando.

Resolviendo un patrón

Un patrón típico podría verse así:

Con un patrón simple como este, hay dos formas en que dos dibujan el patrón. Puede comenzar en cualquiera de los dos extremos sueltos y viajar a través de los nodos resaltados al otro. Si bien esto es cierto para muchos patrones, particularmente los que los seres humanos emplean típicamente, esto no es cierto para todos los patrones.

Considere el siguiente patrón:

Hay dos soluciones inmediatamente reconocibles. Uno que comienza en la esquina superior izquierda:

Y uno que comienza en el centro inferior:

Sin embargo, debido a que una línea puede pasar a través de un punto una vez que ya se ha seleccionado, hay un patrón adicional que comienza en la parte superior central:

Este patrón particular tiene 3 soluciones, pero los patrones pueden tener entre 1 y 4 soluciones ^{[cita requerida]} .

Aquí hay algunos ejemplos de cada uno:

1)

2)

3)

4)

I / O

Un nodo puede representarse como los enteros de cero a nueve inclusive, sus equivalentes de cadena o los caracteres de a a i (o de A a I). Cada nodo debe tener una representación única de uno de estos conjuntos.

Una solución estará representada por un contenedor ordenado que contiene representaciones de nodos. Los nodos deben ordenarse en el mismo orden en que se pasan.

Un patrón estará representado por un contenedor desordenado de pares de nodos. Cada par representa un borde que comienza a conectar los dos puntos en el par. Las representaciones de patrones no son únicas.

Tomará una representación de patrón como entrada a través de métodos de entrada estándar y generará todas las soluciones posibles que crean el mismo patrón a través de métodos de salida estándar.

Puede suponer que cada entrada tendrá al menos una solución y conectará al menos 4 nodos.

Puede optar por utilizar un contenedor ordenado en lugar de uno no ordenado, si así lo desea o se ve obligado por la selección de idioma.

Casos de prueba

Con los nodos dispuestos en el siguiente patrón:

0 1 2
3 4 5
6 7 8

Sea {...}un contenedor desordenado, [...]sea ​​un contenedor ordenado y (...)sea ​​un par.

Las siguientes entradas y salidas deben coincidir

{(1,4),(3,5),(5,8)} -> {[1,4,3,5,8]}
{(1,4),(3,4),(5,4),(8,5)} -> {[1,4,3,5,8]}
{(0,4),(4,5),(5,8),(7,8)} -> {[0,4,5,8,7],[7,8,5,4,0]}
{(0,2),(2,4),(4,7)} -> {[0,1,2,4,7],[1,0,2,4,7],[7,4,2,1,0]}
{(0,2),(2,6),(6,8)} -> {[0,1,2,4,6,7,8],[1,0,2,4,6,7,8],[8,7,6,4,2,1,0],[7,8,6,4,2,1,0]}
{(2,3),(3,7),(7,8)} -> {[2,3,7,8],[8,7,3,2]}
{(0,7),(1,2),(1,4),(2,7)} -> {[0,7,2,1,4],[4,1,2,7,0]}
{(0,4),(0,7),(1,3),(2,6),(2,8),(3,4),(5,7)} -> {[1,3,4,0,7,5,8,2,6]}
{(1,3),(5,8)} -> {}

Un álbum imgur de todos los casos de prueba como imágenes se puede encontrar aquí . Los patrones están en soluciones azules en rojo.

Tanteo

Este es el código de golf. Pocos bytes ganan.

Python 2.7, 493 430 bytes

exec("L=['012','345','678','036','147','258','048','246'];L+=[i[::-1]IL];S=sorted;F=lambda t:''.join(str(i)It)\ndef N(x):\n s=' '.join(F(S(i))Ix)\nIL:s=s.replace(i[::2],i[:2]+' '+i[1:])\n return S(set(s.split()))\ndef P(s):\n e=0\nIL:e|=-1<s.find(i[::2])<s.find(i[1])\n return[zip(s[:-1],s[1:]),L][e]\nx=N(input());print[F(i)I__import__('itertools').permutations({iI`x`if i.isdigit()})if x==N(P(F(i)))]".replace('I',' for i in '))

La versión de una sola línea envuelve el programa exec("...".replace('I',' for i in '))para que todos los bucles for y generadores se puedan acortar con una sola Iy ahorra 15 bytes en esta versión más legible:

L=['012','345','678','036','147','258','048','246'];L+=[i[::-1]for i in L]
S=sorted;F=lambda t:''.join(str(i)for i in t)
def N(x):
 s=' '.join(F(S(i))for i in x)
 for i in L:s=s.replace(i[::2],i[:2]+' '+i[1:])
 return S(set(s.split()))
def P(s):
 e=0
 for i in L:e|=-1<s.find(i[::2])<s.find(i[1])
 return[zip(s[:-1],s[1:]),L][e]
x=N(input())
print[F(i)for i in __import__('itertools').permutations({i for i in`x`if i.isdigit()})if x==N(P(F(i)))]

El programa toma la entrada de la manera que se muestra (p {(1,4),(3,4),(5,4),(8,5)}. Ej. ) O como una lista de cadenas (p ['14','34','54','85']. Ej. ) (O en otros formatos compatibles con Python) y devuelve la salida como una lista de cadenas. Entonces técnicamente tenemos un contenedor ordenado de contenedores ordenados.

La función Nnormaliza un patrón para poder comparar fácilmente dos patrones. La normalización clasifica los pares que denotan bordes (en '02'lugar de '20'), usa el reemplazo de cadena para expandir los bordes dobles (por ejemplo, se '02'convierte '01 12'), divide los bordes en un conjunto para eliminar duplicados y ordena el resultado.

La función Faplana las tuplas de ints / strings a strings, por lo que podemos normalizar las rutas producidas de diferentes maneras.

La lista Lcontiene todas las líneas en la pantalla.

Luego tomamos cada permutación de todos los dígitos en el patrón normalizado y calculamos una ruta válida o Lsi no es válida (que nunca se normaliza a la lista de pares como lo harían las rutas reales), o una lista de pares que indica que los nodos de orden son visitados si es válido. Si esto se normaliza con el mismo patrón, entonces tenemos una solución válida y la incluimos en la lista final.

La comprobación principal necesaria para validar una permutación como una cadena ses -1<s.find(i[::2])<s.find(i[1]), que detecta un error con una línea i. Por ejemplo, con la línea, '210'el código detecta un error si '20'ocurre (es decir, su índice es mayor que -1) y '1'ocurre después de él. No tenemos que preocuparnos de que no ocurra 1 porque el 1 aparecerá en el patrón normalizado cuando no estaba en la entrada.

NOTA: Sé que reemplazar str(i)for i in t con map(str,t) y {i for i in`x`if i.isdigit()} con set('012345678')&set(`x`) acortaría el código original, pero esto aún sería un poco más largo que la sustitución I .