Permet de définir le processus d'écrasement d'un tableau de nombres. Dans un écrasement, nous lisons le tableau de gauche à droite. Si, à un moment donné, nous rencontrons deux du même élément d'affilée, nous supprimons le premier et doublons le second. Par exemple, voici le processus d'écrasement du tableau suivant

[5,2,2,3]
 ^
[5,2,2,3]
   ^
[5,2,2,3]
     ^
[5,4,3]
   ^
[5,4,3]
     ^

Le même élément peut être replié plusieurs fois, par exemple [1,1,2]devient [4]quand on les écrase.

Nous appellerons un tableau non écrasable lorsque le processus d'écrasement de ce tableau ne le modifie pas. Par exemple, [1,2,3]est toujours [1,2,3]après avoir été écrasé.

Votre tâche consiste à prendre un tableau et à déterminer le nombre d'écrasements nécessaires pour le rendre impossible à écraser. Vous avez uniquement besoin de prendre en charge des entiers compris entre 0 et 2 ³² -1

Il s'agit de code-golf donc les réponses seront notées en octets avec moins d'octets étant meilleurs.

Cas de test

[1] -> 0
[1,1] -> 1
[2,1,1] -> 2
[4,2,1,1] -> 3
[2,2,2,1,1] -> 3
[0,0,0,0] -> 1
[4,0,0,0,4] -> 1
[4,0,0,0,0,4] -> 1
[] -> 0

assemblage x86 (64 bits), 66 65 octets

31 c0 57 59 56 51 56 5f 4d 31 c0 48 83 c6 08 48
83 e9 01 76 1b fc f2 48 a7 75 15 48 d1 67 f8 51
56 57 f3 48 a5 5f 5e 59 fd 48 a7 49 ff c0 eb e5
59 5e 4c 29 c1 48 ff c2 4d 85 c0 75 c7 48 ff c8
c3

Les instructions de chaîne étaient utiles. Il n'était pas nécessaire de corriger les erreurs hors-un dans un environnement 64 bits.

Code source entièrement commenté:

.globl crush
crush:
/* return value */
xor %eax, %eax
/* save our length in rcx */
push %rdi
pop %rcx
pass:
/* save the start of the string and the length */
push %rsi
push %rcx
/* this is the loop */
/* first copy source to dest */
push %rsi
pop %rdi
/* and zero a variable to record the number of squashes we make this pass */
xor %r8, %r8
/* increment source, and decrement ecx */
add $8,%rsi
sub $1,%rcx
/* if ecx is zero or -1, we're done (we can't depend on the code to take care of this
automatically since dec will leave the zero flag set and cmpsq won't change it) */
jbe endpass
compare:
/* make sure we're going forward */
cld
/* compare our two values until we find two that are the same */
repne cmpsq
/* if we reach here, we either found the end of the string, or
we found two values that are the same. check the zero flag to
find out which */
jne endpass
/* okay, so we found two values that are the same. what we need
to do is double the previous value of the destination, and then
shift everything leftwards once */
shlq $1, -8(%rdi)
/* easiest way to shift leftwards is rep movsq, especially since
our ecx is already right. we just need to save it and the rsi/rdi */
push %rcx
push %rsi
push %rdi
rep movsq
pop %rdi
pop %rsi
pop %rcx
/* problem: edi and esi are now one farther than they should be,
since we can squash this dest with a different source. consequently
we need to put them back where they were. */
std
cmpsq
/* we don't need to put ecx back since the list is now one shorter
than it was. */
/* finally, mark that we made a squash */
inc %r8
/* okay, once we've reached this point, we should have:
 edi and esi: next two values to compare
 ecx: number of comparisons left
so we just jump back to our comparison operation */
jmp compare
endpass:
/* we reached the end of the string. retrieve our old ecx and esi */
pop %rcx
pop %rsi
/* rsi is accurate, but rcx is not. we need to subtract the number of squashes
that we made this pass. */
sub %r8, %rcx
/* record that we performed a pass */
inc %rax
/* if we did make any squashes, we need to perform another pass */
test %r8, %r8
jnz pass
/* we reached the end; we've made as many passes as we can.
decrement our pass counter since we counted one too many */
dec %rax
/* and finally return it */
ret

Je peux essayer de le faire en 32 bits, ne serait-ce que pour le plaisir, car ces préfixes REX m'ont vraiment tué.

Edit: rasé d'un octet en remplaçant lodsq par add,% rdx par% rax et en réduisant deux cld en un.

Pyth , 22 octets

tl.uu?&GqeGH+PGyH+GHN[

Vérifiez tous les cas de test.

Haskell , 66 octets

f(a:b:x)|a==b=f$a+a:x|1>0=a:f(b:x)
f x=x
g x|f x==x=0|1>0=1+g(f x)

Essayez-le en ligne!

Explication

fest une fonction qui écrase une liste. Il effectue le béguin comme décrit dans la question. gest une fonction qui compte le nombre d'écrasements. Si f x==x, g x=0sinon g x=1+g(f x).

Paradoc (v0.2.10), 16 octets (CP-1252)

{—1\ε=k+x}]»}IL(

Essayez-le en ligne! / avec en-tête / pied de page qui vérifie tous les cas de test

Prend une liste sur la pile et donne un nombre sur la pile.

Mise en œuvre assez simple, pour être tout à fait honnête. Écrase une liste en commençant par une sentinelle -1, en parcourant la liste, en poussant chaque élément et en l'ajoutant à l'élément en dessous s'il est égal. À la fin, nous avons coupé le -1. Nous ne broyons que des nombres égaux ensemble et tous les nombres du problème ne sont pas négatifs, donc la sentinelle -1 n'affectera pas le processus de broyage. Avec l'écrasement implémenté, il suffit de compter les itérations jusqu'à son point fixe.

Explication:

{            }I  .. Iterate this block: repeatedly apply it until a fixed
                 .. point is reached, and collect all intermediate results
 —1              ..   Push -1 (note that that's an em dash)
   \             ..   Swap it under the current list of numbers
    ε    }       ..   Execute this block for each element in the list:
     =           ..     Check if it's equal to the next element on the stack...
      k          ..       ... while keeping (i.e. not popping either of) them
       +         ..     Add the top two elements of the stack...
        x        ..       ... that many times (so, do add them if they were
                 ..       equal, and don't add them if they weren't)
          ]      ..   Collect all elements pushed inside the block that
                 ..     we're iterating into a list
           »     ..   Tail: take all but the first element (gets rid of the -1)
              L  .. Compute the length of the number of intermediate results
               ( .. Subtract 1

Si nous pouvions supposer que l'entrée n'était pas vide, nous n'aurions pas besoin de la sentinelle et pourrions raser 2 octets: {(\ε=k+x}]}IL(

Autre fait amusant: nous ne perdons que 2 octets si nous nous forçons à n'utiliser que ASCII: {1m\{=k+x}e]1>}IL(

JavaScript (ES6), 86 octets

f=a=>a.length>eval("for(i=0;a[i]>-1;)a[i]==a[++i]&&a.splice(--i,2,a[i]*2);i")?1+f(a):0

Non golfé et expliqué

f=a=>                           // function taking array a
    a.length > eval("           // if a.length > the result of the following...
        for(i=0; a[i]>-1;)      //   loop from 0 until the current value is undefined (which is not > -1)
            a[i] == a[++i] &&   //     if the current value equals the next one...
                a.splice(--i,   //       splice the array at the first index of the pair...
                    2,          //       by replacing 2 items...
                    a[i]*2);    //       with the current item * 2
                                //       this also decrements the counter, which means the current value is now the next
    i")                         //   return the counter, which is new a.length
        ? 1+f(a)                // if that was true, the array was crushed. add 1 and recur with the new array
        : 0                     // otherwise just return 0

Les tests

f=a=>a.length>eval("for(i=0;a[i]>-1;)a[i]==a[++i]&&a.splice(--i,2,a[i]*2);i")?1+f(a):0

;[ [1], [1,1], [2,1,1], [4,2,1,1], [2,2,2,1,1], [0,0,0,0], [4,0,0,0,4], [4,0,0,0,0,4], []
].forEach(x=>console.log( JSON.stringify(x) + " -> " + f(x) ))

.as-console-wrapper{max-height:100%!important}

JavaScript, 67 octets

f=a=>a.map(a=>k[k[d-1]!=a?d++:(a*=z=2,d-1)]=a,k=d=[z=0])&&z&&f(k)+1

Essayez-le en ligne!

Brain-Flak , 144 octets

([])({<{}>(<(([][()]){[{}]<({}[({})]<(())>){({}<{}>({})<>)((<>))}>{}{{}(<(({}){})>)}{}([][()])})>{()(<{}>)}{}{}<><([]){{}({}<>)<>([])}>{}<>)}<>)

Essayez-le en ligne!

Explication

([])                                                                 Push stack height (starts main loop if list nonempty)
     {                                                       }       Do while the last iteration involved at least one crush:
      <{}>                                                           Remove crush indicator
           <(...)>                                                   Do a crush iteration
                  {()(<{}>)}                                         Evaluate to 1 if list was changed
                            {}{}                                     Remove zeroes
                                <>                        <>         On other stack:
                                  <([]){{}        ([])}>{}           Do while stack is nonempty:
                                          ({}<>)<>                   Move to first stack
          (                                                 )        Push 1 if crush worked, 0 otherwise
    (                                                         <>)    Push sum of results on other stack and implicitly print

La fonction d'écrasement évalue le nombre de paires d'éléments qui ont été écrasés ensemble:

([][()]){[{}]                                                            ([][()])}    Do while stack height isn't 1:
              ({}[({})]      )                                                        Calculate difference between top two elements
                       <(())>                                                         Push a 1 below difference
                              {                    }                                  If difference was nonzero (don't crush this pair)
                               ({}    ({})<>)                                         Reconstruct top element and place on other stack
                                  <{}>       ((<>))                                   Push zeros to exit this conditional and skip next
             <                                      >{}                               Evaluate as zero
                                                       {              }{}             If difference was zero (crush this pair):
                                                        {}                            Evaluate as previously pushed 1
                                                          (<(({}){})>)                Double top of stack

Java 8, 120 octets

Un lambda de List<Long>à Integer. La liste d'entrée doit implémenter remove(int)(par exemple ArrayList). Attribuer à Function<List<Long>, Integer>.

l->{int c=-1,i,f=1;for(;f>0;c++)for(f=i=0;++i<l.size();)if(l.get(i)-l.get(i-1)==0)l.set(i-=f=1,2*l.remove(i));return c;}

Essayez-le en ligne

Lambda non golfé

l -> {
    int
        c = -1,
        i,
        f = 1
    ;
    for (; f > 0; c++)
        for (f = i = 0; ++i < l.size(); )
            if (l.get(i) - l.get(i - 1) == 0)
                l.set(i -= f = 1, 2 * l.remove(i));
    return c;
}

ccompte le nombre d'écrasements jusqu'à présent, ireprésente l'index dans la liste et findique s'il faut continuer d'écraser la liste à la fin d'une itération. À l'intérieur des boucles, chaque paire adjacente est comparée. iest incrémenté sans condition, donc si un élément est supprimé par écrasement, iest décrémenté en premier pour annuler l'incrément. L'ancien élément est supprimé de la liste.

Remerciements

• Correction d'un bug grâce à Olivier Grégoire: test d'égalité en box

Perl 5 , 96 octets

94 code, 2 pour -pa

do{$\++;$l=@F;for($i=0;++$i<@F;){$F[$i]==$F[$i-1]&&splice@F,$i,2,$F[$i--]*2}}while$l!=@F}{$\--

Essayez-le en ligne!

JavaScript (ES6), 70 octets

f=(a,j=m=0,t=[])=>a.map(e=>t[e==t[j-1]?(e*=m=2,j-1):j++]=e)&&m&&1+f(t)

Explication:

f=(
  a,                  //the input
  j=m=0,              //j is the index into t; m starts out falsey
  t=[]                //t will hold the crushed array
)=>
  a.map(e=>           //for each element in the array
    t[e==t[j-1] ?     //if the element repeats:
      (e*=m=2,        //... multiply it by two, set m to truthy,
       j-1) :         //... and index the previous element of t.
      j++             //else append to t, and increment its index.
    ]=e               //set this index of t to the current value of e
  ) &&                //map is always truthy
  m &&                //if m is falsey, return 0
  1+f(t)              //else return 1 plus the recurse on t

Cas de test:

f=(a,j=m=0,t=[])=>a.map(e=>t[e==t[j-1]?(e*=m=2,j-1):j++]=e)&&m&&1+f(t)

console.log(f([1])) // 0
console.log(f([1,1])) // 1
console.log(f([2,1,1])) // 2
console.log(f([4,2,1,1])) // 3
console.log(f([2,2,2,1,1])) // 3
console.log(f([0,0,0,0])) // 1
console.log(f([4,0,0,0,4])) // 1
console.log(f([4,0,0,0,0,4])) // 1
console.log(f([])) // 0

Python 2 , 112 110 108 107 105 100 octets

Edit: enregistré 2 octets en supprimant ordans l'instruction return

Edit: économisé 2 octets en ayant icomme index du deuxième des deux éléments à accéder

Edit: sauvé 1 octet grâce à @ Mr.Xcoder

Edit: économisé 7 octets grâce à @jferard

def f(x):
 i=e=1
 while x[i:]:
	if x[~-i]==x[i]:del x[i];i-=1;x[i]*=2;e=2
	i+=1
 return~-e and-~f(x)

Essayez-le en ligne!

JavaScript (ES6), 83 octets

f=([x,y,...a],b=[],c)=>1/x?x==y?f([x+y,...a],b,1):f([y,...a],[...b,x],c):c?1+f(b):0

Explication: Les éléments sont extraits récursivement du tableau d'origine et des valeurs uniques sont ajoutées à btandis cqu'un indicateur indique si le tableau a été correctement écrasé.

J, 54 octets

[:<:@#[:".@":@(,`(+:@[,}.@])@.({.@]=[))/^:a:@".@":_,|.

Essayez-le en ligne!

Pas mon meilleur golf par tous les moyens. Il doit sûrement y avoir un meilleur moyen de convertir une liste avec un élément en un atome.

Explication

crush =. ,`(+:@[ , }.@])@.({.@] = [)/
times =. <:@# [: ".@":@crush^:a:@".@": _ , |.

écraser

Cela écrase un tableau une fois. Il faut lui donner le tableau à l' envers car l'insert de J fonctionne de droite à gauche (quelque chose que j'ai appris aujourd'hui). Cela n'a pas d'importance particulière, car tout ce dont nous avons besoin pour la sortie est le nombre de fois que nous pouvons écraser le tableau.

,`(+:@[ , }.@])@.({.@] = [)/
                           /  Fold/reduce from the right
                  {.@] = [    Head of the running array equals the left argument?
   +:@[ ,                     If so, prepend double the argument to 
          }.@]                the array minus its head
,                             Else, prepend the left argument.

fois

C'est assez simple: appliquez l'écrasement au tableau jusqu'à ce que notre résultat converge, mais il y a quelques problèmes que j'ai dû traiter avec ce résultat en beaucoup plus de code que prévu.

Premièrement, lorsque l'écrasement se réduit à un seul élément, cet élément se trouve en fait dans une liste à un élément (c'est-à-dire qu'il n'est pas atomique), de sorte que la fonction est à nouveau appliquée , ce qui entraîne un comptage excessif. Pour résoudre ce problème, j'ai utilisé un hack que j'ai trouvé pour réduire une seule liste d'éléments en un atome qui est ".@":(convertir en chaîne puis évaluer).

Deuxièmement, des crusherreurs sur la liste vide. Je pense que vous pouvez définir comment une fonction doit se comporter lors de la réception d'une entrée vide avec insert ( /), mais je n'ai rien trouvé après un aperçu rapide, donc j'utilise une autre solution. Cette solution consiste à ajouter _(infini) à la liste car elle n'affectera jamais le nombre de fois où le tableau est écrasé ( _ > 2^64). Cependant , il en résulte une liste d'éléments unique consistant _en étant donné la liste vide, donc nous avons besoin de se convertir à un atome de nouveau avant d' écraser.

<:@# [: ".@":@crush^:a:@".@": _ , |.
                                  |.  Reverse input
                              _ ,     Prepend infinity
                        ".@":         Convert single-element list to atom
              crush                   Crush the list and after
        ".@":                         Convert single-element list to atom 
                   ^:a:               until it converges, storing each 
                                      iteration in an array
<:@#                                  Length of the resulting list minus 1

Gelée , 21 octets

ṪḤ,⁼?⁹⁸;µ/Ḋ$¹L’$?ÐĿL’

Essayez-le en ligne!

R , 142 octets

f=function(l,r=l,k=0,T=1)"if"(sum(l|1)<2,k,{while(T<sum(r|1))"if"(r[T]-r[T+1],T<-T+1,{r<-r[-T]
r[T]<-2*r[T]})
"if"(all(r==l),k,f(r,r,k+1,1))})

Horrible, je suis sûr qu'il existe un moyen plus intelligent.

Les entiers R sont en fait tous au maximum 2^31-1.

Essayez-le en ligne!