¿Mi patrón de deslizamiento es legal?

154

La mayoría de los teléfonos inteligentes con Android permiten al usuario usar un patrón deslizante para abrir su teléfono:

patrón de bloqueo

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 , por lo que gana la menor cantidad de bytes.

Stanri
fuente
2
Relacionado.
Martin Ender
¿Se garantiza que la lista de entrada no está vacía?
Zgarb
@ Zgarb sí. No será vacío.
stanri
Pregunta matemática relacionada: math.stackexchange.com/questions/205049/…
Pureferret

Respuestas:

69

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.

a=>a[p=1]*a.every(n=>a[p=a[n&p&p*n%5<0|~(p-=n)==9&&p/2]&&-n]^=p)

Casos de prueba

¿Cómo?

Preámbulo

Dos dígitos son opuestos vertical, horizontal o diagonalmente si:

  • Ambos son impares, diferentes entre sí y diferentes de 5 (figura 1)
  • O ambos son pares y su suma es 10 (figura 2)

    dígitos opuestos

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

a =>
  // force a falsy result if a[1] is undefined
  a[p = 1] *
  // walk through all values n in a[]
  a.every(n =>
    // access either a[-n] or a[undefined]
    a[
      // set p to either -n or undefined
      p =
        // read either a[0] or a[in_between_digit]
        a[
          n & p & p * n % 5 < 0 | ~(p -= n) == 9
          && p / 2
        ]
        && -n
    ]
    // toggle the flag
    ^= p
  )

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] ^= -nestablecerá el indicador y permitirá que el every()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] ^= undefinedda como resultado 0 , que también obliga al ciclo a fallar

Detectar 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:

n & p & ((p * n) % 5 < 0) | ~(p -= n) == 9

que es equivalente a:

n & p & ((p * n) % 5 < 0) | (p -= n) == -10

Nota: En JS, el resultado del módulo tiene el mismo signo que el dividendo.

Se puede interpretar como:

(n is odd AND -p is odd AND (neither -p or n is equal to 5)) OR (n + -p = 10)

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 9

Respuesta original, 90 bytes.

Eliminado de esta publicación para que no se vuelva demasiado detallado. Puedes verlo aquí .

Arnauld
fuente
-1 byte reemplazándolo !!a[1]&con a[1]&&, ya que cualquier valor verdadero puede ser devuelto
Herman L
@HermanLauenstein Gracias, eso parece estar bien. (Ahora, a[1]*es aún más corto.)
Arnauld
1
Estaba tratando desesperadamente de pensar en una fórmula para has a node directly in line, no me di cuenta de que sería tan simple ...
Neil
@Neil Al mirar el historial de revisiones de esta publicación, estoy seguro de que puedes darte cuenta de que tampoco me di cuenta de inmediato ... :)
Arnauld
Creo que se puede sustituir ?a[-n]^=1:0con &&a[-n]^=1de -1, no se puede probar (en el móvil)
Stan Strum
45

Código de máquina x86 de 32 bits, 62 60 bytes

Hexdump:

33 c0 60 8b f2 33 db 99 80 f9 02 72 2d ad 50 0f
ab c2 72 25 3b c3 77 01 93 2b c3 d1 e8 72 14 68
92 08 0e 02 0f a3 5c 04 ff 5f 73 07 03 d8 0f a3
da 73 06 5b e2 d7 61 40 c3 58 61 c3

Recibe la longitud de la lista ecxy un puntero al primer elemento edx, y devuelve el resultado en al:

__declspec(naked) bool __fastcall check(int length, const int* list)

Hay 8 líneas que contienen un nodo en el medio:

1 - 3
4 - 6
7 - 9
1 - 7
2 - 8
3 - 9
1 - 9
3 - 7

Los agrupé de acuerdo con la diferencia entre el número más grande y el más pequeño.

Diferencia 2: 3 líneas (comenzando en 1, 4 o 7)
    1 - 3
    4 - 6
    7 - 9
Diferencia 4: 1 línea (a partir de 3)
    3 - 7
Diferencia 6: 3 líneas (comenzando en 1, 2 o 3)
    1 - 7
    2 - 8
    3 - 9
Diferencia 8: 1 línea (a partir de 1)
    1 - 9

Luego, lo convertí en una tabla de búsqueda 2-D indexada por media diferencia y un número menor:

76543210
--------
10010010 - half-difference 1
00001000 - half-difference 2
00001110 - half-difference 3
00000010 - half-difference 4

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:

bt byte ptr [esp + eax - 1], ebx; // -1 because half-difference is 1-based

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:

    xor eax, eax;   // prepare to return false
    pushad;         // save all registers
    mov esi, edx;   // esi = pointer to input list
    xor ebx, ebx;   // ebx = previously encountered number = 0
    cdq;            // edx = bitmap of visited numbers = 0

    cmp cl, 2;      // is input list too short?
    jb bad_no_pop;  // bad!

again:
    lodsd;          // read one number
    push eax;

    bts edx, eax;   // check and update the bitmap
    jc bad;         // same number twice? - bad!

    cmp eax, ebx;   // sort two recent numbers (ebx = minimum)
    ja skip1;
    xchg eax, ebx;
skip1:

    // Check whether the line crosses a node
    sub eax, ebx;   // calculate half the difference
    shr eax, 1;
    jc skip_cross;  // odd difference? - no node in the middle

    push 0x020e0892;// push magic bitmap onto stack
    bt byte ptr [esp + eax - 1], ebx; // is there a node in the middle?
    pop edi;
    jnc skip_cross; // no - skip the check

    add ebx, eax;   // calculate the node in the middle
    bt edx, ebx;    // was it visited?
    jnc bad;        // no - bad!

skip_cross:
    pop ebx;
    loop again;

    // The loop was finished normally - return true
    popad;          // restore registers
    inc eax;        // change 0 to 1
    ret;            // return

    // Return false
bad:
    pop eax;        // discard data on stack
bad_no_pop:
    popad;          // restore registers
    ret;            // return
anatolyg
fuente
¡Agradable! Realmente me gusta esta bt byte ptr [esp + eax], ebx.
Arnauld
55
Es bueno ver la solución de ensamblaje :) Puede usar en cdqlugar de xor edx, edxcomo eaxes cero. Además, se puede doblar la dec eaxen bt [esp + eax - 1], ebxque es la misma longitud, pero a continuación le permite quitar la inc ebxtarde. Esto debería ahorrarte dos bytes.
Jester
Gracias por las ideas! Has asegurado tu lugar en el paraíso del golfista, si hay uno :)
anatolyg
55
Creo que todos podemos estar de acuerdo en que el paraíso de los golfistas es un infierno para todos los demás.
Adonalsium
19

Python 2 , 140 131 114 104 99 bytes

-2 bytes gracias a Jonathan Frech
-5 bytes gracias a Chas Brown

v={0};k=input()
for l,n in zip(k,k[1:])or q:(2**n+~2**l)%21%15%9==5<v-{l+n>>1}==v>q;v|={l};n in v>q

Pruébalo en línea!

Explicación:

# full program, raising a NameError for invalid input
v={0}            # set of visited nodes
k=input()        # load pattern
# iterate through adjacent pairs, if there is no pair, raise a NameError
for l,n in zip(k,k[1:])or q:
  # detect moves skipping over nodes, details below
  (2**n + ~2**l) % 21 % 15 % 9 == 5 < v - {l+n >> 1} == v > q
  v |= {l}       # add the last node to the set of visited nodes
  n in v > q     # if the current node was previously visited, raise a NameError

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:

a  b  2^a-2^b-1  (2^a-2^b-1)%21%15%9
1  3         -7                    5
1  7       -127                    5
1  9       -511                    5
2  8       -253                    5
3  1          5                    5
3  7       -121                    5
3  9       -505                    5
4  6        -49                    5
6  4         47                    5
7  1        125                    5
7  3        119                    5
7  9       -385                    5
8  2        251                    5
9  1        509                    5
9  3        503                    5
9  7        383                    5

(2**n+~2**l)%21%15%9==5primero comprueba si tal par está presente, luego v-{l+n>>1}==vcomprueba si el nodo intermedio, que está dado por (a+b)/2, no fue visitado todavía y qgenera un NameError. Al usar la comparación encadenada entre estos pares, la siguiente comparación solo se ejecuta cuando regresó la anterior True.

ovs
fuente
17

Jalea ,  24 22 19  18 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¬aSHa oSH(OK para tener dos resultados ya que aplanar, medio de 1es 0.5que 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)

d3ZIỊoSH;µƝFf9Ḷ¤Q⁼

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.5o3.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):

d3ZIỊoSH;µƝFf9Ḷ¤Q⁼ - left input is a list of integers   e.g. [3,4,7,1,2,8,3]
          µƝ       - perform the chain to the left for adjacent pairs:
                   - e.g. for [a,b] in:   [3,4]         [4,7]         [7,1]         [1,2]         [2,8]         [8,3]
 d3                -   divmod by 3        [[1,0],[1,1]] [[1,1],[2,1]] [[2,1],[0,1]] [[0,1],[0,2]] [[0,2],[2,2]] [[2,2],[1,0]]
   Z               -   transpose          [[1,1],[0,1]] [[1,2],[1,1]] [[2,0],[1,1]] [[0,0],[1,2]] [[0,2],[2,2]] [[2,1],[2,0]]
    I              -   differences        [0,1]         [1,0]         [-2,0]        [0,1]         [2,0]         [-1,-2]
     Ị             -   abs(v)<=1          [1,1]         [1,1]         [0,1]         [1,1]         [0,1]         [1,0]
       S           -   sum (of [a,b])      7            11            8              3            10            11
      o            -   OR (vectorises)    [1,1]         [1,1]         [8,1]         [1,1]         [10,1]        [1,11]
        H          -   halve (vectorises) [0.5,0.5]     [0.5,0.5]     [4,0.5]       [0.5,0.5]     [5,0.5]       [0.5,5.5]
         ;         -   concatenate        [0.5,0.5,3,4] [0.5,0.5,4,7] [4,0.5,7,1]   [0.5,0.5,1,2] [5,0.5,2,8]   [0.5,5.5,8,3]
            F      - flatten              [0.5,0.5,3,4,  0.5,0.5,4,7,  4,0.5,7,1,    0.5,0.5,1,2,  5,0.5,2,8,    0.5,5.5,8,3]
                ¤  - nilad followed by link(s) as a nilad:
              9    -   literal nine
               Ḷ   -   lowered range = [0,1,2,3,4,5,6,7,8]
             f     - filter keep          [        3,4,          4,7,  4,    7,1,            1,2,  5,    2,8,         ,8,3]
                 Q  - deduplicate          [3,4,7,1,2,5,8]
                  ⁼ - equal to the input?  e.g. 0 (here because 5 was introduced AND because 3 was removed from the right)

Método anterior

Gelatina ,  36  35 bytes

9s3;Z$;“Æ7a‘DZ¤;U$;©0m€2iị®oµƝFQ⁼ȧȦ

Prué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:

9s3;Z$;“Æ7a‘DZ¤;U$;©0
9s3                   - nine (implicit range) split into threes = [[1,2,3],[4,5,6],[7,8,9]]
     $                - last two links as a monad:
    Z                 -   transpose = [[1,4,7],[2,5,8],[6,7,9]]
   ;                  -   concatenate = [[1,2,3],[4,5,6],[7,8,9],[1,4,7],[2,5,8],[3,6,9]]
              ¤       - nilad followed by link(s) as a nilad:
       “Æ7a‘          -   code-page index list = [13,55,97]
            D         -   decimal (vectorises) = [[1,3],[5,5],[9,7]]
             Z        -   transpose = [[1,5,9],[3,5,7]]
      ;               - concatenate = [[1,2,3],[4,5,6],[7,8,9],[1,4,7],[2,5,8],[3,6,9],[1,5,9],[3,5,7]]
                 $    - last two links as a monad:
                U     -   upend = [[3,2,1],[6,5,4],[9,8,7],[7,4,1],[8,5,2],[9,6,3],[9,5,1],[7,5,3]]
               ;      -   concatenate = [[1,2,3],[4,5,6],[7,8,9],[1,4,7],[2,5,8],[3,6,9],[1,5,9],[3,5,7],[3,2,1],[6,5,4],[9,8,7],[7,4,1],[8,5,2],[9,6,3],[9,5,1],[7,5,3]]
                    0 - literal zero (to cater for non-matches in the main link since ị, index into, is 1-based and modular the 0th index is the rightmost)
                  ;   - concatenate = [[1,2,3],[4,5,6],[7,8,9],[1,4,7],[2,5,8],[3,6,9],[1,5,9],[3,5,7],[3,2,1],[6,5,4],[9,8,7],[7,4,1],[8,5,2],[9,6,3],[9,5,1],[7,5,3],0]
                   ©  - copy the result to the register

Ahora la toma de decisiones:

...m€2iị®oµƝFQ⁼ȧȦ - left input is a list of integers               e.g. [4,5,8,2,3,9,4]
          µƝ      - perform the chain to the left for adjacent pairs:
                  - i.e. for [a,b] in [[4,5],[5,8],[8,2],[2,3],[3,9],[9,4]]
...               -   perform the code described above = [[1,2,3],[4,5,6],[7,8,9],[1,4,7],[2,5,8],[3,6,9],[1,5,9],[3,5,7],[3,2,1],[6,5,4],[9,8,7],[7,4,1],[8,5,2],[9,6,3],[9,5,1],[7,5,3],0]
   m€2            -   modulo-2 slice €ach = [[1,3],[4,6],[3,9],[1,7],[2,8],[6,9],[1,9],[3,7],[3,1],[6,4],[9,7],[7,1],[8,2],[9,3],[9,1],[7,3],[0]]
      i           -   index of [a,b] in that (or 0 if not there)    e.g. [0,0,13,0,6,0]
        ®         -   recall from register = [[1,2,3],[4,5,6],[7,8,9],[1,4,7],[2,5,8],[3,6,9],[1,5,9],[3,5,7],[3,2,1],[6,5,4],[9,8,7],[7,4,1],[8,5,2],[9,6,3],[9,5,1],[7,5,3],0]
       ị          -   index into (1-based & modular)     e.g. [0,0,[8,5,2],0,[3,6,9],0]
         o        -   OR [a,b]           e.g. [[4,5],[5,8],[8,5,2],[2,3],[3,6,9],[9,4]]
            F     - flatten                          e.g. [4,5,5,8,8,5,2,2,3,3,6,9,9,4]
             Q    - deduplicate                                    e.g. [4,5,8,2,3,6,9]
              ⁼   - equal to the input?                            e.g. 0 (here because 6 was introduced AND because 4 was removed from the right)
                Ȧ - any and all? (0 if input is empty [or contains a falsey value when flattened - no such input], 1 otherwise)
               ȧ  - AND (to force an empty input to evaluate as 1 AND 0 = 0)
Jonathan Allan
fuente
¿Cómo sale a 19 bytes cuando hay un montón de caracteres unicode?
Izkata
@Izkata Jelly usa su propia página de códigos, que puede ver haciendo clic en "bytes" en el encabezado. En su forma de byte sin procesar, cada uno de los caracteres Unicode que puede ver en el código fuente es solo un byte.
Jonathan Allan
15

Stax , 28 bytes

æ¡_t¿♂≥7▼├öä▒╨½╧£x╪╨┌i╒ë╖¢g•

Ejecutarlo

Produce 0 para falso y enteros positivos para verdadero. La representación ascii correspondiente del mismo programa es esta.

cu=x%v*x2BF1379E-%_|+YA=!*yhxi(#+*

La idea general es calcular varias condiciones necesarias para los patrones de deslizamiento legales y multiplicarlos todos juntos.

cu=                                 First: no duplicates
   x%v*                             Second: length of input minus 1
       x2B                          Get all adjacent pairs  
          F                         For each pair, execute the rest
           1379E-%                  a) Any digits that are not 1, 3, 7, 9?
                  _|+Y              Get sum of pair, and store in Y register
                      A=!           b) Sum is not equal to 10?
                         *          c) multiply; logical and: a, b
                          yh        half of y; this will be equal to the
                                        number directly between the current
                                        pair if there is one
                            xi(#    d) has the middle number been observed yet?
                                +   e) plus; logical or: c, d
                                 *  multiply by the accumulated value so far
recursivo
fuente
Uso inteligente del Yregistro.
Weijun Zhou
Otro problema en github.
Weijun Zhou
1
Casualmente ya había solucionado ese error, pero no lo había implementado hasta ahora. (no afecta mi programa)
recursivo
1
Puede sonar extraño, pero puede descartar el primero ve incluirlo 1como valor falso. 2y arriba son verdaderas.
Weijun Zhou
10

JavaScript, 112 bytes

x=>/^(?!.*(.).*\1|[^5]*(19|28|37|46|91|82|73|64)|[^2]*(13|31)|[^8]*(79|97)|[^4]*(17|71)|[^6]*(39|93))../.test(x)

Quizás algún lenguaje basado en expresiones regulares debería ser más corto. Pero no lo se.

Gracias a Neil, cambie )(?!para |guardar 3 bytes.

tsh
fuente
@WeijunZhou Tengo verdad para 213, ¿qué pasa?
tsh
No pasa nada, lo siento.
Weijun Zhou
Ahora, desde que OP aclaró, falla 144.
Weijun Zhou
1
@WeijunZhou debería ser reparado; 2 bytes más ...
tsh
En caso de que se lo pregunte, un puerto Retina 0.8.2 parece funcionar a 98 bytes.
Neil
6

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.

A`(.).*\1|^([^5]*(19|28|37|46|91|82|73|64)|[^2]*(13|31)|[^8]*(79|97)|[^4]*(17|71)|[^6]*(39|93)|.$)

Pruébalo en línea

mbomb007
fuente
6

Casco , 25 20 bytes

S=öufΛ¦1ΣẊ§Jzo½+em‰3

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

S=öufΛ¦1ΣẊ§Jzo½+em‰3  Implicit input, say [0,4,6,7,1]
                 m‰3  Divmod each by 3: L = [[0,0],[1,1],[2,0],[2,1],[0,1]]
         Ẋ§Jzo½+e     This part inserts the middle node between adjacent nodes.
         Ẋ            Do this for each adjacent pair, e.g. [1,1],[2,0]:
          §           Apply two functions and combine results with third.
            zo½+      First function:
            z         Zip with
               +      addition,
             o½       then halve: N = [3/2,1/2]
                e     Second function: pair: P = [[1,1],[2,0]]
           J          Combining function: join P with N: [[1,1],[3/2,1/2],[2,0]]
                      Result is a list of such triples.
        Σ             Concatenate: [[0,0],[1/2,1/2],[1,1],[1,1],[3/2,1/2],...,[0,1]]
    f                 Keep only those pairs
     Λ                both of whose elements
      ¦1              are divisible by 1, i.e. are integers: [[0,0],[1,1],[1,1],,...,[0,1]]
   u                  Remove duplicates: [[0,0],[1,1],[2,0],[2,1],[0,1]]
S=ö                   Is the result equal to L? Implicitly print 1 or 0.
Zgarb
fuente
3

C ++, 267 256 bytes

#define R)return 0
#define H(a,q)if(d==q&&n==a&&!m[a]R;
int v(int s[],int l){if(l<2 R;int m[10]{},i=1,p=s[0],d,n;for(;i<l;++i){m[p]=1;if(m[s[i]]R;d=(d=p-s[i])<0?-d:d;if(d%2<1){n=(p+s[i])/2;H(5,4)H(5,8)H(2,2)H(5,2)H(8,2)H(4,6)H(5,6)H(6,6)}p=s[i];}return 1;}

Para verificar si el patrón no salta sobre un nodo no visitado, hace varias cosas:

  1. Calcule ddónde destá la diferencia numérica entre el nodo actual y el último nodo.
  2. Si des extraño, entonces no hay necesidad de verificarlo, no puede saltarse un nodo.
  3. Si des igual a 4o 8, entonces el salto es entre nodos 1-9o 3-7, así que verifique el nodo5
  4. Si des 2 y el nodo medio ( (last_node + current_node)/2) es 2,5 u 8, compruebe el nodo medio
  5. Si des 6, comprobar misma que antes, pero con 4, 5o6

Los parámetros son un int[]y su recuento de elementos. Devuelve un intque se puede interpretar como un booltipo

HatsuPointerKun
fuente
!(d%2)=> d%2<1debería funcionar.
Zacharý
256 bytes
Zacharý
Aprendí un nuevo truco: int s[]=> int*s. Creo que eso funcionará.
Zacharý
2

Perl, 135 bytes (134 + -n)

@a{split//}=1;(@{[/./g]}==keys%a&&/../)||die();for$c(qw/132 465 798 174 285 396 195 375/){$c=~/(.)(.)(.)/;/^[^$3]*($1$2|$2$1)/&&die()}

Versión ligeramente no golf

@a{split//} = 1;
(@{[/./g]} == keys %a && /../) || die();
for $c (qw/132 465 798 174 285 396 195 375/) {
  $c=~/(.)(.)(.)/;
  /^[^$3]*($1$2|$2$1)/&&die()
}

Salidas a través del código de salida. 0es 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.

Silvio Mayolo
fuente
2

MATL , 42 41 39 bytes

9:IeXKi"Ky@=&fJ*+XK+y&fJ*+Em~zw0@(]z8<v

Esto produce

  • un vector de columna no vacío que contiene solo números distintos de cero como salida verdadera; o
  • un vector de columna no vacío que contiene al menos un cero como falso.

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.

Luis Mendo
fuente
2

Stax , 73 72 66 65 bytes CP437

ÉWyƒ▬ºJOTƒw-H┌↓&ⁿç↨¼<ü6π║¢S○j⌂zXΣE7≈╩╕╤ö±÷C6▒☼■iP-↑⌐¥]╩q|+zΦ4Φ·¥Ω

79 bytes cuando está desempaquetado,

d4{cAs-5F132396978714EEL3/{xs:IBc0<A*++cEd:-1=sccHs|M=s{U>m|A**mEx%2<xu%x%=!L|+

Ejecutar y depurar en línea!

o ejecute la prueba por lotes , donde meXhay 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 0para casos verdaderos .

Explicación

dborra la pila de entrada. La entrada está en variable de xtodos 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 matriz a, 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**mEPara cada lista de nodos no válidos, realice las siguientes verificaciones. El resultado de los resultados de la verificación se andedita utilizando el **. Como hay 8 listas de nodos no válidas, el resultado de este código será una matriz de 8 elementos. El último Edespacha 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, 5en el conjunto de nodos 1,5,9) es -1(lo que significa que no existe en la matriz de entrada), cambie el índice a 9.

cEd:-1=pruebe si los dos "nodos terminales" (por ejemplo, 1,5en el conjunto de nodos 1,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|Aprueba 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. |atambién podría haberse usado para verificar simplemente si hay elementos verdaderos en la matriz.

Salida implícita.

Weijun Zhou
fuente
2

Java, 375 355 bytes

-20 bytes gracias a Zacharý

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;}

Este es un puerto de esta respuesta y funciona con los mismos principios

HatsuPointerKun
fuente
Woah Estás respondiendo en Java.
Zacharý
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)
Zacharý
Puedes cambiar (d==2)a justo d==2, lo pasé por alto antes.
Zacharý
d%2==0=>d%2<1
Zacharý
0

Pyth , 33 bytes

q{@U9.nm+mc|g1aZksd2-MC.DR3d_dC,t

Banco de pruebas.

Utiliza indexación basada en 0.

Explicación

q {@ U9.nm + mc | g1aZksd2-MC.DR3d_dC, t -> Programa completo. Entrada: una lista L de STDIN.

                               , t -> Emparejar L con L sin el primer elemento.
                              C -> Transponer.
       m -> Mapa sobre la lista de pares (listas de 2 elementos):
        + mc | g1aZksd2-MC.DR3d -> La función a mapear (variable: d):
                         R d -> Para cada elemento de d ...
                       .D 3 -> ... Tome su divmod por 3.
                      C -> Tranpose.
                    -M -> Reduce cada uno por sustracción.
         m -> Para cada diferencia (variable: k):
            g1aZl -> Is | k | ≤ 1?
           El | sd -> Si eso es falso, reemplácelo por la suma de d.
          c 2 -> Dividir por 2.
        + _d -> Añade el reverso de d al resultado de la asignación.
     .n -> Acoplar.
  @ U9 -> Tome la intersección con (ℤ ∩ [0; 9)).
 {-> Deduplicar.
q -> Y verifica si el resultado es igual a L.

Enfoque alternativo para 34 bytes :

q{sI#I#+Fm+,hdcR2+MCd]edCtBK.DR3QK
Sr. Xcoder
fuente
0

Japt , 35 bytes

eUä@[(Xu3 aYu3)¥1ªX+Y ÷2XY]Ãc f9o)â

Pruébalo en línea!

Ligeramente poco golfista y cómo funciona

eUä@[(Xu3 aYu3)¥1ªX+Y ÷2XY]Ãc f9o)â

Implicit beginning U(input) and some arbitrary sequence conversions

UeUä@[(Xu3 aYu3)==1||X+Y ÷2XY]} c f9o)â

  Uä             Convert the input array into length-2 subsections and map...
    @[ ... ]}      function of X,Y which returns an array of...
      Xu3 aYu3==1||X+Y ÷2          (abs(X%3 - Y%3)==1||X+Y)/2,
                         XY        X, Y
  c              Flatten the result of mapping
    f9o          Intersect with range(9)
        â        Take unique elements, preserving order
Ue             Is the result the same as original array?

Porté la idea de esta solución Jelly , con alguna diferencia en la determinación de posibles saltos:

  • La respuesta Jelly usa divmod para ver si un par tiene una diferencia de 2 cuando se aplica /3o %3.
  • Esta respuesta solo usa %3y 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.
Bubbler
fuente
0

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.

v={9}
s=input()
for n,l in zip(s[1:]or q,s):n/3+l/3&1|n%3+l%3&1or n+l>>1in v or q;v|={l};n in v>q

Pruébalo en línea!

Luciano
fuente