Ist mein Wischmuster legal?

154

Bei den meisten Android-Smartphones kann der Benutzer ein Wischmuster verwenden, um das Telefon zu öffnen:

Sperrmuster

Bestimmte Muster sind legitim und andere sind unmöglich. Geben Sie bei einem Eingabewischmuster eine Wahrheit oder eine Falschangabe zurück, die angibt, ob das angegebene Eingabemuster zulässig ist oder nicht.

Eingang

Das Raster ist zeilenweise mit 1 bis 9 gekennzeichnet:

1 2 3   
4 5 6   
7 8 9

Die Eingabe ist eine Zahl, die aus den vom ersten bis zum letzten besuchten Knoten besteht. Das Wischmuster oben lautet beispielsweise 12357.

Die Eingabe kann eine Dezimalzahl, eine Zeichenfolge oder eine Liste von Zahlen sein. Es wird keine 0 enthalten, da es keinen Knoten 0 gibt.

Änderung: Indexierung von 0-8 ist zulässig, da viele Sprachen einen Index von 0 aufweisen. Wenn Sie 0-8 verwenden, müssen Sie dies zu Beginn Ihrer Antwort angeben und die Testfälle entsprechend anpassen.

Regeln

  • Jeder Knoten startet zunächst als nicht besucht und darf nur einmal besucht werden. Jedes Muster, das einen Knoten mehr als einmal besucht, ist falsch.

  • Ein wahres Muster muss mindestens einen Schlag enthalten, also mindestens 2 Knoten.

  • Es ist nicht möglich, einen nicht besuchten Knoten direkt neben einem anderen zu überspringen. Zum Beispiel ist 13 falsch, weil 2 nicht besucht ist und direkt in der Reihe steht.

  • Es ist nur möglich, einen besuchten Knoten zu überspringen. 42631 ist ein Beispiel dafür.

  • Linien können sich sonst kreuzen. Zum Beispiel ist 1524 wahr.

  • Angenommen, die Knotenbreiten sind unbedeutend und ignorieren praktische Probleme (Fingerdicke usw.). 16 ist also wahr, auch wenn es in der Realität etwas schwieriger zu erreichen ist.

Testfälle

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

Dies ist , daher gewinnt die geringste Anzahl von Bytes.

Stanri
quelle
2
Verbunden.
Martin Ender
Ist die Eingabeliste garantiert nicht leer?
Zgarb,
@ Zgarb ja. Es wird nicht leer sein.
Stanri
Verwandte Mathematik-Frage: math.stackexchange.com/questions/205049/…
Pureferret

Antworten:

69

JavaScript (ES6), 64 Byte

Nimmt die Eingabe als Array von Zahlen. Falsche Werte sind 0 oder NaN . Wahrheitswerte sind ausschließlich positive ganze Zahlen.

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

Testfälle

Wie?

Präambel

Zwei Ziffern stehen sich vertikal, horizontal oder diagonal gegenüber, wenn:

  • sie sind beide seltsam, verschieden voneinander und verschieden von 5 (Abbildung 1)
  • ODER sie sind beide gerade und ihre Summe ist 10 (Abbildung 2)

    entgegengesetzte Ziffern

Außerdem ist die Ziffer, die zwischen zwei gegenüberliegenden Ziffern n und p steht, gleich (n + p) / 2 .

Formatierter Quellcode

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
  )

Verfolgen Sie die vorherigen Ziffern

Flags für besuchte Ziffern werden bei negativen Indizes im Eingabearray a gespeichert , damit sie nicht mit den ursprünglichen Elementen kollidieren.

  • Wenn p auf -n gesetzt ist :

    Wenn die aktuelle Ziffer n zuvor nicht ausgewählt wurde, a[-n] ^= -nwird das Flag gesetzt und die every()Schleife mit der nächsten Iteration fortgesetzt. Andernfalls wird das Flag gelöscht und die Schleife sofort zum Fehlschlagen gezwungen.

  • Wenn p auf undefiniert gesetzt ist :

    a[undefined] ^= undefinedergibt 0 , was auch den Fehler der Schleife erzwingt.

Entgegengesetzte Ziffern erkennen

Der folgende Ausdruck wird verwendet, um zu testen, ob die aktuelle Ziffer n und die vorherige Ziffer -p entgegengesetzte Ziffern sind, wie in der Präambel definiert:

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

was äquivalent ist zu:

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

Hinweis: In JS hat das Modulo-Ergebnis das gleiche Vorzeichen wie die Dividende.

Es kann interpretiert werden als:

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

Daher gibt dieser Ausdruck genau dann 1 zurück, wenn n und -p entgegengesetzte Ziffern sind oder dieselbe ungerade Ziffer sind. Da eine Ziffer nicht zweimal ausgewählt werden kann, wird letzterer Fall trotzdem korrekt behandelt.

Wenn dieser Ausdruck 1 zurückgibt , testen wir a [p / 2] (wobei p jetzt gleich der negierten Summe der Ziffern ist), um zu wissen, ob die 'Zwischenziffer' zuvor besucht wurde. Ansonsten testen wir eine [0], die garantiert wahr ist.

Über die erste Iteration

Die erste Iteration ist ein Sonderfall, da es keine vorherige Ziffer gibt und wir möchten, dass sie bedingungslos erfolgreich ist.

Wir erreichen das, indem wir p auf 1 initialisieren , weil für jedes n in [1 .. 9] :

  • (1 * n) % 5 kann nicht negativ sein
  • ~(1 - n) kann nicht gleich 9 sein

Ursprüngliche Antwort, 90 Bytes

Wurde aus diesem Beitrag entfernt, damit er nicht zu ausführlich wird. Sie können es hier sehen .

Arnauld
quelle
-1 Byte durch Ersetzen !!a[1]&durch a[1]&&, da jeder wahrheitsgemäße Wert zurückgegeben werden kann
Herman L
@HermanLauenstein Danke, das scheint in der Tat in Ordnung zu sein. (Jetzt a[1]*ist es noch kürzer.)
Arnauld
1
Ich habe verzweifelt versucht, eine Formel für zu finden has a node directly in line, ich wusste nicht, dass es so einfach sein würde ...
Neil,
@Neil Wenn du dir den Revisionsverlauf dieses Posts ansiehst, kannst du sicher sagen, dass ich das auch nicht sofort bemerkt habe ... :)
Arnauld
Denken Sie, Sie können ?a[-n]^=1:0mit &&a[-n]^=1-1 ersetzen , können nicht testen (auf dem Handy)
Stan Strum
45

x86-32-Bit-Computercode, 62-60 Byte

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

Es empfängt die Länge der Liste in ecxund einen Zeiger auf das erste Element in edxund gibt das Ergebnis zurück in al:

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

Es gibt 8 Zeilen, die einen Knoten in der Mitte enthalten:

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

Ich habe sie nach dem Unterschied zwischen der größeren und der kleineren Zahl gruppiert.

Unterschied 2: 3 Zeilen (ab 1, 4 oder 7)
    1 - 3
    4 - 6
    7 - 9
Unterschied 4: 1 Linie (ab 3)
    3 - 7
Unterschied 6: 3 Zeilen (ab 1, 2 oder 3)
    1 - 7
    2 - 8
    3 - 9
Unterschied 8: 1 Linie (ab 1)
    1 - 9

Dann habe ich das in eine 2-D-Nachschlagetabelle konvertiert, die nach halber Differenz und kleinerer Zahl indiziert ist:

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

Dies ergibt eine "magische" Bitmap von 32 Bits. Um es zu indizieren, schiebt der Code es in den Stapel. Dann extrahiert es ein Byte unter Verwendung eines Index und aus diesem Byte extrahiert es ein Bit unter Verwendung des anderen Index. All dies mit einer Anweisung:

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

Wenn die Bitmap angibt, dass sich in der Mitte ein Knoten befindet, ist die Berechnung einfach. Addieren Sie die Hälfte der Differenz zur kleineren Zahl.

Versammlungsquelle:

    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
quelle
Nett! Ich mag das wirklich bt byte ptr [esp + eax], ebx.
Arnauld
5
Schön zu sehen, Montagelösung :) Sie können cdqanstelle von xor edx, edxas eaxis zero verwenden. Außerdem können falten Sie die dec eaxin bt [esp + eax - 1], ebxdenen gleiche Länge , aber dann können Sie das entfernen inc ebxspäter. Das sollte Ihnen zwei Bytes sparen.
Jester
Danke für die Ideen! Sie haben sich Ihren Platz im
Golfparadies
5
Ich denke, wir sind uns alle einig, dass das Golfparadies die Hölle für alle anderen ist.
Adonalsium
19

Python 2 , 140 131 114 104 99 Bytes

-2 Bytes dank Jonathan Frech
-5 Bytes dank 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

Probieren Sie es online!

Erläuterung:

# 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

Probieren Sie es online!

Nur 8 Knotenpaare haben einen Knoten dazwischen. Ein Knotenpaar kann durch die Formel als einzelne Ganzzahl dargestellt werden 2^a-2^b-1. Diese Zahl kann durch wiederholtes Modulo verkürzt werden:

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==5prüft zunächst, ob ein solches Paar vorhanden ist, v-{l+n>>1}==vprüft dann , ob der von angegebene dazwischenliegende Knoten (a+b)/2noch nicht besucht wurde und qlöst einen NameError aus. Bei Verwendung eines verketteten Vergleichs zwischen diesen Paaren wird der nächste Vergleich nur ausgeführt, wenn der vorherige zurückgegeben wird True.

ovs
quelle
17

Jelly ,  24 22 19  18 Bytes

-2 , da wir nicht mehr erforderlich sind , eine leere Liste zu handhaben
, -1 Umschalten von verbinden j@, verketten, ;(der verpassten Punkt nicht braucht beschäftigt in der Mitte für das Verfahren angetroffen werden, zu Beginn des Trios zu sein , ist in Ordnung )
-2 vom Einschalten P¬aSHbis oSH(OK zwei Ergebnisse haben , da wir glätten, die Hälfte 1ist 0.5die ohnehin herausgefiltert wird, und verwendet haben Auswirkungen auf entweder auf dem Verfahren nicht mehr gleichen Ergebnisse mit)
-1 Dank Herrn Xcoder (0-indiziert Eingabe ist erlaubt)

d3ZIỊoSH;µƝFf9Ḷ¤Q⁼

Ein monadischer Link, der eine Liste von Ganzzahlen [0,8]aufnimmt 1und einen Wahrheitswert ( 0) zurückgibt, wenn dies legal ist, und einen Falschwert ( ), wenn dies nicht der Fall ist .

Probieren Sie es online! oder sehen Sie sich eine Testsuite an .

Wie?

Betrachtet jedes benachbarte Paar von 0-indizierten Knoten in der Eingabeliste. Unterscheidet sich die Ganzzahldivision durch drei der beiden durch 2, befinden sie sich in der oberen und unteren Reihe. Unterscheidet sich das Modulo durch drei der beiden durch 2, befinden sie sich in der linken und rechten Spalte. Die Summe solcher Paare geteilt durch zwei ist entweder der 0-indizierte Mittelknoten einer Drei-Knoten-Linie oder ein nicht ganzzahliger Wert - diese Werte werden also zuerst vor dem 0-indizierten Paar und dann vor jedem eingefügt Scheinknoten (wie 0.5oder3.5) entfernt werden, wird die resultierende Liste von Listen abgeflacht und dann desupliziert (um auftragsbewahrte, eindeutige Einträge zu erhalten) und schließlich mit der Eingabe verglichen - für einen legalen Swipe wird all dies zu einem No-Op, solange es illegal ist Diese fügen fehlende Mittelknoten hinzu und / oder entfernen doppelte Knoten (beachten Sie, dass für eine Eingabeliste der Länge 1 keine spezielle Groß- / Kleinschreibung erforderlich ist, da keine benachbarten Paare vorhanden sind):

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)

Vorherige Methode

Jelly ,  36  35 Bytes

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

Probieren Sie es online! oder sehen Sie sich eine Testsuite an .

Wie?

Ähnlich wie oben, jedoch werden alle Möglichkeiten mit drei Knotenlinien konstruiert und eine Suche durchgeführt (anstatt die Summe für den mittleren Knoten mit divmod zu testen und zu halbieren).

Erstens die Konstruktion der Liste der Dreiknotenlinien:

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

Nun die Entscheidungsfindung:

...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
quelle
Wie kommt es zu 19 Bytes, wenn es eine Reihe von Unicode-Zeichen gibt?
Izkata
@Izkata Jelly verwendet eine eigene Codepage, die Sie durch Klicken auf "Bytes" in der Kopfzeile anzeigen können. In seiner rohen Byteform ist jedes der Unicode-Zeichen, die Sie im Quellcode sehen können, nur ein einzelnes Byte.
Jonathan Allan
15

Stax , 28 Bytes

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

Starte es

Es erzeugt 0 für falsch und positive ganze Zahlen für wahr. Dies ist die entsprechende ASCII-Darstellung desselben Programms.

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

Die allgemeine Idee ist, mehrere notwendige Bedingungen für legale Wischmuster zu berechnen und sie alle miteinander zu multiplizieren.

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
rekursiv
quelle
Clevere Verwendung des YRegisters.
Weijun Zhou
Ein weiteres Problem bei Github.
Weijun Zhou
1
Ich hatte diesen Fehler zufällig bereits behoben, ihn aber erst jetzt bereitgestellt. (es hat keinen Einfluss auf mein Programm)
rekursiver
1
Es mag seltsam klingen, aber Sie können den ersten fallen lassen vund 1als falschen Wert einfügen. 2und darüber sind wahr.
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)

Vielleicht sollte eine auf Regex basierende Sprache kürzer sein. Aber ich weiß es nicht.

Dank Neil, ändern )(?!zu |3 Bytes zu speichern.

tsh
quelle
@WeijunZhou Ich habe für 213 wahr, was ist los?
Dienstag,
Nichts ist falsch, tut mir leid.
Weijun Zhou
Jetzt seit OP geklärt, scheitert z 144.
Weijun Zhou
1
@ WeijunZhou sollte behoben werden; 2 weitere Bytes ...
tsh
Für den Fall, dass Sie sich fragen, scheint ein Retina 0.8.2-Port mit 98 Bytes zu funktionieren.
Neil
6

Retina 0.8.2 , 98 Bytes

Beeinflusst durch die Antwort von tsh . Ich habe versucht, es "neu zu formulieren", um das Gegenteil zu erreichen.

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

Probieren Sie es online aus

mbomb007
quelle
6

Schale , 25 bis 20 Bytes

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

Nimmt eine Liste von Ganzzahlen mit 0-basierter Indizierung auf. Gibt 0 oder 1 zurück. Probieren Sie es online aus!

Erläuterung

Ich habe einige Ideen aus Jonathan Allans Gelee-Antwort gestohlen . Die Idee ist dieselbe: Fügen Sie einen neuen "Durchschnittsknoten" zwischen jedes benachbarte Paar ein, filtern Sie diejenigen heraus, die keine tatsächlichen Knoten sind, entfernen Sie Duplikate und vergleichen Sie sie mit der ursprünglichen Liste. Wenn die ursprüngliche Liste Duplikate enthält, ist das Ergebnis falsch. Wenn die Liste einen nicht besuchten Knoten überspringt, ist er in der verarbeiteten Liste zwischen dem entsprechenden Paar vorhanden und das Ergebnis ist falsch. Wenn die Eingabe ein Singleton ist, ist die verarbeitete Liste leer und das Ergebnis ist falsch. Ansonsten ist es wahr.

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

Um zu überprüfen, ob das Muster einen nicht besuchten Knoten nicht überspringt, werden verschiedene Aktionen ausgeführt:

  1. Berechnen Sie, dwo dsich die numerische Differenz zwischen dem aktuellen und dem letzten Knoten befindet.
  2. Wenn des ungerade ist, muss es nicht überprüft werden. Es kann keinen Knoten überspringen.
  3. Wenn dgleich 4oder ist 8, erfolgt der Sprung zwischen den Knoten 1-9oder 3-7. Überprüfen Sie daher den Knoten5
  4. Wenn d2 ist und der mittlere Knoten ( (last_node + current_node)/2) entweder 2,5 oder 8 ist, dann überprüfe den mittleren Knoten
  5. Wenn d6 ist, überprüfen Sie das gleiche wie zuvor, aber mit 4, 5oder6

Die Parameter sind ein int[]und es ist die Anzahl der Elemente. Es gibt einen zurück, intder als boolTyp interpretiert werden kann

HatsuPointerKun
quelle
!(d%2)=> d%2<1sollte funktionieren.
Zacharý
256 Bytes
Zacharý
Ich habe einen neuen Trick gelernt: int s[]=> int*s. Ich denke das wird funktionieren.
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()}

Leicht ungolfierte Version

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

Ausgänge über Exit-Code. 0ist wahr, jeder andere Wert ist falsch. Wie pro Meta Konsens wird STDERR Ausgabe im Fehlerfall ignoriert.

Es gibt wahrscheinlich eine schnellere Möglichkeit, die Regel "Überspringen nicht möglich" zu überprüfen, als einfach alle Möglichkeiten aufzulisten.

Silvio Mayolo
quelle
2

MATL , 42 41 39 Bytes

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

Dies erzeugt

  • ein nicht leerer Spaltenvektor, der nur Zahlen ungleich Null als wahrheitsgemäße Ausgabe enthält; oder
  • ein nicht leerer Spaltenvektor, der mindestens eine Null als falsch enthält.

Hier können Sie nachlesen, warum diese Ausgaben jeweils wahr und falsch sind. Probieren Sie es online!

Oder überprüfen Sie alle Testfälle , mit Fußzeile Code, der den Standard enthält Test für Truthiness / falsiness.

Luis Mendo
quelle
2

Stax , 73 72 66 65 Bytes CP437

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

79 Bytes beim Auspacken,

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

Online ausführen und debuggen!

oder führen Sie den Batch-Test durch , wobei meXsich ein Header befindet, damit Stax mehrzeilige Eingaben verarbeiten kann.

Implementierung ohne Verwendung von Hash. Gibt eine streng positive Zahl (tatsächlich die Anzahl der fehlgeschlagenen Tests) für falsche und 0für wahrheitsgemäße Fälle aus.

Erläuterung

dLöscht den Eingabestapel. Die Eingabe ist xohnehin variabel .

4{cAs-5F Erzeugt den ersten Teil der Liste der mittleren Knoten.

132396978714EE codiert den zweiten Teil der Liste der mittleren Knoten fest.

L3/Sammelt alle Elemente im Hauptstapel und teilt sie in Teile auf, die jeweils 3 Elemente enthalten. Das Ergebnis ist ein Array a, das nur das Array aller ungültigen 3-Knoten-Gruppen ist.

{xs:IBc0<A*++cEd:-1=sccHs|M=s{U>m|A**mEFühren Sie für jede ungültige Knotenliste die folgenden Überprüfungen durch. Das Ergebnis der Prüfergebnisse wird andmit dem **. Da es 8 ungültige Knotenlisten gibt, ist das Ergebnis dieses Codes ein Array von 8 Elementen. Das endgültige EVersenden des Arrays an seine einzelnen Elemente im Hauptstapel.

xs:I Ruft den Index der Knotenlistenelemente im Eingabearray ab.

Bc0<A*++Wenn der Index des "mittleren Knotens" (z. B. 5im Knotensatz 1,5,9) ist -1(was bedeutet, dass er im Eingabearray nicht vorhanden ist), ändern Sie den Index in 9.

cEd:-1=Testen Sie, ob die beiden "Endknoten" (z. B. 1,5im Knotensatz 1,5,9) im Eingangsarray benachbart sind.

sccHs|M= Testen Sie, ob der transformierte Index des "mittleren Knotens" größer ist als der der beiden "Endknoten". Dies schließt zwei Fälle ein: Der "mittlere Knoten" fehlt, oder der "mittlere Knoten" kommt nach den beiden "Endknoten".

s{U>m|Atestet, ob beide Indizes der "Endknoten" nicht negativ sind. (dh beide erscheinen in der Eingabe).

Es werden zwei zusätzliche Tests durchgeführt.

x%2< testet, ob das Eingabearray ein Singleton ist.

xu%x%=! testet, ob Knoten doppelt besucht wurden.

Der Hauptstapel enthält 10 Testergebnisse (eines für jede ungültige Knotenliste plus zwei zusätzliche Tests).

L|+sammelt die 10 Elemente und fügt sie hinzu. |akönnte auch verwendet worden sein, die einfach prüft, ob es irgendwelche wahrheitsgemäßen Elemente auf dem Array gibt.

Implizite Ausgabe.

Weijun Zhou
quelle
2

Java, 375 355 Bytes

-20 Bytes dank 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;}

Dies ist eine Portierung dieser Antwort und sie funktioniert nach den gleichen Grundsätzen

HatsuPointerKun
quelle
Woah. Sie sind in Java verärgert.
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;}sollte funktionieren (Reihenfolge der Operationen)
Zacharý
Sie können (d==2)einfach ändern d==2, ich habe das vorher übersehen.
Zacharý
d%2==0=>d%2<1
Zacharý
0

Pyth , 33 Bytes

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

Testsuite.

Verwendet eine 0-basierte Indizierung.

Erläuterung

q {@ U9.nm + mc | g1aZksd2-MC.DR3d_dC, t -> Volles Programm. Eingabe: eine Liste L von STDIN.

                               , t -> Paar L mit L ohne das erste Element.
                              C -> Transponieren.
       m -> Karte über die Liste der Paare (2-Element-Listen):
        + mc | g1aZksd2-MC.DR3d -> Die abzubildende Funktion (Variable: d):
                         R d -> Für jedes Element von d ...
                       .D 3 -> ... Nimm seinen divmod mit 3.
                      C -> Tranpose.
                    -M -> Jeweils durch Subtraktion reduzieren.
         m -> Für jede Differenz (Variable: k):
            g1aZl -> Is | k | ≤ 1?
           | sd -> Wenn das falsch ist, ersetzen Sie es durch die Summe von d.
          c 2 -> Dividiere durch 2.
        + _d -> Hänge die Umkehrung von d an das Ergebnis der Zuordnung an.
     .n -> Abflachen.
  @ U9 -> Nehmen Sie die Kreuzung mit (ℤ ∩ [0; 9)).
 {-> Deduplizieren.
q -> Und überprüfe, ob das Ergebnis gleich L ist.

Alternativer Ansatz für 34 Bytes :

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

Japt , 35 Bytes

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

Probieren Sie es online!

Etwas ungolfed & wie es funktioniert

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?

Portierte die Idee aus dieser Jelly-Lösung mit einigen Unterschieden bei der Bestimmung möglicher Sprünge:

  • Die Jelly-Antwort verwendet divmod, um zu sehen, ob ein Paar beim Anwenden von /3oder einen Unterschied von 2 hat %3.
  • Diese Antwort verwendet nur %3und prüft, ob die Differenz 0 oder 2 ist. Wenn die Differenz 0 ist, sind die beiden Zellen vertikal ausgerichtet und Nicht-Sprünge haben immer noch die Eigenschaft von (X+Y)%2 != 0.
Bubbler
quelle
0

Python 2 , 97 Bytes

Basierend auf der Antwort von ovs, aber 2 Bytes kürzer und weniger kryptisch. Konvertiert einfach Indizes in 2D-Koordinaten und testet die Parität. Nimmt 0-8 Indizes an.

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

Probieren Sie es online!

Luciano
quelle