Periksa kata Lyndon

22

Sebuah Lyndon kata adalah string yang ketat leksikografi lebih kecil daripada rotasi siklik. Diberikan string biner, tentukan apakah itu kata Lyndon dalam sesedikit mungkin byte.

Misalnya, 001011adalah kata Lyndon. Rotasinya, yang tercantum di bawah ini, diperoleh dengan menggerakkan simbol pertama ke ujung berulang kali.

001011
010110
101100
011001
110010
100101

Dari jumlah tersebut, string asli datang secara leksikografis terlebih dahulu, atau setara, mewakili angka biner terkecil.

Namun, 001001ini bukan kata Lyndon karena salah satu rotasinya sama dengan dirinya sendiri, yang mengikatnya secara leksikografis paling awal.

Masalah terkait.

Input: String biner yang tidak kosong atau daftar digit 0dan 1. Anda tidak boleh menggunakan angka, ingin 5mewakili 101.

Output: Nilai Truthy atau Falsey yang konsisten yang mengatakan apakah string itu kata Lyndon.

Built-in khusus untuk kata-kata Lyndon tidak diperbolehkan.

Kasus uji:

Kata-kata Lyndon dengan panjang hingga 6 adalah:

0
1
01
001
011
0001
0011
0111
00001
00011
00101
00111
01011
01111
000001
000011
000101
000111
001011
001101
001111
010111
011111

Panjang non-Lyndon hingga 4 adalah:

00
10
11
000
010
100
101
110
111
0000
0010
0100
0101
0110
1000
1001
1010
1011
1100
1101
1110
1111

Papan peringkat:

Tampilkan cuplikan kode

code-golf string Tidak
sumber

Jawaban:

5

Python 2, 42

Tampaknya cukup baik untuk dibandingkan dengan sufiks alih-alih mengganggu rotasi.

f=lambda s,i=1:i/len(s)or s<s[i:]*f(s,i+1)

Pengaturan rekursi sepertinya tidak terlalu bagus; mungkin itu bisa dilakukan dengan lebih baik.

Versi 44 byte ini membuatnya lebih jelas apa yang terjadi:

lambda s:all(s<=s[i:]for i in range(len(s)))
feersum
sumber
4

Haskell, 43 38 byte

f x=all(x<=)$init$scanl(const.tail)x x

scanl(const.tail)x xmembangun daftar semua sufiks x, termasuk string kosong ""di akhir, yang dilucuti init.

Sunting: @feersum melihat bug di versi pertama saya dan muncul dengan gagasan bahwa membandingkan sufiks sudah cukup.

nimi
sumber
Bagaimana cara memeriksa bahwa tidak ada rotasi xyang sama dengan x?
feersum
@feersum: tidak. Itu bug. Memperbaikinya. Terima kasih telah mencari tahu!
nimi
4

Pyth, 9 byte

!f>z>zTUz

Demonstrasi

Menggunakan Vihan et. Pendekatan sufiks al.

isaacg
sumber
Sial, saya pikir saya ke sesuatu di sana: p +1
Downgoat
2

CJam, 15 14 byte

r_,,\fm<(f>1-!

Coba biola ini dalam juru bahasa CJam atau verifikasi semua kasus uji sekaligus.

Bagaimana itu bekerja

r              e# Read a token from STDIN.
 _,            e# Push the length of a copy.
   ,           e# Turn length L into [0 ... L-1].
    \fm<       e# Rotate the token 0, ..., and L-1 units to the left.
        (      e# Shift out the first rotation, i.e., the original token.
         f>    e# Compare all other rotations with this one.
           1-  e# Remove 1 from the resulting array of Booleans.
             ! e# Apply logical NOT to turn an empty array into 1, and a
               e# non-empty one into 0.
Dennis
sumber
2

J, 11 char

Output 1pada kata-kata Lyndon dan 0sebaliknya.

0=0({/:)<\.

<\.mengambil sufiks dan kemudian /:memberi tahu kami cara mengurutkannya secara leksikografis. {mengambil entri pada 0indeks -th dan 0=memeriksa apakah nol: jika ya, kita memiliki kata Lyndon, karena akhiran terbesar tidak akan berubah tempat dalam bentuk; jika bukan nol, itu bukan kata Lyndon, karena beberapa sufiks secara leksikografis lebih awal.

   0=0({/:)<\. '001011'
1
   0=0({/:)<\. '001001'
0
algoritme hiu
sumber
2

TeaScript , 10 byte

xe»x«xS(i©

Sangat golf, pendek. Cobalah online

Penjelasan && Tidak Disatukan

xe(#x<=xS(i))

xe(#      // Loop through x
          // Check if all iterations return true
    x <=  // Input is less than or equal to...
    xS(i) // Input chopped at current index
)
Downgoat
sumber
Astaga, kau mengalahkan <s> Pyth </s> Dennis ! Bagaimana ini mungkin?
ETHproduk
2
@ETHproductions Dalam dunia di mana Dennis bisa keluar-golfed apa pun mungkin: p
Downgoat
Saya akan menikmati saat ini selama itu berlangsung, maka jawaban CJam dan Pyth mungkin akan lebih banyak
golf
Tunggu, tunggu ... Saya melihat bahwa ini benar menangani kasus seperti 00, tetapi bagaimana cara melakukan ini tanpa mengetahui bahwa dirinya sama dengan dirinya sendiri (yaitu kapan i==0)?
ETHproduk
@ ETHproductions Ini sebenarnya bukan siklus seperti jawaban feersum , hanya membandingkan sufiks yang secara fungsional setara
Downgoat
1

Haskell, 29

f s=all(s<=)$init$scanr(:)[]s

Cek apakah spaling banyak sufiksnya tidak kosong, seperti jawaban nimi .

Ekspresi scanr(:)[]menghasilkan daftar sufiks dengan mendaftar.

>> scanr(:)[] "abcd"
["abcd","bcd","cd","d",""]

The initkemudian menghilangkan string kosong di akhir. Akhirnya, all(s<=)periksa apakah setiap sufiks xmemuaskan s<=x. Karena akhiran pertama itu ssendiri, maka <=diperlukan.

Tidak
sumber
1

Ruby, 37 byte

->s{(1...s.size).all?{|i|s[i..-1]>s}}

Pengujian:

lyndon_words = %w(0 1 01 001 011 0001 0011 0111 00001 00011 00101 00111
                  01011 01111 000001 000011 000101 000111 001011 001101
                  001111 010111 011111)

not_lyndon_words = %w(00 10 11 000 010 100 101 110 111 0000 0010 0100 0101
                      0110 1000 1001 1010 1011 1100 1101 1110 1111)

f=->s{(1...s.size).all?{|i|s[i..-1]>s}}

p lyndon_words.all? &f      # => true
p not_lyndon_words.any? &f  # => false
daniero
sumber
1

Burlesque, 15 byte

JiRJU_j<]x/==&&

Terutama 8 dari 7 byte itu untuk memeriksa apakah tidak mengikat. Kalau tidak, Anda bisa pergi dengan sederhana JiR<]==.

Penjelasan:

J       -- duplicate word
iR      -- all rotations
J       -- duplicate list of all rotations
U_      -- check if list contains no duplicates
j       -- swap
<]      -- find minimum of the list
x/      -- rotate top
==      -- compare minimum with the original word
&&      -- and results of min == orig and list unique
mroman
sumber
0

Pyth - 12 byte

Harapan untuk bermain golf sedikit.

.A<Lzt.<Lzlz

Coba online .

Maltysen
sumber
0

Javascript (ES6), 129 byte

a=Array;s=prompt();console.log(a.from(a(s.length),(x,i)=>i).map(n=>(s.substring(n)+s.substring(0,n--))).sort().pop().contains(s))
anOKsquirrel
sumber
0

Javascript, 91 87 byte

f=x=>(y=(x+x).slice(1,-1),x[0]==x||!(y.indexOf(x)+1)&&!x.indexOf('0')&&x.slice(-1)==1);

Saya pada dasarnya menggabungkan kata dengan dirinya sendiri dan memeriksa apakah itu masih ada. Untuk memeriksa apakah itu adalah angka terkecil yang mungkin, saya hanya memeriksa bahwa itu dimulai dengan 0 dan diakhiri dengan 1.

Tes

[
['0',1],
['1',1],
['01',1],
['001',1],
['011',1],
['0001',1],
['0011',1],
['0111',1],
['00001',1],
['00011',1],
['00101',1],
['00111',1],
['01011',1],
['01111',1],
['000001',1],
['000011',1],
['000101',1],
['000111',1],
['001011',1],
['001101',1],
['001111',1],
['010111',1],
['011111',1],
['00',0],
['10',0],
['11',0],
['000',0],
['010',0],
['100',0],
['101',0],
['110',0],
['111',0],
['0000',0],
['0010',0],
['0100',0],
['0101',0],
['0110',0],
['1000',0],
['1001',0],
['1010',0],
['1011',0],
['1100',0],
['1101',0],
['1110',0],
['1111',0]
].forEach(t =>{ 
  r=f(t[0])
  x=t[1]
  console.log('Test '+(r==x?'OK':'Fail (Expected: ' + x +')')
  +'\nInput: '+t[0]+'\nResult: ' +r+'\n')                       
})
Naouak
sumber
0

Mathematica, 86 byte

(s=Table[#~StringRotateLeft~i,{i,StringLength@#}];Last@s==First@Sort@s&&s~Count~#==1)&

memasukkan

["1111"]

J42161217
sumber