Meu padrão de furto é legal?

154

A maioria dos smartphones Android permite que o usuário use um padrão de furto para abrir o telefone:

padrão de Bloqueio

Certos padrões são legítimos e outros são impossíveis. Dado um padrão de furto de entrada, retorne uma verdade ou falsidade indicando se o padrão de entrada fornecido é legal ou não.

Entrada

A grade é rotulada em linha 1 a 9:

1 2 3   
4 5 6   
7 8 9

A entrada é um número composto pelos nós visitados do primeiro ao último. Por exemplo, o padrão de furto acima é 12357.

A entrada pode ser um número decimal, sequência ou lista de números. Não conterá 0 porque não há nó 0.

Alteração: a indexação de 0 a 8 é permitida, pois muitos idiomas indexam de 0. Se você usar de 0 a 8, será necessário indicar como tal no início de sua resposta e ajustar os casos de teste de acordo.

Regras

  • Cada nó inicia como não visitado inicialmente e pode ser visitado apenas uma vez. Qualquer padrão que visite um nó mais de uma vez é falso.

  • Um padrão de verdade deve conter pelo menos um golpe, portanto, no mínimo 2 nós.

  • Não é possível pular um nó não visitado diretamente em linha com outro. Por exemplo, 13 é falso porque 2 não é visitado e está diretamente alinhado.

  • Só é possível pular um nó visitado. 42631 é um exemplo disso.

  • As linhas podem cruzar-se de outra maneira. Por exemplo, 1524 é verdade.

  • Suponha que as larguras dos nós sejam insignificantes e ignore questões práticas (espessura dos dedos, etc.). Portanto, 16 é verdade, embora possa ser um pouco mais difícil de alcançar na realidade.

Casos de teste

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

Isso é , então o menor número de bytes vence.

Stanri
fonte
2
Relacionado.
Martin Ender
A lista de entrada tem garantia de não ser vazia?
Zgarb 13/02/19
@Zgarb yes. Não será vazio.
stanri
Pergunta sobre matemática relacionada: math.stackexchange.com/questions/205049/…
Pureferret 15/02

Respostas:

69

JavaScript (ES6), 64 bytes

Recebe a entrada como uma matriz de números. Os valores de falsidade são 0 ou NaN . Os valores reais são números inteiros estritamente 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 teste

Quão?

Preâmbulo

Dois dígitos são opostos na vertical, na horizontal ou na diagonal se:

  • ambos são ímpares, diferentes um do outro e diferentes de 5 (figura 1)
  • OU ambos são pares e sua soma é 10 (figura 2)

    dígitos opostos

Além disso, o algarismo de pé entre dois dígitos opostas n e p é igual a (n + p) / 2 .

Código fonte formatado

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
  )

Acompanhar os dígitos anteriores

Os sinalizadores dos dígitos visitados são armazenados em índices negativos na matriz de entrada a , para que não colidam com seus elementos originais.

  • Se p estiver definido como -n :

    Se o dígito atual n não foi selecionado anteriormente, a[-n] ^= -ndefinirá o sinalizador e deixará o every()loop continuar com a próxima iteração. Caso contrário, ele limpará a bandeira e forçará o loop a falhar imediatamente.

  • Se p estiver definido como indefinido :

    a[undefined] ^= undefinedresulta em 0 , o que também força o loop a falhar.

Detectando dígitos opostos

A expressão a seguir é usada para testar se o dígito atual n e o dígito anterior -p são dígitos opostos, conforme definido no preâmbulo:

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

que é equivalente a:

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

Nota: Em JS, o resultado do módulo tem o mesmo sinal que o dividendo.

Pode ser interpretado como:

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

Portanto, essa expressão retornará 1 se e somente se n e -p forem dígitos opostos ou forem o mesmo dígito ímpar. Como um dígito não pode ser selecionado duas vezes, este último caso é resolvido corretamente.

Se essa expressão retornar 1 , testamos um [p / 2] (onde p agora é igual à soma negada dos dígitos) para saber se o 'dígito intermediário' foi visitado anteriormente. Caso contrário, testamos um [0] que é garantido como verdadeiro.

Sobre a primeira iteração

A primeira iteração é um caso especial, pois não existe um dígito anterior e queremos que ele seja incondicionalmente bem-sucedido.

Conseguimos isso inicializando p para 1 , porque para qualquer n em [1 .. 9] :

  • (1 * n) % 5 não pode ser negativo
  • ~(1 - n) não pode ser igual a 9

Resposta original, 90 bytes

Removido desta postagem para que não fique muito detalhado. Você pode vê-lo aqui .

Arnauld
fonte
-1 byte substituindo !!a[1]&por a[1]&&, já que qualquer valor verdadeiro pode ser retornado
Herman L
@HermanLauenstein Obrigado, isso parece realmente bom. (Agora, a[1]*é ainda mais curto.)
Arnauld
1
Eu estava tentando desesperadamente pensar em uma fórmula para has a node directly in line, eu não sabia que seria tão simples ...
Neil
@Neil Ao olhar para o histórico de revisões deste post, eu tenho certeza que você pode dizer que eu não sabia que imediatamente qualquer um ... :)
Arnauld
Pense que você pode substituir ?a[-n]^=1:0com &&a[-n]^=1para-1, não pode testar (no celular)
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

Ele recebe o comprimento da lista ecxe um ponteiro para o primeiro elemento em edxe retorna o resultado em al:

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

Existem 8 linhas que contêm um nó no meio:

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

Agrupei-os de acordo com a diferença entre o número maior e o menor.

Diferença 2: 3 linhas (começando em 1, 4 ou 7)
    1 - 3
    4 - 6
    7 - 9
Diferença 4: 1 linha (começando em 3)
    3 - 7
Diferença 6: 3 linhas (começando em 1, 2 ou 3)
    1 - 7
    2 - 8
    3 - 9
Diferença 8: 1 linha (começando em 1)
    1 - 9

Em seguida, converti isso para uma tabela de pesquisa 2D indexada pela meia diferença e número menor:

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

Isso cria um bitmap "mágico" de 32 bits. Para indexá-lo, o código o empurra para a pilha. Em seguida, extrai um byte usando um índice e, a partir desse byte, extrai um bit usando o outro índice. Tudo isso usando uma instrução:

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

Se o bitmap indicar que existe um nó no meio, é fácil calcular - adicione metade da diferença ao número menor.

Fonte de montagem:

    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
fonte
Agradável! Eu realmente gosto disso bt byte ptr [esp + eax], ebx.
Arnauld 12/02
5
É bom ver a solução de montagem :) Você pode usar cdq vez de xor edx, edxcomo eaxé zero. Além disso, você pode dobrar o dec eaxem bt [esp + eax - 1], ebxque é o mesmo comprimento, mas, em seguida, permite que você remova a inc ebxtarde. Isso deve economizar dois bytes.
Jester
Obrigado pelas idéias! De ter assegurado o seu lugar no paraíso do golfista, se houver um :)
anatolyg
5
Acho que todos podemos concordar que o paraíso dos golfistas é um inferno para todos os outros.
Adonalsium
19

Python 2 , 140 131 114 104 99 bytes

-2 bytes graças a Jonathan Frech
-5 bytes graças 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

Experimente online!

Explicação:

# 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

Experimente online!

Apenas 8 pares de nós têm um nó entre eles. Um par de nós pode ser representado como um único número inteiro pela fórmula 2^a-2^b-1. Este número pode ser reduzido por 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==5primeiro verifica se esse par está presente, depois v-{l+n>>1}==vtesta se o nó intermediário, fornecido por (a+b)/2, ainda não foi visitado e qgera um NameError. Ao usar a comparação encadeada entre esses pares, a próxima comparação é executada apenas quando a anterior retornou True.

ovs
fonte
17

Gelatina ,  24 22 19  18 bytes

-2, já que não somos mais obrigados a lidar com uma lista vazia
-1, alternando de join, j@para concatenar ;(o item perdido não precisa ser encontrado no meio para o método empregado, estar no início do trio é bom. )
-2 alternando de P¬aSHpara oSH(OK para obter dois resultados, pois achatamos, metade 1é0.5 que é filtrado para fora de qualquer forma, e ter vários resultados iguais não tem efeito sobre o método utilizado qualquer um)
-1 Graças ao Sr. Xcoder (0-indexado entrada é permitida)

d3ZIỊoSH;µƝFf9Ḷ¤Q⁼

Um link monádico que obtém uma lista de números inteiros em [0,8] e retorna um valor 1verdadeiro ( 0) se for legal e um valor falsey ( ) se não.

Experimente online!ou veja uma suíte de testes .

Quão?

Examina cada par adjacente de nós indexados 0 na lista de entrada. Se a divisão inteira por três dos dois diferir por 2, eles estarão nas linhas superior e inferior; se o módulo por três dos dois diferir por 2, eles estarão nas colunas da esquerda e da direita. A soma desses pares divididos por dois é o nó médio indexado a 0 de uma linha de três nós ou um valor não inteiro - portanto, esses valores são inseridos primeiro na frente do par indexado em 0 e, em seguida, qualquer nós falsos (como 0.5ou3.5) são removidos, a lista resultante de listas é achatada e desduplicada (para gerar entradas exclusivas preservadas por ordem) e finalmente comparada à entrada - para um furto legal, tudo isso acabará sendo proibido enquanto ilegal ones adicionam nós médios ausentes e / ou removem nós duplicados (observe que nenhuma caixa especial é necessária para uma lista de entrada de comprimento 1, pois não possui pares adjacentes):

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

Geléia ,  36  35 bytes

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

Experimente online! ou veja uma suíte de testes .

Quão?

Semelhante ao acima, mas constrói todas as possibilidades de linha de três nós e executa a pesquisa (em vez de verificar o uso do divmod para testar e reduzir pela metade a soma do nó intermediário).

Primeiramente a construção da lista de linhas de três nós:

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

Agora a tomada de decisão:

...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
fonte
Como sai para 19 bytes quando há um monte de caracteres unicode?
Izkata 18/02/19
O @Izkata Jelly usa sua própria página de códigos, que você pode ver clicando em "bytes" no cabeçalho. Na forma de byte bruto, cada um dos caracteres Unicode que você pode ver no código-fonte é apenas um byte.
Jonathan Allan
15

Stax , 28 bytes

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

Executá-lo

Produz 0 para números inteiros falsos e positivos para verdadeiro. A representação ascii correspondente do mesmo programa é essa.

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

A idéia geral é calcular várias condições necessárias para os padrões de furto legal e multiplicá-los 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
fonte
Uso inteligente do Yregistro.
Weijun Zhou
Outra questão no github.
Weijun Zhou
1
Por coincidência, eu já havia corrigido esse bug, mas não o havia implantado até agora. (isso não afeta meu programa)
recursiva
1
Pode parecer estranho, mas você pode largar o primeiro ve incluir 1como valor falso. 2e acima são verdadeiras.
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)

Talvez alguma linguagem baseada em regex deva ser mais curta. Mas eu não sei.

Graças a Neil, altere )(?!para |salvar 3 bytes.

tsh
fonte
@WeijunZhou Eu me apaixonei pelo 213, o que há de errado?
tsh 12/02
Nada está errado, desculpe por isso.
Weijun Zhou 12/02
Agora, desde que o OP foi esclarecido, falha 144.
Weijun Zhou 12/02
1
@WeijunZhou deve ser corrigido; Mais 2 bytes ...
tsh 12/02
Caso você esteja se perguntando, uma porta Retina 0.8.2 parece funcionar a 98 bytes.
Neil
6

Retina 0.8.2 , 98 bytes

Influenciado pela resposta do tsh . Tentei "reformular" para que fosse o oposto, correspondendo a furtos inválidos e depois ao 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)|.$)

Experimente online

mbomb007
fonte
6

Casca , 25 20 bytes

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

Leva uma lista de números inteiros com indexação baseada em 0. Retorna 0 ou 1. Experimente online!

Explicação

Eu roubei algumas idéias da resposta de Jonathan Allan Jelly . A idéia é a mesma: insira um novo "nó médio" entre cada par adjacente, filtre aqueles que não são nós reais, remova duplicatas e compare com a lista original. Se a lista original contiver duplicatas, o resultado será falso. Se a lista ignorar um nó não visitado, ele estará presente na lista processada entre o par correspondente e o resultado será falso. Se a entrada for um singleton, a lista processada estará vazia e o resultado será falso. Caso contrário, é verdade.

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
fonte
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 se o padrão não pula um nó não visitado, ele faz várias coisas:

  1. Calcule donde destá a diferença numérica entre o nó atual e o último nó.
  2. Se dfor ímpar, não há necessidade de verificar, ele não pode pular um nó.
  3. Se dfor igual a 4ou 8, o salto será entre nós 1-9ou 3-7, portanto, verifique o nó5
  4. Se dfor 2 e o nó do meio ( (last_node + current_node)/2) for 2,5 ou 8, verifique o nó do meio
  5. Se dfor 6, mesmo verificar como antes, mas com 4, 5ou6

Os parâmetros são um int[]e é contagem de elementos. Retorna um intque pode ser interpretado como um booltipo

HatsuPointerKun
fonte
!(d%2)=> d%2<1deve funcionar.
Zachary
256 bytes
Zacharý 13/11
Eu aprendi um novo truque: int s[]=> int*s. Eu acho que vai dar certo.
Zachary
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()}

Versão ligeiramente não destruída

@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()
}

Saídas via código de saída. 0é verdade, qualquer outro valor é falso. Conforme meta consenso , a saída STDERR no caso de falha é ignorada.

Provavelmente, há uma maneira mais rápida de verificar a regra "não é possível pular" do que simplesmente listar todas as possibilidades.

Silvio Mayolo
fonte
2

MATL , 42 41 39 bytes

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

Isso produz

  • um vetor de coluna não vazio contendo apenas números diferentes de zero como saída de verdade; ou
  • um vetor de coluna não vazio contendo pelo menos um zero como falso.

Aqui você pode ler por que essas saídas são respectivamente verdadeiras e falsas. Experimente online!

Ou verifique todos os casos de teste , com código de rodapé que inclua o teste padrão de veracidade / falsidade.

Luis Mendo
fonte
2

Stax , 73 72 66 65 bytes CP437

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

79 bytes quando descompactado,

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

Execute e depure online!

ou execute o teste em lote , onde meXhá um cabeçalho para que o Stax possa processar a entrada de várias linhas.

Implementação sem usar hash.Outputs num número estritamente positivo (na verdade, o número de testes com falha) para casos falsos e 0para truthy queridos.

Explicação

dlimpa a pilha de entrada. A entrada está na variávelx qualquer maneira.

4{cAs-5F gera a primeira parte da lista de nós do meio.

132396978714EE codifica a segunda parte da lista de nós do meio.

L3/ Coleta todos os elementos na pilha principal e se divide em partes, cada uma contendo 3 elementos, o resultado é um array a , que é apenas a matriz de todos os grupos de 3 nós inválidos.

{xs:IBc0<A*++cEd:-1=sccHs|M=s{U>m|A**mEPara cada lista de nós inválidos, execute as seguintes verificações. O resultado dos resultados da verificação é anded usando o **. Como existem 8 listas de nós inválidos, o resultado desse código será uma matriz de 8 elementos. O final Eenvia a matriz para seus elementos individuais na pilha principal.

xs:I obtenha o índice dos elementos da lista de nós na matriz de entrada.

Bc0<A*++Se o índice de "nó do meio" (por exemplo, 5no conjunto de nós 1,5,9) for -1(o que significa que não existe na matriz de entrada), altere o índice para 9.

cEd:-1=teste se os dois "nós terminais" (por exemplo, 1,5no conjunto de nós 1,5,9) são adjacentes na matriz de entrada.

sccHs|M= testar se o índice transformado do "nó do meio" é maior que o dos dois "nós terminais", o que inclui dois casos: o "nó do meio" está ausente ou o "nó do meio" vem depois dos dois "nós de terminal"

s{U>m|Atesta se os dois índices dos "nós finais" não são negativos. (ou seja, ambos aparecem na entrada).

Dois testes adicionais são realizados,

x%2< testa se a matriz de entrada é um singleton.

xu%x%=! testa se os nós foram visitados duas vezes.

Há 10 resultados de teste na pilha principal (um para cada lista de nós inválidos, mais dois testes adicionais).

L|+ coleta os 10 elementos e os adiciona. |atambém poderia ter sido usado, o que simplesmente verifica se existem elementos verdadeiros na matriz.

Saída implícita.

Weijun Zhou
fonte
2

Java, 375 355 bytes

-20 bytes graças 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;}

Esta é uma porta desta resposta e funciona com os mesmos princípios

HatsuPointerKun
fonte
Woah. Você está respondendo em Java.
Zacharý 23/02
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;}deve trabalhar (ordem de operações)
Zachary
Você pode mudar (d==2)para apenas d==2, eu negligenciei isso antes.
Zacharý
d%2==0=>d%2<1
Zacharý
0

Pitão , 33 bytes

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

Suíte de teste.

Usa indexação baseada em 0.

Explicação

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

                               , t -> Emparelhe L com L sem o primeiro elemento.
                              C -> Transpor.
       m -> Mapa sobre a lista de pares (listas de 2 elementos):
        + mc | g1aZksd2-MC.DR3d -> A função a ser mapeada (variável: d):
                         R d -> Para cada elemento d ...
                       .D 3 -> ... Pegue seu divmod por 3.
                      C -> Tranpose.
                    -M -> Reduza cada subtração.
         m -> Para cada diferença (variável: k):
            g1aZl -> Is | k | ≤ 1?
           | sd -> Se isso for falso, substitua-o pela soma de d.
          c 2 -> Divida por 2.
        + _d -> Anexe o reverso de d ao resultado do mapeamento.
     .n -> Achatar.
  @ U9 -> Pegue a interseção com (ℤ ∩ [0; 9)).
 {-> Desduplicar.
q -> E verifique se o resultado é igual a L.

Abordagem alternativa para 34 bytes :

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

Japonês , 35 bytes

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

Experimente online!

Ligeiramente não-destruído e como 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?

Transportou a ideia dessa solução Jelly , com alguma diferença na determinação de possíveis saltos:

  • A resposta Jelly usa divmod para verificar se um par tem diferença de 2 quando aplicado /3ou %3.
  • Esta resposta usa apenas %3e verifica se a diferença é 0 ou 2. Se a diferença for 0, as duas células estão alinhadas verticalmente e os não-saltos ainda compartilham a propriedade de (X+Y)%2 != 0.
Bubbler
fonte
0

Python 2 , 97 bytes

Com base na resposta dos ovs, mas 2 bytes mais curtos e menos enigmáticos. Apenas converte índices em coordenadas 2D e testa a paridade. Assume de 0 a 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

Experimente online!

Luciano
fonte