Vamos a definir el proceso de aplastar una serie de números. En un flechazo leemos la matriz de izquierda a derecha. Si en un momento nos encontramos con dos del mismo elemento en una fila, eliminamos el primero y duplicamos el segundo. Por ejemplo, aquí está el proceso de aplastar la siguiente matriz

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

El mismo elemento se puede plegar varias veces, por ejemplo, [1,1,2]se convierte [4]cuando se aplastan.

Llamaremos a una matriz inquebrantable cuando el proceso de aplastar esa matriz no la cambie. Por ejemplo, [1,2,3]todavía está [1,2,3]después de ser aplastado.

Su tarea es tomar una matriz y determinar la cantidad de aplastamientos necesarios para que no se pueda aplastar. Solo necesita admitir enteros en el rango de 0 a 2 ³² -1

Este es el código de golf, por lo que las respuestas se puntuarán en bytes, siendo mejores menos bytes.

Casos de prueba

[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

Conjunto x86 (64 bits), 66 65 bytes

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

Las instrucciones de cadena fueron útiles. Tener que corregir los errores fuera de uno en un entorno de 64 bits no fue así.

Código fuente completamente comentado:

.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

Puedo intentar hacer esto en 32 bits, aunque solo sea por diversión, ya que esos prefijos REX realmente me mataron.

Editar: se eliminó un byte reemplazando lodsq con add,% rdx con% rax, y contrayendo dos cld en uno.

Pyth , 22 bytes

tl.uu?&GqeGH+PGyH+GHN[

Verifique todos los casos de prueba.

Haskell , 66 bytes

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)

Pruébalo en línea!

Explicación

fes una función que aplasta una lista. Realiza el flechazo como se describe en la pregunta. ges una función que cuenta el número de enamoramientos. Si f x==x, de lo g x=0contrario g x=1+g(f x).

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

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

Pruébalo en línea! / con encabezado / pie de página que verifica todos los casos de prueba

Toma una lista en la pila y da como resultado un número en la pila.

Implementación bastante sencilla, para ser honesto. Aplasta una lista comenzando con un centinela -1, recorriendo la lista, empujando cada elemento y agregándolo al elemento debajo de él si son iguales. Al final cortamos el -1. Solo aplastamos números iguales y todos los números del problema no son negativos, por lo que el centinela -1 no afectará el proceso de aplastamiento. Con el aplastamiento implementado, solo es cuestión de contar las iteraciones hasta su punto fijo.

Explicación:

{            }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 pudiéramos asumir que la entrada no está vacía, no necesitaríamos el centinela y podríamos recortar 2 bytes: {(\ε=k+x}]}IL(

Otro dato divertido: solo perdemos 2 bytes si nos obligamos a usar solo ASCII: {1m\{=k+x}e]1>}IL(

JavaScript (ES6), 86 bytes

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

No golfista y explicado

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

Pruebas

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 bytes

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

Pruébalo en línea!

Brain-Flak , 144 bytes

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

Pruébalo en línea!

Explicación

([])                                                                 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 función de aplastamiento evalúa el número de pares de elementos que fueron aplastados juntos:

([][()]){[{}]                                                            ([][()])}    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 bytes

Una lambda de List<Long>a Integer. La lista de entrada debe implementarse remove(int)(por ejemplo ArrayList). Asignar a 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;}

Pruébalo en línea

Lambda sin 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;
}

ccuenta el número de aplastamientos hasta el momento, ies el índice en la lista e findica si se debe continuar aplastando la lista cuando finaliza una iteración. Dentro de los bucles, se compara cada par adyacente. ise incrementa incondicionalmente, por lo que si un elemento se elimina por aplastamiento, ise disminuye primero para cancelar el incremento. El primer elemento se elimina de la lista.

Expresiones de gratitud

• Corrección de errores gracias a Olivier Grégoire: prueba de igualdad en caja

Perl 5 , 96 bytes

94 código, 2 para -pa

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

Pruébalo en línea!

JavaScript (ES6), 70 bytes

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)

Explicación:

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

Casos de prueba:

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 bytes

Editar: guardado 2 bytes al eliminar oren la declaración de devolución

Editar: guardado 2 bytes al tener icomo índice el segundo de los dos elementos a los que se debe acceder

Editar: guardado 1 byte gracias a @ Mr.Xcoder

Editar: guardado 7 bytes gracias a @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)

Pruébalo en línea!

JavaScript (ES6), 83 bytes

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

Explicación: Los elementos se extraen de forma recursiva de la matriz original y se agregan valores únicos, bmientras que ces un indicador para indicar si la matriz se ha triturado con éxito.

J, 54 bytes

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

Pruébalo en línea!

No es mi mejor golf de ninguna manera. Seguramente tiene que haber una mejor manera de convertir una lista con un elemento en un átomo.

Explicación

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

aplastar

Esto aplasta una matriz una vez. Es necesario darle la matriz a la inversa ya que la inserción de J funciona de derecha a izquierda (algo que aprendí hoy). Esto no importa particularmente, ya que todo lo que necesitamos es la cantidad de veces que podemos aplastar la matriz.

,`(+:@[ , }.@])@.({.@] = [)/
                           /  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.

veces

Esto es bastante sencillo: aplique el aplastamiento a la matriz hasta que nuestro resultado converja, pero hay algunos problemas que tuve que resolver con ese resultado en mucho más código del que esperaba.

Primero, cuando el aplastamiento se reduce a un solo elemento, ese elemento está realmente en una lista de un elemento (es decir, no es atómico), por lo que la función se aplica nuevamente, lo que resulta en un conteo excesivo. Para solucionar esto, utilicé un truco que se me ocurrió para reducir una lista de elementos únicos a un átomo que es ".@":(convertir a cadena y luego evaluar).

Segundo, crusherrores en la lista vacía. Yo creo que se puede definir como una función debe comportarse en recibir una entrada de vacío con inserción ( /), pero no pude encontrar nada después de un rápido vistazo, así que estoy usando otra solución. Esta solución alternativa es anteponer _(infinito) a la lista, ya que nunca afectará la cantidad de veces que se aplasta la matriz ( _ > 2^64). Sin embargo , esto da como resultado una lista de un solo elemento que consiste en _cuando se le da la lista vacía, por lo que debemos convertir a un átomo nuevamente antes de la trituración.

<:@# [: ".@":@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

Jalea , 21 bytes

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

Pruébalo en línea!

R , 142 bytes

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, estoy seguro de que hay una manera más inteligente.

Los enteros R son en realidad a lo sumo 2^31-1.

Pruébalo en línea!