Il y a pas mal de défis sur ce site qui vous demandent d'imprimer une séquence, et cela ne fait pas exception.

(L'explication suivante de la séquence de ce défi suppose que les symboles de la séquence sont 0et 1.)

La définition récursive de la séquence de Thue-Morse est que

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

Une définition plus directe est que la séquence de 0à 2**m-1et 2**m to 2**(m+1)-1sont des compléments binaires. Ainsi 0est suivi par 1, 01est suivi par 10, 0110est suivi par 1001, et, en sautant un peu, 0110100110010110est suivi par 1001011001101001.

Le défi consiste à écrire un programme ou une fonction qui imprime la séquence Thue-Morse pour les premiers néléments, où nest tout entier non négatif. La sortie peut utiliser deux symboles quelconques, comme indiqué dans les exemples ci-dessous.

Exemples

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

Règles

• L'entrée sera un entier non négatif. Vous pouvez supposer que toutes les entrées sont valides.

• La sortie doit être les premiers néléments de la séquence Thue-Morse, en utilisant tous les symboles qui conviennent. Si vous le souhaitez, vous pouvez également ajouter un séparateur. Dans mes exemples, je ne l'ai pas fait. Remarque: Cette règle autorise les listes (comme celles de Python), tout comme ,un séparateur valide et cela ne me dérange pas les caractères de début ou de fin, tels que [et ]dans la sortie.

• C'est le golf de code, donc le plus petit nombre d'octets gagne.

Comme toujours, si le problème n'est pas clair, faites-le moi savoir. Bonne chance et bon golf!

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>

Pyth, 6 octets

xMjR2Q

Essayez-le en ligne: Démonstration

Basé sur la solution de @ThomasKwa et une variante de @FryAmTheEggman.

Il utilise le formulaire ci : le ichiffre -ième dans la séquence Thue-Morse est la suivante : xor(digits of i in base 2).

Explication:

xMjR2Q   implicit: Q = input number
  jR2Q   convert each number in [0, 1, ..., Q-1] to its binary digits
xM       xor each binary list

CJam, 17 9 octets

ri{2b:^}/

ou

ri,2fb::^

Testez-le ici.

Explication

Ceci utilise la définition alternative donnée sur Wikipedia, basée sur la parité du nombre de 1s dans la représentation binaire du n.

ri   e# Read input and convert to integer n.
{    e# For each i from 0 to n-1...
  2b e#   Convert i to base 2.
  :^ e#   Fold XOR over the bits to compute the parity of the number of 1s.
}/

La solution alternative utilise ,pour se transformer nexplicitement en une plage [0 ... n-1]avant d'utiliser des opérateurs infixes pour calculer les représentations binaires et le XOR sans avoir besoin d'un bloc.

Solutions bonus

Voici quelques solutions basées sur d'autres définitions. S'il existe deux solutions, la plus courte fera exploser la mémoire très rapidement (car le précalcul génère des 2^nbits avant de tronquer n).

En tant que système L avec 0 --> 01et 1 --> 10:

ri_2mL2,\{2,aA+f=s:~}*<
ri_2,\{2,aA+f=s:~}*<

En niant et en ajoutant la partie précédente:

ri_2mL2,\{_:!+}*<
ri_2,\{_:!+}*<

En utilisant la relation de récurrence donnée dans le défi, en utilisant divmodet XOR pour faire la distinction entre les deux définitions récursives:

ri{Ta{2md\j^}j}/

(Bien que, bien sûr, cette relation de récurrence soit juste une manière différente d'exprimer la séquence Thue-Morse comme la parité des 1 bits dans la représentation binaire de n.)

Dyalog APL, 8 7 octets

≠⌿⍴∘2⊤⍳

Il s'agit d'un train monadique qui attend une origine d'index de 0 ( ⎕IO←0). La fonction non-train équivalente est {≠⌿(⍵⍴2)⊤⍳⍵}.

Explication:

      ⍳      List of numbers from 0 to (input-1)
  ⍴∘2        (input) copies of 2
     ⊤       Convert all the elements in ⍳ to base 2 to (input) digits
≠⌿           Reduce over the first axis by not-equal

La sortie est une liste séparée par des espaces de 0et 1. Essayez-le ici .

Mathematica, 35 21 octets

Mathematica a une fonction intégrée pour la séquence Thue-Morse!

Array[ThueMorse,#,0]&

Réponse originale:

#&@@@DigitCount[Range@#-1,2]~Mod~2&

LabVIEW, 15 primitives LabVIEW

maintenant comme gif super fantaisie avec une sonde

J, 12 11 octets

@ MartinBüttner a enregistré un octet.

~:/@#:"0@i.

Il s'agit d'une fonction monadique (signifiant unaire), utilisée comme suit:

   f =: ~:/@#:"0@i.
   f 10
0 1 1 0 1 0 0 1 1 0

Explication

J'utilise la définition alternative que T _n est la parité du nombre de 1 bits dans la représentation binaire de n.

~:/@#:"0@i.  Input is n.
~:/          Output is XOR folded over
   @#:       the binary representations of
      "0     each element of
        @i.  integers from 0 to n-1.

Pyth, 11 10 octets

m%ssM.Bd2Q

Sorties sous forme de liste de style Python.

Japt , 29 11 octets

Uo ®¤¬r@X^Y

Essayez-le en ligne!

Produit directement sous forme de tableau, ce qui économise environ 4 octets.

Non golfé et explication

Uo ®   ¤  ¬ r@  X^Y
Uo mZ{Zs2 q rXY{X^Y}}
        // Implicit: U = input number
Uo      // Create an array of integers in the range `[0, U)`. 
mZ{Zs2  // Map each item Z in this range to Z.toString(2),
q rXY{  //  split into chars, and reduced by
X^Y}}   //   XORing.
        //  This returns (number of 1s in the binary string) % 2.
        // Implicit: output last expression

Modifier: Vous pouvez maintenant utiliser le code 8 octets suivant (non valide; fonctionnalité publiée après ce défi):

Uo ®¤¬r^

Haskell, 39 36 35 octets

take<*>(iterate([id,(1-)]<*>)[0]!!)

Essayez-le en ligne!

Comment ça marche: commencez [0]et appliquez la x ++ invert xfonctionn fois. Prenez les premiers néléments de la liste résultante. Grâce à la paresse de Haskell, seuls les premiers néléments sont réellement calculés. Remarque: le premier <*>est en contexte de fonction, le second en contexte de liste.

Avec GHC v8.4 (qui n'était pas disponible au moment du défi), il existe une solution à 34 octets:

take<*>(iterate(id<>map(1-))[0]!!)

Modifier: -3 resp. -4 octets grâce à @Laikoni. -1 octet grâce à @ Ørjan Johansen.

Haskell, 54 octets

Moins compact que la solution de nimi, mais je ne voulais pas vous refuser ce brouillage du code fonctionnel. Fonctionne pour n'importe quelle paire d'objets; par exemple, vous pouvez remplacer (f 0.f 1)par(f 'A'.f 'B') .

Basé sur la définition que les 2 premiers ⁿ chiffres sont suivis de la même séquence de chiffres inversés. Ce que nous faisons, c'est construire deux listes côte à côte; un pour la séquence, un pour l'inverse. Nous ajoutons continuellement des parties de plus en plus longues d'une liste à l'autre.

L'implémentation se compose de trois définitions:

t=(f 0.f 1)t
f c=flip take.(c:).g 1
g n l=l n++g(n+n)l

La fonction taccepte n'importe quel nombre et renvoie la séquence Thue-Morse de cette longueur. Les deux autres fonctions sont des aides.

• La fonction freprésente l'une ou l'autre liste; f 0est pour la séquence,f 1 pour l'inverse.
• La fonction gse charge d'ajouter des répétitions de plus en plus longues d'une liste à l'autre.

Violon: http://goo.gl/wjk9S0

Pari / GP , 33 octets

n->[sumdigits(x,2)%2|x<-[0..n-1]]

Essayez-le en ligne!

Burlesque, 21 octets

{0}{J)n!_+}400E!jri.+

Exemples:

blsq ) "20"{0}{J)n!_+}400E!jri.+
{0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 1 0 0 1}
blsq ) "42"{0}{J)n!_+}400E!jri.+
{0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 1 0 0 1 0 1 1 0 0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 0 1}

Explication:

{0}      -- setup
{J)n!_+} -- duplicate, map invert, concatenate
400E!    -- do 400 times (this will eventually run
            out of memory).
jri.+    -- take n elements

Sans la jri.+partie, vous manquerez de mémoire (car elle calculera la séquence morse de longueur d' un nombre incroyablement énorme ). Mais comme Burlesque est paresseux, le simple fait de demander le premier élément n fonctionnera de toute façon.

K5, 27 13 octets

{x#((log x)%log 2){x,~x}/0}

Calculer la séquence est assez facile, le problème évite de trop calculer. Nous pouvons reconnaître que l'expansion facile de la séquence nous donne une séquence de chaînes qui sont des puissances successives de deux longueurs. Prendre la base de journal 2 de l'entrée et l'arrondir nous donnera suffisamment de travail et nous pourrons ensuite le réduire à la taille appropriée:

  {x#((log x)%log 2){x,~x}/0}'(20 42 37 12 0)
(0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 1 0 0 1
 0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 1 0 0 1 0 1 1 0 0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 0 1
 0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 1 0 0 1 0 1 1 0 0 1 1 0 1 0 0 1 1 0 0 1 0
 0 1 1 0 1 0 0 1 1 0 0 1
 ())

Modifier:

Une solution paritaire:

~=/'(64#2)\'!

En action:

  ~=/'(64#2)\'!20
0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 1 0 0 1

Notez que puisque K5 n'a pas de primitive de conversion arbitraire en binaire, je dois spécifier, par exemple, un décodage 64 bits. K5 n'utilise pas de mathématiques de précision arbitraires, il y aura donc une limite à la taille des entrées que nous pouvons traiter dans tous les cas.

Octave, 33 31 octets

Enregistré 2 octets grâce à Thomas Kwa.

@(n)mod(sum(dec2bin(0:n-1)'),2)

Perl 5, 62 49 octets

Ouais, ce n'est pas la meilleure langue pour celui-ci, mais j'aime toujours la façon dont c'est sorti. Nécessite 5.14+ pour /ret say.

sub{$_=0;$_.=y/01/10/r while$_[0]>length;say substr$_,0,$_[0]}

L'utilisation de la définition de parité nécessite 5.12+ pour say:

sub{say map{sprintf("%b",$_)=~y/1//%2}0..$_[0]-1}

Prolog (SWI), 115 octets

Code:

N*X:-N>1,R is N//2,R*Y,X is(N mod 2)xor Y;X=N.
p(N):-M is N-1,findall(E,between(0,M,E),L),maplist(*,L,K),write(K).

Expliqué:

N*X:-                                 % Calculate Thue-Morse number at index N
     N>1,                             % Input is bigger than 1
     R is N//2,R*Y,X is(N mod 2)xor Y % Thue-Morse digit at index N is binary digits of N xor'ed
     ;X=N.                            % OR set X to N (end of recursion)
p(N):-
      M is N-1,                       % Get index of Nth number
      findall(E,between(0,M,E),L),    % Make a list of number 0->N-1
      maplist(*,L,K),                 % Map * on list L producing K
      write(K).                       % Print K

Exemple:

p(20).
[0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1]

Essayez-le en ligne ici

Rétine , 70 69 octets

Utilisation de la définition comme un L-système avec mot initial 0et productions 0 --> 01et 1 --> 10.

^
0;
(T`d`ab`^(.)+;(?!(?<-1>.)+$)
a
01
)`b
10
!`^(?=.*;(.)+)(?<-1>.)+

L'entrée est prise en unaire .

Vous pouvez exécuter le code à partir d'un seul fichier avec l' -sindicateur. Ou essayez-le simplement en ligne.

Explication

^
0;

Ajoute 0;à l'entrée, où 0est le mot initial et ;n'est qu'un séparateur.

(T`d`ab`^(.)+;(?!(?<-1>.)+$)

Le (indique qu'il s'agit du début d'une boucle (qui se répète jusqu'à ce que la boucle cesse de changer la chaîne). Cette étape elle-même se transforme 0et 1devient aet brespectivement (car se ddéveloppe en 0-9). Il le fait aussi longtemps que le mot actuel (dont la longueur est mesurée avec (.)+est plus court que l'entrée (c'est-à-dire tant que nous ne pouvons pas lire la fin de la chaîne en faisant correspondre autant de 1s que nous en avons dans le mot).

a
01

Remplacez a(remplaçant 0) par 01.

)`b
10

Remplacez b(remplaçant 1) par 10. C'est aussi la fin de la boucle. La boucle se termine une fois que la condition de l'étape de translittération échoue, car alors tous les 0s et 1s resteront inchangés et les deux autres étapes ne trouveront rien à faire correspondre.

!`^(?=.*;(.)+)(?<-1>.)+

La dernière étape consiste à tronquer le mot à la longueur de l'entrée. Cette fois, nous mesurons la longueur de l'entrée avec (.)+dans une anticipation. Ensuite, nous faisons correspondre autant de caractères depuis le début de la chaîne.

Rubis, 33

->n{n.times{|i|p ("%b"%i).sum%2}}

Appelez comme ceci:

f=->n{n.times{|i|p ("%b"%i).sum%2}}
f[16]

Utilise le fait que la parité des nombres binaires forme la séquence thue-morse.

Le caractère séparateur est une nouvelle ligne. Convertit le nombre ien une chaîne binaire, puis calcule la somme de tous les codes ASCII, modulo 2.

Si la nouvelle ligne n'est pas un séparateur acceptable, ce qui suit n'a pas de séparateur pour 2 octets supplémentaires:

->n{n.times{|i|$><<("%b"%i).sum%2}}

MATL , 9 octets

Cette langue a été conçue après le défi .

Approche 1:13 octets

Cela construit la séquence en concaténant des copies négatives de blocs de taille croissante.

itBFw"t~h]w:)

Exemple

>> matl itBFw"t~h]w:)
> 20
0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 1 0 0 1

Explication

i           % input number, say "N"
tB          % duplicate and convert to binary. Produces a vector
F           % initialize sequence to "false"
w           % swap to bring vector to top
"           % for loop. There will be at least log2(N) iterations
  t~h       % duplicate, negate, concatenate
]           % end for
w           % swap
:)          % index with vector 1, 2, ..., N

Approche 2: 9 octets

Cela utilise la même approche que la réponse d'Alephalpha .

i:1-B!s2\

Exemple

>> matl i:1-B!s2\
> 20
0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 1 0 0 1

Explication

i           % input "N" 
:1-         % create vector 0, 1, ..., N-1
B           % convert to binary
!           % tranpose
s           % sum
2\          % modulo 2

C, 88 83 octets

Calcule la parité pour chaque position individuelle.

i,j;main(int c,char**a){for(;i<atoi(a[1]);putchar(c))for(c=48,j=i++;j;j&=j-1)c^=1;}

Violon: http://goo.gl/znxmOk

Gelée , 4 octets

ḶB§Ḃ

Notez que ce défi est plus ancien que Jelly.

Essayez-le en ligne!

Comment ça marche

ḶB§Ḃ  Main link. Argument: n (integer)

Ḷ     Unlength; yield [0, ..., n-1].
 B    Compute the binary representation of each integer in the range.
  §   Take the sum of each binary representation.
   Ḃ  Take the LSB of each sum.

Matlab, 42

J'utilise le fait que c'est la même chose que de commencer par 0, puis de répéter l'étape d'ajout du complément de la série actuelle, nfois.

t=0;for k=1:input('');t=[t;~t];end;disp(t)

𝔼𝕊𝕄𝕚𝕟, 11 caractères / 23 octets (non concurrentiel)

Ⓐïⓜ_ⓑⓢĊ⇀$^_

Try it here (Firefox only).

Les cercles sont forts avec celui-ci.

Bash, 71 66 octets

Sur la base de la définition selon laquelle les 2 premiers ⁿ chiffres sont suivis de la même séquence de chiffres inversés.

x=0;y=1;while((${#x}<$1));do z=$x;x=$x$y;y=$y$z;done;echo ${x::$1}

$1 comme paramètre est le nombre de chiffres souhaité.

Violon: http://goo.gl/RkDZIC

Lot, 115 + 2 = 117 octets

Basé sur la réponse Bash.

@echo off
set x=0
set y=1
set z=0
:a
set x=!x!!y!
set y=!y!!z!
set z=!x:~0,%1!
if !z!==!x! goto a
echo !z!

Nécessite un supplément /Vdans l'invocation pour permettre l'utilisation du par !.

ES6, 53 octets

f=(i,x="0",y=1)=>x.length<i?f(i,x+y,y+x):x.slice(0,i)

La récursivité semblait plus simple qu'une boucle.

Par , 8 octets

✶u[Σ_✶¨^

Explication:

✶          parse implicit input number
 u         range [0..n-1]
  [        map:
   Σ           convert to binary
    _✶         get digit list
      ¨^       fold with xor

Produit quelque chose comme:

(0 1 1 0 1 0 0 1)

Math ++ , 86 octets

Utilise 0.0\npour 0 et 1.0\npour 1

?>n
3*!!(n-m)>$
m>a
0>k
6+6*!a>$
9-2*!(a%2)>$
a/2>a
5>$
(a-1)/2>a
!k>k
5>$
k
m+1>m
2>$

Arcyóu , 50 55 octets

J'ai dû ajouter 5 octets pour que cela fonctionne correctement :(

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

Explication (avec pseudocode Pythonesque sur le côté:

(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

Lisp commun , 50 octets

(lambda(n)(dotimes(i n)(princ(mod(logcount i)2))))

Essayez-le en ligne!