Apakah Pola Swipe Saya Legal?

154

Sebagian besar ponsel pintar Android memungkinkan pengguna untuk menggunakan pola gesek untuk membuka telepon mereka:

kunci pola

Pola tertentu sah, dan yang lain tidak mungkin. Diberikan pola sapuan input, kembalikan yang benar atau salah yang menunjukkan apakah pola input yang diberikan legal atau tidak.

Memasukkan

Kotak diberi label baris-bijaksana 1 hingga 9:

1 2 3   
4 5 6   
7 8 9

Input adalah angka yang terdiri dari node yang dikunjungi dari awal hingga akhir. Misalnya, pola gesek di atas adalah 12357.

Input dapat berupa angka desimal, string atau daftar angka. Tidak akan berisi 0 karena tidak ada simpul 0.

Amandemen: pengindeksan 0-8 diperbolehkan karena banyak bahasa mengindeks dari 0. Jika Anda menggunakan 0-8, Anda perlu mengindikasikannya di awal jawaban Anda dan sesuaikan kasus uji.

Aturan

  • Setiap node dimulai sebagai tidak dikunjungi pada awalnya dan hanya dapat dikunjungi sekali. Pola apa pun yang mengunjungi sebuah simpul lebih dari sekali adalah salah.

  • Pola kebenaran harus mengandung setidaknya satu gesekan, jadi minimal 2 simpul.

  • Tidak mungkin untuk melewati simpul yang belum dikunjungi secara langsung sejalan dengan yang lain. Misalnya, 13 adalah palsu karena 2 tidak dikunjungi dan langsung sejalan.

  • Hanya dimungkinkan untuk melewati simpul yang dikunjungi. 42631 adalah contoh dari ini.

  • Garis bisa melewati sebaliknya. Misalnya, 1524 adalah kebenaran.

  • Asumsikan lebar simpul tidak signifikan dan mengabaikan masalah praktis (ketebalan jari, dll). Jadi 16 adalah kebenaran meskipun mungkin sedikit lebih sulit untuk dicapai dalam kenyataan.

Uji Kasus

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

Ini adalah , sehingga jumlah byte terkecil yang menang.

stanri
sumber
2
Terkait.
Martin Ender
Apakah daftar input dijamin tidak kosong?
Zgarb
@ Zgarb ya. Itu akan kosong.
stanri
Pertanyaan terkait matematika: math.stackexchange.com/questions/205049/…
Pureferret

Jawaban:

69

JavaScript (ES6), 64 byte

Mengambil input sebagai array angka. Nilai palsu adalah 0 atau NaN . Nilai kebenaran adalah bilangan bulat yang benar-benar positif.

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

Uji kasus

Bagaimana?

Pembukaan

Dua digit ditentang secara vertikal, horizontal atau diagonal jika:

  • mereka berdua aneh, berbeda satu sama lain dan berbeda dari 5 (gambar 1)
  • ATAU keduanya genap dan jumlahnya 10 (gambar 2)

    digit lawan

Selain itu, digit yang berada di antara dua digit yang berlawanan n dan p sama dengan (n + p) / 2 .

Kode sumber yang diformat

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
  )

Melacak digit sebelumnya

Bendera untuk digit yang dikunjungi disimpan pada indeks negatif dalam larik input a , sehingga tidak bertabrakan dengan elemen aslinya.

  • Jika p diatur ke -n :

    Jika digit saat ini n tidak dipilih sebelumnya, a[-n] ^= -nakan mengatur bendera dan membiarkan every()loop melanjutkan dengan iterasi berikutnya. Jika tidak, itu akan menghapus bendera dan memaksa loop gagal segera.

  • Jika p diatur ke tidak terdefinisi :

    a[undefined] ^= undefinedmenghasilkan 0 , yang juga memaksa loop gagal.

Mendeteksi digit yang berlawanan

Ekspresi berikut digunakan untuk menguji apakah digit saat ini n dan digit sebelumnya p menentang digit, seperti yang didefinisikan dalam pembukaan:

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

yang setara dengan:

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

Catatan: Di JS, hasil modulo memiliki tanda yang sama dengan dividen.

Ini dapat diartikan sebagai:

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

Oleh karena itu, ungkapan ini mengembalikan 1 jika dan hanya jika n dan -p adalah digit yang berlawanan atau mereka adalah digit ganjil yang sama. Karena digit tidak dapat dipilih dua kali, kasing ini juga sudah ditangani dengan benar.

Jika ungkapan ini mengembalikan 1 , kami menguji [p / 2] (di mana p sekarang sama dengan jumlah digit yang dinegasikan) untuk mengetahui apakah 'digit di antara' sebelumnya dikunjungi. Kalau tidak, kami menguji [0] yang dijamin benar.

Tentang iterasi pertama

Iterasi pertama adalah kasus khusus, karena tidak ada digit sebelumnya dan kami ingin itu berhasil tanpa syarat.

Kami mencapainya dengan menginisialisasi p ke 1 , karena untuk setiap n dalam [1 .. 9] :

  • (1 * n) % 5 tidak boleh negatif
  • ~(1 - n) tidak bisa sama dengan 9

Jawaban asli, 90 byte

Dihapus dari pos ini sehingga tidak terlalu bertele-tele. Anda bisa melihatnya di sini .

Arnauld
sumber
-1 byte dengan mengganti !!a[1]&dengan a[1]&&, karena setiap nilai truthy dapat dikembalikan
Herman L
@HermanLauenstein Terima kasih, sepertinya memang baik. (Sekarang, a[1]*bahkan lebih pendek.)
Arnauld
1
Saya berusaha keras memikirkan formula untuk has a node directly in line, saya tidak menyadari itu akan sangat sederhana ...
Neil
@Neil Dengan melihat riwayat revisi posting ini, saya yakin Anda dapat mengatakan bahwa saya juga tidak menyadarinya ... :)
Arnauld
Pikirkan Anda dapat mengganti ?a[-n]^=1:0dengan &&a[-n]^=1untuk -1, tidak dapat menguji (di ponsel)
Stan Strum
45

x86 kode mesin 32-bit, 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

Ia menerima panjang daftar ecxdan penunjuk ke elemen pertama edx, dan mengembalikan hasilnya di al:

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

Ada 8 baris yang berisi simpul di tengah:

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

Saya mengelompokkan mereka berdasarkan perbedaan antara yang lebih besar dan yang lebih kecil.

Perbedaan 2: 3 baris (mulai dari 1, 4 atau 7)
    1 - 3
    4 - 6
    7 - 9
Perbedaan 4: 1 baris (mulai dari 3)
    3 - 7
Perbedaan 6: 3 baris (mulai dari 1, 2 atau 3)
    1 - 7
    2 - 8
    3 - 9
Perbedaan 8: 1 baris (mulai dari 1)
    1 - 9

Kemudian, saya mengonversinya menjadi tabel pencarian 2-D yang diindeks oleh setengah perbedaan dan angka yang lebih kecil:

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

Ini membuat bitmap "ajaib" dari 32 bit. Untuk mengindeks, kode mendorongnya ke dalam tumpukan. Kemudian, ia mengekstrak satu byte menggunakan satu indeks, dan dari byte itu, ia mengekstrak satu bit menggunakan indeks lainnya. Semua ini menggunakan satu instruksi:

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

Jika bitmap menunjukkan bahwa ada simpul di tengah, mudah untuk menghitung - tambahkan setengah perbedaan ke angka yang lebih kecil.

Sumber perakitan:

    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
sumber
Bagus! Saya sangat suka ini bt byte ptr [esp + eax], ebx.
Arnauld
5
Bagus untuk melihat solusi perakitan :) Anda dapat menggunakan cdqbukan xor edx, edxsebagai eaxnol. Juga, Anda dapat melipat dec eaxke dalam bt [esp + eax - 1], ebxyang sama panjang tapi kemudian memungkinkan Anda untuk menghapus inc ebxnanti. Ini akan menghemat dua byte.
Jester
Terima kasih atas ide-idenya! Anda telah mengamankan tempat Anda di surga pegolf, jika ada :)
anatolyg
5
Saya pikir kita semua bisa setuju bahwa pegolf surga adalah neraka bagi semua orang.
Adonalsium
19

Python 2 , 140 131 114 104 99 byte

-2 byte terima kasih kepada Jonathan Frech
-5 byte terima kasih kepada 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

Cobalah online!

Penjelasan:

# 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

Cobalah online!

Hanya 8 pasang node yang memiliki simpul di antaranya. Sepasang node dapat direpresentasikan sebagai integer tunggal oleh rumus 2^a-2^b-1. Jumlah ini dapat disingkat dengan modulo berulang:

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==5pertama memeriksa apakah pasangan seperti itu ada, kemudian v-{l+n>>1}==vmenguji apakah simpul di antaranya, yang diberikan oleh (a+b)/2, belum dikunjungi dan qmemunculkan NameError. Dengan menggunakan perbandingan berantai antara pasangan-pasangan ini, perbandingan berikutnya hanya dilakukan ketika sebelumnya dikembalikan True.

ovs
sumber
17

Jelly ,  24 22 19  18 byte

-2 karena kita tidak lagi diharuskan untuk menangani daftar kosong
-1 beralih dari bergabung,, j@untuk menggabungkan, ;(item yang terlewatkan tidak perlu ditemui di tengah untuk metode yang digunakan, karena pada awal trio baik-baik saja )
-2 beralih dari P¬aSHke oSH(OK untuk memiliki dua hasil karena kita meratakan, setengah dari 1adalah 0.5yang disaring pula, dan memiliki beberapa hasil yang sama ada telah mempengaruhi pada metode yang digunakan baik)
-1 Terima kasih kepada Mr Xcoder (0-diindeks input diizinkan)

d3ZIỊoSH;µƝFf9Ḷ¤Q⁼

Tautan monadik yang mengambil daftar bilangan bulat di dalam [0,8]dan mengembalikan nilai kebenaran ( 1) jika sah dan nilai salah ( 0) jika tidak.

Cobalah online! atau lihat test-suite .

Bagaimana?

Lihat pada setiap pasangan 0-indeks yang berdekatan di dalam daftar input. Jika pembagian bilangan bulat oleh tiga dari dua berbeda dengan 2 mereka berada di baris atas dan bawah, jika modulo oleh tiga dari dua berbeda dengan 2 mereka berada di kolom kiri dan kanan. Jumlah dari pasangan-pasangan tersebut dibagi dua adalah baik simpul tengah terindeks 0 dari garis tiga simpul atau nilai non-integer - jadi nilai-nilai ini pertama kali dimasukkan di depan pasangan terindeks 0 dan kemudian node palsu (suka 0.5atau3.5) dihapus, daftar daftar yang dihasilkan diratakan dan kemudian diduplikasi (untuk menghasilkan entri unik yang diawetkan pesanan) dan akhirnya dibandingkan dengan input - untuk sapuan hukum semua ini akan berakhir menjadi larangan saat ilegal yang akan menambahkan mid-node yang hilang dan / atau menghapus duplikat node (perhatikan bahwa tidak ada casing khusus yang diperlukan untuk daftar input panjang 1 karena tidak memiliki pasangan yang berdekatan):

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)

Metode sebelumnya

Jelly ,  36  35 byte

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

Cobalah online! atau lihat test-suite .

Bagaimana?

Mirip dengan di atas tetapi membangun semua kemungkinan tiga-node-line dan melakukan pencarian (daripada memeriksa saat menggunakan divmod untuk menguji dan mengurangi separuh jumlah untuk mid-node).

Pertama pembangunan daftar tiga-simpul-baris:

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

Sekarang pengambilan keputusan:

...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
sumber
Bagaimana hasilnya hingga 19 byte ketika ada banyak karakter unicode?
Izkata
@Izkata Jelly menggunakan halaman kode sendiri, yang dapat Anda lihat dengan mengklik "byte" di header. Dalam bentuk byte mentahnya, masing-masing karakter Unicode yang dapat Anda lihat dalam kode sumber hanya satu byte.
Jonathan Allan
15

Stax , 28 byte

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

Menjalankannya

Ini menghasilkan 0 untuk false, dan bilangan bulat positif untuk true. Representasi ascii yang sesuai dari program yang sama adalah ini.

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

Gagasan umum adalah menghitung beberapa kondisi yang diperlukan untuk pola gesek legal dan melipatgandakan semuanya.

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
rekursif
sumber
Penggunaan Yregister yang cerdas.
Weijun Zhou
Masalah lain di github.
Weijun Zhou
1
Saya kebetulan sudah memperbaiki bug itu, tetapi belum menyebarkannya sampai sekarang. (itu tidak mempengaruhi program saya)
rekursif
1
Ini mungkin terdengar aneh, tetapi Anda dapat menjatuhkan yang pertama vdan memasukkannya 1sebagai nilai palsu. 2dan di atas adalah kebenaran.
Weijun Zhou
10

JavaScript, 112 byte

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)

Mungkin beberapa bahasa berbasis regex harus lebih pendek. Tapi saya tidak tahu.

Berkat Neil, ubah )(?!untuk |menyimpan 3 byte.

tsh
sumber
@ WeijunZhou aku benar untuk 213, ada apa?
tsh
Tidak ada yang salah, maaf untuk itu.
Weijun Zhou
Sekarang karena OP diklarifikasi, gagal untuk 144.
Weijun Zhou
1
@ WeijunZhou harus diperbaiki; 2 byte lagi ...
tsh
Jika Anda bertanya-tanya, sebuah port Retina 0.8.2 tampaknya berfungsi pada 98 byte.
Neil
6

Retina 0.8.2 , 98 byte

Dipengaruhi oleh jawaban tsh . Saya mencoba untuk "ulangi" itu menjadi kebalikannya, cocok dengan gesekan yang tidak valid, kemudian 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)|.$)

Cobalah online

mbomb007
sumber
6

Sekam , 25 20 byte

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

Mengambil daftar bilangan bulat dengan pengindeksan berbasis 0. Menghasilkan 0 atau 1. Cobalah secara online!

Penjelasan

Saya mencuri beberapa ide dari jawaban Jelly Jonathan Allan . Idenya sama: masukkan "simpul rata-rata" yang baru di antara setiap pasangan yang berdekatan, filter yang bukan simpul yang sebenarnya, hapus duplikat dan bandingkan dengan daftar asli. Jika daftar asli berisi duplikat, hasilnya palsu. Jika daftar melewatkan simpul yang belum dikunjungi, maka ada dalam daftar yang diproses di antara pasangan yang sesuai, dan hasilnya adalah palsu. Jika input adalah singleton, daftar yang diproses kosong, dan hasilnya palsu. Kalau tidak, itu adalah kebenaran.

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
sumber
3

C ++, 267 256 byte

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

Untuk memeriksa apakah polanya tidak melewati simpul yang belum dikunjungi, ia melakukan beberapa hal:

  1. Hitung di dmana dperbedaan numerik antara node saat ini dan node terakhir.
  2. Jika dganjil, maka tidak perlu memeriksa, itu tidak dapat melewati node.
  3. Jika dsama dengan 4atau 8, maka lompatan adalah antara node 1-9atau 3-7, jadi periksa node5
  4. Jika d2, dan simpul tengah ( (last_node + current_node)/2) adalah 2,5 atau 8, maka periksa simpul tengah
  5. Jika d6, periksa sama seperti sebelumnya tetapi dengan 4, 5atau6

Parameternya adalah int[]dan elemennya dihitung. Ini mengembalikan intyang dapat diartikan sebagai booltipe

HatsuPointerKun
sumber
!(d%2)=> d%2<1harus bekerja.
Zacharý
256 byte
Zacharý
Saya belajar trik baru: int s[]=> int*s. Saya pikir itu akan berhasil.
Zacharý
2

Perl, 135 byte (134 + -n)

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

Versi sedikit ungolfed

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

Keluaran melalui kode keluar. 0adalah kebenaran, nilai lainnya salah. Sesuai konsensus meta , output STDERR dalam kasus kegagalan diabaikan.

Mungkin ada cara yang lebih cepat untuk memeriksa aturan "tidak dapat melompati" daripada sekadar mendaftar semua kemungkinan.

Silvio Mayolo
sumber
2

MATL , 42 41 39 byte

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

Ini menghasilkan

  • vektor kolom tidak kosong yang hanya berisi angka bukan nol sebagai output yang benar; atau
  • vektor kolom tidak kosong yang mengandung setidaknya nol sebagai kepalsuan.

Di sini Anda dapat membaca mengapa output ini masing-masing benar dan salah. Cobalah online!

Atau verifikasi semua kasus uji , dengan kode footer yang mencakup tes standar untuk kebenaran / kepalsuan.

Luis Mendo
sumber
2

Stax , 73 72 66 65 byte CP437

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

79 byte saat dibongkar,

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

Jalankan dan debug online!

atau menjalankan uji batch , di mana meXadalah header sehingga Stax dapat memproses input multiline.

Implementasi tanpa menggunakan hash.Outputs nomor ketat positif (sebenarnya jumlah tes gagal) untuk falsy kasus dan 0untuk truthy yang.

Penjelasan

dmembersihkan tumpukan input. Inputnya dalam variabel x.

4{cAs-5F menghasilkan bagian pertama dari daftar simpul tengah.

132396978714EE hardcode bagian kedua dari daftar simpul tengah.

L3/Mengumpulkan semua elemen dalam tumpukan utama dan membaginya menjadi beberapa bagian yang masing-masing berisi 3 elemen, hasilnya adalah array a, yang merupakan array dari semua grup 3-simpul yang tidak valid.

{xs:IBc0<A*++cEd:-1=sccHs|M=s{U>m|A**mEUntuk setiap daftar simpul yang tidak valid, lakukan pemeriksaan berikut. Hasil dari hasil pemeriksaan anded menggunakan **. Karena ada 8 daftar simpul yang tidak valid, hasil dari kode ini adalah array dari 8 elemen. Final Emengirimkan array ke elemen individualnya di stack utama.

xs:I dapatkan indeks elemen daftar simpul dalam array input.

Bc0<A*++Jika indeks "simpul tengah" (misalnya 5dalam set simpul 1,5,9) adalah -1(yang berarti tidak ada dalam array input), ubah indeks ke 9.

cEd:-1=uji apakah dua "terminal node" (misalnya 1,5dalam set simpul 1,5,9) berdekatan dalam array input.

sccHs|M= menguji apakah indeks yang diubah dari "simpul tengah" lebih besar daripada dua "simpul terminal", yang mencakup dua kasus: "simpul tengah" tidak ada, atau "simpul tengah" muncul setelah dua "simpul terminal"

s{U>m|Amenguji apakah kedua indeks dari "end node" tidak negatif. (Yaitu mereka berdua muncul di input).

Dua tes tambahan dilakukan,

x%2< menguji apakah array input adalah singleton.

xu%x%=! menguji apakah ada simpul yang telah dikunjungi dua kali.

Ada 10 hasil tes pada tumpukan utama (satu untuk setiap daftar simpul yang tidak valid, ditambah dua tes tambahan).

L|+mengumpulkan 10 elemen dan menambahkannya. |abisa juga digunakan yang hanya memeriksa apakah ada elemen yang benar pada array.

Output tersirat.

Weijun Zhou
sumber
2

Java, 375 355 byte

-20 byte terima kasih kepada 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;}

Ini adalah port dari jawaban ini dan bekerja pada prinsip yang sama

HatsuPointerKun
sumber
Wow. Anda terjawab di Jawa.
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;}harus bekerja (urutan operasi)
Zacharý
Anda bisa berubah (d==2)menjadi adil d==2, saya mengabaikan itu sebelumnya.
Zacharý
d%2==0=>d%2<1
Zacharý
0

Pyth , 33 byte

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

Suite uji.

Menggunakan pengindeksan berbasis 0.

Penjelasan

q {@ U9.nm + mc | g1aZksd2-MC.DR3d_dC, t -> Program lengkap. Input: daftar L dari STDIN.

                               , t -> Pasangkan L dengan L tanpa elemen pertama.
                              C -> Transpose.
       m -> Peta di atas daftar pasangan (daftar 2-elemen):
        + mc | g1aZksd2-MC.DR3d -> Fungsi yang akan dipetakan (variabel: d):
                         R d -> Untuk setiap elemen d ...
                       .D 3 -> ... Ambil divmodnya 3.
                      C -> Tranpose.
                    -M -> Kurangi masing-masing dengan pengurangan.
         m -> Untuk setiap perbedaan (variabel: k):
            g1aZl -> Is | k | ≤ 1?
           | sd -> Jika itu salah, gantilah dengan jumlah d.
          c 2 -> Bagi dengan 2.
        + _d -> Tambahkan kebalikan dari d ke hasil pemetaan.
     .n -> Ratakan.
  @ U9 -> Ambil persimpangan dengan (ℤ ∩ [0; 9)).
 {-> Deduplicate.
q -> Dan periksa apakah hasilnya sama dengan L.

Pendekatan alternatif untuk 34 byte :

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

Japt , 35 byte

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

Cobalah online!

Sedikit tidak berbulu & Cara kerjanya

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?

Mengaitkan ide dari solusi Jelly ini , dengan beberapa perbedaan dalam menentukan potensi lompatan:

  • Jawaban Jelly menggunakan divmod untuk melihat apakah pasangan memiliki perbedaan 2 saat diterapkan /3atau %3.
  • Jawaban ini hanya menggunakan %3dan memeriksa apakah perbedaannya adalah 0 atau 2. Jika perbedaannya adalah 0, kedua sel tersebut selaras secara vertikal, dan non-lompatan masih memiliki properti (X+Y)%2 != 0.
Bubbler
sumber
0

Python 2 , 97 byte

Berdasarkan jawaban Ovs tetapi 2 byte lebih pendek dan lebih samar. Konversi indeks menjadi koordinat 2d dan uji paritas. Asumsikan indeks 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

Cobalah online!

Luciano
sumber