# Check Lyndon word

A Lyndon word is a string that is strictly lexicographically smaller than any of its cyclic rotations. Given a binary string, determine if it's a Lyndon word in as few bytes as possible.

For example, 001011 is a Lyndon word. Its rotations, listed below, are obtained by repeatedly moving the first symbol to the end.

001011
010110
101100
011001
110010
100101


Of these, the original string comes lexicographically first, or equivalently, represents the smallest binary number.

However, 001001 is not a Lyndon word because one of its rotations is the same as itself, which ties it for lexicographically earliest.

A related problem.

Input: A non-empty binary string or list of digits 0 and 1. You may not use numbers, like 5 to represent 101.

Output: A consistent Truthy or Falsey value that says whether the string is a Lyndon word.

Built-ins specifically for Lyndon words are not allowed.

Test cases:

The Lyndon words with length up to 6 are:

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


The non-Lyndon words of length up to 4 are:

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


    var QUESTION_ID=62587,OVERRIDE_USER=20260;function answersUrl(e){return"https://api.stackexchange.com/2.2/questions/63075/answers?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function commentUrl(e,s){return"https://api.stackexchange.com/2.2/answers/"+s.join(";")+"/comments?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+COMMENT_FILTER}function getAnswers(){jQuery.ajax({url:answersUrl(answer_page++),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){answers.push.apply(answers,e.items),answers_hash=[],answer_ids=[],e.items.forEach(function(e){e.comments=[];var s=+e.share_link.match(/\d+/);answer_ids.push(s),answers_hash[s]=e}),e.has_more||(more_answers=!1),comment_page=1,getComments()}})}function getComments(){jQuery.ajax({url:commentUrl(comment_page++,answer_ids),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){e.items.forEach(function(e){e.owner.user_id===OVERRIDE_USER&&answers_hash[e.post_id].comments.push(e)}),e.has_more?getComments():more_answers?getAnswers():process()}})}function getAuthorName(e){return e.owner.display_name}function process(){var e=[];answers.forEach(function(s){var r=s.body;s.comments.forEach(function(e){OVERRIDE_REG.test(e.body)&&(r="<h1>"+e.body.replace(OVERRIDE_REG,"")+"</h1>")});var a=r.match(SCORE_REG);a&&e.push({user:getAuthorName(s),size:+a[2],language:a[1],link:s.share_link})}),e.sort(function(e,s){var r=e.size,a=s.size;return r-a});var s={},r=1,a=null,n=1;e.forEach(function(e){e.size!=a&&(n=r),a=e.size,++r;var t=jQuery("#answer-template").html();t=t.replace("{{PLACE}}",n+".").replace("{{NAME}}",e.user).replace("{{LANGUAGE}}",e.language).replace("{{SIZE}}",e.size).replace("{{LINK}}",e.link),t=jQuery(t),jQuery("#answers").append(t);var o=e.language;/<a/.test(o)&&(o=jQuery(o).text()),s[o]=s[o]||{lang:e.language,user:e.user,size:e.size,link:e.link}});var t=[];for(var o in s)s.hasOwnProperty(o)&&t.push(s[o]);t.sort(function(e,s){return e.lang>s.lang?1:e.lang<s.lang?-1:0});for(var c=0;c<t.length;++c){var i=jQuery("#language-template").html(),o=t[c];i=i.replace("{{LANGUAGE}}",o.lang).replace("{{NAME}}",o.user).replace("{{SIZE}}",o.size).replace("{{LINK}}",o.link),i=jQuery(i),jQuery("#languages").append(i)}}var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe",COMMENT_FILTER="!)Q2B_A2kjfAiU78X(md6BoYk",answers=[],answers_hash,answer_ids,answer_page=1,more_answers=!0,comment_page;getAnswers();var SCORE_REG=/<h\d>\s*([^\n,]*[^\s,]),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/,OVERRIDE_REG=/^Override\s*header:\s*/i;
    body{text-align:left!important}#answer-list,#language-list{padding:10px;width:290px;float:left}table thead{font-weight:700}table td{padding:5px}
    <script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script> <link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"> <div id="answer-list"> <h2>Leaderboard</h2> <table class="answer-list"> <thead> <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr></thead> <tbody id="answers"> </tbody> </table> </div><div id="language-list"> <h2>Winners by Language</h2> <table class="language-list"> <thead> <tr><td>Language</td><td>User</td><td>Score</td></tr></thead> <tbody id="languages"> </tbody> </table> </div><table style="display: none"> <tbody id="answer-template"> <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table> <table style="display: none"> <tbody id="language-template"> <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table>

# Python 2, 42

It seems to be good enough to compare with suffixes instead of bothering with a rotation.

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


The setup of the recursion does not seem very nice; maybe it could be done better.

This 44-byte version makes it more obvious what's going on:

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


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


scanl(const.tail)x x builds a list of all suffixes of x, including the empty string "" at the end, which is stripped off with init.

Edit: @feersum spotted a bug in my first version and came up with the idea that comparing to suffixes is enough.

• How does it check that there aren't any rotations of x that are equal to x? Nov 6, 2015 at 4:18
• @feersum: it doesn't. It's a bug. Fixed it. Thanks for finding out!
– nimi
Nov 6, 2015 at 4:37

# Pyth, 9 bytes

!f>z>zTUz


Demonstration

Uses Vihan et. al.'s suffixes approach.

• Dang it, I thought I was on to something there :p +1 Nov 6, 2015 at 5:44

# J, 11 char

Outputs 1 on Lyndon words and 0 otherwise.

0=0({/:)<\.


<\. takes suffixes and then /: tells us how to sort them lexicographically. { takes the entry at the 0-th index and 0= checks if it's zero: if it is, we have a Lyndon word, because the biggest suffix wouldn't change place in a sort; if it's nonzero, it is not a Lyndon word, because some suffix is lexicographically earlier.

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


# ShapeScript, 57 47 bytes

0?1'@"2"@+"20"$""~"21"$""~@2?2?>1<*'3?_1-*!@#@#


I created ShapeScript for this competition. The interpreter on GitHub has a slightly modified syntax.

Try it online!

• Trivia: This is my 700th PPCG answer. Nov 7, 2015 at 14:41

# CJam, 15 14 bytes

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


Try this fiddle in the CJam interpreter or verify all test cases at once.

### How it works

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.


# TeaScript, 10 bytes

xe»x«xS(i©


Very golf, much short. Try it online

### Explanation && 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
)

• Holy cow, you're beating <s>Pyth</s> Dennis! How is this even possible?! Nov 6, 2015 at 4:40
• @ETHproductions In a world where Dennis can be out-golfed anything is possible :p Nov 6, 2015 at 4:41
• I'll savor this moment while it lasts, then the CJam and Pyth answers will probably be golfed more Nov 6, 2015 at 4:43
• Wait, wait... I see that this properly handles cases like 00, but how does it do this without catching on itself being equal to itself (i.e. when i==0)? Nov 6, 2015 at 4:46
• @ETHproductions This doesn't actually cycle much like feersum's answer, simply comparing the suffixes is functionally equivalent Nov 6, 2015 at 4:47

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


Checks whether s is at most each of its non-empty suffixes, like nimi's answer.

The expression scanr(:)[] generates the list of suffixes by listing.

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


The init then gets rid of the empty string at the end. Finally, all(s<=) checks whether every suffix x satisfies s<=x. Since the first suffix is s itself, a <= is needed.

# Ruby, 37 bytes

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


Testing:

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


## Burlesque, 15 bytes

JiRJU_j<]x/==&&


Mainly 8 of those 7 bytes are to check if it doesn't tie. Otherwise you can go with simply JiR<]==.

Explanation:

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


# Vyxal, 5 bytes

ẏvǔg=


Try it Online!

 vǔ   # Rotate by each of...
ẏ     # 0 to len(x)
g  # Does the (lexicographic) minimum
= # Equal the input?

• From the challenge description: "However, 001001 is not a Lyndon word because one of its rotations is the same as itself, which ties it for lexicographically earliest." Nov 1, 2022 at 8:27

# Pyth - 12 bytes

Hope to golf a little bit.

.A<Lzt.<Lzlz


# 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))


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


I'm basically concatenating the word with itself and check if it's still there. To check if it is the smallest number possible, I just check that it start with a 0 and end with a 1.

### 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')
})


# Mathematica, 86 bytes

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


input

["1111"]

# PowerShell Core, 85 bytes

param($k)($w=0..($l=$k.Length-1)|%{-join$k[-$_..($l-$_)]}|sort)[0]-eq$k-and$w[1]-ne\$k


Try it online!

1. Generates all the rotations of the input
2. Sorts them
3. Checks that the first one equals the input and the second one does not

# 05AB1E, 7 (or 8?) bytes

ā._{QJR


Outputs a 05AB1E truthy/falsey result, where truthy is a 1 padded with leading 0s up to the input-length, and falsey anything else. But since the challenge description mentions 'consistent' truthy/falsey value, a trailing Θ (05AB1E-truthify builtin: ==1) can be added for consistent 1/0 outputs.

Explanation:

ā        # Push a list in the range [1, (implicit) input-length] (without popping)
._      # Rotate the input that many times (vectorized) towards the left
{     # Sort this list of rotations
Q    # Check for each rotation whether it's equal to the (implicit) input
J   # Join the checks together
R  # Reverse this string
# (after which the result is output implicitly)