22
\$\begingroup\$

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>

\$\endgroup\$

14 Answers 14

5
\$\begingroup\$

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)))
\$\endgroup\$
4
\$\begingroup\$

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.

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

Pyth, 9 bytes

!f>z>zTUz

Demonstration

Uses Vihan et. al.'s suffixes approach.

\$\endgroup\$
  • \$\begingroup\$ Dang it, I thought I was on to something there :p +1 \$\endgroup\$ – Downgoat Nov 6 '15 at 5:44
3
\$\begingroup\$

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!

\$\endgroup\$
  • 3
    \$\begingroup\$ Trivia: This is my 700th PPCG answer. \$\endgroup\$ – Dennis Nov 7 '15 at 14:41
2
\$\begingroup\$

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.
\$\endgroup\$
2
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

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
)
\$\endgroup\$
  • \$\begingroup\$ Holy cow, you're beating <s>Pyth</s> Dennis! How is this even possible?! \$\endgroup\$ – ETHproductions Nov 6 '15 at 4:40
  • 2
    \$\begingroup\$ @ETHproductions In a world where Dennis can be out-golfed anything is possible :p \$\endgroup\$ – Downgoat Nov 6 '15 at 4:41
  • \$\begingroup\$ I'll savor this moment while it lasts, then the CJam and Pyth answers will probably be golfed more \$\endgroup\$ – Downgoat Nov 6 '15 at 4:43
  • \$\begingroup\$ 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)? \$\endgroup\$ – ETHproductions Nov 6 '15 at 4:46
  • \$\begingroup\$ @ETHproductions This doesn't actually cycle much like feersum's answer, simply comparing the suffixes is functionally equivalent \$\endgroup\$ – Downgoat Nov 6 '15 at 4:47
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
0
\$\begingroup\$

Pyth - 12 bytes

Hope to golf a little bit.

.A<Lzt.<Lzlz

Try online.

\$\endgroup\$
0
\$\begingroup\$

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))
\$\endgroup\$
0
\$\begingroup\$

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')                       
})  
\$\endgroup\$
0
\$\begingroup\$

Mathematica, 86 bytes

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

input

["1111"]

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.