Considérez une séquence binaire, en utilisant 1et 2, par exemple:

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

Écrivons les longueurs d'exécution de cela:

1, 2, 1, 1, 2, 2, 1, 2, 1, 2, 2, 1 ...
_  _  ____  ____  _  _  _  ____
1, 1, 2,    2,    1, 1, 1, 2,   ...

Dans ce cas, nous obtenons une autre séquence binaire. Bien sûr, ce n'est pas garanti (par exemple, si nous répétions le processus, la troisième exécution le serait 3), mais supposons que nous le faisons.

Maintenant, la question est, pouvons-nous trouver une séquence telle que l'application de ce type d'encodage de longueur d'exécution plusieurs fois nous rend la séquence d'origine? Pour une longueur de cycle de 1 (c'est-à-dire un point fixe de cette transformation), nous trouvons la séquence d'Oldenburger-Kolakoski (entrée OEIS A0000002 ):

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

(Il existe en fait une autre solution: nous pouvons également omettre le début 1.)

Et un cycle de longueur 2? C'est aussi possible! Les deux séquences suivantes sont la liste de chacune des longueurs d'exécution:

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

(Il s'agit des entrées OEIS A025142 et A025143 . C'est la seule solution.)

Peut-on trouver un cycle de longueur 3? Bien sûr, ici chaque séquence est le codage de longueur de la suivante (et la troisième est le codage de longueur de la première):

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

Dans ce cas, il existe une autre solution. Il s'avère que nous pouvons trouver un tel cycle pour chaque durée de cycle. En fait, le nombre de cycles distincts de longueur n est donné par l'entrée OEIS A001037 (sans compter le choix arbitraire de la séquence d'un cycle considérée comme la première).

Fait amusant: aussi improbable que cela puisse paraître, ce défi a été inspiré par l'étude de la carte complexe f(z) = z - 1/z. Celui qui comprend ce que cette carte a à voir avec ce défi obtient un cookie.

Le défi

Étant donné une longueur de cycle k > 0et une longueur de séquence n > 0, sortez les premiers ntermes de kséquences binaires distinctes (infinies) qui forment un cycle sous la transformation de longueur d'exécution ci-dessus. Si plusieurs cycles existent, vous pouvez sortir n'importe lequel d'entre eux. C'est à vous de décider quelle séquence du cycle commencer et dans quelle direction va le cycle (vous pouvez donc soit les sortir de telle sorte que chaque séquence décrit la suivante, soit telle que chaque séquence décrive la précédente, de manière cyclique).

Vous pouvez écrire un programme ou une fonction, en prenant une entrée via STDIN (ou l'alternative la plus proche), un argument de ligne de commande ou un argument de fonction et en sortant le résultat via STDOUT (ou l'alternative la plus proche), une valeur de retour de fonction ou un paramètre de fonction (out).

La sortie peut être dans n'importe quel format de liste imbriqué, sans ambiguïté, tel que la dimension externe est ket la dimension interne est n.

Les règles de code-golf standard s'appliquent.

Exemples supplémentaires

Voici quelques exemples. Mais comme je l'ai dit, les solutions ne sont pas uniques, donc vos propres solutions peuvent différer et toujours être correctes. Peut-être que cela vous aidera à trouver une solution. Chaque exemple est k nsuivi des séquences, de sorte que chaque ligne décrit la suivante (cycliquement):

4 20
1, 2, 1, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 1, 2, 2, 1, 2
2, 1, 1, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 2, 1, 2, 1, 1, 2, 1
2, 2, 1, 2, 1, 1, 2, 1, 1, 2, 2, 1, 2, 1, 1, 2, 1, 2, 2, 1
1, 1, 2, 2, 1, 2, 2, 1, 2, 1, 1, 2, 1, 2, 2, 1, 1, 2, 1, 1

5 6
2, 2, 1, 2, 2, 1
1, 1, 2, 2, 1, 2
2, 1, 2, 2, 1, 1
1, 1, 2, 1, 1, 2
2, 1, 2, 2, 1, 2

8 20
2, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2
1, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 1, 1, 2, 1, 1
2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 2, 1, 2, 1, 1, 2, 1, 1, 2, 2
2, 2, 1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 1, 1, 2, 2, 1, 2, 2
1, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1
2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 2, 1, 2, 1, 1, 2, 1, 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, 2, 1, 1, 2, 2, 1, 2, 2, 1, 2, 1, 1, 2, 1, 1

13 50
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, 2, 2, 1, 1, 2, 1, 1, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 2, 1, 2, 1, 1
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, 2, 2, 1, 1, 2, 1, 1, 2, 2, 1, 2, 1, 1
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, 2, 2, 1, 1, 2, 1, 2, 2, 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, 1, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 2, 2, 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, 1, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 2, 2, 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, 1, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 1, 1, 2
2, 1, 1, 2, 2, 1, 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, 2, 1, 1, 2, 1, 1, 2, 2, 1, 2, 1, 1, 2, 1, 2, 2, 1
1, 1, 2, 1, 2, 2, 1, 1, 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, 1, 1, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 2, 1
1, 2, 1, 1, 2, 1, 1, 2, 2, 1, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 2, 1, 2, 1, 1, 2, 1, 1, 2, 2, 1, 2, 2, 1, 1
1, 2, 2, 1, 2, 1, 1, 2, 1, 2, 2, 1, 1, 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, 2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 1
1, 2, 2, 1, 1, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 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, 2
1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 1, 1, 2, 1, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 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, 2, 1, 2, 1, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 2, 1, 2, 1, 1

Notez que toutes les lignes des deux dernières sorties ne diffèrent pas, bien qu'elles finiraient par être si elles nétaient suffisamment grandes.

questions connexes

• Générer une séquence de Kolakoski

CJam (41 octets)

{Ma*{1:Bm<{1+ee{(1&B^)+}%e~A<0:B;}%}@:A*}

Il s'agit d'une fonction anonyme qui prend les entrées sur la pile dans l'ordre n ket laisse les sorties sur la pile. Démo en ligne

L'idée de base est de commencer par une colonne de mots de Lyndon [2 1 1 1 ...]et de s'étendre itérativement à droite sur la base que connaissant l'élément initial de chaque ligne et l'alternance, nous pouvons décoder en longueur et obtenir plus d'éléments.

Haskell, 72 octets

~(a:b)?c=c:[c|a>1]++b?(3-c)
k!n=take k$take n<$>last(k!n)?2:map(?1)(k!n)

Démo:

*Main> 4!20
[[2,1,1,2,2,1,2,2,1,2,1,1,2,1,1,2,2,1,2,1],[1,1,2,1,2,2,1,1,2,1,1,2,2,1,2,2,1,2,1,1],[1,2,1,1,2,1,1,2,2,1,2,1,1,2,1,2,2,1,1,2],[1,2,2,1,2,1,1,2,1,2,2,1,1,2,1,1,2,1,2,2]]

APL (Dyalog Unicode) , 35 octets

{(⍺↑¨⊣{⍵/(≢⍵)⍴⍺,3-⍺}¨¯1⌽⊢)⍣≡⍨1+⍵↑1}

Essayez-le en ligne!

Un dfn anonyme dont l'argument de gauche est net celui de droite est k.

Traduction presque directe de la réponse Haskell d' Anders Kaseorg (adaptée à la nature finie et stricte des tableaux APL), avec un petit indice de l'idée de Peter Taylor :

L'idée de base est de commencer par une colonne de mots de Lyndon [2 1 1 1 ...]et de s'étendre itérativement à droite sur la base que connaissant l'élément initial de chaque ligne et l'alternance, nous pouvons décoder en longueur et obtenir plus d'éléments.

Comment ça marche

{(⍺↑¨⊣{⍵/(≢⍵)⍴⍺,3-⍺}¨¯1⌽⊢)⍣≡⍨1+⍵↑1}  ⍝ left argument(⍺)←n, right(⍵)←k
                             1+⍵↑1   ⍝ u←[2, 1, ..., 1] of length k
                            ⍨        ⍝ Run the following with both sides being u:
 (                       )⍣≡         ⍝  Repeat until fixpoint:
                                     ⍝  (left: u, right: intermediate result v)
                     ¯1⌽⊢            ⍝   Rotate v down once
     ⊣{            }¨                ⍝   Zip with left side u: (left elem u_i, right elem v_i)
              ⍺,3-⍺                  ⍝    Make a 2-elem array [u_i, 3-u_i] which is [1 2] or [2 1]
         (≢⍵)⍴                       ⍝    Cycle the above to the length of v_i
       ⍵/                            ⍝    Duplicate each element of above v_i times e.g. 1 1 2/2 1 2 → 2 1 2 2
       ⍵/(≢⍵)⍴⍺,3-⍺                  ⍝    Run-length decode v_i with alternating 1 and 2's, starting with u_i
  ⍺↑¨                                ⍝   Extend or truncate each row to length n

Comparaison avec la version Haskell d'Anders

Le code Haskell d'Anders (entre parenthèses pour plus de clarté) fonctionne comme ceci:

~(a:b)?c=(c:[c|a>1])++(b?(3-c))
  (c:[c|a>1])  -- Two copies of c if head of x > 1, one copy otherwise
  ++(b?(3-c))  -- Run-length decode the rest with alternating 1 and 2

k!n=take k$take n<$>((last(k!n))?2):(map(?1)(k!n))
  take k$         -- take first k rows
  take n<$>       -- take first n elements from each row
  ((last(k!n))?2) -- run-length decode the last row with starting value 2
  :(map(?1)(k!n)) -- run-length decode the other rows with starting value 1

Dans une itération, cela équivaut à "ajouter la k-ème ligne, décoder la longueur de chaque ligne, puis éliminer la dernière ligne". Nous pouvons le simplifier pour "tourner une fois et décoder la longueur", que j'ai implémenté comme ¯1⌽.

Pour la fonction de décodage de longueur, j'ai simplement utilisé la primitive APL /, tandis que la version Haskell utilise des listes infinies pour l'implémenter.