Verifique a palavra Lyndon

22

Uma palavra de Lyndon é uma string estritamente lexicograficamente menor do que qualquer uma de suas rotações cíclicas. Dada uma sequência binária, determine se é uma palavra Lyndon no menor número de bytes possível.

Por exemplo, 001011é uma palavra de Lyndon. Suas rotações, listadas abaixo, são obtidas movendo repetidamente o primeiro símbolo até o fim.

001011
010110
101100
011001
110010
100101

Destes, a sequência original vem lexicograficamente primeiro, ou equivalente, representa o menor número binário.

No entanto, 001001não é uma palavra de Lyndon porque uma de suas rotações é a mesma que ela mesma, o que a vincula lexicograficamente mais cedo.

Um problema relacionado.

Entrada: uma sequência de caracteres binária não vazia ou uma lista de dígitos 0e 1. Você não pode usar números, como 5para representar 101.

Saída: um valor Truthy ou Falsey consistente que diz se a sequência é uma palavra de Lyndon.

Não são permitidos embutidos especificamente para palavras Lyndon.

Casos de teste:

As palavras de Lyndon com comprimento de até 6 são:

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

As palavras não-Lyndon de comprimento até 4 são:

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

Entre os melhores:

Mostrar snippet de código

code-golf string xnor
fonte

Respostas:

5

Python 2, 42

Parece ser bom o suficiente para comparar com sufixos em vez de se preocupar com uma rotação.

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

A configuração da recursão não parece muito agradável; talvez isso possa ser feito melhor.

Esta versão de 44 bytes torna mais óbvio o que está acontecendo:

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

Haskell, 43 38 bytes

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

scanl(const.tail)x xcria uma lista de todos os sufixos de x, incluindo a string vazia ""no final, que é retirada com init.

Edit: @feersum viu um bug na minha primeira versão e teve a ideia de que comparar com sufixos é suficiente.

nimi
fonte
Como verifica se não há rotações xiguais a x?
feersum
@ Feersum: isso não acontece. É um bug. Corrigido. Obrigado por descobrir!
N
4

Pitão, 9 bytes

!f>z>zTUz

Demonstração

Usa Vihan et. abordagem de sufixos de al.

isaacg
fonte
Dang, eu pensei que eu era sobre a algo lá: p +1
Downgoat
2

CJam, 15 14 bytes

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

Experimente este violino no intérprete CJam ou verifique todos os casos de teste de uma só vez.

Como funciona

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
fonte
2

J, 11 caracteres

Saídas 1em palavras Lyndon e 0outros.

0=0({/:)<\.

<\.usa sufixos e depois /:nos diz como classificá-los lexicograficamente. {pega a entrada no 0-ésimo índice e0= verifica se é zero: se for, temos uma palavra de Lyndon, porque o maior sufixo não mudaria de lugar em uma espécie; se for diferente de zero, não é uma palavra de Lyndon, porque algum sufixo é lexicograficamente anterior.

   0=0({/:)<\. '001011'
1
   0=0({/:)<\. '001001'
0
algoritmshark
fonte
2

TeaScript , 10 bytes

xe»x«xS(i©

Muito golfe, muito curto. Experimente online

Explicação && Ungolfed

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
fonte
Puta merda, você está derrotando <s> Pyth </s> Dennis ! Como isso é possível?!
ETHproductions
2
@ETHproductions Em um mundo onde Dennis pode ser out-golfed tudo é possível: p
Downgoat
Vou saborear esse momento enquanto durar, então as respostas CJam e Pyth provavelmente serão mais
jogadas.
Espere, espere ... Vejo que isso lida corretamente com casos como esse 00, mas como isso acontece sem que se pareça igual a si mesmo (ou seja, quando i==0)?
ETHproductions
@ETHproductions Este na verdade não ciclo muito parecido de feersum resposta , simplesmente comparando os sufixos é funcionalmente equivalente
Downgoat
1

Haskell, 29

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

Verifica se shá no máximo cada um dos sufixos não vazios, como a resposta de nimi .

A expressão scanr(:)[]gera a lista de sufixos listando.

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

O initentão se livra da string vazia no final. Por fim, all(s<=)verifica se todo sufixo é xsatisfatório s<=x. Como o primeiro sufixo é sele próprio, <=é necessário.

xnor
fonte
1

Ruby, 37 bytes

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

Teste:

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
fonte
1

Burlesco, 15 bytes

JiRJU_j<]x/==&&

Principalmente 8 desses 7 bytes devem verificar se não estão vinculados. Caso contrário, você pode usar simplesmente JiR<]==.

Explicação:

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
fonte
0

Javascript (ES6), 129 bytes

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
fonte
0

Javascript, 91 87 bytes

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

Estou basicamente concatenando a palavra consigo mesma e verificando se ela ainda está lá. Para verificar se é o menor número possível, basta verificar se começa com 0 e termina com 1.

Testes

[
['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
fonte
0

Mathematica, 86 bytes

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

entrada

["1111"]

J42161217
fonte