25
\$\begingroup\$

There's quite a few challenges on this site that ask you to print out a sequence, and this is no exception.

(The following explanation of the sequence for this challenge assumes the symbols in the sequence are 0 and 1.)

The recursive definition of the Thue-Morse sequence is that

T_0 = 0
T_2n = T_n
T_2n+1 = 1 - T_n

A more direct definition is that the sequence from 0 to 2**m-1 and 2**m to 2**(m+1)-1 are binary complements. So 0 is followed by 1, 01 is followed by 10, 0110 is followed by 1001, and, skipping ahead a bit, 0110100110010110 is followed by 1001011001101001.

The challenge is to write a program or a function that prints out the Thue-Morse sequence for the first n elements, where n is any non-negative integer. The output can use any two symbols, as shown in the examples below.

Examples

>>> tm_01(20)
01101001100101101001
>>> tm_ab(42)
abbabaabbaababbabaababbaabbabaabbaababbaab
>>> tm_paren(37)
())()(())(()())()(()())(())()(())(()(
>>> tm_space_star(12)
 ** *  **  *
>>> tm_01(0)
                # to show that this is a valid input

Rules

  • The input will be any non-negative integer. You can assume all inputs are valid.

  • The output must be the first n elements of the Thue-Morse sequence, using any symbols that are convenient. If you like, you can also add a separator. In my examples, I have not. Note: This rule allows lists (like those of Python), as , is a valid separator and I don't mind leading or trailing characters, such as [ and ] in the output.

  • This is code golf, so the smallest number of bytes wins.

As always, if the problem is unclear, please let me know. Good luck and good golfing!

Catalogue

var QUESTION_ID=65549;var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe";var COMMENT_FILTER="!)Q2B_A2kjfAiU78X(md6BoYk";var OVERRIDE_USER=47581;var answers=[],answers_hash,answer_ids,answer_page=1,more_answers=true,comment_page;function answersUrl(index){return"http://api.stackexchange.com/2.2/questions/"+QUESTION_ID+"/answers?page="+index+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function commentUrl(index,answers){return"http://api.stackexchange.com/2.2/answers/"+answers.join(';')+"/comments?page="+index+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+COMMENT_FILTER}function getAnswers(){jQuery.ajax({url:answersUrl(answer_page++),method:"get",dataType:"jsonp",crossDomain:true,success:function(data){answers.push.apply(answers,data.items);answers_hash=[];answer_ids=[];data.items.forEach(function(a){a.comments=[];var id=+a.share_link.match(/\d+/);answer_ids.push(id);answers_hash[id]=a});if(!data.has_more)more_answers=false;comment_page=1;getComments()}})}function getComments(){jQuery.ajax({url:commentUrl(comment_page++,answer_ids),method:"get",dataType:"jsonp",crossDomain:true,success:function(data){data.items.forEach(function(c){if(c.owner.user_id===OVERRIDE_USER)answers_hash[c.post_id].comments.push(c)});if(data.has_more)getComments();else if(more_answers)getAnswers();else process()}})}getAnswers();var SCORE_REG=/<h\d>\s*([^\n,<]*(?:<(?:[^\n>]*>[^\n<]*<\/[^\n>]*>)[^\n,<]*)*),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/;var OVERRIDE_REG=/^Override\s*header:\s*/i;function getAuthorName(a){return a.owner.display_name}function process(){var valid=[];answers.forEach(function(a){var body=a.body;a.comments.forEach(function(c){if(OVERRIDE_REG.test(c.body))body='<h1>'+c.body.replace(OVERRIDE_REG,'')+'</h1>'});var match=body.match(SCORE_REG);if(match)valid.push({user:getAuthorName(a),size:+match[2],language:match[1],link:a.share_link,});else console.log(body)});valid.sort(function(a,b){var aB=a.size,bB=b.size;return aB-bB});var languages={};var place=1;var lastSize=null;var lastPlace=1;valid.forEach(function(a){if(a.size!=lastSize)lastPlace=place;lastSize=a.size;++place;var answer=jQuery("#answer-template").html();answer=answer.replace("{{PLACE}}",lastPlace+".").replace("{{NAME}}",a.user).replace("{{LANGUAGE}}",a.language).replace("{{SIZE}}",a.size).replace("{{LINK}}",a.link);answer=jQuery(answer);jQuery("#answers").append(answer);var lang=a.language;lang=jQuery('<a>'+lang+'</a>').text();languages[lang]=languages[lang]||{lang:a.language,lang_raw:lang.toLowerCase(),user:a.user,size:a.size,link:a.link}});var langs=[];for(var lang in languages)if(languages.hasOwnProperty(lang))langs.push(languages[lang]);langs.sort(function(a,b){if(a.lang_raw>b.lang_raw)return 1;if(a.lang_raw<b.lang_raw)return-1;return 0});for(var i=0;i<langs.length;++i){var language=jQuery("#language-template").html();var lang=langs[i];language=language.replace("{{LANGUAGE}}",lang.lang).replace("{{NAME}}",lang.user).replace("{{SIZE}}",lang.size).replace("{{LINK}}",lang.link);language=jQuery(language);jQuery("#languages").append(language)}}
body{text-align:left!important}#answer-list{padding:10px;width:290px;float:left}#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="language-list"> <h2>Shortest Solution 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> <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> <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\$
12
  • 1
    \$\begingroup\$ Related. \$\endgroup\$ Dec 2, 2015 at 16:23
  • 1
    \$\begingroup\$ in simpler words you could say: the function is recursive, negate the input and append it. \$\endgroup\$
    – Eumel
    Dec 2, 2015 at 16:43
  • 2
    \$\begingroup\$ Borderline dupe \$\endgroup\$ Dec 2, 2015 at 16:59
  • 2
    \$\begingroup\$ @PeterTaylor In what way? One possible answer to the linked question is the Thue-Morse sequence, but this question is to generate the Thue-Morse and nothing else. \$\endgroup\$
    – Sherlock9
    Dec 2, 2015 at 17:03
  • 1
    \$\begingroup\$ Because some of the answers to the previous question can be used to answer this question with trivial changes, and all answers to this question can be used to answer the previous question with trivial changes. \$\endgroup\$ Dec 2, 2015 at 19:22

36 Answers 36

1
2
1
\$\begingroup\$

Arcyóu, 50 55 bytes

I had to add 5 bytes to get it to work correctly :(

(f i(_(#(l)))(r b^(@(> i 0)(pg 0(% i 2)(: i(#/ i 2))))0

Explanation (with Pythonesque pseudocode along the side:

(f i (_ (# (l)))       ; For i in range(int(input())):
  (r b^                ; Reduce with binary xor
    (@ (> i 0)         ; While i > 0:
      (pg 0            ; Return first of its arguments
        (% i 2)        ; i mod 2
        (: i (#/ i 2)) ; i //= 2
      )
    )
    0                  ; Default reduce argument of 0 for the first bit in the sequence
\$\endgroup\$
1
\$\begingroup\$

Husk, 6 bytes

moF≠ḋŀ

Try it online!

Using infinite list:

↑¹!¡S+m¬;0

Try it online!

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

Python 3, 84 80 60 bytes

Since nobody else was using characters other than 0 and 1, I decided to write my own answer. Here, I use the characters o and t, but I was quite tempted to use b and o, or p and o :P

This is a parity checker in 60 bytes.

lambda n:''.join("ot"[bin(i).count("1")%2]for i in range(n))

This is a string rewriting algorithm in 109 bytes.

def t(n):
 r="o";s=""
 for i in range(len(bin(n))):
  for c in r:s+="otto"[c>"o"::2]
  r=s;s=""
 return r[:n]
\$\endgroup\$
0
\$\begingroup\$

K (ngn/k), 16 bytes

{2!+/'(x#2)\'!x}

Try it online!

\$\endgroup\$
1
  • \$\begingroup\$ I think {2!+/(x#2)\!x} works for the non-zero inputs, potentially saving two bytes. \$\endgroup\$
    – coltim
    Dec 27, 2020 at 1:10
0
\$\begingroup\$

Stax, 5 bytes

╩0ΔΔ(

Run and debug it at staxlang.xyz!

Unpacked (6 bytes) and explanation:

mv:11I
mv        Map block over range [0,n):
  :1        Popcount
    1I      Is odd?
            Implicit print with newline

1I is bitwise and with 1. 2% would work just as well, also packing to 5 bytes.

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

Python, 43 bytes

def f(n):n>0==f(n-1);print(n.bit_count()%2)

Attempt This Online!

\$\endgroup\$
1
2

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.