C'est ainsi que la séquence de Kolakoski (OEIS A000002 ) est définie:

La séquence de Kolakoski est une séquence qui contient 1et 2, et le ne élément de la séquence est la longueur du ne groupe d'éléments égaux (run) dans la séquence elle-même. Les 20 premiers termes de la séquence et les longueurs respectives sont:

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

Essentiellement, la longueur des groupes d'éléments égaux de la séquence de Kolakoski est la séquence de Kolakoski elle-même.

Jusqu'ici, tout va bien, mais pourquoi devrions-nous nous limiter à 1et 2? On ne va pas! Étant donné deux entrées, un tableau d'entiers positifs Aet un entier N, retourne les premiers Ntermes de la séquence de type Kolakoski définie par cyclage A. Pour mieux comprendre, voici un exemple travaillé avec les longueurs des groupes nouvellement ajoutés entre parenthèses:

A = [2, 3, 1]
N = 25

2: [[2], 2 ]
3: [ 2 ,[2], 3 , 3 ]
1: [ 2 , 2 ,[3], 3 , 1 , 1 , 1 ]
2: [ 2 , 2 , 3 ,[3], 1 , 1 , 1 , 2 , 2 , 2 ]
3: [ 2 , 2 , 3 , 3 ,[1], 1 , 1 , 2 , 2 , 2 , 3 ]
1: [ 2 , 2 , 3 , 3 , 1 ,[1], 1 , 2 , 2 , 2 , 3 , 1 ]
2: [ 2 , 2 , 3 , 3 , 1 , 1 ,[1], 2 , 2 , 2 , 3 , 1 , 2 ]
3: [ 2 , 2 , 3 , 3 , 1 , 1 , 1 ,[2], 2 , 2 , 3 , 1 , 2 , 3 , 3 ]
1: [ 2 , 2 , 3 , 3 , 1 , 1 , 1 , 2 ,[2], 2 , 3 , 1 , 2 , 3 , 3 , 1 , 1 ]
2: [ 2 , 2 , 3 , 3 , 1 , 1 , 1 , 2 , 2 ,[2], 3 , 1 , 2 , 3 , 3 , 1 , 1 , 2 , 2 ]
3: [ 2 , 2 , 3 , 3 , 1 , 1 , 1 , 2 , 2 , 2 ,[3], 1 , 2 , 3 , 3 , 1 , 1 , 2 , 2 , 3 , 3 , 3 ]
1: [ 2 , 2 , 3 , 3 , 1 , 1 , 1 , 2 , 2 , 2 , 3 ,[1], 2 , 3 , 3 , 1 , 1 , 2 , 2 , 3 , 3 , 3 , 1 ]
2: [ 2 , 2 , 3 , 3 , 1 , 1 , 1 , 2 , 2 , 2 , 3 , 1 ,[2], 3 , 3 , 1 , 1 , 2 , 2 , 3 , 3 , 3 , 1 , 2 , 2 ]
C: [ 2 , 2 , 3 , 3 , 1 , 1 , 1 , 2 , 2 , 2 , 3 , 1 , 2 , 3 , 3 , 1 , 1 , 2 , 2 , 3 , 3 , 3 , 1 , 2 , 2 ]

Voici un autre exemple travaillé avec un leader 1:

A = [1, 2, 3]
N = 10

1: [[1]]
2: [ 1 ,[2], 2 ]
3: [ 1 , 2 ,[2], 3 , 3 ]
1: [ 1 , 2 , 2 ,[3], 3 , 1 , 1 , 1 ]
2: [ 1 , 2 , 2 , 3 ,[3], 1 , 1 , 1 , 2 , 2 , 2 ]
C: [ 1 , 2 , 2 , 3 , 3 , 1 , 1 , 1 , 2 , 2 ]

Comme vous pouvez le voir ci-dessus, le résultat final a été coupé en N = 10éléments. Le ne élément doit être la longueur du ne groupe d'éléments égaux, même si l'élément lui-même appartient au groupe auquel il se réfère. Comme dans le cas ci-dessus, le premier se 1réfère au premier de ces groupes qui n'est que cela 1, et le premier se 2réfère au deuxième de ces groupes, qui commence par lui.

Règles

• Vous pouvez supposer qu'il An'aura jamais deux ou plusieurs éléments égaux consécutifs. Apeut contenir un entier plus d'une fois, mais les premier et dernier éléments ne seront pas égaux et Acontiendront au moins 2 éléments (par exemple [1, 2, 2, 3], [2, 4, 3, 1, 2]et [3]ne seront pas donnés). En effet, s'il y avait des éléments égaux consécutifs, le résultat final aurait été un préfixe non valide pour une telle séquence.
• Vous pouvez supposer Aque ne contient que des entiers positifs (car une telle séquence ne serait pas définie autrement).
• Vous pouvez supposer qu'il Ns'agit d'un entier non négatif ( N >= 0).
• Vous ne pouvez pas renvoyer plus de termes que demandé.
• L'utilisation de l'une des failles standard est strictement interdite.
• Vous pouvez utiliser n'importe quelle méthode d'E / S raisonnable .
• Votre réponse ne doit pas fonctionner au-delà des limites du langage naturel, mais en théorie, votre algorithme devrait fonctionner pour des entrées et des entiers arbitrairement grands .
• C'est le golf de code , donc la réponse la plus courte l'emporte.

Cas de test

[5, 1, 2], 0 -> []
[2, 3, 1], 25 -> [2, 2, 3, 3, 1, 1, 1, 2, 2, 2, 3, 1, 2, 3, 3, 1, 1, 2, 2, 3, 3, 3, 1, 2, 2]
[1, 2, 3], 10 -> [1, 2, 2, 3, 3, 1, 1, 1, 2, 2]
[1, 2], 20 -> [1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 2, 1]
[1, 3], 20 -> [1, 3, 3, 3, 1, 1, 1, 3, 3, 3, 1, 3, 1, 3, 3, 3, 1, 1, 1, 3]
[2, 3], 50 -> [2, 2, 3, 3, 2, 2, 2, 3, 3, 3, 2, 2, 3, 3, 2, 2, 3, 3, 3, 2, 2, 2, 3, 3, 3, 2, 2, 3, 3, 2, 2, 2, 3, 3, 3, 2, 2, 3, 3, 2, 2, 2, 3, 3, 3, 2, 2, 2, 3, 3]
[7, 4], 99 -> [7, 7, 7, 7, 7, 7, 7, 4, 4, 4, 4, 4, 4, 4, 7, 7, 7, 7, 7, 7, 7, 4, 4, 4, 4, 4, 4, 4, 7, 7, 7, 7, 7, 7, 7, 4, 4, 4, 4, 4, 4, 4, 7, 7, 7, 7, 7, 7, 7, 4, 4, 4, 4, 7, 7, 7, 7, 4, 4, 4, 4, 7, 7, 7, 7, 4, 4, 4, 4, 7, 7, 7, 7, 4, 4, 4, 4, 7, 7, 7, 7, 7, 7, 7, 4, 4, 4, 4, 4, 4, 4, 7, 7, 7, 7, 7, 7, 7, 4]
[1, 2, 3], 5 -> [1, 2, 2, 3, 3]
[2, 1, 3, 1], 2 -> [2, 2]
[1, 3, 5], 2 -> [1, 3]
[2, 3, 2, 4], 10 -> [2, 2, 3, 3, 2, 2, 2, 4, 4, 4]

Husk , 8 octets

Ṡωȯ↑⁰`Ṙ¢

Prend d'abord la longueur, puis la liste. Essayez-le en ligne!

Explication

Ṡωȯ↑⁰`Ṙ¢  Inputs: n=9 and x=[2,1,3]
Ṡωȯ       Apply the following function to x until a fixed point is reached:
           Argument is a list, say y=[2,2,1,3,3,3]
       ¢   Cycle x: [2,1,3,2,1,3..
     `Ṙ    Replicate to lengths in y: [2,2,1,1,3,2,2,2,1,1,1,3,3,3]
   ↑⁰      Take first n elements: [2,2,1,1,3,2,2,2,1]
          Final result is [2,2,1,1,3,2,1,1,1], print implicitly.

Pyth, 14 octets

u<s*V]M*QlGGvz

Essayez-le en ligne: démonstration ou suite de tests

Explication:

u                 start with G = input array
       *QlG       repeat input array
     ]M           put every element into its own list
   *V      G      repeat every list vectorized by the counts in G
  s               flatten
 <          vz    take the first (second input line) numbers
                  and assign them to G until you reach fixed point

Java 8, 151 + 19119115 octets

a->n->{int c=0,l[]=new int[n],i=0,j;for(;i<n;i++)for(j=0;j<(c==i?a[i]:l[i])&c<n;j++)l[c++]=a[i%a.length];return l;}

Essayez-le en ligne!

R , 120 114 108 octets

-6 octets grâce à plannapus

function(A,N){i=inverse.rle
w=length
a=rle(A)
while(w(a$l)<N){a[[1]]=i(a)
a[[2]]=rep(A,l=w(a$l))}
i(a)[0:N]}

Essayez-le en ligne!

Fonction anonyme; Inverse successivement le RLE, en remplaçant les longueurs a[[1]]par le RLE inversé, et les valeurs a[[2]]avec Arépliquées à une longueur égale à celle de a$l.

Haskell , 68 octets

Un grand merci à Laikoni et flawr pour leur aide dans le débogage et le golf de cette réponse dans le salon de discussion PPCG Haskell, Of Monads and Men . Suggestions de golf bienvenues! Essayez-le en ligne!

(.f).take
f a@(z:_)=(z<$[1..z])++do i<-[1..];cycle a!!i<$[1..f a!!i]

La première ligne est une fonction anonyme. La deuxième ligne est la compréhension de la liste infinie qui produit notre séquence de type Kolakoski.

Explication

Tout d'abord, nous définissons zcomme la tête de aavec a@(z:_). Ensuite, nous initialisons la séquence avec (z<$[1..z]).

Ensuite, à 1partir de maintenant, do i<-[1..]nous ajoutons ce qui suit à la séquence :, cycle a!!i<$[1..f a!!i]qui est le i-ième membre des temps aajoutés (cyclés indéfiniment) f a!!i.

Enfin, la fonction anonyme reprend simplement les premiers ntermes de notre séquence de type Kolaskoski.

Python 2 , 123 octets

x,y=input()
k=x[0]
t,j=[],0
if k==1:t,j=[k]+x[1]*[x[1]],2
while len(t)<y:t+=(j and t[j]or k)*[x[j%len(x)]];j+=1
print t[:y]

Essayez-le en ligne!