Il s’agit là d’un nouveau défi , qui vise à adapter les exigences d’E / S à nos normes récentes. Ceci est fait dans le but de permettre à plus de langues de participer à un défi concernant cette séquence populaire. Voir ce méta post pour une discussion de la rediffusion.

La séquence de Kolakoski est une séquence amusante auto-référentielle, qui a l'honneur d'être la séquence OEIS A000002 (et beaucoup plus facile à comprendre et à mettre en œuvre que A000001). La séquence commence par 1 , consiste uniquement en 1 s et 2 s et l'élément de séquence a (n) décrit la longueur du n- ième passage de 1 s ou 2 s dans la séquence. Ceci définit de manière unique la séquence à être (avec une visualisation des parcours en dessous):

1,2,2,1,1,2,1,2,2,1,2,2,1,1,2,1,1,2,2,1,2,1,1,2,1,2,2,1,1,2,1,1,2,...
= === === = = === = === === = === === = = === = = === === = === =
1, 2,  2, 1,1, 2, 1, 2,  2, 1, 2,  2, 1,1, 2, 1,1, 2,  2, 1, 2, 1,...

Votre tâche consiste bien entendu à mettre en œuvre cette séquence. Vous pouvez choisir l’un des trois formats suivants:

1. Prenez une entrée n et sortez le n- ième terme de la séquence, n commençant à 0 ou à 1 .
2. Prendre une entrée n et délivrer en sortie les termes jusqu'à et y compris le n ième terme de la séquence, où n commence soit de 0 ou 1 ( à savoir , soit imprimer la première n ou le premier n + 1 termes).
3. Afficher les valeurs de la séquence indéfiniment.

Dans les deuxième et troisième cas, vous pouvez choisir n’importe quel format de liste raisonnable et non ambigu. C'est bien s'il n'y a pas de séparateur entre les éléments, car ils sont toujours un seul chiffre par définition.

Dans le troisième cas, si votre soumission est une fonction, vous pouvez également renvoyer une liste infinie ou un générateur dans les langues qui les prennent en charge.

Vous pouvez écrire un programme ou une fonction et utiliser n’importe laquelle de nos méthodes standard de réception d’entrée et de sortie. Notez que ces failles sont interdites par défaut.

C'est du code-golf , donc la réponse valide la plus courte - mesurée en octets - est gagnante.

Gelée , 7 octets

2Rṁxṁµ¡

C'est un programme complet qui imprime les n premiers termes.

Essayez-le en ligne!

Comment ça fonctionne

2Rṁxṁµ¡  Main link. Argument: n (integer)

     µ   Combine the preceding links into a monadic chain.
      ¡  Set t = n.  Call the chain n times, updating t with the return value after
         each call. Yield the last value of t.
2R           Set the return value to 2 and take its range. Yields [1, 2].
  ṁ          Mold; cyclically repeat 1 and 2 to match t's length.
             In the first run, ṁ promotes t = n to [1, ..., n].
   x         Repeat the k-th element of the result t[k] times.
             In the first run, x repeats each element t = n times.
    ṁ        Mold; truncate the result to match the length of t.
             In the first run, ṁ promotes t = n to [1, ..., n].                 

Exemple d'exécution

Soit n = 5 .

La première invocation de la chaîne se répète 1, 2 de manière cyclique pour atteindre la longueur 5 , puis chaque élément 5 fois, et finalement tronque le résultat à la longueur 5 .

  1         2         1         2         1
x 5         5         5         5         5
---------------------------------------------------
  1 1 1 1 1 2 2 2 2 2 1 1 1 1 1 2 2 2 2 2 1 1 1 1 1

  1 1 1 1 1

Cela donne une liste de longueur 5 . Le premier élément est le premier élément de la séquence de Kolakoski.

La deuxième invocation de la chaîne se répète 1, 2 de manière cyclique pour atteindre la longueur 5 , puis répète le k ^ème élément j fois, où j est le k ^ème élément de la liste précédente et tronque finalement le résultat à la longueur 5 .

   1 2 1 2 1
x  1 1 1 1 1
------------
   1 2 1 2 1

   1 2 1 2 1

Cela donne une autre liste de longueur 5 . Les deux premiers éléments sont les deux premiers éléments de la séquence de Kolakoski.

Le processus se poursuit pendant trois autres itérations.

   1 2   1 2   1
x  1 2   1 2   1
----------------
   1 2 2 1 2 2 1

   1 2 2 1 2

   1 2   1   2 1
x  1 2   2   1 2
------------------
   1 2 2 1 1 2 1 1

   1 2 2 1 1

   1 2   1   2 1
x  1 2   2   1 1
----------------
   1 2 2 1 1 2 1

   1 2 2 1 1

Ce sont les cinq premiers éléments de la séquence de Kolakoski.

Python 2 , 51 octets

l=[2]
print 1,2,
for x in l:print x,;l+=x*[l[-1]^3]

Imprime indéfiniment. Construit la liste au lfur et à mesure de son itération. Pour chaque entrée xde l, ajoute des xcopies de 1ou 2, selon ce qui est opposé au dernier élément actuel.

La principale difficulté concerne le fragment auto-référentiel initial [1,2,2]. Ce code n'imprime que l'initiale 1,2et procède de là. L'impression supplémentaire coûte 12 octets. Sans ça:

39 octets , deux premières entrées manquantes:

l=[2]
for x in l:print x;l+=x*[l[-1]^3]

Une autre approche consiste à initialiser spécialement les deux premières entrées. Nous initialisons lde [0,0,2]manière à ce que les deux premières entrées ne provoquent pas d’ajout, mais print x or nsoient imprimées comme n.

51 octets

l=[0,0,2]
n=1
for x in l:print x or n;l+=x*[n];n^=3

Une autre solution consiste à initialiser l=[1], suivre l’alternance manuellement net corriger l’impression:

51 octets

n,=l=[1]
for x in l:print(l==[1,1])+x;l+=x*[n];n^=3

Sans le (l==[1,1])+, tout fonctionne sauf les séquences imprimées qui commencent 1,1,2au lieu de 1,2,2. Il doit y avoir un meilleur moyen de reconnaître que nous en sommes à la deuxième étape.

Et un autre correctif étrange, également le même nombre d'octets:

51 octets

l=[1];q=2
for x in l:print x;l+=x*[l[-1]^3]*q;q=q<2

Wumpus , 13 à 11 octets

=[=)O?=!00.

Essayez-le en ligne!

Imprime la séquence indéfiniment sans séparateurs.

Je suis vraiment surpris par la brièveté de la situation.

Explication

L'idée de base est de conserver la séquence sur la pile et d'utiliser à plusieurs reprises l'élément le plus en bas pour générer une autre exécution, puis l'imprimer. Nous abusons effectivement de la pile comme une file d'attente ici. Nous pouvons également enregistrer quelques octets en travaillant 0et 1(en incrémentant uniquement pour la sortie) au lieu de 1et 2, car nous n'avons ainsi pas besoin d'initialiser explicitement la pile avec un 1et nous pouvons utiliser la négation logique pour basculer entre les deux valeurs.

     The entire program is run in a loop.
     At the beginning of loop iteration i, a(i)-1 will be at the bottom of the
     stack and the first element of the ith run of values will be on top.
     The caveat is that on the first iteration, the stack is empty, but
     popping from an empty stack produces an implicit zero.
=    Duplicate the top of the stack. Since this is defined as "pop x, push
     x, push x" this will result in 2 zeros when the stack is empty.
     After this we've got two copies of the ith run's value on top of the stack.
[    Pull up a(i)-1 from the bottom of the stack.
=)O  Duplicate, increment to a(i) and print it.
?=   If a(i)-1 is 1 (as opposed to 0), make another copy of the top of the
     stack. We've now got a(i)+1 copies, so one more than the run should be 
     long, but that's great because we can use the additional copy to get 
     the start of the next run.
!    Logical negation which swaps 0 and 1.
00.  Jump back to the beginning of the program.

Brachylog , 30 26 25 23 17 16 14 octets

~a₀{1|2}ᵐḅlᵐ?l

Affiche les n premières valeurs. Utilise la "variable de sortie" .pour l'entrée et génère la "variable d'entrée" ?. Essayez-le en ligne!

Explication

Je suis assez satisfait du résultat déclaratif: le programme est en gros une description de haut niveau de la liste de sortie et de sa relation avec l'entrée.

~a₀{1|2}ᵐḅlᵐ?l  Input is a number N.
                Output is a term that I'll call T.
~a₀             T is a prefix of a list L.
   {   }ᵐ       Each element of L
    1|2         is either 1 or 2.
         ḅ      If you cut L into blocks of equal elements
          lᵐ    and take the length of each block,
            ?   the result is T.
             l  The length of T is N.

Étant donné {1|2}ᵐque les listes d'essais sont répertoriées dans l'ordre lexicographique, la sortie commence par 1.

Coque , 10 octets

Ṡωo↑⁰`Ṙ¢ḣ2

Retourne les n premières valeurs. Essayez-le en ligne!

Explication

Ṡωo↑⁰`Ṙ¢ḣ2  Input is an integer N.
        ḣ2  The range [1,2]
       ¢    Cycle: C = [1,2,1,2,1,2...
 ω          Iterate until fixed point is found:
Ṡ    `Ṙ      Replicate the list C element-wise according to the current list,
  o↑⁰        then take first N elements.

Pour l'entrée 20, le processus se déroule comme suit:

[1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2...
[1,2,2,1,2,2,1,2,2,1,2,2,1,2,2,1,2,2,1,2]
[1,2,2,1,1,2,1,1,2,2,1,2,2,1,1,2,1,1,2,2]
[1,2,2,1,1,2,1,2,2,1,2,1,1,2,2,1,2,2,1,1]
[1,2,2,1,1,2,1,2,2,1,2,2,1,1,2,1,1,2,1,2]
[1,2,2,1,1,2,1,2,2,1,2,2,1,1,2,1,1,2,2,1]
[1,2,2,1,1,2,1,2,2,1,2,2,1,1,2,1,1,2,2,1]

Java 10, 155 108 105 100 97 octets

v->{var s="122";for(int i=1;;s+=(1+i%2)*(s.charAt(i)>49?11:1))System.out.print(s.charAt(++i-2));}

Imprime indéfiniment sans délimiteur.

-3 octets après un conseil indirect de @Neil .
-5 octets grâce à @MartinEnder .
-3 octets convertissant Java 8 en Java 10.

Explication:

Essayez-le en ligne (expire après 60 secondes sur TIO).

v->{              // Method with empty unused parameter and no return-type
  var s="122";    //  String, starting at "122"
  for(int i=1;;   //  Loop `i` from 1 upwards indefinitely
      s+=         //    After every iteration: Append the String with:
         (1+i%2)  //     1+`i`modulo-2
         *(s.charAt(i)>49?11:1))
                  //     either once or twice depending on the digit at index `i`
    System.out.print(s.charAt(++i-2));}
                  //   Print the character at index `i-2` of the String
                  //   After we've first increased `i` by 1 with `++i`

Gelée , 10 octets

’߀+\<¹SḂ‘

Retourne le n ^ème terme.

Essayez-le en ligne!

Comment ça fonctionne

’߀+\<¹SḂ‘  Main link. Argument: n (positive integer)

’           Decrement; yield n-1.
 ߀         Recursively map the main link over [1, ..., n-1].
   +\       Take the cumulative sum.
            The k-th sum is the combined length of the first k runs.
     <¹     Compare each sum with n.
       S    Sum the Booleans.
            This counts the number of runs that occur before the n-th term.
            If there's an even number (including 0) of runs, the n-th term is 1.
            If there's an odd number of runs, the n-th term is 2.
        Ḃ   Extract the least significant bit of the count.
         ‘  Increment.

Haskell , 33 octets

r=r%1
~(x:t)%n=n:[n|x>1]++t%(3-n)

Essayez-le en ligne!

Ørjan Johansen a économisé 7 octets en utilisant un motif irréfutable pour forcer le préfixe.

Gol> <> , 8 7 octets

:{:PnKz

Essayez-le en ligne!

Explication

Ceci est un port de ma réponse Wumpus . Gol> <> est fondamentalement le langage qui possède toutes les fonctionnalités nécessaires pour porter la réponse Wumpus (spécifiquement, des zéros implicites au bas de la pile, "dupliqué" implémenté "Pop, push, push" et une commande de rotation de pile), mais :

• Il possède une grille toroïdale, ce qui signifie que nous n’avons pas besoin de l’explicite 00.pour revenir au début.
• Il a K, qui est "pop N, puis dupliquer le prochain élément N fois", qui peut remplacer ?=, en sauvegardant un autre octet.

Ainsi, la cartographie de Wumpus à Gol> <> devient:

Wumpus   Gol><>
=        :
[        {
=        :
)        P
O        n
?=       K
!        z
00.

Shakespeare Programming Language , 594 583 572 octets

Merci à Ed Wynn pour -10 octets!

,.Ford,.Puck,.Act I:.Scene I:.[Enter Ford and Puck]Ford:You cat!Open heart!You big cat!Open heart!Puck:Remember you!Remember me!Scene V:.Ford:You is the sum ofI a cat!Puck:Recall!Open heart!Ford:Remember a pig!Is I nicer a cat?If notyou be the sum ofyou a big pig!Scene X:.Puck:Recall!Ford:Is I nicer zero?If soremember I!If solet usScene X!Puck:Is I nicer zero?You is the sum ofI a big cat!If soyou is I!Remember zero!Remember I!Remember you!You be the difference betweena big cat you!Scene L:.Ford:Recall!Is you worse I?If so,let usScene V!Puck:Remember I!Let usScene L!

Essayez-le en ligne!

Il s’agit d’une version de la solution ungolfée d’ Ed Wynn qui a débuté à partir de la solution de 828 octets qu’il a liée dans les commentaires pour ensuite devenir un peu cinglée.

Explication:

,.Ford,.Puck,.Act I:.Scene I:.[Enter Ford and Puck]    Boilerplate, introducing the characters
Ford:You cat!Open heart!You big cat!Open heart!  Print 1,2 as the first two terms of the sequence

Puck:Remember you!Remember me!  Initialise stack as 0, 2
                                Ford's value is currently 0, representing the value to be pushed to the stack

Scene V:.     Start infinite loop
  Ford:You is the sum ofI a cat!         
  Puck:Recall!Open heart!                 Pop the next value in the stack and print it
  Ford:Remember a pig!                    Push -1 as the end of the stack
  Is I nicer a cat?                       If Ford's value is 2
  If notyou be the sum ofyou a big pig! Subtract 2 from Puck's value to represent making 2 only one copy

        #Reverse the stack until it reaches the terminator value 0 or -1
  Scene X:.Puck:Recall!Ford:Is I nicer zero?If soremember I!If solet usScene X!

  Puck:Is I nicer zero?                          Check if the Puck's value is bigger than 0 (only making one copy)
  You is the sum of Ia big cat!                 Set Ford's value to Puck+2 to counter the change
  If soyou is I!                                But undo it if making one copies
  Remember zero!                                 Push 0 as the stack terminator
  Remember I!                                    Push Ford's value, which is 0 or -1 if this is a single copy, or 1 or 2 for a double copy
  Remember you!                                  Push one copy of Puck's value
  You be the difference betweena big cat you!   Map Ford's value from 1,2 to 1,0

  Scene L:.   #Reverse the stack until it reaches the terminator 0 
     Ford:Recall!Is you worse I?If solet us Scene V!
     Puck:Remember I!Let usScene L!

> <> , 13 12 octets

0:{:1+n?:0=!

Essayez-le en ligne!

Une réponse du port Wumpus de Martin Ender . Malheureusement, il ><>n’ya pas de commande d’incrémentation ou d’inversion ni de 0 implicite au bas de la pile, ce qui le rend un peu plus long.

JavaScript, 67 66 60 58 52 51 50 octets

Eh bien, mon cerveau me démangeait plus qu'il ne l'aurait dû! Retire le thème nterme, indexé par 0.

s=`122`
x=1
f=n=>s[n]||f(n,s+=s[++x%2]*(s[x]+0-9))

5 + 1 octets sauvés grâce à tsh grattant mon cerveau qui pique!

Essaye-le

L'extrait ci-dessous affichera les 50 premiers termes.

s=`122`
x=1
f=n=>s[n]||f(n,s+=s[++x%2]*(s[x]+0-9))
o.innerText=[...Array(50).keys()].map(f).join`, `

<pre id=o></pre>

Explication

C’est l’une des rares occasions où nous pouvons déclarer certaines variables en dehors du champ de notre fonction, les modifier au sein de la fonction et pouvoir toujours les réutiliser lors d’appels ultérieurs de la fonction.

s=`122`       :Initialise variable s as the string "122"
x=1           :Initialise variable x as integer 1
f=n=>         :Named function f taking input as an argument through parameter n
 s[n]         :If s has a character at index n, return it and exit
 ||           :Or
 f(n          :Call f with n again
  ,s+=        :At the same time, append to s
  s[++x%2]    :  Increment x, modulo by 2 and get the character at that index in s
  *           :  Multiplied by (the above gets cast to an integer)
  (s[x]+0-9)  :  Append a 0 to the xth character of s and subtract 9
 )            :  (The above gives "1"+0-9="10"-9=1 or "2"+0-9="20"-9=11)

Python (2 et 3), 65 à 60 octets

f=lambda n:sum([f(i)*[i%2+1]for i in range(2,n)],[1,2,2])[n]

Renvoie la n ième entrée, 0-indexé.

Alternative (65 octets):

f=lambda n:n>1and sum([f(i)*[i%2+1]for i in range(n)],[])[n]or-~n

Haskell , 48 octets

-1 octet grâce à nimi. -2 octets grâce à Lynn.

c=1:2:c
l=1:2:drop 2(id=<<zipWith replicate l c)

Essayez-le en ligne!

Répétez chaque élément sa position mod 2 + 1 fois.

brainfuck , 61 octets

+.+.[.[>]>+++>+++<<<[->+>->-<<<]<[[->+<]<]>>--[[>]<,<[<]>+]>]

Essayez-le en ligne!

Imprime les nombres comme codes de caractères indéfiniment. Pour plus de clarté, voici une version imprimée en chiffres (à l’exception des deux premiers éléments, qui sont assez faciles à vérifier).

Comment ça fonctionne:

+.+. Prints the first two elements. These are the self-referential elements
     This also intitialises the tape with the third element, 2
[ Start infinite loop
   . Print current lowest element
   [>]>+++>+++ Move to end of tape and create two 3s
   <<<[->+>->-<<<] Subtract the last element of the tape from these 3s
   <[[->+<]<]>> Move to the beginning of the tape
   --  Subtract two from the first element
       This leaves 2 as 0 and 1 as -1
   [ If the number was 1
     [>]<,  Delete the excess element from the end of the tape
     <[<]>+ Remove the -1
   ]
   > Move to the next element of the list
]

05AB1E , 12 à 9 octets

3 octets sauvés grâce à Grimy

Imprime les n premiers éléments.

Δ2LÞsÅΓI∍

Essayez-le en ligne!

Explication

Δ           # repeat until ToS doesn't change
 2LÞ        # push [1,2,1,2 ...]               
    sÅΓ     # run-length encode with previous value (initially input)
       I∍   # extend/shorten to the length specified by input

05AB1E , 15 octets

ƵLS[DNÌ©èF®É>¸«

Essayez-le en ligne! ou avec une limite d'itération

Explication

ƵLS               # push our initial list [1,2,2]
   [              # for every N in [0 ...
    D             # duplicate current list of numbers
     NÌ©è         # get the N+2'th element from the list
         F        # that many times do
          ®É>     # push ((N+2)%2==1)+1
             ¸«   # append to current list

Python 3 , 55 54 octets

n=h=1;l=[]
while n:print(h);n^=3;h,*l=l+[n]*(l+[2])[0]

Essayez-le en ligne!

J , 12 octets

Fonction à un seul argument prenant n et produisant les n premiers termes. Essayez-le en ligne!

$(1+2|I.)^:]

Je viens d’améliorer ma vieille réponse à la vieille question.

I.est un verbe qui prend un tableau de nombres et crée une liste d’index, de sorte que si le k- ème élément du tableau est n , l’indice k apparaît n fois. Nous allons l'utiliser pour amorcer la séquence de Kolakowski à partir d'une graine initiale. Chaque étape se déroulera comme suit:

1 2   2   1 1 2   1 2   2   1   (some prefix)
0 1 1 2 2 3 4 5 5 6 7 7 8 8 9   (use I.)
0 1 1 0 0 1 0 1 1 0 1 1 0 0 1   (mod 2)
1 2 2 1 1 2 1 2 2 1 2 2 1 1 2   (add 1) 

Si nous effectuons cette opération ( 1+2|I.) encore et encore à partir de 10, cela ressemble à ceci:

10
1 1 1 1 1 1 1 1 1 1
1 2 1 2 1 2 1 2 1 2
1 2 2 1 2 2 1 2 2 1 2 2 1 2 2
1 2 2 1 1 2 1 1 2 2 1 2 2 1 1 ...
1 2 2 1 1 2 1 2 2 1 2 1 1 2 2 ...
1 2 2 1 1 2 1 2 2 1 2 2 1 1 2 ...

Remarquez comment nous obtenons de plus en plus de termes corrects, et après un certain temps, les n premiers termes sont corrigés. Il est difficile de décrire avec précision le nombre d'itérations nécessaires pour s'installer, mais il semble être approximativement logarithmique en n , donc si nous l'exécutons n fois ( ^:]), tout devrait bien se passer. (Consultez ces autres séquences OEIS pour plus d'informations: longueurs de génération , sommes partielles .)

Une fois cela fait, tout ce que nous avons à faire est d’utiliser les n premiers termes $. La construction $vde n'importe quel verbe vest un exemple de crochet, et le donner ncomme argument s'exécutera n $ (v n).

Voici l'ancienne version 13 octets qui est beaucoup moins de gaspillage de temps et de l' espace: ($1+2|I.)^:_~. Elle tronque l'entrée à chaque étape, ce qui permet d'exécuter autant de fois que nécessaire pour régler, au lieu de procéder de manière linéaire plusieurs fois.

Fueue , 30 octets

Fueue est un esolang basé sur une file d'attente dans lequel le programme en cours et ses données sont tous deux dans la même file d'attente. L'exécution s'effectue tour à tour par la file d'attente et la programmation nécessite beaucoup de synchronisation pour empêcher toute exécution au mauvais moment.

1)2:[[2:])~)~:~[[1]:~))~:~~]~]

Essayez-le en ligne!

Ce qui précède imprime une liste interminable de chiffres sous forme de codes de contrôle. Pour 34 octets, il peut imprimer les chiffres réels:

49)50:[[50:])~)~:~[[49]:~))~:~~]~]

Essayez-le en ligne!

Le reste de l'explication utilise la dernière version.

Résumé des éléments de la Fueue

La file d'attente Fueue peut contenir les types d'éléments suivants:

• Entiers, qui impriment leur code codé Unicode lorsqu’ils sont exécutés,
• Des blocs de sous-programme délimités par des crochets, qui sont heureusement inactifs (juste en train de passer à la fin de la file), à ​​moins que la )fonction ne les débloque , et
• Fonctions à caractère unique, qui s'exécutent si elles sont suivies du type d'argument correct et restent inactives.
  • Les seules fonctions utilisées dans ce programme sont ~(permuter deux éléments suivants), :(dupliquer l’élément suivant) et )(débloquer le bloc suivant).

Vue d'ensemble de haut niveau

Pendant la boucle principale du programme, la file d'attente est composée de:

• une chaîne de blocs représentant des chiffres à parcourir;
  • Un chiffre 1 ou 2 est représenté par les blocs [49]et [50:], respectivement.
• une section de boucle principale auto-répliquée qui traverse les blocs de chiffres et place une alternance de 1 et de 2 après eux, puis les débloque.
  • Un bloc de chiffres débloqué imprime son propre chiffre d , puis crée d copies du bloc suivant, créant ainsi les chiffres pour l'exécution qu'il décrit.

Trace de bas niveau des 10 premières commandes

Cmds   Explanation              Queue
49     Print '1'.               )50:[[50:])~)~:~[[49]:~))~:~~]~]
)      Inactive, move to end.   50:[[50:])~)~:~[[49]:~))~:~~]~])
50     Print '2'.               :[[50:])~)~:~[[49]:~))~:~~]~])
:[...] Duplicate block.         )[[50:])~)~:~[[49]:~))~:~~]~][[50:])~)~:~[[49]:~))~:~~]~]
)[...] Deblock (rmv. brackets). [[50:])~)~:~[[49]:~))~:~~]~][50:])~)~:~[[49]:~))~:~~]~
[...]  Inactive.                [50:])~)~:~[[49]:~))~:~~]~[[50:])~)~:~[[49]:~))~:~~]~]
[50:]  Inactive.                )~)~:~[[49]:~))~:~~]~[[50:])~)~:~[[49]:~))~:~~]~][50:]
)      Inactive.                ~)~:~[[49]:~))~:~~]~[[50:])~)~:~[[49]:~))~:~~]~][50:])
~)~    Swap ) and ~.            :~[[49]:~))~:~~]~[[50:])~)~:~[[49]:~))~:~~]~][50:])~)
:~     Duplicate ~.             [[49]:~))~:~~]~[[50:])~)~:~[[49]:~))~:~~]~][50:])~)~~

Procédure pas à pas d'une itération de boucle principale complète

Un espace facultatif a été inséré pour séparer les commandes.

49 ) 50 :[[50:])~)~:~[[49]:~))~:~~]~]

Cycle 1: 49impressions 1. )est inactif, en attente d'être rapproché du bloc de la boucle principale. 50impressions 2. :duplique le bloc de boucle principal (qui nécessite une copie pour l'auto-réplication).

) [[50:])~)~:~[[49]:~))~:~~]~] [[50:])~)~:~[[49]:~))~:~~]~]

Cycle 2: )débloque le premier bloc de la boucle principale pour qu’il commence à exécuter le cycle suivant.

[50:] ) ~)~ :~ [[49]:~))~:~~] ~[[50:])~)~:~[[49]:~))~:~~]~]

Cycle 3: [50:]représente le premier chiffre produit dans la chaîne, 2non débloqué. Ce qui suit )finira par le faire après que le reste de la boucle principale l'aura parcourue. ~)~:~est un golfé (en utilisant un échange et une copie) un délai d’un cycle de ~)~~. [[49]:~))~:~~]est inactif. ~permute le bloc de boucle principale suivant au-delà du [50:]bloc de chiffres.

) ~)~ ~[[49]:~))~:~~][50:] [[50:])~)~:~[[49]:~))~:~~]~]

Cycle 4: )attend encore, ~)~produit ~), ~swaps [[49]:~))~:~~]passé le [50:]bloc de chiffres.

) ~)[50:] [[49]:~))~:~~] [[50:])~)~:~[[49]:~))~:~~]~]

Cycle 5: ~swaps )passé le [50:]bloc de chiffres.

)[50:] )[[49]:~))~:~~] [[50:])~)~:~[[49]:~))~:~~]~]

Cycle 6: Le premier )débloque maintenant le [50:]bloc de chiffres, le suivant )débloque le sous-programme [[49]:~))~:~~].

50 :[49] :~ ) ) ~:~ ~[[50:])~)~:~[[49]:~))~:~~]~]

Cycle 7: 50imprime 2, :duplique le [49]bloc de chiffres qui vient d'être produit , créant ainsi une série de deux 1secondes. :~))~:~est un délai d'un cycle de ~~))~:. ~permute le bloc de boucle principale restant après le premier [49].

[49] ~~) ) ~:[49] [[50:])~)~:~[[49]:~))~:~~]~]

Cycle 8: ~~))est un délai d'un cycle de )~). ~swaps :passé l'heure actuelle traversée [49].

[49] ) ~)[49] :[[50:])~)~:~[[49]:~))~:~~]~]

Cycle 9: ~swaps )passé [49]. :duplique le bloc de la boucle principale.

[49] )[49] )[[50:])~)~:~[[49]:~))~:~~]~] [[50:])~)~:~[[49]:~))~:~~]~]

Cycle 10: Le premier )débloque le [49]bloc de chiffres qui vient d’être traversé, le second )redémarre la boucle principale pour parcourir la suivante (voir ci-dessus au début de la file d’attente).

x86, 41 37 35 33 28 octets

J'ai eu beaucoup de plaisir à déconner avec différentes instructions x86, car il s'agit de ma première réponse x86 "non triviale". En fait, j’ai d’abord appris les x86-64 et j’ai économisé de nombreux octets en convertissant mon programme au format 32 bits.

Il s’avère que l’algorithme que j’ai utilisé chez OEIS pousse les valeurs dans un tableau, ce qui le rend disponible pour x86 et le stockage des valeurs sur la pile (notez que MIPS n’a pas d’instructions de pile).

Actuellement, le programme prend des Nvaleurs en entrée ecxet renvoie une adresse dans ebpun tableau avec le nième élément représentant la nième valeur de la séquence. Je suppose que le retour sur la pile et le calcul des valeurs supplémentaires sont valables (nous considérons quand même ce qui est au-delà du tableau comme une ordure).

Changelog

• -4 octets en calculant x = 2 - n%2à xorchaque itération

• -2 octets en utilisant la boucle do-while au lieu de while.

• -2 octets en poussant les valeurs initiales 1, 2, 2 en utilisant eax

• -5 octets en ne stockant pas nexplicitement mais en exécutant des Ntemps de boucle

.section .text
.globl main
main:
        mov     $10, %ecx           # N = 10 

start:
        mov     %esp, %ebp          # Save sp
        push    $1
        push    $2                  # x = 2
        pop     %eax       
        push    %eax                # push 2
        push    %eax                # push 2
        mov     %esp, %esi          # sn = stack+3 addr

loop:                               
        xor     $3, %al             # flip x between 1 <-> 2 
        push    %eax                # push x      
                                    # maybe use jump by parity?
        cmp     $2, (%esi)          # if *sn == 2 
        jne     loop1
        push    %eax                # push x

loop1: 
        sub     $4, %esi            # sn += 1
        loop    loop                # --N, do while (N)
end:
        mov     %ebp, %esp          # Restore sp
        ret

Objdump:

00000005 <start>:
   5:   89 e5                   mov    %esp,%ebp
   7:   6a 01                   push   $0x1
   9:   6a 02                   push   $0x2
   b:   58                      pop    %eax
   c:   50                      push   %eax
   d:   50                      push   %eax
   e:   89 e6                   mov    %esp,%esi

00000010 <loop>:
  10:   34 03                   xor    $0x3,%al
  12:   50                      push   %eax
  13:   83 3e 02                cmpl   $0x2,(%esi)
  16:   75 01                   jne    19 <loop1>
  18:   50                      push   %eax

00000019 <loop1>:
  19:   83 ee 04                sub    $0x4,%esi
  1c:   e2 f2                   loop   10 <loop>

0000001e <end>:
  1e:   89 ec                   mov    %ebp,%esp
  20:   c3                      ret 

C (gcc) , 72 71 65 64 62 octets

-9 octets grâce à @ceilingcat

x,y;f(z){for(x=y=-1;putchar(49-~x%2);y=-~y|z&x/2)x^=z=y&~-~y;}

Essayez-le en ligne!

Génère des valeurs de la séquence indéfiniment (option 3 du challenge)

Perl 5 , 36 octets

Encore une modification triviale de la solution classique TPR (0,3):

Affiche les séries de 0àn

#!/usr/bin/perl
use 5.10.0;
say$_=($n+=!--$_[$n])%2+1for@_=0..<>

Essayez-le en ligne!

Javascript ES6 - 71 70 68 octets

(_="122")=>{for(x=1;;_+=(1+x%2)*(_[x]>1?11:1))console.log(_[++x-2])}

1 bit sauvé grâce à Neil

Tanks to Shaggy pour avoir corrigé mon erreur, également pour avoir économisé 1 bit.

f = (_="122") => {
  for(x=1;x<20;_+=(1+x%2)*(_[x]>1?11:1))
    document.getElementById('content').innerHTML += '   ' + _[++x-2]
}
f()

<div id="content"></div>

Appleseed , 89 octets

(def K(lambda()(concat(q(1 2))(drop 2(flatten(zip-with repeat-val(cycle(q(1 2)))(K)))))))

Définit une fonction Kqui ne prend aucun argument et retourne la séquence de Kolakoski sous forme de liste infinie.Essayez-le en ligne!

Cette approche a été inspirée par la réponse de Haskell de totalementhuman . Mon approche originale était plus longue et était probablement O (2 ^ n). : ^ P

Ungolfed

(def kolakoski
 (lambda ()
  (concat (list 1 2)
   (drop 2
    (flatten
     (zip-with repeat-val
      (cycle (list 1 2))
      (kolakoski)))))))

La liste de retour commence par (1 2). Après cela, pour générer le reste (en lisant de l'intérieur):

• Appel récursivement (kolakoski)pour obtenir la liste de séquences de Kolakoski (en raison d'une évaluation paresseuse, peu importe que la liste n'ait pas encore été générée)
• (cycle (list 1 2)) crée une liste infinie (1 2 1 2 1 2 ...)
• Compressez les deux listes infinies en utilisant la fonction repeat-val. Cela répétera le 1ou 2de la cycleliste une ou deux fois en fonction de la valeur associée dans la liste Kolakoski. Résultat:((1) (2 2) (1 1) ...)
• flatten cette liste dans (1 2 2 1 1 ...)
• Nous avons déjà les deux premiers termes de (concat (list 1 2), donc nous avons droples deux premiers de la liste générée pour éviter les doublons.

Stax , 12 octets

╦╥2Bïß▄n»-[╒

Exécuter et déboguer

Ceci est la représentation ascii du même programme.

G@}2R;D{|;^]*m$

Il étend la séquence x fois, où x est l'entrée. Ensuite, il sort le ^xième élément, indexé par 0.

G }             G jumps to trailing } and returns when done
 @              get xth element in array
   2R           [1, 2]
     ;D         repeat the rest x times
       {     m  map array using block
        |;^]    produces [1] and [2] alternately
            *   repeat array specified number of times
              $ flatten array

Voici une solution bonus de 12 octets qui produit une sortie sous forme de flux infini. Appuyez sur Run pour commencer.

R, 63 octets ou 61 octets

Mise en œuvre 1: imprime le n ^ième terme de la séquence.

x=scan()
a=c(1,2,2)
for(n in 3:x)a=c(a,rep(2-n%%2,a[n]))
a[x]

Mise en œuvre 2: affiche les n premiers termes de la séquence.

x=scan()
a=c(1,2,2)
for(n in 3:x)a=c(a,rep(2-n%%2,a[n]))
a[1:x]

(La différence est seulement dans la dernière ligne.)

Oui, oui, vous pouvez vous plaindre que ma solution est inefficace, qu'elle calcule vraiment plus de termes que nécessaire, mais quand même ...

Mise à jour: Merci à @Giuseppe pour avoir réduit de 9 octets.

Shakespeare Programming Language, 575 octets (mais défectueux) ou 653 ou 623 octets

,.Puck,.Ford,.Act I:.Scene X:.[Enter Puck and Ford]Ford:You big cat!Scene L:.Ford:Is I nicer zero?If so,let us Scene V.Is you nicer a big cat?If so,you is the sum of you a big lie.If so,open heart!Open heart!Scene M:.Puck:Remember you!Is I nicer a cat?You big cat.If so,you cat.Ford:Recall!Is you nicer zero?If not,let us Scene X.Is you nicer a big cat?If not,let us Scene M.You is the sum of you a big lie.Scene V:.Ford:Remember you!Is you worse a big big cat?If not, you big cat.Is you as big as a big cat?If not,you zero.You is the sum of I you.Puck:Recall!Let us Scene L.

Dans la catégorie SPL, très disputée, cela battrait l'entrée actuelle de Jo King (583 octets), sauf qu'elle est défectueuse: tout d'abord, elle ne fonctionne pas dans la version TIO (implémentation du site Web SPL) - mais elle fonctionne dans le Perl version , alors peut-être que ce n'est pas un défaut grave. Deuxièmement, les deux premiers chiffres ne sont pas imprimés. Si nous admettions ce défaut dans la solution de Jo King, cette solution défectueuse aurait une longueur de 553 octets, ce qui est supérieur à ma solution défectueuse.

Ma solution échoue sous TIO pour deux raisons: nous essayons de nous baser sur une pile vide qui renvoie zéro quand elle est sautée; et nous passons à la première scène, avec "[Enter Ford and Puck]" même si personne n’a quitté la scène. Ce ne sont que des avertissements dans la version Perl. Si je corrige ces erreurs et que je mets les deux premiers chiffres, j'atteins 653 octets:

 ,.Puck,.Ford,.Act I:.Scene I:.[Enter Puck and Ford]Ford:You cat!Open heart!You big cat!Open heart!You zero!Scene X:.Ford:Remember you!You big cat!Scene L:.Ford:Is I nicer zero?If so,let us Scene V.Is you nicer a big cat?If so,you is the sum of you a big lie.If so,open heart!Open heart!Scene M:.Puck:Remember you!Is I nicer a cat?You big cat.If so,you cat.Ford:Recall!Is you nicer zero?If not,let us Scene X.Is you nicer a big cat?If not,let us Scene M.You is the sum of you a big lie.Scene V:.Ford:Remember you!Is you worse a big big cat?If not, you big cat.Is you as big as a big cat?If not,you zero.You is the sum of I you.Puck:Recall!Let us Scene L.

Essayez-le en ligne!

Je peux générer la séquence complète dans l'implémentation Perl en utilisant 623 octets:

,.Puck,.Ford,.Act I:.Scene I:.[Enter Puck and Ford]Ford:You cat!Open heart!You big cat!Open heart!Scene L:.Ford:Is I nicer zero?If so,let us Scene V.Is you nicer a big cat?If so,you is the sum of you a big lie.If so,open heart!Open heart!Scene M:.Puck:Remember you!Is I nicer a cat?You big cat.If so,you cat.Ford:Recall!Is you worse a cat?If so,you big cat!If so,let us Scene L.Is you nicer a big cat?If not,let us Scene M.You is the sum of you a big lie.Scene V:.Ford:Remember you!Is you worse a big big cat?If not, you big cat.Is you as big as a big cat?If not,you zero.You is the sum of I you.Puck:Recall!Let us Scene L.

Toutefois, je tiens à souligner que cette solution est rapide comparée à de nombreuses autres solutions et utilise des quantités logarithmiques de mémoire plutôt que de stocker la liste complète. (Ceci est similaire à la solution C de vazt, à laquelle elle est liée de manière lointaine.) Cela ne fait aucune différence pour le golf, mais j'en suis néanmoins satisfait. Vous pouvez générer un million de chiffres en une minute environ en Perl (par exemple, si vous passez à sed et wc pour obtenir un nombre de chiffres), l'autre solution pouvant vous donner quelques milliers de chiffres.

Explication

Nous stockons une séquence de variables dans l'ordre: pile de Puck (de bas en haut), valeur de Puck, valeur de Ford, pile de Ford (de haut en bas). Hormis les valeurs zéro aux extrémités (le zéro à gauche pouvant provenir d'une pile vide), chaque valeur est le chiffre généré à la génération suivante, suivi de 2 si la génération suivante a besoin d'un autre enfant de ce parent. Lorsque nous avons N valeurs non nulles dans la séquence, nous générons tous les enfants jusqu'à la N-ième génération incluse, dans une sorte de parcours d'arbre en profondeur d'abord. Nous imprimons des valeurs uniquement de la N-ième génération. Lorsque la N-ième génération est complètement générée, les valeurs stockées sont en fait les valeurs de départ pour les générations 2 à (N + 1). Nous ajoutons donc un 2 à gauche et recommençons, générant cette fois le (N + 1). ) -th génération.

Donc, un aperçu: Scène X: Quand nous arrivons ici, c’est le début d’un nouveau parcours. Rondelle == 0. Nous mettons éventuellement ce zéro sur la pile de Puck et fixons Puck = 2. Scène L: Si Ford == 0, nous avons atteint la génération d’impression. Sinon, allez à V. Pour l'impression, si 2 ont été ajoutés à la valeur de Puck, supprimez-les et imprimez-les deux fois; sinon, imprimez-le une fois. Scène M: Il s’agit d’une boucle dans laquelle nous basculons à plusieurs reprises sur la valeur de Puck et remontons dans la séquence. On répète jusqu'à atteindre la fin (Puck == 0), auquel cas on passe à X, ou on atteint une valeur qui nécessite un autre enfant (Puck> 2), auquel cas on soustrait le supplément de 2 et on avance dans V. Scène V: Ici nous allons en avant. Si Puck vaut 2 ou 4, la génération suivante contiendra deux enfants du parent actuel, donc Ford + = 2. Avancez dans la séquence. Allez à L pour vérifier la terminaison.

axo , 13 octets

[:|[1+{#;1;-_

Essayez-le en ligne!

Explication

Cela a commencé comme port d'une solution alternative dans ma réponse à Wumpus :

2%)[=]&=[O00.

Cela a abouti à 18 octets. J'ai fini par jouer aux 13 octets que vous voyez ci-dessus pour l'adapter davantage au fonctionnement d'axo. Cette version à 13 octets a finalement inspiré l'amélioration de Wumpus jusqu'à 11 octets, elle est donc maintenant plus proche de cette version.

Comme dans Wumpus, dans l'itération i , le bas de la pile contient un (i) -1 et le haut, le premier élément de la i ème exécution, mais nous travaillons toujours avec 0 et 1 , à l'exception de l'impression.

[:    Store a copy of the top of the stack in register A.
|     Pull up a(i)-1 from the bottom of the stack.
[1+{  Print a(i).
#;    If a(i)-1 is 1, push the value in register A.
1;-   Push another copy of that value and subtract it from 1 to swap
      0 and 1 for the next run.
_     Jump back to the beginning of the program.

Ruby , 45 39 octets

a=*i=0;loop{a+=[k=1+i%2]*p(a[i+=1]||k)}

imprime indéfiniment

Essayez-le en ligne!

Essayez-le avec une fonction d'impression surchargée qui vous permet de choisir un séparateur et le nombre d'éléments imprimés