Mon modèle de balayage est-il légal?

154

La plupart des smartphones Android permettent à l'utilisateur d'utiliser un motif de balayage pour ouvrir leur téléphone:

Serrure à motif

Certains modèles sont légitimes et d'autres sont impossibles. Avec un motif de balayage d’entrée, renvoyez une vérité ou une fausseté en indiquant si le motif d’entrée donné est légal ou non.

Contribution

La grille est libellée rangée de 1 à 9:

1 2 3   
4 5 6   
7 8 9

L'entrée est un nombre composé des nœuds visités du premier au dernier. Par exemple, le motif de balayage ci-dessus est 12357.

L'entrée peut être un nombre décimal, une chaîne ou une liste de nombres. Il ne contiendra pas 0 car il n'y a pas de noeud 0.

Amendement: l'indexation 0-8 est autorisée car de nombreuses langues indexent à partir de 0. Si vous utilisez 0-8, il sera nécessaire de l'indiquer au début de votre réponse et d'ajuster les cas de test en conséquence.

Règles

  • Chaque nœud commence comme non visité initialement et ne peut être visité qu'une seule fois. Toute régularité qui visite un noeud plusieurs fois est de la fausseté.

  • Un motif de vérité doit contenir au moins un balayage, donc au moins 2 nœuds.

  • Il n'est pas possible de passer directement sur un nœud non visité pour le rapprocher d'un autre. Par exemple, 13 est faux, car 2 n'est pas visité et est directement aligné.

  • Il est uniquement possible de sauter un nœud visité. 42631 en est un exemple.

  • Les lignes peuvent se croiser autrement. Par exemple, 1524 est la vérité.

  • Supposons que les largeurs de nœud ne sont pas significatives et ignorent les problèmes pratiques (épaisseur des doigts, etc.). Donc 16 est la vérité même si cela peut être un peu plus difficile à réaliser en réalité.

Cas de test

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

C'est du , donc le plus petit nombre d'octets gagne.

Stanri
la source
La liste de saisie est-elle garantie d'être non vide?
Zgarb
@Zgarb oui. Ce sera non vide.
Stanri
Question liée mathématiques: math.stackexchange.com/questions/205049/...
Pureferret

Réponses:

69

JavaScript (ES6), 64 octets

Prend les entrées sous forme de tableau de nombres. Les valeurs de fausseté sont 0 ou NaN . Les valeurs de vérité sont des entiers strictement positifs.

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

Cas de test

Comment?

Préambule

Deux chiffres sont opposés verticalement, horizontalement ou en diagonale si:

  • ils sont tous les deux étranges, différents l'un de l'autre et différents de 5 (figure 1)
  • OU ils sont tous les deux pairs et leur somme est 10 (figure 2)

    chiffres opposés

De plus, le chiffre entre deux chiffres opposés n et p est égal à (n + p) / 2 .

Code source formaté

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
  )

Garder une trace des chiffres précédents

Les drapeaux des chiffres visités sont stockés à des indices négatifs dans le tableau d'entrée a , afin qu'ils ne se heurtent pas à ses éléments d'origine.

  • Si p est défini sur -n :

    Si le chiffre actuel n n’a pas été précédemment sélectionné, a[-n] ^= -nle drapeau est activé et la every()boucle continue à la prochaine itération. Sinon, cela effacera l'indicateur et forcera la boucle à échouer immédiatement.

  • Si p est défini sur non défini :

    a[undefined] ^= undefinedaboutit à 0 , ce qui force également la boucle à échouer.

Détecter les chiffres opposés

L'expression suivante permet de vérifier si le chiffre actuel n et le chiffre précédent -p sont des chiffres opposés, tels que définis dans le préambule:

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

qui équivaut à:

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

Remarque: dans JS, le résultat du modulo a le même signe que le dividende.

Cela peut être interprété comme:

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

Par conséquent, cette expression renvoie 1 si et seulement si n et -p sont des chiffres opposés ou le même chiffre impair. Comme un chiffre ne peut pas être sélectionné deux fois, ce dernier cas est correctement pris en charge de toute façon.

Si cette expression renvoie 1 , nous testons a [p / 2] (où p est maintenant égal à la somme des chiffres niés) afin de savoir si le 'chiffre intermédiaire' a déjà été visité. Sinon, nous testons un [0] dont la véracité est garantie.

A propos de la première itération

La première itération est un cas particulier, car il n’ya pas de chiffre précédent et nous voulons qu’elle soit couronnée de succès sans condition.

Nous y parvenons en initialisant p sur 1 , car pour tout n dans [1. 9] :

  • (1 * n) % 5 ne peut pas être négatif
  • ~(1 - n) ne peut pas être égal à 9

Réponse originale, 90 octets

Supprimé de ce post pour qu'il ne soit pas trop bavard. Vous pouvez le voir ici .

Arnauld
la source
-1 octet en remplaçant !!a[1]&par a[1]&&, puisque toute valeur de vérité peut être retournée
Herman L
@ HermanLauenstein Merci, cela semble bien aller. (Maintenant, a[1]*c'est encore plus court.)
Arnauld
1
J'essayais désespérément de has a node directly in linetrouver une formule , je ne savais pas que ce serait si simple ...
Neil
@Neil En regardant l'historique des révisions de ce billet, je suis sûr que vous pouvez dire que je ne m'en suis pas rendu compte immédiatement non plus ... :)
Arnauld
Pensez que vous pouvez remplacer ?a[-n]^=1:0par &&a[-n]^=1-1, vous ne pouvez pas tester (sur mobile)
Stan Strum
45

Code machine x86 32 bits, 62 à 60 octets

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

Il reçoit la longueur de la liste ecxet un pointeur sur le premier élément edxet renvoie le résultat sous la forme al:

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

Il y a 8 lignes qui contiennent un nœud au milieu:

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

Je les ai regroupés en fonction de la différence entre le plus grand et le plus petit nombre.

Différence 2: 3 lignes (commençant à 1, 4 ou 7)
    1 - 3
    4 - 6
    7 - 9
Différence 4: 1 ligne (à partir de 3)
    3 - 7
Différence 6: 3 lignes (commençant à 1, 2 ou 3)
    1 - 7
    2 - 8
    3 - 9
Différence 8: 1 ligne (à partir de 1)
    1 - 9

Ensuite, j'ai converti cela en une table de recherche 2D indexée par demi-différence et par un nombre plus petit:

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

Cela fait un bitmap "magique" de 32 bits. Pour l'indexer, le code le pousse dans la pile. Ensuite, il extrait un octet en utilisant un index et à partir de cet octet, il extrait un bit en utilisant l'autre index. Tout cela en une seule instruction:

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

Si le bitmap indique qu'il y a un nœud au milieu, il est facile à calculer - ajoutez la moitié de la différence au nombre le plus petit.

Source d'assemblage:

    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
la source
Agréable! J'aime vraiment ça bt byte ptr [esp + eax], ebx.
Arnauld
5
C'est bien de voir la solution d'assemblage :) Vous pouvez utiliser cdqau lieu de xor edx, edxcomme eaxc'est zéro. En outre, vous pouvez plier le dec eaxdans bt [esp + eax - 1], ebxqui est la même longueur, mais vous permet ensuite de supprimer le inc ebxplus tard. Cela devrait vous faire économiser deux octets.
Jester
Merci pour les idées! Vous avez obtenu votre place dans le paradis des golfeurs, le cas échéant :)
anatolyg
5
Je pense que nous pouvons tous convenir que le paradis des golfeurs est un enfer pour tous les autres.
Adonalsium
19

Python 2 , 140 131 114 104 99 octets

-2 octets grâce à Jonathan Frech
-5 octets grâce à 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

Essayez-le en ligne!

Explication:

# 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

Essayez-le en ligne!

Seules 8 paires de nœuds ont un nœud entre elles. Une paire de nœuds peut être représentée sous la forme d'un entier unique par la formule 2^a-2^b-1. Ce nombre peut être raccourci par modulo répété:

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==5vérifie d'abord si une telle paire est présente, puis vérifie si v-{l+n>>1}==vle nœud situé entre, qui est donné par (a+b)/2, n'a pas encore été visité et qlève une erreur NameError. En utilisant une comparaison chaînée entre ces paires, la comparaison suivante n'est exécutée que lorsque la précédente est renvoyée True.

ovs
la source
17

Jelly ,  24 22 19  18 octets

-2 puisqu'il n'est plus nécessaire de gérer une liste vide
-1 de passer de la jointure j@à la concaténation ;(l'élément manquant n'a pas besoin d'être rencontré au milieu pour la méthode utilisée, le début du trio convient parfaitement )
-2 commutation de P¬aSHà oSH(OK d'avoir deux résultats puisque nous aplatir la moitié de 1est 0.5que l' on filtre sur de toute façon, et ayant de multiples résultats égaux n'a aucun effet sur la méthode employée soit)
-1 Merci à M. Xcoder (0-indexé l'entrée est autorisée)

d3ZIỊoSH;µƝFf9Ḷ¤Q⁼

Un lien monadique prenant une liste d'entiers dans [0,8]et renvoyant une valeur de vérité ( 1) si légal et une valeur de falsey ( 0) sinon.

Essayez-le en ligne! ou voir une suite de tests .

Comment?

Examine chaque paire adjacente de nœuds à index 0 dans la liste d'entrée. Si la division entière par trois des deux diffère de 2, elle se trouve dans les rangées supérieure et inférieure, si le modulo par trois des deux diffère de 2, elle se trouve dans les colonnes de gauche et de droite. La somme de ces paires divisée par deux est soit le nœud milieu indexé par 0 d'une ligne à trois nœuds, soit une valeur non entière. Ces valeurs sont donc d'abord insérées devant la paire indexée par 0, puis toutes les valeurs suivantes. faux nœuds (comme 0.5ou3.5) sont supprimés, la liste de listes résultante est aplatie puis dédupliquée (pour obtenir des entrées uniques préservées dans l'ordre) et enfin comparée à l'entrée - pour un balayage légal, tout cela deviendra un no-op tant qu'il sera illégal ceux-ci ajouteront des noeuds intermédiaires manquants et / ou supprimeront des noeuds en double (notez qu'aucun casier spécial n'est requis pour une liste d'entrée de longueur 1, car elle n'a pas de paires 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éthode précédente

Gelée ,  36  35 octets

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

Essayez-le en ligne! ou voir une suite de tests .

Comment?

Semblable à ce qui précède, il construit toutes les possibilités de ligne à trois noeuds et effectue une recherche (plutôt que de vérifier au fur et à mesure qu'il utilise divmod pour tester et diviser par deux la somme du noeud moyen).

Tout d'abord la construction de la liste des lignes à trois nœuds:

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

Maintenant, la prise de décision:

...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
la source
Comment se fait-il à 19 octets quand il y a beaucoup de caractères Unicode?
Izkata
@Izkata Jelly utilise sa propre page de code, que vous pouvez voir en cliquant sur "octets" dans l'en-tête. Sous forme d'octet brut, chacun des caractères Unicode que vous pouvez voir dans le code source n'est qu'un seul octet.
Jonathan Allan
15

Stax , 28 octets

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

Exécuter

Il produit 0 pour faux et des entiers positifs pour vrai. La représentation ascii correspondante du même programme est la suivante.

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

L'idée générale est de calculer plusieurs conditions nécessaires pour les motifs de balayage légaux et de les multiplier tous ensemble.

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
récursif
la source
Utilisation intelligente du Yregistre.
Weijun Zhou
Un autre problème sur github.
Weijun Zhou
1
Comme par hasard, j'avais déjà corrigé ce bogue, mais je ne l'avais pas déployé jusqu'à présent. (cela n'affecte pas mon programme)
récursif le
1
Cela peut sembler étrange, mais vous pouvez supprimer le premier vet l'inclure 1comme valeur de fausseté. 2et au-dessus sont la vérité.
Weijun Zhou
10

JavaScript, 112 octets

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)

Peut-être que certains langages basés sur regex devraient être plus courts. Mais je ne sais pas.

Grâce à Neil, changez )(?!pour |économiser 3 octets.

tsh
la source
@ WeijunZhou Je suis devenu vrai pour 213, qu'est-ce qui ne va pas?
Tsh
Rien n'est faux, désolé pour ça.
Weijun Zhou
Maintenant, puisque OP clarifié, échoue pour 144.
Weijun Zhou
1
@ WeijunZhou devrait être corrigé; 2 autres octets ...
tsh
Au cas où vous vous le demanderiez, un portage Retina 0.8.2 semble fonctionner à 98 octets.
Neil
6

Retina 0.8.2 , 98 octets

Influencé par la réponse de tsh . J'ai essayé de "reformuler" pour que ce soit l'inverse, en faisant correspondre les balayages non valides, puis Anti-grep.

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

Essayez-le en ligne

mbomb007
la source
6

Husk , 25 à 20 octets

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

Prend une liste d'entiers avec indexation basée sur 0. Renvoie 0 ou 1. Essayez-le en ligne!

Explication

J'ai volé des idées à la réponse de Jonathan Allan sur Jelly . L'idée est la même: insérer un nouveau "nœud moyen" entre chaque paire adjacente, filtrer ceux qui ne sont pas des nœuds réels, supprimer les doublons et les comparer à la liste d'origine. Si la liste d'origine contient des doublons, le résultat est faux. Si la liste ignore un nœud non visité, il est présent dans la liste traitée située entre la paire correspondante et le résultat est faux. Si l'entrée est un singleton, la liste traitée est vide et le résultat est faux. Sinon, c'est la vérité.

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
la source
3

C ++, 267 256 octets

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

Pour vérifier si le modèle ne passe pas sur un nœud non visité, il effectue plusieurs opérations:

  1. Calculez ddest la différence numérique entre le nœud actuel et le dernier nœud.
  2. Si dc'est étrange, alors il n'y a pas besoin de vérifier, il ne peut pas ignorer un nœud.
  3. Si dest égal à 4ou 8, alors le saut est entre noeuds 1-9ou 3-7, alors vérifiez noeud5
  4. Si dest égal à 2 et si le nœud du milieu ( (last_node + current_node)/2) est 2,5 ou 8, vérifiez le nœud du milieu
  5. Si dest égal à 6, même vérification qu'auparavant mais avec 4, 5ou6

Les paramètres sont un int[]et c'est le nombre d'éléments. Il retourne un intqui peut être interprété comme un booltype

HatsuPointerKun
la source
!(d%2)=> d%2<1devrait fonctionner.
Zacharý
256 octets
Zacharý
J'ai appris un nouveau tour: int s[]=> int*s. Je pense que ça va marcher.
Zacharý
2

Perl, 135 octets (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()}

Version légèrement non-golfée

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

Sorties via le code de sortie. 0est la vérité, toute autre valeur est la fausseté. Conformément au méta-consensus , la sortie de STDERR dans le cas de la défaillance est ignorée.

Il existe probablement un moyen plus rapide de vérifier la règle "ne peut pas sauter par-dessus" simplement en listant toutes les possibilités.

Silvio Mayolo
la source
2

MATL , 42 41 39 octets

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

Cela produit

  • un vecteur colonne non vide contenant uniquement des nombres non nuls en tant que sortie vérité; ou
  • un vecteur de colonne non vide contenant au moins un zéro en tant que falsy.

Ici vous pouvez lire pourquoi ces sorties sont respectivement vérité et fausseté. Essayez-le en ligne!

Ou vérifiez tous les cas de test , avec un code de pied de page qui inclut le test standard de véracité / fausseté.

Luis Mendo
la source
2

Stax , 73 72 66 65 octets CP437

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

79 octets une fois décompressé,

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

Exécuter et déboguer en ligne!

ou exécutez le test par lots , où se meXtrouve un en-tête afin que Stax puisse traiter les entrées multilignes.

Mise en œuvre sans utiliser de hachage. Nombre de sorties strictement positif (en fait, nombre de tests ayant échoué) pour les cas de fausseté et les cas 0de vérité .

Explication

defface la pile d'entrée. L'entrée est dans variable xquand même.

4{cAs-5F génère la première partie de la liste des nœuds intermédiaires.

132396978714EE code en dur la deuxième partie de la liste des nœuds du milieu.

L3/Collecte tous les éléments de la pile principale et les divise en parties contenant chacune 3 éléments. Le résultat est un tableau a, qui est simplement le tableau de tous les groupes de 3 nœuds non valides.

{xs:IBc0<A*++cEd:-1=sccHs|M=s{U>m|A**mEPour chaque liste de nœud non valide, effectuez les vérifications suivantes. Le résultat des résultats de contrôle est andédité à l’aide de **. Comme il existe 8 listes de nœuds non valides, le résultat de ce code sera un tableau de 8 éléments. La dernière Eenvoie le tableau à ses éléments individuels sur la pile principale.

xs:I obtenir l'index des éléments de la liste de noeuds dans le tableau d'entrée.

Bc0<A*++Si l'index de "nœud central" (par exemple 5dans l'ensemble de nœuds 1,5,9) est -1(ce qui signifie qu'il n'existe pas dans le tableau d'entrée), remplacez l'index par 9.

cEd:-1=vérifier si les deux "nœuds terminaux" (par exemple 1,5dans l'ensemble de nœuds 1,5,9) sont adjacents dans le tableau d'entrée.

sccHs|M= teste si l'indice transformé du "nœud intermédiaire" est supérieur à ceux des deux "nœuds terminaux", ce qui inclut deux cas: le "nœud intermédiaire" est manquant ou le "nœud intermédiaire" vient après les deux "nœuds terminaux"

s{U>m|Ateste si les deux index des "noeuds finaux" sont non négatifs. (c'est-à-dire qu'ils apparaissent tous les deux dans l'entrée).

Deux tests supplémentaires sont effectués,

x%2< teste si le tableau d'entrée est un singleton.

xu%x%=! teste si les nœuds ont été visités deux fois.

Il y a 10 résultats de test sur la pile principale (un pour chaque liste de nœuds non valides, plus deux tests supplémentaires).

L|+collecte les 10 éléments et les ajoute. |aaurait également pu être utilisé pour vérifier s'il y a des éléments de vérité sur le tableau.

Sortie implicite.

Weijun Zhou
la source
2

Java, 375 355 octets

-20 octets grâce à 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;}

Ceci est un port de cette réponse et il fonctionne sur les mêmes principes

HatsuPointerKun
la source
Woah. Vous répondez à 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;}devrait fonctionner (ordre des opérations)
Zacharý
Vous pouvez changer (d==2)pour juste d==2, j'ai négligé cela avant.
Zacharý
d%2==0=>d%2<1
Zacharý
0

Pyth , 33 octets

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

Suite de tests.

Utilise l'indexation basée sur 0.

Explication

q {@ U9.nm + mc | g1aZksd2-MC.DR3d_dC, t -> Programme complet. Entrée: une liste L de STDIN.

                               , t -> Paire L avec L sans le premier élément.
                              C -> Transposer.
       m -> Carte sur la liste des paires (listes à 2 éléments):
        + mc | g1aZksd2-MC.DR3d -> La fonction à mapper (variable: d):
                         R d -> Pour chaque élément de d ...
                       .D 3 -> ... Prenez son divmod par 3.
                      C -> Transposer.
                    -M -> Réduire chacun par soustraction.
         m -> Pour chaque différence (variable: k):
            g1aZl -> Is | k | ≤ 1?
           | sd -> Si c'est faux, remplacez-le par la somme de d.
          c 2 -> Diviser par 2.
        + _d -> Ajoute l'inverse de d au résultat de la cartographie.
     .n -> Aplatir.
  @ U9 -> Prenez l'intersection avec (∩ [0; 9)).
 {-> Dédupliquer.
q -> Et vérifiez si le résultat est égal à L.

Approche alternative pour 34 octets :

q{sI#I#+Fm+,hdcR2+MCd]edCtBK.DR3QK
M. Xcoder
la source
0

Japt , 35 octets

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

Essayez-le en ligne!

Légèrement non-golfé & comment ça marche

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é l'idée de cette solution Jelly , avec une différence dans la détermination des sauts potentiels:

  • La réponse Jelly utilise divmod pour voir si une paire a une différence de 2 lorsqu'elle est appliquée /3ou %3.
  • Cette réponse utilise uniquement %3et vérifie si la différence est 0 ou 2. Si la différence est 0, les deux cellules sont alignées verticalement et les non-sauts partagent toujours la propriété de (X+Y)%2 != 0.
Barboteur
la source
0

Python 2 , 97 octets

Basé sur la réponse de ovs mais 2 octets plus court et moins crypté. Convertit simplement les index en coordonnées 2D et teste la parité. Suppose que 0 à 8 index.

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

Essayez-le en ligne!

Luciano
la source