22
2
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>
1Related. – Martin Ender – 2015-12-02T16:23:47.017
1in simpler words you could say: the function is recursive, negate the input and append it. – Eumel – 2015-12-02T16:43:04.320
@Eumel yeah, but that might give people too big a hint. I do want to see some variety in the solutions. – Sherlock9 – 2015-12-02T16:45:15.220
2Borderline dupe – Peter Taylor – 2015-12-02T16:59:19.003
2@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. – Sherlock9 – 2015-12-02T17:03:18.373
Well, I did say you could put separators in the sequence and the
,
between list items is a separator. I'll allow it. Let me edit the question to indicate this. @ThomasKwa – Sherlock9 – 2015-12-02T18:17:33.5071Because 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. – Peter Taylor – 2015-12-02T19:22:40.233
1Do they have to be single symbols, or will any two easily distinguishable non-empty strings work? – SuperJedi224 – 2015-12-04T01:14:41.470
@SuperJedi224 That's a good point. Any two distinguishable non-emergency strings are alright – Sherlock9 – 2015-12-04T03:34:05.413
Does it have to be
1
and0
, or cana
andb
work? – Rɪᴋᴇʀ – 2016-03-27T16:39:42.930@EasterlyIrk You are allowed to used any two distinguishable non-empty strings, including
a
andb
. – Sherlock9 – 2016-03-27T17:16:48.300@Sherlock9 okay, thanks. – Rɪᴋᴇʀ – 2016-03-27T17:59:29.000