Check Lyndon word

Question

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

Leaderboard:

    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>

Answer 1

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

Answer 2

Haskell, 43 38 bytes

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.

Answer 3

Pyth, 9 bytes

!f>z>zTUz

Demonstration

Uses Vihan et. al.'s suffixes approach.

Answer 4

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

Answer 5

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!

Answer 6

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.

Answer 7

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
)

Answer 8

Haskell, 29

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.

Answer 9

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

Answer 10

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

Answer 11

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?

Answer 12

Pyth - 12 bytes

Hope to golf a little bit.

.A<Lzt.<Lzlz

Try online.

Answer 13

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

Answer 14

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

Answer 15

Mathematica, 86 bytes

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

input

["1111"]

Answer 16

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

Answer 17

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.

Try it online or verify some more test cases.

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)