Verifique la palabra de Lyndon

22

Una palabra de Lyndon es una cadena que es estrictamente lexicográfica más pequeña que cualquiera de sus rotaciones cíclicas. Dada una cadena binaria, determine si es una palabra Lyndon en la menor cantidad de bytes posible.

Por ejemplo, 001011es una palabra de Lyndon. Sus rotaciones, enumeradas a continuación, se obtienen moviendo repetidamente el primer símbolo hasta el final.

001011
010110
101100
011001
110010
100101

De estos, la cadena original viene primero lexicográficamente, o de manera equivalente, representa el número binario más pequeño.

Sin embargo, 001001no es una palabra de Lyndon porque una de sus rotaciones es la misma, lo que lo vincula desde el punto de vista lexicográfico más temprano.

Un problema relacionado

Entrada: una cadena binaria no vacía o una lista de dígitos 0y 1. Es posible que no utilice números, como 5para representar 101.

Salida: Un valor consistente de Verdad o Falsey que dice si la cadena es una palabra de Lyndon.

No se permiten las incorporaciones específicas para palabras de Lyndon.

Casos de prueba:

Las palabras de Lyndon con una longitud de hasta 6 son:

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

Las palabras que no son Lyndon de longitud hasta 4 son:

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

Tabla de clasificación:

Mostrar fragmento de código

code-golf string xnor
fuente

Respuestas:

5

Pitón 2, 42

Parece ser lo suficientemente bueno para comparar con sufijos en lugar de molestarse con una rotación.

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

La configuración de la recursión no parece muy agradable; tal vez podría hacerse mejor.

Esta versión de 44 bytes hace más obvio lo que está sucediendo:

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

Haskell, 43 38 bytes

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

scanl(const.tail)x xcrea una lista de todos los sufijos de x, incluida la cadena vacía ""al final, que se elimina con init.

Editar: @feersum detectó un error en mi primera versión y se me ocurrió la idea de que comparar con sufijos es suficiente.

nimi
fuente
¿Cómo verifica que no haya rotaciones xiguales x?
fiesta del
@feersum: no lo hace. Es un error Arreglado. Gracias por descubrirlo!
nimi
4

Pyth, 9 bytes

!f>z>zTUz

Demostración

Utiliza Vihan et. enfoque de sufijos de al.

isaacg
fuente
Maldita sea, pensé que estaba
haciendo
2

CJam, 15 14 bytes

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

Pruebe este violín en el intérprete de CJam o verifique todos los casos de prueba a la vez.

Cómo 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
fuente
2

J, 11 char

Salidas 1en palabras de Lyndon y de 0otra manera.

0=0({/:)<\.

<\.toma sufijos y luego /:nos dice cómo clasificarlos lexicográficamente. {toma la entrada en el 0índice -th y 0=comprueba si es cero: si es así, tenemos una palabra de Lyndon, porque el sufijo más grande no cambiaría de lugar; si no es cero, no es una palabra de Lyndon, porque algunos sufijos son lexicográficamente anteriores.

   0=0({/:)<\. '001011'
1
   0=0({/:)<\. '001001'
0
Algoritmo de tiburón
fuente
2

TeaScript , 10 bytes

xe»x«xS(i©

Muy golf, muy corto. Pruébalo en línea

Explicación && 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
fuente
Santa vaca, estás golpeando a <s> Pyth </s> Dennis ! ¡¿Como es esto posible?!
ETHproductions
2
@ETHproductions En un mundo donde Dennis puede ser superado, cualquier cosa es posible: p
Downgoat
Saborearé este momento mientras dure, entonces las respuestas de CJam y Pyth probablemente se jugarán más
Downgoat
Espera, espera ... Veo que esto maneja adecuadamente los casos 00, pero ¿cómo lo hace sin que se dé cuenta de que es igual a sí mismo (es decir, cuándo i==0)?
ETHproductions
@ETHproductions Esto en realidad no tiene un ciclo muy parecido a la respuesta de feersum , simplemente comparar los sufijos es funcionalmente equivalente
Downgoat
1

Haskell, 29

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

Comprueba si ses a lo sumo cada uno de sus sufijos no vacíos, como la respuesta de nimi .

La expresión scanr(:)[]genera la lista de sufijos por listado.

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

La initcontinuación, se deshace de la cadena vacía al final. Finalmente, all(s<=)verifica si cada sufijo xsatisface s<=x. Como el primer sufijo es él smismo, <=se necesita a.

xnor
fuente
1

Ruby, 37 bytes

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

Pruebas:

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

Burlesque, 15 bytes

JiRJU_j<]x/==&&

Principalmente 8 de esos 7 bytes son para verificar si no está vinculado. De lo contrario, puede ir simplemente JiR<]==.

Explicación:

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
fuente
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
fuente
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);

Básicamente estoy concatenando la palabra consigo misma y verifico si todavía está allí. Para verificar si es el número más pequeño posible, solo verifico que comience con un 0 y termine con un 1.

Pruebas

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

Mathematica, 86 bytes

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

entrada

["1111"]

J42161217
fuente