Permutasi semut

37

pengantar

Misalkan Anda memiliki penggaris dengan angka dari 0 hingga r-1 . Anda menempatkan semut di antara dua angka, dan ia mulai merangkak tak menentu pada penggaris. Penguasa sangat sempit sehingga semut tidak bisa berjalan dari satu posisi ke posisi lain tanpa berjalan di semua nomor di antaranya. Saat semut berjalan pada nomor untuk pertama kalinya, Anda merekamnya, dan ini memberi Anda permutasi dari angka r . Kami mengatakan bahwa permutasi adalah gelisah jika dapat dihasilkan oleh semut dengan cara ini. Atau, permutasi p gelisah jika setiap entri p [i] kecuali yang pertama berada dalam jarak 1 dari beberapa entri sebelumnya.

Contohnya

Panjang-6 permutasi

4, 3, 5, 2, 1, 0

gelisah, karena 3 berada dalam jarak 1 dari 4 , 5 berada dalam jarak 1 dari 4 , 2 berada dalam jarak 1 dari 3 , 1 berada dalam jarak 1 dari 2 , dan 0 berada dalam jarak 1 dari 1 . Permutasi

3, 2, 5, 4, 1, 0

tidak gelisah, karena 5 tidak berada dalam jarak 1 dari 3 atau 2 ; semut harus melewati 4 untuk sampai ke 5 .

Tugas

Diberi permutasi dari angka-angka dari 0 ke r-1 untuk sekitar 1 ≤ r ≤ 100 dalam format apa pun yang masuk akal, mengeluarkan nilai yang benar jika permutasi itu gelisah, dan nilai yang salah jika tidak.

Uji kasus

[0] -> True
[0, 1] -> True
[1, 0] -> True
[0, 1, 2] -> True
[0, 2, 1] -> False
[2, 1, 3, 0] -> True
[3, 1, 0, 2] -> False
[1, 2, 0, 3] -> True
[2, 3, 1, 4, 0] -> True
[2, 3, 0, 4, 1] -> False
[0, 5, 1, 3, 2, 4] -> False
[6, 5, 4, 7, 3, 8, 9, 2, 1, 0] -> True
[4, 3, 5, 6, 7, 2, 9, 1, 0, 8] -> False
[5, 2, 7, 9, 6, 8, 0, 4, 1, 3] -> False
[20, 13, 7, 0, 14, 16, 10, 24, 21, 1, 8, 23, 17, 18, 11, 2, 6, 22, 4, 5, 9, 12, 3, 15, 19] -> False
[34, 36, 99, 94, 77, 93, 31, 90, 21, 88, 30, 66, 92, 83, 42, 5, 86, 11, 15, 78, 40, 48, 22, 29, 95, 64, 97, 43, 14, 33, 69, 49, 50, 35, 74, 46, 26, 51, 75, 87, 23, 85, 41, 98, 82, 79, 59, 56, 37, 96, 45, 17, 32, 91, 62, 20, 4, 9, 2, 18, 27, 60, 63, 25, 61, 76, 1, 55, 16, 8, 6, 38, 54, 47, 73, 67, 53, 57, 7, 72, 84, 39, 52, 58, 0, 89, 12, 68, 70, 24, 80, 3, 44, 13, 28, 10, 71, 65, 81, 19] -> False
[47, 48, 46, 45, 44, 49, 43, 42, 41, 50, 40, 39, 38, 51, 37, 36, 52, 35, 34, 33, 32, 53, 54, 31, 30, 55, 56, 29, 28, 57, 58, 59, 60, 27, 26, 61, 25, 62, 63, 64, 65, 66, 67, 24, 23, 22, 21, 68, 69, 20, 19, 18, 17, 70, 71, 16, 15, 72, 73, 74, 75, 76, 14, 13, 12, 77, 11, 10, 9, 8, 78, 7, 79, 80, 6, 81, 5, 4, 3, 82, 2, 83, 84, 1, 85, 86, 87, 0, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99] -> True

Fakta menyenangkan: untuk r ≥ 1 , ada tepat 2 r-1 permutasi panjang gelisah r .

Zgarb
sumber
7
Ini adalah tantangan yang sangat menarik dengan banyak solusi berbeda: Saya menghitung setidaknya 7 strategi unik yang digunakan sejauh ini.
ETHproduk
1
Bentuk input permutasi terstruktur berkontribusi banyak pada berbagai pendekatan. Kondisi untuk gelisah dapat diekspresikan dengan cara yang berbeda yang tidak setara pada daftar umum.
xnor
1
Saya kecewa belum ada solusi ANTSI C.
Sabuk NoSeat

Jawaban:

18

Pyth, 7 byte

/y+_QQS

Cobalah online. (Hanya kasus uji kecil yang disertakan karena run-time eksponensial.) Output 2 untuk Truthy, 0 untuk Falsey.

/          Count the number of occurences of
      S     the sorted input (implicit Q)
 y          in the order-preserved power set
  +_QQ       of the input prepended by its reverse

Dengan kata lain,

lambda l: subseq(sorted(l), concat(reverse(l), l))

di mana subseqmenampilkan apakah elemen-elemen dari daftar pertama muncul secara berurutan dalam daftar kedua, tidak harus berdekatan. Hal subseqini dilakukan dalam Pyth dengan mengambil semua himpunan bagian dari daftar kedua, yang menjaga urutan elemen, dan menghitung jumlah kemunculan daftar pertama. Ini membutuhkan waktu yang eksponensial.

Mengapa ini bekerja? Untuk permutasi menjadi gelisah, melangkah dari 0 ke n-1 harus terdiri dari hanya akan pergi, kemudian pergi hanya ke kanan. Ini karena elemen yang lebih besar dari elemen pertama harus meningkat dari kiri ke kanan, dan yang kurang dari itu harus berkurang dari kiri ke kanan.

[2, 3, 1, 4, 0]
             ^
       ^     0
 ^     1      
 2  ^        
    3     ^
          4

Jika kita mirror daftar dengan meletakkan salinan terbalik ke kiri, jalan ini sekarang hanya berjalan dengan benar.

[0, 4, 1, 3, 2, 2, 3, 1, 4, 0]
 ^            |             
 0     ^      |             
       1      | ^           
              | 2  ^        
              |    3     ^  
              |          4                                  

Sebaliknya, setiap kanan daftar cermin ini sesuai dengan jalan kiri-lalu-kanan dari daftar asli. Kanan ini hanya merupakan urutan berikutnya dari 0 hingga n-1. Dalam daftar gelisah, urutan diurutkan ini unik, kecuali untuk pilihan sewenang-wenang antara dua salinan yang berdekatan dari elemen pertama yang asli.

Tidak
sumber
7
Anda dapat memotongnya menjadi 6 byte dengan menggunakan ... hanya bercanda.
jwg
2
Ada sesuatu yang mengerikan tentang menggunakan pendekatan waktu eksponensial untuk masalah dengan solusi waktu linear yang jelas bahkan jika itu turun dengan baik.
David Conrad
@ jwg sebenarnya aku percaya itu. Jika hitungan daftar mengambil argumen dalam urutan yang berlawanan, Anda bisa mendapatkan 6 byte dengan mengambil dua input secara implisit.
xnor
ayyyyy, beralih ke sisi pyth: D
Maltysen
11

Haskell, 46 byte

(%)=scanl1
f l=zipWith(+)(min%l)[0..]==max%l

Cek apakah perbedaan vektor maxima yang sedang berjalan dan minima yang sedang berjalan adalah [0,1,2,3 ...].

l =             [2, 3, 1, 4, 0]

scanl1 max l =  [2, 3, 3, 4, 0]
scanl1 min l =  [2, 2, 1, 1, 0]  
difference =    [0, 1, 2, 3, 4]

Zgarb menyimpan 2 byte dengan (%)=scanl1.

Tidak
sumber
Itu sangat pintar! +1
Gabriel Benamy
1
Bisakah Anda menyimpan beberapa byte dengan mendefinisikan (#)=scanl1?
Zgarb
1
@ Zgarb Terima kasih, saya lupa Anda bisa melakukan itu.
xnor
9

JavaScript (ES6), 45

a=>a.every((v,i)=>a[v]=!i|a[v-1]|a[v+1],a=[])

Saya pikir itu terlalu sederhana untuk dibutuhkan sebagai penjelasan, tetapi ada trik, dan untuk berjaga-jaga, ini adalah versi pertama saya, pra-golf

a => {
  k = []; // I'll put a 1 in this array at position of each value 
          // that I find scanning the input list
  return a.every((v,i) => { // execute for each element v at position i
    // the index i is needed to manage the first iteration
    // return 1/true if ok, 0/false if not valid
    // .every will stop and return false if any iteration return falsy
    k[v] = 1; // mark the current position
    if ( i == 0 )
    {  // the first element is always valid
       return true;
    }
    else
    {
       return k[v-1] == 1 // valid if near a lesser value
              || k[v+1] == 1; // or valid if near a greater value
    }
  })
}

Catatan: dalam kode golf adigunakan bukan k, karena saya tidak perlu referensi ke array asli di dalam everypanggilan. Jadi saya menghindari mencemari namespace global menggunakan kembali parameter

Uji

antsy=
a=>a.every((v,i)=>a[v]=!i|a[v-1]|a[v+1],a=[])

var OkAll=true
;`[0] -> True
[0, 1] -> True
[1, 0] -> True
[0, 1, 2] -> True
[0, 2, 1] -> False
[2, 1, 3, 0] -> True
[3, 1, 0, 2] -> False
[1, 2, 0, 3] -> True
[2, 3, 1, 4, 0] -> True
[2, 3, 0, 4, 1] -> False
[0, 5, 1, 3, 2, 4] -> False
[6, 5, 4, 7, 3, 8, 9, 2, 1, 0] -> True
[4, 3, 5, 6, 7, 2, 9, 1, 0, 8] -> False
[5, 2, 7, 9, 6, 8, 0, 4, 1, 3] -> False
[20, 13, 7, 0, 14, 16, 10, 24, 21, 1, 8, 23, 17, 18, 11, 2, 6, 22, 4, 5, 9, 12, 3, 15, 19] -> False
[34, 36, 99, 94, 77, 93, 31, 90, 21, 88, 30, 66, 92, 83, 42, 5, 86, 11, 15, 78, 40, 48, 22, 29, 95, 64, 97, 43, 14, 33, 69, 49, 50, 35, 74, 46, 26, 51, 75, 87, 23, 85, 41, 98, 82, 79, 59, 56, 37, 96, 45, 17, 32, 91, 62, 20, 4, 9, 2, 18, 27, 60, 63, 25, 61, 76, 1, 55, 16, 8, 6, 38, 54, 47, 73, 67, 53, 57, 7, 72, 84, 39, 52, 58, 0, 89, 12, 68, 70, 24, 80, 3, 44, 13, 28, 10, 71, 65, 81, 19] -> False
[47, 48, 46, 45, 44, 49, 43, 42, 41, 50, 40, 39, 38, 51, 37, 36, 52, 35, 34, 33, 32, 53, 54, 31, 30, 55, 56, 29, 28, 57, 58, 59, 60, 27, 26, 61, 25, 62, 63, 64, 65, 66, 67, 24, 23, 22, 21, 68, 69, 20, 19, 18, 17, 70, 71, 16, 15, 72, 73, 74, 75, 76, 14, 13, 12, 77, 11, 10, 9, 8, 78, 7, 79, 80, 6, 81, 5, 4, 3, 82, 2, 83, 84, 1, 85, 86, 87, 0, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99] -> True`
.split`\n`.forEach(row => {
  var rowElements = row.match(/\w+/g), 
      expected = rowElements.pop()=='True',
      input = rowElements.map(x => +x),
      result = antsy(input),
      ok = result == expected;
  OkAll = OkAll && ok;
  console.log(ok?'OK':'KO', input+' -> '+result)
})
console.log(OkAll ? 'All passed' : 'Failed')

edc65
sumber
Sangat bagus. Saya mencoba pendekatan ini dengan rekursi, tetapi saya tidak bisa mendapatkannya di bawah 65:f=([q,...a],x=[])=>x&&(x[q]=!(x+x)|x[q+1]|x[q-1])&&(a+a?f(a,x):1)
ETHproduksi
Bagaimana cara kerjanya? Apakah Anda menggunakan sihir daftar yang bisa berubah?
Zgarb
Penjelasan @Zgarb ditambahkan
edc65
6

Python 2, 49 byte

f=lambda l:l==[]or max(l)-min(l)<len(l)*f(l[:-1])

Cek apakah setiap awalan daftar berisi semua angka antara min dan maks inklusif. Ia melakukannya dengan memeriksa apakah perbedaan max dan min kurang dari panjangnya.


54 byte:

f=lambda l:1/len(l)or-~l.pop()in[min(l),max(l)+2]*f(l)

Memeriksa apakah elemen terakhir kurang dari satu min dari elemen lainnya, atau satu lebih dari maks. Kemudian, hapus elemen terakhir dan berulang. Pada daftar elemen tunggal, menghasilkan True.

Ini juga dapat diperiksa melalui pemahaman daftar yang lucu tapi lebih lama.

lambda l:all(l.pop()in[min(l)-1,max(l)+1]for _ in l[1:])

Saya ingin menggunakan ketidaksetaraan min(l)-2<l.pop()<max(l)+2, tetapi popkebutuhan harus terjadi terlebih dahulu. Menggunakan program untuk menghasilkan melalui kode kesalahan kemungkinan akan lebih pendek.

Tidak
sumber
6

Mathematica, 42 byte

!MatchQ[#,{a__,b_,___}/;Min@Abs[{a}-b]>1]&

Gunakan pencocokan pola untuk mencoba dan menemukan awalan ayang selisih maksimumnya dari elemen berikutnya blebih besar dari 1(dan meniadakan hasil MatchQ).

Martin Ender
sumber
6

Perl, 39 38 35 byte

Termasuk +1 untuk -p

Berikan urutan pada STDIN:

antsy.pl <<< "2 1 3 0"

antsy.pl:

#!/usr/bin/perl -p
s%\d+%--$a[$&]x"@a"=~/1  /%eg;$_++
Ton Hospel
sumber
2
Saya mengalami kesulitan mencoba memahami yang satu ini ... Ingin menjelaskan sedikit? terima kasih :-) (ide utamanya saja sudah cukup)
Dada
4

MATL , 11 byte

&-|R1=a4L)A

Cobalah online! Atau verifikasi semua kasus uji .

Penjelasan

Ini menghitung matriks dari semua perbedaan mutlak berpasangan dan menjaga bagian segitiga atas. Hasilnya benar jika ada setidaknya nilai 1 di semua kolom kecuali yang pertama.

&-     % All pairwise differences
|      % Absolute value
R      % Upper triangular part
1=     % Does each entry equal 1?
a      % Logical "or" along each column
4L)    % Remove first value
A      % Logical "and" of all results
Luis Mendo
sumber
4

R, 72 64 60 byte

v=scan();for(i in seq(v))T=c(T,diff(sort(v[1:i])));all(T==1)

Permutasi gelisah jika dan hanya jika semua subpermutasi kirinya kontinu (yaitu memiliki perbedaan satu ketika diurutkan).

Jika input dijamin memiliki panjang lebih dari satu, maka kita dapat menggantinya 1:sum(1|v)dengan seq(v), yang menghemat empat byte.

Kondisi seq(v)in jika berperilaku berbeda ketika inputnya panjang satu --- itu menghasilkan urutan 1:vbukan seq_along(v). Namun, untungnya, hasilnya ternyata TRUEdalam kasus ini, yang merupakan perilaku yang diinginkan. Hal yang sama juga terjadi untuk input panjang nol.

Dalam R, Tadalah variabel preset sama dengan TRUE(tetapi R memungkinkan Anda untuk mendefinisikannya kembali). TRUEjuga dianggap sama dengan 1.

Terima kasih kepada @Billywob untuk beberapa peningkatan bermanfaat pada solusi asli.

JDL
sumber
1
Membaca input menggunakan scanakan menghemat dua byte. Dalam hal ini jumlah byte yang persis sama dengan forpendekatan loop: v=scan();c=c();for(i in 1:sum(1|v))c=c(c,diff(sort(v[1:i])));all(c==1)yang akan menjadi 2 byte lebih pendek dari pendekatan vektor Anda.
Billywob
Gagasan bagus, dan saya bisa melangkah lebih baik, saya pikir dengan menyalahgunakan T. Akan diedit.
JDL
3

05AB1E , 7 byte

Âìæ¹{¢O

Cobalah online! atau sebagai test suite yang dimodifikasi .

Penjelasan

Menggunakan proses yang dijelaskan oleh xnor dalam jawaban Pyth-nya yang brilian .
Mengembalikan 2 untuk contoh yang benar dan 0 untuk yang salah.

Âì        # prepend a reversed copy of input to input
  æ       # take powerset
   ¹{     # push a sorted copy of input
     ¢    # count occurances of sorted input in powerset
      O   # sum occurances (which for some reason is needed, feels like a bug)
Emigna
sumber
3

Perl, 63 byte

Perhatikan bahwa @Gabriel Banamy datang dengan (55 bytes) lebih pendek jawabannya . Tapi saya pikir solusi ini masih menarik, jadi saya mempostingnya.

Hitungan byte mencakup 62 byte kode dan -nbendera.

s/\d+/1x($&+1)/ge;/ 1(1*)\b(?{$.&=$`=~m%\b(11)?$1\b%})^/;say$.

Untuk menjalankannya:

perl -nE 's/\d+/1x($&+1)/ge;/ 1(1*)\b(?{$.&=$`=~m%\b(11)?$1\b%})^/;say$.' <<< "3 2 5 4 1 0"

Penjelasan singkat : mengonversi setiap angka kke representasi unary k+1(yang +1diperlukan agar 0tidak diabaikan). Kemudian untuk setiap angka k+1(dinyatakan dalam unary as 1(1*)), kita melihat apakah ada k( $1memegang k) atau k+2(yang kemudian 11$1) ada dalam string sebelumnya (direferensikan oleh $-backtick). Jika tidak, maka kita atur $.ke nol. Pada akhirnya kami mencetak $.yang akan menjadi 1jika kami tidak pernah mengaturnya ke nol, atau nol sebaliknya.

Dada
sumber
3

Brain-Flak 302 264 256 Bytes

Terima kasih kepada Wheat Wizard untuk menyimpan 46 byte

([]){{}({}<>)<>([])}{}<>(({}))([]){{}({}<>)<>([])}{}<>(({}<>))<>(()){{}(({})<(({})<>[({})]<>(())){((<{}{}>))}{}{{}({}<><{}>)(<>)}{}<>({}<<>(({})<>[({})<>(())]){((<{}{}>))}{}{{}({}<><{}>)(<>)}{}<>>)<>>[({})](<()>)){{}{}(<(())>)}{}}([][()(())]){((<{}{}>))}{}

Bagian atas tumpukan akan menjadi 1 untuk truey dan 0 untuk falsy.

Truthy: Cobalah Online!
Falsy: Cobalah Online!

Idenya adalah untuk memegang nomor minimum dan maksimum yang telah dikunjungi semut di tumpukan. Kemudian bandingkan setiap nomor dengan keduanya dan perbarui yang sesuai. Jika angka berikutnya tidak 1 kurang dari min atau 1 lebih dari maks, keluar dari loop dan kembalikan false.


Penjelasan singkat:

([])                             # duplicate the bottom element by
{{}({}<>)<>([])}{}<>             # reversing everything onto the other stack 
(({}))([])                       # duplicating the top element
{{}({}<>)<>([])}{}<>             # and reversing everything back

(({}<>))<>                       # copy the top element to the other stack (push twice)
(()){{}                          # push a 1 so the loop starts, and repeat until the top
                                 # two elements are equal
(({})<                           # hold onto the top element to compare later
(({})<>[({})]<>(()))             # push a 0 if diff with the top of the other stack is +1
{{}({}<><{}>)(<>)}{}             # logical not (the previous line pushed a 1 as the second
                                 # element already)
{{}({}<><{}>)<>(<()>)}{}         # replace the top of the other stack with this element if
                                 # the logical not gave us 1
<>({}<<>                         # take the minimum off the other stack temporarily 
(({})<>[({})<>(())])             # push a 0 if diff with the top of the other stack is -1
{((<{}{}>))}{}                   # logical not (the previous line pushed a 1 as the second
                                 # element already)
{{}({}<><{}>)(<>)}{}             # replace the top of the other stack with this element if
                                 # the logical not gave us 1
<>>)<>                           # put the minimum on back on
>)                               # put the element you were comparing back on
[({})](<()>)){{}{}(<(())>)}{}    # push 1 or 0 for not equal to the element we held earlier
                                 # (push the second number back on)
}                                # repeat the loop if the top 2 weren't equal
([][()(())]){((<{}{}>))}{}       # logical not of the height of the stack
Riley
sumber
Saya akan memeriksa pengurangan push pop. Saya sudah melihat beberapa tempat di mana Anda bisa menggunakan strategi ini.
Wheat Wizard
@WheatWizard Saya yakin ada beberapa, saya hanya belum punya waktu untuk menyelesaikannya. Terima kasih atas pengingatnya.
Riley
Saya senang ini setidaknya masuk akal bagi Anda O_O
Gabriel Benamy
Anda juga dapat mengganti instance ([]){({}[()]<({}<>)<>>)}{}dengan ([]){{}({}<>)<>([])}{}untuk menyimpan beberapa byte lagi
Wheat Wizard
3

Jelly , 9 8 7 byte

;@UŒPċṢ

Cobalah secara Online!

Terjemahan Jelly untuk jawaban xnor.

Solusi lama:

;\Ṣ€IỊȦ
;\Ṣ€IE€P

Cobalah online!

Bekerja sangat mirip dengan jawaban Pyth saya di bawah:

;\          All prefixes (Accumulate (\) over concatenation (;))
  Ṣ€        (Ṣ)ort each (€) prefix
    I       (I)ncrements of each prefix (differences between consecutive elements).  Implicit vectorization.
     E€     Check if all elements are (E)qual (they will be iff the permutation is antsy,
               and all elements will be 1) for each (€) prefix
       P    Is this true for all prefixes?
     ỊȦ     For the other answer, are (Ȧ)ll elements 1 or less (Ị)?
Steven H.
sumber
Konversi metode lain xnor ke Jelly juga 7 byte »\_«\⁼Ṣtetapi jauh lebih efisien
mil
ŒBŒPċṢdan ;\Ṣ€IỊȦharus menyimpan satu byte dalam setiap pendekatan.
Dennis
Sayangnya, yang pertama tidak berfungsi karena saya akan membutuhkan input yang dibalik untuk dipantulkan, seperti UŒBŒPċṢyang tidak menyimpan byte. Itu bagus, meskipun; Saya telah salah membaca atom itu untuk menghasilkan BUKAN logis dari apa yang sebenarnya dilakukannya.
Steven H.
Saya tidak yakin mengapa Anda membutuhkan U(atau @sekarang saya memikirkannya). Jika sebuah array gelisah, begitu pula array terbalik, bukan?
Dennis
1
Tidak harus: [2, 1, 3, 0]gelisah tetapi [0, 3, 1, 2]tidak.
Steven H.
3

CJam ( 21 20 byte)

{:A,{_)A<$2*)@-#},!}

Test suite online

Pembedahan

Ini menggunakan pengamatan oleh xnor dalam jawabannya Haskell bahwa perbedaan antara maksimum dan minimum nelemen pertama harus n-1.

{         e# Define a block. Stack: array
  :A,     e#   Store the array in A and get its length
  {       e#   Filter (with implicit , so over the array [0 ... len-1])
    _)A<  e#     Get the first i+1 elements of A (so we iterate over prefixes)
    $2*)  e#     Extract the last element without leaving an empty array if the
          e#     prefix is of length 1 by first duplicating the contents of the
          e#     prefix and then popping the last element
    @-#   e#     Search the prefix for max(prefix)-i, which should be min(prefix)
          e#     giving index 0
  },      e#   So the filter finds values of i for which the prefix of length i+1
          e#   doesn't have max(prefix) - min(prefix) = i
  !       e#   Negate, giving truthy iff there was no i matching the filter
}

Pendekatan alternatif (juga 20 byte)

{_{a+_)f-:z1&,*}*^!}

Test suite online

Ini memeriksa secara langsung bahwa setiap elemen setelah yang pertama berada pada jarak 1 dari elemen sebelumnya. Karena input adalah permutasi dan karenanya tidak mengulangi nilai, ini adalah tes yang cukup. Terima kasih kepada Martin untuk penghematan 1 byte.

Pembedahan

{_{a+_)f-:z1&,*}*^!}

{         e# Declare a block. Stack: array
  _       e#   Work with a copy of the array
  {       e#   Fold...
    a+    e#     Add to the accumulator.
    _)f-  e#     Dup, pop last, map subtraction to get distance of this element from
          e#     each of the previous ones
    :z1&, e#     Check whether the absolute values include 1
    *     e#     If not, replace the accumulator with an empty array
  }*
  ^!      e#   Test whether the accumulator is equal to the original array
          e#   Note that this can't just be = because if the array is of length 1
          e#   the accumulator will be 0 rather than [0]
}
Peter Taylor
sumber
Saya pikir ini menghemat satu? {_{a+_)f-:z1&,*}*^!}
Martin Ender
@ MartinEnder, sangat bagus. Anehnya Anda memposting bahwa sama seperti saya memposting pendekatan yang sama sekali berbeda dengan jumlah byte yang sama.
Peter Taylor
3

Java, 100 98 79 75 byte

a->{int n=a[0],m=n-1;for(int i:a)n-=i==m+1?m-m++:i==n-1?1:n+1;return n==0;}

Dahulu:

a->{int m,n;m=n=a[0];--m;for(int i:a)if(i==m+1)m=i;else if(i==n-1)n=i;else return 0>1;return 1>0;}

Disimpan 3 byte dengan mengganti truedan falsedengan 1>0dan 0>1.

Disimpan 23 byte berkat saran luar biasa dari Peter Taylor!

Tidak Disatukan:

a -> {
    int n = a[0], m = n - 1;
    for (int i : a)
        n -= i == m + 1? m - m++ : i == n - 1? 1 : n + 1;
    return n == 0;
}

Melacak nilai tertinggi dan terendah yang terlihat sejauh mdan n; hanya menerima nilai baru jika itu m + 1atau n - 1yaitu nilai berikutnya yang lebih tinggi atau lebih rendah; inisialisasi nilai tinggi,m ,, menjadi satu kurang dari elemen pertama sehingga akan "cocok" pertama kali di sekitar loop. Catatan: ini adalah algoritma online waktu linear. Ini hanya membutuhkan tiga kata memori, untuk nilai saat ini, tertinggi sejauh ini, dan terendah sejauh ini, tidak seperti banyak solusi lainnya.

Jika nilai berikutnya melewatkan ujung tinggi dan rendah dari kisaran, nilai terendah sejauh ini diatur ke -1dan kemudian ujung rendah tidak akan pernah dapat melanjutkan dan mencapai nol. Kami kemudian mendeteksi urutan gelisah dengan memeriksa apakah nilai rendah,n ,, mencapai nol.

(Sayangnya ini kurang efisien karena kita selalu harus melihat seluruh urutan daripada menyerah setelah kesalahan pertama nomor yang , tetapi sulit untuk berdebat dengan penghematan 23-byte (!) Ketika solusi lain menggunakan O (n ^ 2 ) dan pendekatan waktu eksponensial.)

Pemakaian:

import java.util.function.Predicate;

public class Antsy {
    public static void main(String[] args) {
        int[] values = { 6, 5, 4, 7, 3, 8, 9, 2, 1, 0 };
        System.out.println(test(values,
            a -> {
                int n = a[0], m = n - 1;
                for (int i : a)
                    n -= i == m + 1? m - m++ : i == n - 1? 1 : n + 1;
                return n == 0;
            }
        ));
    }

    public static boolean test(int[] values, Predicate<int[]> pred) {
        return pred.test(values);
    }
}

Catatan: ini juga dapat ditulis tanpa memanfaatkan Java 8 lambdas:

Java 7, 89 byte

boolean c(int[]a){int n=a[0],m=n-1;for(int i:a)n-=i==m+1?m-m++:i==n-1?1:n+1;return n==0;}
David Conrad
sumber
Penanganan kasus khusus yang baik. int m,n;m=n=a[0];--m;bisa jadi int n=a[0],m=n-1;, dan yang mahal returndan elsebisa dikurangi dengan i==m+1?m++:n=(i==n-1)?i:-1;return n==0;(atau yang serupa - saya belum menguji ini).
Peter Taylor
@PeterTaylor Fantastic! Sayangnya, Java tidak akan mengizinkan efek samping seperti m++atau di m+=1sana, jadi saya masih membutuhkan ifdan else, dan kehilangan aspek hubungan pendek pada nilai buruk pertama, tetapi itu adalah peningkatan besar. Terima kasih!
David Conrad
Ini akan memungkinkan efek samping dalam ekspresi yang kompleks. Apa yang mungkin tidak suka adalah menggunakan ekspresi umum sebagai pernyataan. Dalam kasus terburuk Anda perlu membuat variabel dummy jdan menetapkan hasilnya, tetapi curiga akan ada cara yang lebih baik untuk melakukannya.
Peter Taylor
@PeterTaylor Yah, saya mencoba beberapa variasi, termasuk menugaskannya ke variabel dummy g, dan saya tidak bisa membuatnya berfungsi. (Saya menggunakan Java 9-ea + 138, mungkin itu perbedaan antara Java 8 dan Java 9?) Saya dapat mencoba lagi besok.
David Conrad
Oke. n-=i==m+1?m-m++:i==n-1?1:n+1;
Peter Taylor
2

Pyth ( fork ), 13 byte

!sstMM.+MSM._

Tidak ada tautan Try Try Online untuk garpu Pyth ini. Garpu menyertakan fungsi delta .+, yang bukan bagian dari pustaka Pyth standar.

Penjelasan:

           ._  For each of the prefixes:
         SM    Sort it
      .+M      Get deltas (differences between consecutive elements), which for antsy
                 permutations would all be 1s
   tMM         Decrement each of the elements (all 0s for antsy permutations)
 ss            Sum all the results from the above together, 0 for antsy and >0 for non-antsy
!              Logical negation.
Steven H.
sumber
3
Melihat ini meyakinkan saya untuk menggabungkan ini ke Pyth.
isaacg
2

Perl, 66 54 +1 = 55 byte

+1 byte untuk -n.

s/\d+/$.&=!@a||1~~[map{abs$_-$&}@a];push@a,$&/eg;say$.

Penjelasan:

s/\d+/$.&=!@a||1~~[map{abs$_-$&}@a];push@a,$&/eg;say$.
#input is automatically read into $_.
#regex automatically is performed on $_.
s/   /                                       /eg;
    #Substitution regex.
    #/g means to keep searching after the first match
    #/e evaluates the replacement as code instead of regex.
  \d+  #Match of at least 1 digit.  Match automatically gets stored in $&
      $.&=  #$. is initially 1.  This basically says $. = $. & (code)
           !@a  #Since @a is uninitialized, this returns !0, or 1
                #We don't want to check anything for the first match
              || #logical or
                1~~
                   #~~ is the smartmatch operator.  When RHS is scalar and LHS is array reference,
                   #it returns 1 iff RHS is equal to at least one value in de-referenced LHS.
                   [map{abs$_-$&}@a];
                       #Return an array reference to the array calculated by |$_ - $&|
                       #where $_ iterates over @a.  Remember $& is the stored digit capture.
                                     push@a,$& #pushes $& at the end of @a.
                                                 say$. #output the result

Mencetak 0 jika salah, 1 jika benar.

-11 byte terima kasih kepada @Dada

Gabriel Benamy
sumber
1
Yang itu sangat bagus. Anda dapat mengubahnya menjadi 55 byte perl -nE 's/\d+/$.&=!@a||1~~[map{abs$_-$&}@a];push@a,$&/eg;say$.':: -nalih-alih <>=~memungkinkan Anda untuk menghapus /rmodifier. gunakan \d+lalu $&ganti (\d+)dan $1. !@abukannya 0>$#a. $.&=bukannya $.&&=. push@a,$&bukannya@a=(@a,$&)
Dada
Untuk beberapa alasan, sistem saya memberi tahu saya file baru sepanjang 55 byte, yang jelas salah karena hanya 54 karakter, jadi ???
Gabriel Benamy
Hmm itu aneh. (dan saya tidak tahu dari mana asalnya). Tapi saya cukup yakin hanya 54 (script PPCG-Design memberitahu saya 54, dan aplikasi bytecount saya memberitahu saya juga 54).
Dada
2
Apakah mungkin jumlah byte keluar karena file memiliki baris baru yang tidak perlu pada akhirnya?
trichoplax
2

Brainfuck, 60 byte

,+[>+>+<<-]
,+
[
  [>->->+<<<-]
  >-
  [
    +>+
    [
      <<<
    ]
  ]
  >[>]
  <[<+<+>>-]
  <<<,+
]
>.

Permutasi diberikan sebagai byte tanpa pemisah dan tanpa baris baru terminasi. Karena \x00terjadi pada input, ini dirancang untuk implementasi dengan EOF = -1. Output \x00untuk false dan \x01true.

Jika permutasi \x01hingga chr(r)diizinkan, maka kami dapat mengganti semua instance ,+dengan ,untuk skor 57 dengan aEOF = 0 implementasi.

Cobalah secara online (versi 57-byte): Input dapat diberikan sebagai permutasi dari setiap rentang byte yang berdekatan tidak termasuk \x00, dan output akan menjadi\x00 false dan minimum rentang untuk true.

Kami melacak min dan max yang terlihat sejauh ini, dan untuk setiap karakter setelah yang pertama, periksa apakah min-1 atau max + 1 atau tidak. Dalam kasus keduanya, pindahkan pointer ke luar ruang kerja normal sehingga sel-sel lokal menjadi nol.

Tata letak memori dari ruang kerja normal pada awal loop utama adalah

c a b 0 0

di mana ckarakter saat ini, amin, dan bmaks. (Untuk versi 60-byte, semuanya ditangani dengan offset 1 karena ,+.)

Mitch Schwartz
sumber
1

Brachylog , 22 byte

:@[fb:{oLtT,Lh:T:efL}a

Cobalah online!

Penjelasan

Saya belum menemukan cara singkat untuk memeriksa apakah daftar berisi bilangan bulat berturut-turut atau tidak. Yang terpendek yang saya temukan adalah untuk menghasilkan rentang antara elemen pertama dan terakhir dari daftar itu dan memeriksa bahwa rentang itu adalah daftar asli.

:@[fb                       Take all but the first prefixes of the Input
     :{             }a      This predicate is true for all those prefixes
       oLtT,                Sort the prefix, call it L, its last element is T
            Lh:T            The list [First element of L, T]
                :efL        Find all integers between the First element of L and T. It must
                              result in L
Fatalisasi
sumber
Berkisar dari pertama hingga terakhir adalah satu pendekatan yang pernah saya alami di CJam. Yang lainnya adalah jenis, perbedaan berpasangan, periksa semuanya 1. Saya tidak tahu betapa mudahnya itu di Brachylog.
Peter Taylor
@PeterTaylor Tidak ada cara singkat untuk menghasilkan pasangan berturut-turut (atau langsung menghitung perbedaan berpasangan) sayangnya (untuk saat ini).
Fatalkan
1

Batch, 133 byte

@set/au=%1,l=%1-1,a=0
@for %%n in (%*)do @call:l %%n
@exit/b%a%
:l
@if %1==%u% (set/au+=1)else if %1==%l% (set/al-=1)else set a=1

Mengambil input sebagai argumen baris perintah. Keluar dengan tingkat kesalahan 0 untuk sukses, 1 untuk kegagalan.

Neil
sumber
1

J, 14 byte

/:~-:>./\-<./\

Ini didasarkan pada @ xnor metode .

Penjelasan

/:~-:>./\-<./\  Input: array P
        \       For each prefix of P
     >./          Reduce using the maximum
          <./\  Get the minimum of each prefix of p
         -      Subtract between each
   -:           Test if it matches
/:~               P sorted
mil
sumber
1

Java, 170 byte

boolean f(int[]a){int l=a.length,i=0,b=0,e=l-1;int[]x=new int[l];for(;i<l;i++)x[i]=i;for(i--;i>0;i--)if(a[i]==x[b])b++;else if(a[i]==x[e])e--;else return 0>1;return 1>0;}

Array xmemiliki nilai dari 0 hingga angka maksimum secara berurutan (Python akan jauh lebih baik di sini ...). Lingkaran mundur mencoba mencocokkan nomor terendah ( x[b]) atau tertinggi ( x[e]) yang belum ditemukan; jika ya, angka itu dapat dicapai pada langkah itu.

Uji kode di sini .

AlexRacer
sumber
0

Mathematica, 47 byte

Sedikit lebih lama dari solusi Martin Ender (kejutan kejutan!). Tapi itu salah satu upaya saya yang lebih sulit dibaca, jadi itu bagus: D

#=={}||{Max@#,Min@#}~MemberQ~Last@#&&#0@Most@#&

Penjelasan:

#=={}                         empty lists are antsy (function halts with True)
 ||                            or
{Max@#,Min@#}~MemberQ~Last@#  lists where the last number is largest or smallest
                              are possibly antsy (else function halts with False)
 &&                            and
#0@Most@#&                    recursively call this function after dropping the
                              last element of the list
Greg Martin
sumber
0

Java 7, 170 169 byte

import java.util.*;Object c(int[]a){List l=new ArrayList();l.add(a[0]);for(int i:a){if(l.indexOf(i)<0&l.indexOf(i-1)<0&l.indexOf(i+1)<0)return 0>1;l.add(i);}return 1>0;}

Tidak digabungkan & kode uji:

Coba di sini.

import java.util.*;
class M{
  static Object c(int[] a){
    List l = new ArrayList();
    l.add(a[0]);
    for(int i : a){
      if(l.indexOf(i) < 0 & l.indexOf(i-1) < 0 & l.indexOf(i+1) < 0){
        return 0>1; //false
      }
      l.add(i);
    }
    return 1>0; //true
  }

  public static void main(String[] a){
    System.out.println(c(new int[]{ 0 }));
    System.out.println(c(new int[]{ 0, 1 }));
    System.out.println(c(new int[]{ 1, 0 }));
    System.out.println(c(new int[]{ 0, 1, 2 }));
    System.out.println(c(new int[]{ 0, 2, 1 }));
    System.out.println(c(new int[]{ 2, 1, 3, 0 }));
    System.out.println(c(new int[]{ 3, 1, 0, 2 }));
    System.out.println(c(new int[]{ 1, 2, 0, 3 }));
    System.out.println(c(new int[]{ 2, 3, 1, 4, 0 }));
    System.out.println(c(new int[]{ 0, 5, 1, 3, 2, 4 }));
    System.out.println(c(new int[]{ 6, 5, 4, 7, 3, 8, 9, 2, 1, 0 }));
    System.out.println(c(new int[]{ 4, 3, 5, 6, 7, 2, 9, 1, 0, 8 }));
    System.out.println(c(new int[]{ 5, 2, 7, 9, 6, 8, 0, 4, 1, 3 }));
    System.out.println(c(new int[]{ 20, 13, 7, 0, 14, 16, 10, 24, 21, 1, 8, 23, 17, 18, 11, 2, 6, 22, 4, 5, 9, 12, 3, 15, 19 }));
    System.out.println(c(new int[]{ 34, 36, 99, 94, 77, 93, 31, 90, 21, 88, 30, 66, 92, 83, 42, 5, 86, 11, 15, 78, 40, 48, 22, 29, 95, 64, 97, 43, 14, 33, 69, 49, 50, 35, 74, 46, 26, 51, 75, 87, 23, 85, 41, 98, 82, 79, 59, 56, 37, 96, 45, 17, 32, 91, 62, 20, 4, 9, 2, 18, 27, 60, 63, 25, 61, 76, 1, 55, 16, 8, 6, 38, 54, 47, 73, 67, 53, 57, 7, 72, 84, 39, 52, 58, 0, 89, 12, 68, 70, 24, 80, 3, 44, 13, 28, 10, 71, 65, 81, 19 }));
    System.out.println(c(new int[]{ 47, 48, 46, 45, 44, 49, 43, 42, 41, 50, 40, 39, 38, 51, 37, 36, 52, 35, 34, 33, 32, 53, 54, 31, 30, 55, 56, 29, 28, 57, 58, 59, 60, 27, 26, 61, 25, 62, 63, 64, 65, 66, 67, 24, 23, 22, 21, 68, 69, 20, 19, 18, 17, 70, 71, 16, 15, 72, 73, 74, 75, 76, 14, 13, 12, 77, 11, 10, 9, 8, 78, 7, 79, 80, 6, 81, 5, 4, 3, 82, 2, 83, 84, 1, 85, 86, 87, 0, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99 }));
  }
}

Keluaran:

true
true
true
true
false
true
false
true
true
false
true
false
false
false
false
true
Kevin Cruijssen
sumber