Czy mój wzór machnięcia jest legalny?

154

Większość smartfonów z Androidem pozwala użytkownikowi użyć wzoru machnięcia, aby otworzyć telefon:

blokada wzoru

Niektóre wzorce są uzasadnione, a inne niemożliwe. Biorąc pod uwagę wzorzec przesunięcia wejściowego, zwróć prawdę lub fałsz wskazujący, czy dany wzorzec wejściowy jest zgodny z prawem, czy nie.

Wejście

Siatka jest oznaczona wierszami od 1 do 9:

1 2 3   
4 5 6   
7 8 9

Dane wejściowe to liczba składająca się z węzłów odwiedzanych od pierwszego do ostatniego. Na przykład powyższy wzór machnięcia to 12357.

Dane wejściowe mogą być liczbą dziesiętną, łańcuchem lub listą liczb. Nie będzie zawierać 0, ponieważ nie ma węzła 0.

Poprawka: indeksowanie 0–8 jest dozwolone, ponieważ wiele języków indeksuje od 0. Jeśli używasz 0–8, konieczne będzie wskazanie jako takie na początku odpowiedzi i odpowiednie dostosowanie przypadków testowych.

Zasady

  • Każdy węzeł zaczyna się jako niezaproszony na początku i można go odwiedzić tylko raz. Każdy wzorzec, który odwiedza węzeł więcej niż jeden raz, jest fałszem.

  • Prawdziwy wzór musi zawierać co najmniej jedno przesunięcie, a więc co najmniej 2 węzły.

  • Nie można pominąć nieoczekiwanego węzła bezpośrednio z innym. Na przykład 13 jest fałszem, ponieważ 2 nie jest odwiedzane i jest bezpośrednio w linii.

  • Możliwe jest jedynie pominięcie odwiedzonego węzła. 42631 jest tego przykładem.

  • W przeciwnym razie linie mogą się krzyżować. Na przykład 1524 jest prawdą.

  • Załóżmy, że szerokości węzłów są nieznaczne i ignorują problemy praktyczne (grubość palca itp.). Tak więc 16 jest prawdą, chociaż w rzeczywistości może być nieco trudniejsze do osiągnięcia.

Przypadki testowe

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

To jest , więc wygrywa najmniejsza liczba bajtów.

stanri
źródło
2
Związane z.
Martin Ender
Czy lista wejściowa jest gwarantowana jako niepusta?
Zgarb
@Zgarb tak. To będzie niepuste.
stanri
Powiązane pytanie matematyczne: math.stackexchange.com/questions/205049/…
Pureferret

Odpowiedzi:

69

JavaScript (ES6), 64 bajty

Pobiera dane wejściowe jako tablicę liczb. Wartości Falsy to 0 lub NaN . Prawdziwe wartości są ściśle dodatnimi liczbami całkowitymi.

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

Przypadki testowe

W jaki sposób?

Preambuła

Dwie cyfry są naprzeciw siebie w pionie, w poziomie lub po przekątnej, jeżeli:

  • oba są nieparzyste, różnią się od siebie i różnią się od 5 (rysunek 1)
  • LUB oba są parzyste, a ich suma wynosi 10 (rysunek 2)

    przeciwne cyfry

Poza tym cyfra stojąca między dwiema przeciwnymi cyframi n i p jest równa (n + p) / 2 .

Sformatowany kod źródłowy

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
  )

Śledzenie poprzednich cyfr

Flagi dla odwiedzanych cyfr są przechowywane pod ujemnymi indeksami w tablicy wejściowej a , aby nie kolidowały z jej oryginalnymi elementami.

  • Jeśli p jest ustawione na -n :

    Jeśli bieżąca cyfra n nie była wcześniej wybrana, a[-n] ^= -nustawi flagę i pozwoli every()pętli przejść do następnej iteracji. W przeciwnym razie wyczyści flagę i zmusi pętlę do natychmiastowego niepowodzenia.

  • Jeśli p jest ustawione na niezdefiniowany :

    a[undefined] ^= undefineddaje w wyniku 0 , co również powoduje uszkodzenie pętli.

Wykrywanie przeciwnych cyfr

Poniższe wyrażenie służy do sprawdzenia, czy bieżąca cyfra n i poprzednia cyfra -p są cyframi przeciwnymi, zgodnie z definicją w preambule:

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

co jest równoważne z:

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

Uwaga: W JS wynik modulo ma taki sam znak jak dywidenda.

Można to interpretować jako:

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

Dlatego wyrażenie to zwraca 1 wtedy i tylko wtedy, gdy n i -p są cyframi przeciwnymi lub są tymi samymi cyframi nieparzystymi. Ponieważ cyfra nie może być wybrana dwukrotnie, ten drugi przypadek jest właściwie załatwiony.

Jeśli to wyrażenie zwraca 1 , testujemy [p / 2] (gdzie p jest teraz równe negowanej sumie cyfr), aby dowiedzieć się, czy „cyfra pośrednia” była wcześniej odwiedzana. W przeciwnym razie testujemy [0], który z pewnością jest prawdziwy.

O pierwszej iteracji

Pierwsza iteracja jest szczególnym przypadkiem, ponieważ nie ma poprzedniej cyfry i chcemy, aby odniosła bezwarunkowy sukces.

To osiągnąć poprzez uruchomienie s do 1 , gdyż dla każdej n w [1 .. 9] :

  • (1 * n) % 5 nie może być negatywne
  • ~(1 - n) nie może być równe 9

Oryginalna odpowiedź, 90 bajtów

Usunięto z tego postu, aby nie stał się zbyt gadatliwy. Możesz to zobaczyć tutaj .

Arnauld
źródło
-1 bajt, zastępując !!a[1]&w a[1]&&to, że każdy wartości truthy można zawrócić
Herman L
@HermanLauenstein Dzięki, to naprawdę wydaje się OK. (Teraz a[1]*jest jeszcze krótszy.)
Arnauld
1
Desperacko próbowałem wymyślić jakąś formułę has a node directly in line, ale nie zdawałem sobie sprawy, że byłoby to takie proste ...
Neil
@Neil Patrząc na historię zmian tego postu, jestem pewien, że możesz powiedzieć, że nie zdawałem sobie z tego sprawy natychmiast ... :)
Arnauld
Że można zastąpić ?a[-n]^=1:0z &&a[-n]^=1do -1, nie można przetestować (na telefon)
Stan Strum
45

x86 32-bitowy kod maszynowy, 62 60 bajtów

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

Pobiera długość listy ecxi wskaźnik do pierwszego elementu w edx, i zwraca wynik w al:

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

Istnieje 8 linii, które zawierają węzeł pośrodku:

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

Pogrupowałem je według różnicy między większą a mniejszą liczbą.

Różnica 2: 3 wiersze (od 1, 4 lub 7)
    1–3
    4 - 6
    7 - 9
Różnica w linii 4: 1 (od 3)
    3 - 7
Różnica 6: 3 wiersze (od 1, 2 lub 3)
    1 - 7
    2 - 8
    3 - 9
Różnica 8: 1 linia (od 1)
    1 - 9

Następnie przekonwertowałem to na tabelę wyszukiwania 2D zindeksowaną połową różnicy i mniejszą liczbą:

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

To tworzy „magiczną” bitmapę o 32 bitach. Aby go zindeksować, kod wypycha go na stos. Następnie wyodrębnia jeden bajt za pomocą jednego indeksu i z tego bajtu wyodrębnia jeden bit za pomocą drugiego indeksu. Wszystko to za pomocą jednej instrukcji:

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

Jeśli mapa bitowa wskazuje, że na środku jest węzeł, łatwo to obliczyć - dodaj połowę różnicy do mniejszej liczby.

Źródło zestawu:

    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
anatolig
źródło
Miły! Naprawdę to lubię bt byte ptr [esp + eax], ebx.
Arnauld
5
Miło widzieć rozwiązanie montażowe :) Możesz użyć cdqzamiast xor edx, edxas eaxzero. Możesz również złożyć dec eaxdo, bt [esp + eax - 1], ebxktóry ma taką samą długość, ale następnie pozwala usunąć inc ebxpóźniej. Powinno to zaoszczędzić dwa bajty.
Jester
Dzięki za pomysły! Udało ci się zabezpieczyć swoje miejsce w raju dla golfistów, jeśli taki istnieje :)
anatolyg
5
Myślę, że wszyscy możemy się zgodzić, że raj dla golfistów jest piekłem dla wszystkich innych.
Adonalsium
19

Python 2 , 140 131 114 104 99 bajtów

-2 bajty dzięki Jonathan Frech
-5 bajtów dzięki 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

Wypróbuj online!

Wyjaśnienie:

# 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

Wypróbuj online!

Tylko 8 par węzłów ma między nimi węzeł. Formuła zawiera dwa węzły jako jedną liczbę całkowitą 2^a-2^b-1. Liczbę tę można skrócić powtarzając moduł:

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==5najpierw sprawdza, czy taka para jest obecna, a następnie v-{l+n>>1}==vsprawdza, czy węzeł pomiędzy, który jest podany przez (a+b)/2, nie był jeszcze odwiedzany i qwywołuje błąd NameError. Przy użyciu porównania łańcuchowego między tymi parami następne porównanie jest wykonywane tylko wtedy, gdy poprzednie zostało zwrócone True.

ovs
źródło
17

Galaretka ,  24 22 19  18 bajtów

-2, ponieważ nie jesteśmy już zobowiązani do obsługi pustej listy
-1 przełączanie z łączenia, j@na konkatenację ;(brakujący element nie musi być spotykany w środku dla zastosowanej metody, będąc na początku trio jest w porządku )
-2 przejście od P¬aSHcelu oSH(aby spowodować dwie ponieważ spłaszczenie połowa 1jest 0.5, który odsącza się, i tak, posiadające wiele jednakowych wyników nie ma wpływu na sposób stosować albo)
-1 Dzięki p Xcoder (0 indeksowane wejście jest dozwolone)

d3ZIỊoSH;µƝFf9Ḷ¤Q⁼

Monadyczny link pobierający listę liczb całkowitych [0,8]i zwracający prawdziwą wartość ( 1), jeśli jest legalna, i falsey ( 0), jeśli nie.

Wypróbuj online! lub zobacz zestaw testowy .

W jaki sposób?

Patrzy na każdą sąsiednią parę zindeksowanych węzłów na liście wejściowej. Jeśli dzielenie liczb całkowitych przez trzy z dwóch różni się o 2, są one w górnym i dolnym rzędzie, jeśli moduł przez trzy z dwóch różni się o 2, znajdują się w lewej i prawej kolumnie. Suma takich par podzielona przez dwa to albo środkowy węzeł o indeksie 0 trzy-węzłowej linii, albo wartość niecałkowita - więc te wartości są najpierw wstawiane przed parą indeksowanych 0, a następnie dowolne fałszywe węzły (jak 0.5lub3.5) są usuwane, wynikowa lista list jest spłaszczana, a następnie usuwana z duplikatów (w celu uzyskania zachowanych, unikatowych wpisów) i ostatecznie porównywana z danymi wejściowymi - w przypadku legalnego przeciągnięcia wszystko to zakończy się brakiem działania, chociaż będzie nielegalne te dodadzą brakujące węzły środkowe i / lub usuwają zduplikowane węzły (zauważ, że dla listy danych wejściowych o długości 1 nie jest wymagana specjalna obudowa, ponieważ nie ma ona par sąsiednich):

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)

Poprzednia metoda

Galaretka ,  36  35 bajtów

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

Wypróbuj online! lub zobacz zestaw testowy .

W jaki sposób?

Podobnie do powyższego, ale konstruuje wszystkie możliwości linii trzech węzłów i wykonuje wyszukiwanie (zamiast sprawdzania, jak to robi za pomocą divmod do testowania i połowy sumy dla środkowego węzła).

Po pierwsze, budowa listy linii trzech węzłów:

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

Teraz podejmowanie decyzji:

...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
źródło
Jak to się dzieje do 19 bajtów, gdy jest kilka znaków Unicode?
Izkata
@Izkata Jelly używa własnej strony kodowej, którą można zobaczyć, klikając „bajty” w nagłówku. W postaci nieprzetworzonego bajtu każdy ze znaków Unicode, które można zobaczyć w kodzie źródłowym, jest tylko jednym bajtem.
Jonathan Allan
15

Stax , 28 bajtów

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

Uruchom

Daje 0 dla false, a dodatnie liczby całkowite dla true. Odpowiada to reprezentacji ascii tego samego programu.

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

Ogólną ideą jest obliczenie kilku niezbędnych warunków dla legalnych wzorców machnięcia i pomnożenie ich wszystkich razem.

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
rekurencyjny
źródło
Sprytne korzystanie z Yrejestru.
Weijun Zhou
Kolejny problem na githubie.
Weijun Zhou
1
Przypadkowo naprawiłem już ten błąd, ale dopiero teraz go wdrożyłem. (nie wpływa to na mój program)
rekurencyjny
1
Może to zabrzmieć dziwnie, ale możesz upuścić pierwszą vi dołączyć 1jako wartość fałszowania. 2a powyżej są prawdą.
Weijun Zhou
10

JavaScript, 112 bajtów

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)

Może jakiś język oparty na wyrażeniach regularnych powinien być krótszy. Ale nie wiem.

Dzięki Neilowi ​​zmień, )(?!aby |zapisać 3 bajty.

tsh
źródło
@WeijunZhou Mam prawdę o 213, co jest nie tak?
tsh
Nie ma nic złego, przepraszam za to.
Weijun Zhou
Teraz, gdy wyjaśniono OP, nie udaje się 144.
Weijun Zhou
1
@WeijunZhou powinien zostać naprawiony;
Jeszcze
Jeśli się zastanawiasz, wydaje się, że port Retina 0.8.2 działa na 98 bajtach.
Neil
6

Retina 0.8.2 , 98 bajtów

Pod wpływem odpowiedzi tsh . Próbowałem „przeformułować” to odwrotnie, dopasowując nieprawidłowe przesunięcia, a następnie 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)|.$)

Wypróbuj online

mbomb007
źródło
6

Łuska , 25 20 bajtów

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

Pobiera listę liczb całkowitych z indeksowaniem opartym na 0. Zwraca 0 lub 1. Wypróbuj online!

Wyjaśnienie

Ukradłem kilka pomysłów z odpowiedzi Jonathana Allana na galaretkę . Pomysł jest taki sam: wstaw nowy „średni węzeł” między każdą sąsiednią parą, odfiltruj te, które nie są rzeczywistymi węzłami, usuń duplikaty i porównaj z oryginalną listą. Jeśli oryginalna lista zawiera duplikaty, wynikiem jest fałsz. Jeśli lista pomija nieoczekiwany węzeł, to jest obecna na przetworzonej liście między odpowiednią parą, a wynikiem jest fałsz. Jeśli dane wejściowe są singletonem, przetworzona lista jest pusta, a wynikiem jest fałsz. W przeciwnym razie jest to prawda.

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
źródło
3

C ++, 267 256 bajtów

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

Aby sprawdzić, czy wzorzec nie przeskakuje nie odwiedzonego węzła, wykonuje kilka czynności:

  1. Oblicz, dgdzie djest numeryczna różnica między bieżącym węzłem a ostatnim węzłem.
  2. Jeśli djest nieparzysty, nie trzeba go sprawdzać, nie można pominąć węzła.
  3. Jeśli djest równe 4lub 8, wówczas skok odbywa się między węzłami 1-9lub 3-7, więc sprawdź węzeł5
  4. Jeśli dma wartość 2, a środkowy węzeł ( (last_node + current_node)/2) ma wartość 2,5 lub 8, sprawdź węzeł środkowy
  5. Jeśli djest 6, sprawdź to samo co poprzednio, ale z 4, 5lub6

Parametry są int[]równe liczbie elementów. Zwraca wartość, intktóra może być interpretowana jako booltyp

HatsuPointerKun
źródło
!(d%2)=> d%2<1powinno działać.
Zacharý
256 bajtów
Zacharý
Nauczyłem się nowej sztuczki: int s[]=> int*s. Myślę, że to zadziała.
Zacharý
2

Perl, 135 bajtów (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()}

Wersja lekko nie golfowa

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

Dane wyjściowe za pośrednictwem kodu wyjścia. 0jest prawdą, każda inna wartość to fałsz. Zgodnie z meta-konsensusem wyjście STDERR w przypadku awarii jest ignorowane.

Prawdopodobnie istnieje szybszy sposób na sprawdzenie zasady „nie można przeskoczyć” niż tylko wypisanie wszystkich możliwości.

Silvio Mayolo
źródło
2

MATL , 42 41 39 bajtów

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

To produkuje

  • niepusty wektor kolumny zawierający tylko niezerowe liczby jako prawdziwe dane wyjściowe; lub
  • niepusty wektor kolumny zawierający co najmniej zero jako fałsz.

Tutaj możesz przeczytać, dlaczego te dane wyjściowe są odpowiednio prawdziwe i fałszywe.Wypróbuj online!

Lub zweryfikuj wszystkie przypadki testowe za pomocą stopki zawierającej standardowy test na prawdziwość / fałsz.

Luis Mendo
źródło
2

Stax , 73 72 66 65 bajtów CP437

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

79 bajtów po rozpakowaniu,

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

Uruchom i debuguj online!

lub uruchom test partii , gdzie meXjest nagłówek, aby Stax mógł przetwarzać dane wielowierszowe.

Wdrożenie bez użycia skrótu. Wypisuje liczbę ściśle dodatnią (w rzeczywistości liczbę nieudanych testów) dla przypadków fałszowania i 0dla prawdy .

Wyjaśnienie

dczyści stos wejściowy. W xkażdym razie dane wejściowe są zmienne .

4{cAs-5F generuje pierwszą część listy środkowego węzła.

132396978714EE na stałe wpisuje drugą część listy środkowego węzła.

L3/Zbiera wszystkie elementy w głównym stosie i dzieli na części, z których każda zawiera 3 elementy, w wyniku czego powstaje tablica a, która jest tylko tablicą wszystkich nieprawidłowych grup 3-węzłowych.

{xs:IBc0<A*++cEd:-1=sccHs|M=s{U>m|A**mEDla każdej listy nieprawidłowych węzłów wykonaj następujące kontrole. Wyniki kontroli są andedytowane przy użyciu **. Ponieważ istnieje 8 niepoprawnych list węzłów, wynikiem tego kodu będzie tablica 8 elementów. Final Ewysyła tablicę do poszczególnych elementów na głównym stosie.

xs:I pobierz indeks elementów listy węzłów w tablicy wejściowej.

Bc0<A*++Jeśli indeks „środkowego węzła” (np. 5W zestawie węzłów 1,5,9) wynosi -1(co oznacza, że ​​nie istnieje on w tablicy wejściowej), zmień indeks na 9.

cEd:-1=sprawdzić, czy dwa „węzły końcowe” (np. 1,5w zestawie węzłów 1,5,9) sąsiadują ze sobą w tablicy wejściowej.

sccHs|M= przetestować, czy transformowany indeks „węzła środkowego” jest większy niż indeks dwóch „węzłów końcowych”, co obejmuje dwa przypadki: brakuje „węzła środkowego” lub „węzeł środkowy” występuje po dwóch „węzłach końcowych”

s{U>m|Asprawdza, czy oba indeksy „węzłów końcowych” są nieujemne. (tzn. oba pojawiają się na wejściu).

Przeprowadzane są dwa dodatkowe testy,

x%2< sprawdza, czy tablica wejściowa jest singletonem.

xu%x%=! sprawdza, czy są to węzły, które były odwiedzane dwukrotnie.

Na głównym stosie znajduje się 10 wyników testu (po jednym dla każdej listy nieprawidłowych węzłów oraz dwa dodatkowe testy).

L|+ zbiera 10 elementów i dodaje je. |amożna również użyć, który po prostu sprawdza, czy w tablicy są jakieś prawdziwe elementy.

Wyjściowy wynik.

Weijun Zhou
źródło
2

Java, 375 355 bajtów

-20 bajtów dzięki Zacharýowi

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

To jest część tej odpowiedzi i działa na tych samych zasadach

HatsuPointerKun
źródło
Łał Odpowiadasz w Javie.
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;}powinien działać (kolejność operacji)
Zacharý
Możesz zmienić (d==2)na właśnie d==2, wcześniej to przeoczyłem.
Zacharý
d%2==0=>d%2<1
Zacharý
0

Pyth , 33 bajty

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

Zestaw testowy.

Wykorzystuje indeksowanie 0.

Wyjaśnienie

q {@ U9.nm + mc | g1aZksd2-MC.DR3d_dC, t -> Pełny program. Dane wejściowe: lista L ze STDIN.

                               , t -> Sparuj L z L bez pierwszego elementu.
                              C -> Transpozycja.
       m -> Mapa nad listą par (listy 2-elementowe):
        + mc | g1aZksd2-MC.DR3d -> Funkcja do mapowania (zmienna: d):
                         R d -> Dla każdego elementu d ...
                       .D 3 -> ... Weź divmod o 3.
                      C -> Tranpose.
                    -M -> Zmniejsz każdy przez odjęcie.
         m -> Dla każdej różnicy (zmienna: k):
            g1aZl -> Is | k | ≤ 1?
           | sd -> Jeśli to fałsz, zastąp go sumą d.
          c 2 -> Podziel przez 2.
        + _d -> Dołącz odwrotność d do wyniku mapowania.
     .n -> Spłaszcz.
  @ U9 -> Skręć w skrzyżowanie za pomocą (ℤ ∩ [0; 9)).
 {-> Deduplikuj.
q -> I sprawdź, czy wynik jest równy L.

Alternatywne podejście do 34 bajtów :

q{sI#I#+Fm+,hdcR2+MCd]edCtBK.DR3QK
Pan Xcoder
źródło
0

Japt , 35 bajtów

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

Wypróbuj online!

Nieco golfa i jak to działa

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?

Przeniesiono pomysł z tego rozwiązania Jelly , z pewną różnicą w określaniu potencjalnych skoków:

  • Odpowiedź Jelly używa divmod, aby sprawdzić, czy para ma różnicę 2 po zastosowaniu /3lub %3.
  • Ta odpowiedź używa tylko %3i sprawdza, czy różnica wynosi 0 lub 2. Jeśli różnica wynosi 0, dwie komórki są wyrównane w pionie, a elementy bez skoku nadal mają tę samą właściwość (X+Y)%2 != 0.
Bubbler
źródło
0

Python 2 , 97 bajtów

Na podstawie odpowiedzi ovs, ale 2 bajty krótsze i mniej tajemnicze. Po prostu konwertuje indeksy na współrzędne 2d i testuje parzystość. Przyjmuje indeksy 0–8.

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

Wypróbuj online!

Luciano
źródło