La mayoría de los teléfonos inteligentes con Android permiten al usuario usar un patrón deslizante para abrir su teléfono:
Ciertos patrones son legítimos y otros son imposibles. Dado un patrón de deslizamiento de entrada, devuelve un verdadero o falso que indica si el patrón de entrada dado es legal o no.
Entrada
La cuadrícula está etiquetada en fila 1 a 9:
1 2 3
4 5 6
7 8 9
La entrada es un número compuesto por los nodos visitados del primero al último. Por ejemplo, el patrón de deslizamiento anterior es 12357.
La entrada puede ser un número decimal, una cadena o una lista de números. No contendrá 0 porque no hay nodo 0.
Enmienda: la indexación 0-8 está permitida ya que muchos idiomas indexan desde 0. Si usa 0-8, será necesario indicarlo como tal al comienzo de su respuesta y ajustar los casos de prueba en consecuencia.
Reglas
Cada nodo comienza como no visitado inicialmente y solo se puede visitar una vez. Cualquier patrón que visite un nodo más de una vez es falso.
Un patrón verdadero debe contener al menos un deslizamiento, por lo que un mínimo de 2 nodos.
No es posible omitir un nodo no visitado directamente en línea con otro. Por ejemplo, 13 es falso porque 2 no está visitado y está directamente en línea.
Solo es posible omitir un nodo visitado. 42631 es un ejemplo de esto.
Las líneas pueden cruzarse de otra manera. Por ejemplo, 1524 es verdad.
Suponga que los anchos de los nodos son insignificantes e ignoran los problemas prácticos (grosor de los dedos, etc.). Por lo tanto, 16 es verdadero a pesar de que puede ser un poco más difícil de lograr en la realidad.
Casos de prueba
1 -> false
12 -> true
13 -> false
16 -> true
31 -> false
33 -> false
137 -> false
582 -> true
519 -> true
1541 -> false
12357 -> true
15782 -> true
19735 -> false
42631 -> true
157842 -> true
167294385 -> true
297381645 -> false
294381675 -> true
Este es el código de golf , por lo que gana la menor cantidad de bytes.
fuente
Respuestas:
JavaScript (ES6), 64 bytes
Toma la entrada como una matriz de números. Los valores de falsa son 0 o NaN . Los valores de verdad son enteros estrictamente positivos.
Casos de prueba
Mostrar fragmento de código
¿Cómo?
Preámbulo
Dos dígitos son opuestos vertical, horizontal o diagonalmente si:
O ambos son pares y su suma es 10 (figura 2)
Además, el dígito que se encuentra entre dos dígitos opuestos n y p es igual a (n + p) / 2 .
Código fuente formateado
Realizar un seguimiento de los dígitos anteriores
Las banderas para los dígitos visitados se almacenan en índices negativos en la matriz de entrada a , para que no choquen con sus elementos originales.
Si p se establece en -n :
Si el dígito actual n no se seleccionó previamente,
a[-n] ^= -n
establecerá el indicador y permitirá que elevery()
ciclo continúe con la siguiente iteración. De lo contrario, borrará la bandera y forzará al bucle a fallar inmediatamente.Si p se establece en indefinido :
a[undefined] ^= undefined
da como resultado 0 , que también obliga al ciclo a fallarDetectar dígitos opuestos
La siguiente expresión se usa para probar si el dígito actual n y el dígito anterior -p son dígitos opuestos, como se define en el preámbulo:
que es equivalente a:
Nota: En JS, el resultado del módulo tiene el mismo signo que el dividendo.
Se puede interpretar como:
Por lo tanto, esta expresión devuelve 1 si y sólo si n y p se oponen dígitos o que son el mismo dígito impar. Debido a que un dígito no se puede seleccionar dos veces, este último caso se soluciona correctamente de todos modos.
Si esta expresión devuelve 1 , probamos un [p / 2] (donde p ahora es igual a la suma negada de los dígitos) para saber si el 'dígito intermedio' fue visitado previamente. De lo contrario, probamos un [0] que se garantiza que es verdadero.
Sobre la primera iteración
La primera iteración es un caso especial, ya que no hay un dígito anterior y queremos que sea incondicionalmente exitoso.
Lo conseguimos inicializando p en 1 , porque para cualquier n en [1 .. 9] :
(1 * n) % 5
no puede ser negativo~(1 - n)
no puede ser igual a 9Respuesta original, 90 bytes.
Eliminado de esta publicación para que no se vuelva demasiado detallado. Puedes verlo aquí .
fuente
!!a[1]&
cona[1]&&
, ya que cualquier valor verdadero puede ser devueltoa[1]*
es aún más corto.)has a node directly in line
, no me di cuenta de que sería tan simple ...?a[-n]^=1:0
con&&a[-n]^=1
de -1, no se puede probar (en el móvil)Código de máquina x86 de 32 bits,
6260 bytesHexdump:
Recibe la longitud de la lista
ecx
y un puntero al primer elementoedx
, y devuelve el resultado enal
:Hay 8 líneas que contienen un nodo en el medio:
Los agrupé de acuerdo con la diferencia entre el número más grande y el más pequeño.
Luego, lo convertí en una tabla de búsqueda 2-D indexada por media diferencia y un número menor:
Esto hace un mapa de bits "mágico" de 32 bits. Para indexarlo, el código lo empuja a la pila. Luego, extrae un byte usando un índice, y de ese byte, extrae un bit usando el otro índice. Todo esto usando una sola instrucción:
Si el mapa de bits indica que hay un nodo en el medio, es fácil de calcular: agregue la mitad de la diferencia al número más pequeño.
Fuente de montaje:
fuente
bt byte ptr [esp + eax], ebx
.cdq
lugar dexor edx, edx
comoeax
es cero. Además, se puede doblar ladec eax
enbt [esp + eax - 1], ebx
que es la misma longitud, pero a continuación le permite quitar lainc ebx
tarde. Esto debería ahorrarte dos bytes.Python 2 ,
14013111410499 bytes-2 bytes gracias a Jonathan Frech
-5 bytes gracias a Chas Brown
Pruébalo en línea!
Explicación:
Pruébalo en línea!
Solo 8 pares de nodos tienen un nodo entre ellos. La fórmula puede representar un par de nodos como un entero entero
2^a-2^b-1
. Este número puede acortarse mediante un módulo repetido:(2**n+~2**l)%21%15%9==5
primero comprueba si tal par está presente, luegov-{l+n>>1}==v
comprueba si el nodo intermedio, que está dado por(a+b)/2
, no fue visitado todavía yq
genera un NameError. Al usar la comparación encadenada entre estos pares, la siguiente comparación solo se ejecuta cuando regresó la anteriorTrue
.fuente
Jalea ,
24 22 1918 bytes-2 ya que ya no estamos obligados a manejar una lista vacía
-1 cambiar de unir,
j@
para concatenar,;
(el elemento perdido no necesita encontrarse en el medio para el método empleado, estar al comienzo del trío está bien )-2 cambiar de
P¬aSH
aoSH
(OK para tener dos resultados ya que aplanar, medio de1
es0.5
que se filtra fuera de todos modos, y que tiene múltiples resultados iguales no tiene efecto en el método empleado tampoco)-1 Gracias al Sr. Xcoder (0-indexado se permite la entrada)
Un enlace monádico que toma una lista de enteros
[0,8]
y devuelve un valor verdadero (1
) si es legal y un valor falso (0
) si no.Pruébalo en línea! o ver un conjunto de pruebas .
¿Cómo?
Mira cada par adyacente de nodos indexados a 0 en la lista de entrada. Si la división de enteros entre tres de los dos difiere en 2, están en las filas superior e inferior, si el módulo entre tres de los dos difiere en 2, están en las columnas izquierda y derecha. La suma de tales pares divididos por dos es el nodo medio indexado en 0 de una línea de tres nodos o un valor no entero, por lo que estos valores se insertan primero delante del par indexado en 0 y luego cualquier nodos falsos (como
0.5
o3.5
) se eliminan, la lista de listas resultante se aplana y luego se desduplica (para obtener entradas únicas y preservadas por orden) y finalmente se compara con la entrada; para un deslizamiento legal, todo esto terminará siendo un no operativo mientras ilegal las unidades agregarán nodos medios faltantes y / o eliminarán nodos duplicados (tenga en cuenta que no se requiere una carcasa especial para una lista de entrada de longitud 1 ya que no tiene pares adyacentes):Método anterior
Gelatina ,
3635 bytesPruébalo en línea! o ver un conjunto de pruebas .
¿Cómo?
Similar a lo anterior, pero construye todas las posibilidades de línea de tres nodos y realiza una búsqueda (en lugar de verificar a medida que avanza usando divmod para probar y reducir a la mitad la suma para el nodo medio).
En primer lugar, la construcción de la lista de líneas de tres nodos:
Ahora la toma de decisiones:
fuente
Stax , 28 bytes
Ejecutarlo
Produce 0 para falso y enteros positivos para verdadero. La representación ascii correspondiente del mismo programa es esta.
La idea general es calcular varias condiciones necesarias para los patrones de deslizamiento legales y multiplicarlos todos juntos.
fuente
Y
registro.v
e incluirlo1
como valor falso.2
y arriba son verdaderas.JavaScript, 112 bytes
Quizás algún lenguaje basado en expresiones regulares debería ser más corto. Pero no lo se.
Mostrar fragmento de código
Gracias a Neil, cambie
)(?!
para|
guardar 3 bytes.fuente
144
.Retina 0.8.2 , 98 bytes
Influenciado por la respuesta de tsh . Traté de "reformularlo" para que sea lo contrario, haciendo coincidir los deslizamientos no válidos, luego Anti-grepping.
Pruébalo en línea
fuente
Casco ,
2520 bytesToma una lista de enteros con indexación basada en 0. Devuelve 0 o 1. ¡ Pruébelo en línea!
Explicación
Robé algunas ideas de la respuesta Jelly de Jonathan Allan . La idea es la misma: inserte un nuevo "nodo promedio" entre cada par adyacente, filtre los que no son nodos reales, elimine los duplicados y compárelos con la lista original. Si la lista original contiene duplicados, el resultado es falso. Si la lista omite un nodo no visitado, entonces está presente en la lista procesada entre el par correspondiente, y el resultado es falso. Si la entrada es un singleton, la lista procesada está vacía y el resultado es falso. De lo contrario, es verdad.
fuente
C ++,
267256 bytesPara verificar si el patrón no salta sobre un nodo no visitado, hace varias cosas:
d
dónded
está la diferencia numérica entre el nodo actual y el último nodo.d
es extraño, entonces no hay necesidad de verificarlo, no puede saltarse un nodo.d
es igual a4
o8
, entonces el salto es entre nodos1-9
o3-7
, así que verifique el nodo5
d
es 2 y el nodo medio ((last_node + current_node)/2
) es 2,5 u 8, compruebe el nodo mediod
es 6, comprobar misma que antes, pero con4
,5
o6
Los parámetros son un
int[]
y su recuento de elementos. Devuelve unint
que se puede interpretar como unbool
tipofuente
!(d%2)
=>d%2<1
debería funcionar.int s[]
=>int*s
. Creo que eso funcionará.Perl, 135 bytes (134 +
-n
)Versión ligeramente no golf
Salidas a través del código de salida.
0
es verdad, cualquier otro valor es falso. Según el meta consenso , se ignora la salida STDERR en el caso de falla.Probablemente haya una forma más rápida de verificar la regla "no se puede saltar" que simplemente enumerar todas las posibilidades.
fuente
MATL ,
424139 bytesEsto produce
Aquí puede leer por qué estas salidas son respectivamente verdadero y falso. Pruébalo en línea!
O verifique todos los casos de prueba , con un código de pie de página que incluya la prueba estándar de veracidad / falsedad.
fuente
Stax ,
73726665 bytes CP43779 bytes cuando está desempaquetado,
Ejecutar y depurar en línea!
o ejecute la prueba por lotes , donde
meX
hay un encabezado para que Stax pueda procesar la entrada de varias líneas.Implementación sin usar hash. Número estrictamente positivo de resultados (en realidad, el número de pruebas fallidas) para casos falsos y
0
para casos verdaderos .Explicación
d
borra la pila de entrada. La entrada está en variable dex
todos modos.4{cAs-5F
genera la primera parte de la lista de nodos medios.132396978714EE
codifica la segunda parte de la lista de nodos medios.L3/
Recopila todos los elementos en la pila principal y se divide en partes, cada una de las cuales contiene 3 elementos, el resultado es una matriza
, que es solo la matriz de todos los grupos de 3 nodos no válidos.{xs:IBc0<A*++cEd:-1=sccHs|M=s{U>m|A**mE
Para cada lista de nodos no válidos, realice las siguientes verificaciones. El resultado de los resultados de la verificación seand
edita utilizando el**
. Como hay 8 listas de nodos no válidas, el resultado de este código será una matriz de 8 elementos. El últimoE
despacha la matriz a sus elementos individuales en la pila principal.xs:I
obtener el índice de los elementos de la lista de nodos en la matriz de entrada.Bc0<A*++
Si el índice de "nodo intermedio" (por ejemplo,5
en el conjunto de nodos1,5,9
) es-1
(lo que significa que no existe en la matriz de entrada), cambie el índice a9
.cEd:-1=
pruebe si los dos "nodos terminales" (por ejemplo,1,5
en el conjunto de nodos1,5,9
) son adyacentes en la matriz de entrada.sccHs|M=
compruebe si el índice transformado del "nodo intermedio" es mayor que el de los dos "nodos terminales", que incluye dos casos: falta el "nodo intermedio" o el "nodo intermedio" aparece después de los dos "nodos terminales"s{U>m|A
prueba si ambos índices de los "nodos finales" no son negativos. (es decir, ambos aparecen en la entrada).Se realizan dos pruebas adicionales,
x%2<
prueba si la matriz de entrada es un singleton.xu%x%=!
prueba si son nodos que han sido visitados dos veces.Hay 10 resultados de prueba en la pila principal (uno para cada una de las listas de nodos no válidos, más dos pruebas adicionales).
L|+
recoge los 10 elementos y los agrega.|a
también podría haberse usado para verificar simplemente si hay elementos verdaderos en la matriz.Salida implícita.
fuente
Java,
375355 bytes-20 bytes gracias a Zacharý
Este es un puerto de esta respuesta y funciona con los mismos principios
fuente
int v(int s[]){int[]m=new int[10];int i=1,p=s[0],d,n,l=s.length;if(l<2)return 0;for(;i<l;++i){m[p]=1;if(m[s[i]]!=0)return 0;d=(d=p-s[i])<0?-d:d;if(d%2==0){n=(p+s[i])/2;if((d==4||d==8)&&n==5&&m[5]==0)return 0;if((d==2)&&(n==2&&m[2]==0||n==5&&m[5]==0||n==8&&m[8]==0))return 0;if(d==6&&(n==4&&m[4]==0||n==5&&m[5]==0||n==6&&m[6]==0))return 0;}p=s[i];}return 1;}
debería funcionar (orden de operaciones)(d==2)
a justod==2
, lo pasé por alto antes.d%2==0
=>d%2<1
Pyth , 33 bytes
Banco de pruebas.
Utiliza indexación basada en 0.
Explicación
Enfoque alternativo para 34 bytes :
fuente
Japt , 35 bytes
Pruébalo en línea!
Ligeramente poco golfista y cómo funciona
Porté la idea de esta solución Jelly , con alguna diferencia en la determinación de posibles saltos:
/3
o%3
.%3
y verifica si la diferencia es 0 o 2. Si la diferencia es 0, las dos celdas están alineadas verticalmente y los no saltos aún comparten la propiedad de(X+Y)%2 != 0
.fuente
Python 2 , 97 bytes
Basado en la respuesta de los ovs pero 2 bytes más cortos y menos crípticos. Simplemente convierte índices a coordenadas 2D y prueba la paridad. Asume 0-8 índices.
Pruébalo en línea!
fuente