Vérifier le mot Lyndon

22

Un mot Lyndon est une chaîne strictement lexicographiquement plus petite que n'importe laquelle de ses rotations cycliques. Étant donné une chaîne binaire, déterminez s'il s'agit d'un mot Lyndon en aussi peu d'octets que possible.

Par exemple, 001011est un mot Lyndon. Ses rotations, répertoriées ci-dessous, sont obtenues en déplaçant à plusieurs reprises le premier symbole jusqu'à la fin.

001011
010110
101100
011001
110010
100101

Parmi ceux-ci, la chaîne d'origine vient lexicographiquement en premier, ou de manière équivalente, représente le plus petit nombre binaire.

Cependant, ce 001001n'est pas un mot de Lyndon car l'une de ses rotations est la même que lui-même, ce qui le lie le plus tôt lexicographiquement.

Un problème connexe.

Entrée: une chaîne binaire non vide ou une liste de chiffres 0et 1. Vous ne pouvez pas utiliser de chiffres, comme 5pour représenter 101.

Sortie: Une valeur Truthy ou Falsey cohérente qui indique si la chaîne est un mot Lyndon.

Les fonctions intégrées spécifiquement pour les mots Lyndon ne sont pas autorisées.

Cas de test:

Les mots Lyndon d'une longueur maximale de 6 sont:

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

Les mots non lyndons d'une longueur maximale de 4 sont:

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

Classement:

Afficher l'extrait de code

code-golf string xnor
la source

Réponses:

5

Python 2, 42

Il semble être assez bon pour comparer avec des suffixes au lieu de se soucier d'une rotation.

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

La configuration de la récursivité ne semble pas très agréable; on pourrait peut-être faire mieux.

Cette version de 44 octets rend plus évident ce qui se passe:

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

Haskell, 43 38 octets

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

scanl(const.tail)x xconstruit une liste de tous les suffixes de x, y compris la chaîne vide ""à la fin, qui est supprimée avec init.

Edit: @feersum a repéré un bogue dans ma première version et a eu l'idée que la comparaison aux suffixes est suffisante.

nimi
la source
Comment vérifie-t-il qu'il n'y a pas de rotation xégale à x?
feersum
@feersum: ce n'est pas le cas. C'est un bug. A corrigé. Merci de l'avoir découvert!
nimi
4

Pyth, 9 octets

!f>z>zTUz

Manifestation

Utilise Vihan et. l'approche des suffixes d'al.

isaacg
la source
Dang it, je pensais que j'étais sur quelque chose là-bas: p +1
Downgoat
2

CJam, 15 14 octets

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

Essayez ce violon dans l'interpréteur CJam ou vérifiez tous les cas de test à la fois.

Comment ça marche

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
la source
2

J, 11 caractères

Sorties 1sur les mots Lyndon et 0autres.

0=0({/:)<\.

<\.prend des suffixes puis /:nous indique comment les trier lexicographiquement. {prend l'entrée au 0-ième index et 0=vérifie s'il est nul: s'il l'est, nous avons un mot Lyndon, car le plus grand suffixe ne changerait pas de place dans une sorte; s'il est différent de zéro, ce n'est pas un mot de Lyndon, car certains suffixes sont lexicographiquement plus tôt.

   0=0({/:)<\. '001011'
1
   0=0({/:)<\. '001001'
0
algorithmshark
la source
2

TeaScript , 10 octets

xe»x«xS(i©

Très golf, beaucoup court. Essayez-le en ligne

Explication && 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
la source
Sainte vache, vous battez <s> Pyth </s> Dennis ! Comment est-ce possible?!
ETHproductions
2
@ETHproductions Dans un monde où Dennis peut être hors-golf, tout est possible: p
Downgoat
Je savourerai ce moment tant qu'il durera, puis les réponses CJam et Pyth seront probablement plus
jouées
Attendez, attendez ... Je vois que cela gère correctement les cas comme 00, mais comment fait-il cela sans se prendre pour égal à lui-même (c'est-à-dire quand i==0)?
ETHproductions
@ETHproductions Cela ne ressemble pas vraiment à la réponse de feersum , simplement comparer les suffixes est fonctionnellement équivalent
Downgoat
1

Haskell, 29

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

Vérifie si sau plus chacun de ses suffixes n'est pas vide, comme la réponse de nimi .

L'expression scanr(:)[]génère la liste des suffixes par listage.

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

Le initse débarrasse ensuite de la chaîne vide à la fin. Enfin, all(s<=)vérifie si chaque suffixe xsatisfait s<=x. Puisque le premier suffixe est slui - même, un <=est nécessaire.

xnor
la source
1

Rubis, 37 octets

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

Essai:

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
la source
1

Burlesque, 15 octets

JiRJU_j<]x/==&&

Surtout, 8 de ces 7 octets doivent vérifier s'il n'est pas lié. Sinon, vous pouvez y aller simplement JiR<]==.

Explication:

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
la source
0

Javascript (ES6), 129 octets

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
la source
0

Javascript, 91 87 octets

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

Je concatène le mot avec lui-même et vérifie s'il est toujours là. Pour vérifier s'il s'agit du plus petit nombre possible, je vérifie simplement qu'il commence par un 0 et se termine par un 1.

Les tests

[
['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
la source
0

Mathematica, 86 octets

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

contribution

["1111"]

J42161217
la source