Vamos definir o processo de esmagar uma matriz de números. Em uma paixonite, lemos a matriz da esquerda para a direita. Se em um ponto encontramos dois elementos iguais seguidos, removemos o primeiro e duplicamos o segundo. Por exemplo, aqui está o processo de esmagar a seguinte matriz

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

O mesmo elemento pode ser dobrado múltiplas vezes, por exemplo, [1,1,2]torna-se [4]quando esmagado.

Nós chamaremos uma matriz de inutilizável quando o processo de esmagar essa matriz não a alterar. Por exemplo, [1,2,3]ainda está [1,2,3]depois de ser esmagado.

Sua tarefa é obter uma matriz e determinar o número de esmagamentos necessários para torná-la inescrutável. Você precisa apenas suportar números inteiros no intervalo de 0 a 2 ³² -1

Isso é código-golfe, então as respostas serão pontuadas em bytes, com menos bytes sendo melhores.

Casos de teste

[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

montagem 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

As instruções das cordas foram úteis. Ter que corrigir erros off-by-one em um ambiente de 64 bits não era.

Código fonte totalmente 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

Eu posso tentar fazer isso em 32 bits, mesmo que por diversão, já que esses prefixos REX realmente me mataram.

Edit: raspou um byte, substituindo lodsq por add,% rdx por% rax e recolhendo dois cld's em um.

Pitão , 22 bytes

tl.uu?&GqeGH+PGyH+GHN[

Verifique todos os casos de teste.

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)

Experimente online!

Explicação

fé uma função que esmaga uma lista. Ele executa a quebra conforme descrito na pergunta. gé uma função que conta o número de esmagamentos. Se f x==x, g x=0de outro modo g x=1+g(f x).

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

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

Experimente online! / com cabeçalho / rodapé que verifica todos os casos de teste

Pega uma lista na pilha e resulta em um número na pilha.

Implementação bastante direta, para ser sincero. Esmaga uma lista começando com um sentinela -1, percorrendo a lista, pressionando cada elemento e adicionando-o ao elemento abaixo dela, se eles forem iguais. No final, cortamos o -1. Nós apenas esmagamos números iguais e todos os números do problema não são negativos, portanto a sentinela -1 não afetará o processo de esmagamento. Com a britagem implementada, é apenas uma questão de contar as iterações para seu ponto fixo.

Explicação:

{            }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

Se pudéssemos assumir que a entrada não era vazia, não precisaríamos do sentinela e poderíamos cortar 2 bytes: {(\ε=k+x}]}IL(

Outro fato interessante: só perdemos 2 bytes se forçarmos a usar apenas 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

Ungolfed e Explained

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

Testes

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

Experimente online!

Flacidez cerebral , 144 bytes

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

Experimente online!

Explicação

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

A função de esmagamento avalia o número de pares de itens que foram esmagados 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

Um lambda de List<Long>para Integer. A lista de entrada deve ser implementada remove(int)(por exemplo ArrayList). Atribuir 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;}

Experimente Online

Lambda ungolfed

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

cconta o número de esmagamentos até o momento, ié o índice na lista e findica se deve continuar esmagando a lista quando uma iteração terminar. Dentro dos loops, cada par adjacente é comparado. ié incrementado incondicionalmente; portanto, se um elemento é removido por esmagamento, ié decrementado primeiro para cancelar o incremento. O elemento anterior é removido da lista.

Agradecimentos

• Correção de erros graças a Olivier Grégoire: teste de igualdade em caixa

Perl 5 , 96 bytes

Código 94, 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}{$\--

Experimente online!

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)

Explicação:

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 teste:

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: salvou 2 bytes removendo orna declaração de retorno

Editar: salvou 2 bytes tendo icomo índice o segundo dos dois elementos a serem acessados

Edit: economizou 1 byte graças a @ Mr.Xcoder

Edit: salvou 7 bytes graças 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)

Experimente online!

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

Explicação: Os elementos são extraídos recursivamente da matriz original e os valores exclusivos são anexados a bwhile cé um sinalizador para indicar se a matriz foi esmagada com êxito.

J, 54 bytes

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

Experimente online!

Não é o meu melhor golfe, por qualquer meio. Certamente deve haver uma maneira melhor de converter uma lista com um item em um átomo.

Explicação

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

A paixão súbita

Isso esmaga uma matriz uma vez. Ele precisa receber a matriz ao contrário, pois a inserção de J funciona da direita para a esquerda (algo que aprendi hoje). Isso não importa particularmente, já que tudo o que precisamos é o número de vezes que podemos esmagar a 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.

vezes

Isso é bastante simples: aplique esmagamento na matriz até que nosso resultado converja, mas há alguns problemas que tive que lidar com esse resultado em muito mais código do que eu previa.

Primeiro, quando a trituração se reduz a um único elemento, na verdade, esse elemento está em uma lista de um item (ou seja, não é atômica), então a função é aplicada novamente, resultando em uma contagem excessiva. Para corrigir isso, usei um hack que criei para reduzir uma lista de elementos simples para um átomo que é ".@":(converter em string e depois avaliar).

Segundo, crusherros na lista vazia. Eu acho que você pode definir como uma função deve se comportar ao receber entrada vazia com insert ( /), mas não consegui encontrar nada depois de uma aparência superficial, por isso estou usando outra solução alternativa. Esta solução alternativa é anexada antecipadamente _(infinito) à lista, pois nunca afetará o número de vezes que a matriz é esmagada ( _ > 2^64). No entanto , isso resulta em uma lista de elementos únicos que consiste em _quando é fornecida a lista vazia, portanto, precisamos converter em um átomo novamente antes de esmagar.

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

Gelatina , 21 bytes

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

Experimente online!

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))})

Horrific, I am sure there's a more clever way.

R integers are actually all at most 2^31-1.

Try it online!