Présentation

Certains d'entre vous connaissent peut-être la séquence de Kolakoski ( A000002 ), une séquence autoréférentielle bien connue qui a la propriété suivante:

C'est une séquence contenant seulement 1 et 2, et pour chaque groupe de 1 et de deux, si vous additionnez la longueur des pistes, elle est égale à elle-même, seulement la moitié de la longueur. En d'autres termes, la séquence de Kolakoski décrit la longueur des séquences de la séquence elle-même. C'est la seule séquence qui fait cela, sauf pour la même séquence avec le 1 initial supprimé. (Cela n'est vrai que si vous vous limitez aux séquences composées de 1 et 2 - Martin Ender)

Le défi

Le défi est, étant donné une liste d'entiers:

• Sortie -1si la liste n'est PAS un préfixe de travail de la séquence de Kolakoski.
• Affiche le nombre d'itérations avant que la séquence ne devienne [2].

L'exemple élaboré

En utilisant l'image fournie comme exemple:

[1,2,2,1,1,2,1,2,2,1,2,2,1,1,2,1,1] # Iteration 0 (the input).
[1,2,2,1,1,2,1,2,2,1,2]             # Iteration 1.
[1,2,2,1,1,2,1,1]                   # Iteration 2.
[1,2,2,1,2]                         # Iteration 3.
[1,2,1,1]                           # Iteration 4.
[1,1,2]                             # Iteration 5.
[2,1]                               # Iteration 6.
[1,1]                               # Iteration 7.
[2]                                 # Iteration 8.

Par conséquent, le nombre résultant est 8pour une entrée de [1,2,2,1,1,2,1,2,2,1,2,2,1,1,2,1,1].

9 convient également si vous effectuez une indexation 1.

La suite de tests (vous pouvez également tester avec des sous-itérations)

------------------------------------------+---------
Truthy Scenarios                          | Output
------------------------------------------+---------
[1,1]                                     | 1 or 2
[1,2,2,1,1,2,1,2,2,1]                     | 6 or 7
[1,2,2,1,1,2,1,2,2,1,2,2,1,1,2,1,1]       | 8 or 9
[1,2]                                     | 2 or 3
------------------------------------------+---------
Falsy Scenarios                           | Output
------------------------------------------+---------
[4,2,-2,1,0,3928,102904]                  | -1 or a unique falsy output.
[1,1,1]                                   | -1
[2,2,1,1,2,1,2] (Results in [2,3] @ i3)   | -1 (Trickiest example)
[]                                        | -1
[1]                                       | -1

Si vous êtes confus:

Truthy: Il atteindra finalement deux sans aucune étape intermédiaire ayant d'autres éléments que 1et 2. -Einkorn Enchanter 20 hours ago

Faux: la valeur de fin ne l'est pas [2]. Les termes intermédiaires contiennent autre chose que quelque chose de l'ensemble [1,2]. Quelques autres choses, voir des exemples.

C'est le code-golf , le nombre d'octets le plus bas sera le vainqueur.

Haskell , 126 87 79 76 75 octets

39 octets économisés grâce à Ørjan Johansen

import Data.List
f[2]=0
f y@(_:_:_)|all(`elem`[1,2])y=1+f(length<$>group y)

Essayez-le en ligne!

Cette erreur sur une mauvaise entrée.

05AB1E , 22 octets

[Dg2‹#γ€gM2›iX]2QJiNë®

Essayez-le en ligne!

Explication

[                        # start a loop
 D                       # duplicate current list
  g2‹#                   # break if the length is less than 2
      γ                  # group into runs of consecutive equal elements
       €g                # get length of each run
         M2›iX           # if the maximum run-length is greater than 2, push 1
              ]          # end loop
               2QJi      # if the result is a list containing only 2
                   N     # push the iteration counter from the loop
                    ë®   # else, push -1
                         # implicitly output top of stack

SCALA, 290 (282?) Caractères, 290 (282?) Octets

Ça m'a pris tellement de temps ... Mais j'ai enfin fini!

avec ce code:

var u=t
var v=Array[Int]()
var c= -1
var b=1
if(!u.isEmpty){while(u.forall(x=>x==1|x==2)){c+=1
if(u.size>1){var p=u.size-1
for(i<-0 to p){if(b==1){var k=u(i)
v:+=(if(i==p)1 else if(u(i+1)==k){b=0
if(p-i>1&&u(i+2)==k)return-1
2}else 1)} else b=1}
u=v
v=v.take(0)}else if(u(0)==2)return c}}
c

Je ne sais pas si je dois compter le var u=tdans les octets, étant donné que je ne l'utilise pas tpendant l'algorithme (la copie est juste pour obtenir un modifiable varau lieu du paramètre tconsidéré comme val- merci ScaLa ). Veuillez me dire si je dois le compter.

Assez dur. Essayez-le en ligne!

PS: je pensais le faire récursivement, mais je vais devoir passer un compteur comme paramètre de la vraie "sous-fonction" récursive; ce fait me fait déclarer deux fonctions, et ces caractères / octets ne sont que perdus.

EDIT: J'ai dû changer (?) Parce que nous ne sommes pas sûrs que nous devrions prendre en compte le [1]cas. Donc , voici le code modifié:

var u=t
var v=Array[Int]()
var c= -1
var b=1
if(!u.isEmpty){try{t(1)}catch{case _=>return if(t(0)==2)0 else -1}
while(u.forall(x=>x==1|x==2)){c+=1
if(u.size>1){var p=u.size-1
for(i<-0 to p){if(b==1){var k=u(i)
v:+=(if(i==p)1 else if(u(i+1)==k){b=0
if(p-i>1&&u(i+2)==k)return-1
2}else 1)} else b=1}
u=v
v=v.take(0)}else if(u(0)==2)return c}}
c

Ce n'est pas optimisé (j'ai un "out" en double pour les mêmes conditions: quand j'arrive [2]et quand param est[2] est traité séparément).

NOUVEAU COÛT = 342 (je n'ai pas modifié le titre exprès)

JavaScript, 146 142 octets

Premier essai en code golf, il semble que le "retour" dans la fonction plus grande soit assez fastidieux ...

De plus, la vérification de b = 1 et b = 2 prend quelques octets ...

Voici le code:

f=y=>{i=t=!y[0];while(y[1]){r=[];c=j=0;y.map(b=>{t|=b-1&&b-2;if(b-c){if(j>0)r.push(j);c=b;j=0}j++});(y=r).push(j);i++}return t||y[0]-2?-1:0^i}

Explication

f=y=>{/*1*/}                                        //function definition

//Inside /*1*/:
  i=t=!y[0];                                        //initialization
                                                    //if the first one is 0 or undefined, 
                                                    //set t=1 so that it will return -1   
                                                    //eventually, otherwise i=0
  while(y[1]){/*2*/}                                //if there are 2+ items, start the loop

  //Inside /*2*/:
    r=[];c=j=0;                                     //initialization
    y.map(b=>{/*3*/});                              //another function definition

    //Inside /*3*/:
      t|=b-1&&b-2;                                  //if b==1 or b==2, set t=1 so that the
                                                    //entire function returns -1
      if(b-c){if(j>0)r.push(j);c=b;j=0}             //if b!=c, and j!=0, then push the 
                                                    //count to the array and reset counter
      j++                                           //counting duplicate numbers

    (y=r).push(j);i++                               //push the remaining count to the array
                                                    //and proceed to another stage

  return t||y[0]-2?-1:0^i                           //if the remaining element is not 2, or
                                                    //t==1 (means falsy), return -1,
                                                    //otherwise return the counter i

Données de test (en utilisant les données de test fournies)

l=[[1,1],[1,2,2,1,1,2,1,2,2,1],[1,2,2,1,1,2,1,2,2,1,2,2,1,1,2,1,1],[1,2],[4,2,-2,1,0,3928,102904],[1,1,1],[2,2,1,1,2,1,2],[]];
console.log(l.map(f));
//Output: (8) [1, 6, 8, 2, -1, -1, -1, -1]

Édition 1: 146 -> 142: révoquer mon édition sur la réduction des octets, car cela affecte la sortie; et quelques modifications sur la dernière déclaration

Gelée ,26 25 22 21 20 octets

FQœ-2R¤
ŒgL€µÐĿṖ-LÇ?

Essayez-le en ligne!

Ce code ne fonctionnait pas correctement avant 20 octets et je n'ai même pas remarqué; il échouait sur le [2,2]cas de test. Devrait fonctionner parfaitement maintenant.

JavaScript (ES6), 127 126 95 80 octets

g=(a,i,p,b=[])=>a.map(x=>3>x&0<x?(x==p?b[0]++:b=[1,...b],p=x):H)==2?i:g(b,~~i+1)

0 indexé. Jette "ReferenceError: X is not defined"et "InternalError: too much recursion"sur une mauvaise entrée.

Cas de test

g=(a,i,p,b=[])=>a.map(x=>3>x&0<x?(x==p?b[0]++:b=[1,...b],p=x):H)==2?i:g(b,~~i+1)

function wrapper(testcase) {
  try {console.log(g(testcase))} catch(e) {
    console.log("Error")
  }
}

wrapper([1,1])
wrapper([1,2,2,1,1,2,1,2,2,1])
wrapper([1,2,2,1,1,2,1,2,2,1,2,2,1,1,2,1,1])
wrapper([1,2])
wrapper([4,2,-2,1,0,3928,102904])
wrapper([1,1,1])
wrapper([2,2,1,1,2,1,2])
wrapper([])
wrapper([1])

Clojure, 110 octets

#(if-not(#{[][1]}%)(loop[c % i 0](if(every? #{1 2}c)(if(=[2]c)i(recur(map count(partition-by + c))(inc i))))))

Un basique loopavec un pré-contrôle des boîtiers de bord. Renvoie nilles entrées non valides. Je ne savais pas (= [2] '(2))c'est true: o

Python 2, 146 octets (fonction uniquement)

f=lambda l,i=0:i if l==[1]else 0if max(l)>2or min(l)<1else f([len(x)+1for x in"".join(`v!=l[i+1]`[0]for i,v in enumerate(l[:-1])).split("T")],i+1)

Renvoie 0 sur l'entrée falsifiée (ok car il est indexé 1). Utilisez-le simplement comme ceci:

print(f([1,2,2,1,1,2,1,2,2,1,2,2,1,1,2,1,1]))

Mathematica, 82 octets

FixedPointList[#/.{{2}->T,{(1|2)..}:>Length/@Split@#,_->0}&,#]~FirstPosition~T-1&

Functionqui remplace à plusieurs reprises {2}par le symbole non défini T, une liste de (un ou plusieurs) 1s et 2s avec l'itération suivante, et toute autre chose 0jusqu'à ce qu'un point fixe soit atteint, puis renvoie FirstPositionle symbole Tdans le FixedPointListmoins résultant 1. La sortie est {n}où nest le nombre ( 1-indexé) d'itérations nécessaires pour atteindre {2}le cas véridique et -1+Missing["NotFound"]le cas falsifié.

Si la sortie doit être nplutôt que {n}, cela coûte trois octets de plus:

Position[FixedPointList[#/.{{2}->T,{(1|2)..}:>Length/@Split@#,_->0}&,#],T][[1,1]]-1&

Python 2 , 184163156 octets

• @Felipe Nardi Batista a économisé 21 octets !!!! Merci beaucoup!!!!
• Halvard Hummel a économisé 7 octets !! Merci

Python 2 , 156 octets

a,c=input(),0
t=a==[]
while 1<len(a)and~-t:
 r,i=[],0
 while i<len(a):
	j=i
	while[a[j]]==a[i:i+1]:i+=1
	r+=[i-j]
 a=r;c+=1;t=any(x>2for x in a)
print~c*t+c

Essayez-le en ligne!

Explication:

a,c=input(),0                             #input and initialize main-counter 

t=a==[]                                   #set t to 1 if list's empty. 

while len(a)>1:                           #loop until list's length is 1.

 r,i=[],0                                 #Initialize temp. list and 
                                          #list-element-pointer 

 while i<len(a):                          #loop for the element in list 

  j=0                                     #set consecutive-item-counter to 0   

  while(i+j)<len(a)and a[i]==a[i+j]:j+=1  #increase the consec.-counter

  r+=[j];i+=j                             #add the value to a list, move the 
                                          #list-element-pointer 

 a=r;c+=1;t=any(x>2for x in a)            #update the main list, increase t 
                                          #the counter, check if any number 
 if t:break;                              #exceeds 2 (if yes, exit the loop)

print[c,-1][t]                            #print -1 if t or else the 
                                          #counter's 
                                          #value 

Gelée , 17 octets

ŒgL€$ÐĿµẎḟ1,2ȯL_2

Essayez-le en ligne!

Python 2 , 122 octets

def f(s,c=2,j=0):
 w=[1]
 for i in s[1:]:w+=[1]*(i!=s[j]);w[-1]+=i==s[j];j+=1
 return(w==[2])*c-({1,2}!=set(s))or f(w,c+1)

Essayez-le en ligne!

Python 3 , 120 octets

def f(s,c=2,j=0):
 w=[1]
 for i in s[1:]:w+=[1]*(i!=s[j]);w[-1]+=i==s[j];j+=1
 return(w==[2])*c-({1,2}!={*s})or f(w,c+1)

Essayez-le en ligne!

Explication

Une nouvelle séquence (w) est initialisée pour stocker la prochaine itération de la réduction. Un compteur (c) est initialisé pour garder une trace du nombre d'itérations.

Chaque élément de la ou des séquences d'origine est comparé à la valeur précédente. S'ils sont identiques, la valeur du dernier élément de (w) est augmentée de 1. S'ils sont différents, la séquence (w) est étendue avec [1].

Si w == [2], le compteur (c) est retourné. Sinon, si la ou les séquences d'origine contiennent d'autres éléments que 1 et 2, une valeur -1 est renvoyée. Si ce n'est pas le cas, la fonction est appelée récursivement avec la nouvelle séquence (w) as (s) et le compteur (c) augmenté de 1.

R, 122 octets

a=scan()
i=0
f=function(x)if(!all(x%in%c(1,2)))stop()
while(length(a)>1){f(a)
a=rle(a)$l
f(a)
i=i+1}
if(a==2)i else stop()

Réussit tous les cas de test. Lance une ou plusieurs erreurs sinon. Je déteste les contrôles de validité; ce code aurait pu être si golfé si les entrées étaient belles; il serait plus court même si l'entrée était une séquence de 1 et de 2, pas nécessairement un préfixe de la séquence de Kolakoski. Ici, nous devons vérifier à la fois le vecteur initial (sinon le cas de test [-2,1]) aurait réussi) et le vecteur résultant (sinon [1,1,1]aurait réussi).

Rubis , 81 77 octets

f=->a,i=1{a[1]&&a-[1,2]==[]?f[a.chunk{|x|x}.map{|x,y|y.size},i+1]:a==[2]?i:0}

Essayez-le en ligne!

Modifier: enregistré 4 octets en convertissant en lambda récursif.

Renvoie un nombre d'itérations indexé à 1 ou 0 comme falsey.

Utilise la méthode chunk de Ruby enumerable, qui fait exactement ce dont nous avons besoin - regrouper des séries consécutives de nombres identiques. Les longueurs des exécutions constituent le tableau pour la prochaine itération. Continue à itérer pendant que le tableau est plus long que 1 élément et qu'aucun nombre autre que 1 et 2 n'a été rencontré.

Pyth , 45 octets

L?||qb]1!lb-{b,1 2_1?q]2b1Z.V0IKy~QhMrQ8*KhbB

Essayez-le en ligne!

C'est probablement encore jouable au golf. Il est certainement jouable au golf si cela .?fonctionnait comme je l'espérais (étant un elsepour la structure la plus intérieure au lieu de la plus extérieure)

L?||qb]1!lb-{b,1 2_1?q]2b1Z # A lambda function for testing an iteration of the shortening
L                           # y=lambda b:
 ?                          # if
    qb]1                    #    b == [1]
   |    !lb                 #      or !len(b)
  |         {b              #        or b.deduplicate()
           -  ,1 2          #             .difference([1,2]):
                  _1        #               return -1
                    ?q]2b1Z # else: return 1 if [2] == b else Z (=0)

.V0                         # for b in range(0,infinity):
   IKy~Q                    # if K:=y(Q :=        (applies y to old value of Q)
        hM                  #    map(_[0],
          rQ8               #               run_length_encode(Q)):
             *Khb           #    print(K*(b+1))
                 B          #    break

Perl 5 -p , 71 octets

$_.=$";s/(. )\1*/$&=~y|12||.$"/ge&$.++while/^([12] ){2,}$/;$_=/^2 $/*$.

Essayez-le en ligne!

1-indexé. Sorties 0pour falsification.