[Question]
  [
Lets define the process of crushing an array of numbers. In a crush we read the array left to right. If at a point we encounter two of the same element in a row we remove the first one and double the second one. For example here is the process of crushing the following array
```
[5,2,2,3]
 ^
[5,2,2,3]
   ^
[5,2,2,3]
     ^
[5,4,3]
   ^
[5,4,3]
     ^
```
The same element can be collapsed multiple times, for example `[1,1,2]` becomes `[4]` when crushed.
We will call an array uncrushable when the process of crushing that array does not change it. For example `[1,2,3]` is still `[1,2,3]` after being crushed.
Your task is to take an array and determine the number of crushes required to make it uncrushable. You need only support integers on the range of **0** to **232-1**
This is [code-golf](/questions/tagged/code-golf "show questions tagged 'code-golf'") so answers will be scored in bytes with less bytes being better.
## Test Cases
```
[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
```
  
[Answer]
# x86 assembly (64-bit), 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
```
String instructions were helpful. Having to correct for off-by-one errors in a 64-bit environment was not.
Fully commentated source code:
```
.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
```
I may try doing this in 32-bit, if only for fun, since those REX prefixes really killed me.
Edit: shaved one byte off by replacing lodsq with add, %rdx with %rax, and collapsing two cld's into one.
[Answer]
# [Pyth](https://github.com/isaacg1/pyth), 22 bytes
```
tl.uu?&GqeGH+PGyH+GHN[
```
[Verify all testcases.](http://pyth.herokuapp.com/?code=tl.uu%3F%26GqeGH%2BPGyH%2BGHN%5B&test_suite=1&test_suite_input=%5B1%5D%0A%5B1%2C1%5D%0A%5B2%2C1%2C1%5D%0A%5B4%2C2%2C1%2C1%5D%0A%5B2%2C2%2C2%2C1%2C1%5D%0A%5B0%2C0%2C0%2C0%5D%0A%5B4%2C0%2C0%2C0%2C4%5D%0A%5B%5D&debug=0)
[Answer]
# [Haskell](https://www.haskell.org/), 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)
```
[Try it online!](https://tio.run/##y0gszk7Nyfn/P00j0SrJqkKzJtHWNsk2TSVRO9GqosbQzsA20SpNAyTDlaZQYVvBla5QUQNi2VbYGoDlDbXTNYACmv9zEzPzbAuKMvNKVNKjDXTAMPY/AA "Haskell – Try It Online")
## Explanation
`f` is a function that crushes a list. It performs the crush as desribed in the question. `g` is a function that counts the number of crushes. If `f x==x`, `g x=0` otherwise `g x=1+g(f x)`.
[Answer]
# [Paradoc](https://github.com/betaveros/paradoc) (v0.2.10), 16 bytes (CP-1252)
```
{—1\ε=k+x}]»}IL(
```
[Try it online!](https://tio.run/##K0gsSkzJT/4fbahgqGCkYKJgoQBnxf6vftQwxTDm3FbbbO2K2thDu2s9fTT@/wcA "Paradoc – Try It Online") / with header/footer that check all [test cases](https://tio.run/##K0gsSkzJT/4fHW0YqxBtqAAijRQgtIkCjGWkYARnGyiAIVgewjZBYkN4EKOAWkwULGJjuaqtEvyVFHTtFJT8/1c/aphiGHNuq222dkVt7KHdtZ4@Gv8DalP/AwA)
Takes a list on the stack, and results in a number on the stack.
Pretty straightforward implementation, to be quite honest. Crushes a list by starting with a sentinel -1, looping through the list, pushing each element and adding it to the element beneath it iff they're equal. At the end we cut off the -1. We only crush equal numbers together and all the problem's numbers are nonnegative, so the -1 sentinel won't affect the crushing process. With crushing implemented, it's only a matter of counting iterations to its fixed point.
Explanation:
```
{            }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
```
If we could assume the input were nonempty, we wouldn't need the sentinel and could shave 2 bytes: `{(\ε=k+x}]}IL(`
Another fun fact: we only lose 2 bytes if we force ourselves to only use ASCII: `{1m\{=k+x}e]1>}IL(`
[Answer]
# 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 and 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
```
## 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}
```
[Answer]
# 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
```
[Try it online!](https://tio.run/##Tc7BCoMwDAbgV9kupZ1RbPG0ke1BSsFgdWi1lTl2kL175xTHCCRfksvf0Yum6tGOz9QHW8fYIOGVsoFGvsBpp20qzRHpZpPkzOmEMypYbsIggUOLesbcCMZmxhruRCJjFfwU@jrrw51rLQ1oCd@uYJsF7FKgfs5hrfW/ufjzthmzJ2s4iXcusi60vjyU4hI/)
[Answer]
# [Brain-Flak](https://github.com/DJMcMayhem/Brain-Flak), 144 bytes
```
([])({<{}>(<(([][()]){[{}]<({}[({})]<(())>){({}<{}>({})<>)((<>))}>{}{{}(<(({}){})>)}{}([][()])})>{()(<{}>)}{}{}<><([]){{}({}<>)<>([])}>{}<>)}<>)
```
[Try it online!](https://tio.run/##LY2xCgMxDEN/5UZp6HCdjX8kZLgbCqWlQ1fhb8/JpSQyecJSzu/x/Nwe7@O1FsYkFKpEwDDASQ3VDKiGRb9AJmX4LdqLJODBSpVUHbbtmyzjv8goEJ1q2/mM/rETDe5p7BJDa6371mff9gs "Brain-Flak – Try It Online")
### Explanation
```
([])                                                                 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
```
The crush function evaluates to the number of pairs of items that were crushed together:
```
([][()]){[{}]                                                            ([][()])}    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
```
[Answer]
# Java 8, 120 bytes
A lambda from `List<Long>` to `Integer`. Input list must implement `remove(int)` (e.g. `ArrayList`). Assign to `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;}
```
[Try It Online](https://tio.run/##jZNNa@MwEIbPzq@Yo7SxRRJ6sqNACRQK2VOPpQetKrtKZclIcpZs8G/PjuJAQkk/jA0j5plB7zvjrdiJwnXKbl/fj13/x2gJ0ogQ4LfQFg6TrPN6J6KCEEXEZK2tMLDFMtZHbVjdWxm1s@zhHCwvuY0Ocblxtlnl8GijapRfgfR9eFu73kbgR1OsDhojyYt5rvOaz6vaeVLVq1klp1OaDjXXfFZNp3ppWND/FKEV1TUxrFGRaFqcg2JOOZ9RZE4njr3yxS/DvGrdTiFIK69i7y3Iajhm1QSljXrPynZOv0KLqslT9No2zy8gfBNoMiH7IOqWRpQmggrAr9y5917sAwvRK9ESq/5CQp9fsHfqmh3mZsgn8MmD2Ry@JhYn4jvqDomfkYsz@TN6hsTl@@4G1/Tdl/SA3gw0GcRa0ZGPfpalCMn3T4nLUMoSTR856YxRMl6x41jYekw4H1h0qZTQVJE2JMMFBHJr2iDWOG0ox6GPS5I97UNULXN9ZPjb2Ggsuaw7E11n9uRUh8uYJE7wHY7/AQ)
## Ungolfed lambda
```
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;
}
```
`c` counts the number of crushes so far, `i` is the index into the list, and `f` indicates whether to continue crushing the list when an iteration finishes. Inside the loops, each adjacent pair is compared. `i` is incremented unconditionally, so if an element is removed by crushing, `i` is decremented first to cancel out the increment. The former element is removed from the list.
## Acknowledgments
* Bugfix thanks to Olivier Grégoire: boxed equality test
[Answer]
# [Perl 5](https://www.perl.org/), 96 bytes
94 code, 2 for `-pa`
```
do{$\++;$l=@F;for($i=0;++$i<@F;){$F[$i]==$F[$i-1]&&splice@F,$i,2,$F[$i--]*2}}while$l!=@F}{$\--
```
[Try it online!](https://tio.run/##JYzBCgIhFAB/ZYPHUukLFfZkwp689QXlIcrogaTsBh0Wf72XFXMYmMOUOKWB@ZoXOAlhIbnR21ue1kBOWSGA9i1sFvBHoODcz6hD388l0SWOXgJJI/8dw9bU@rpTipBWbVXbFpHZdF90p9@5PCk/ZsbDsFNaMZbzBw "Perl 5 – Try It Online")
[Answer]
# 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)
```
**Explanation:**
```
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
```
**Test Cases:**
```
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
```
[Answer]
# [Python 2](https://docs.python.org/2/), 112 110 108 107 105 100 bytes
**Edit:** saved 2 bytes by removing `or` in return statement
**Edit:** saved 2 bytes by having `i` as the index of the second of the two elements to be accessed
**Edit:** saved 1 byte thanks to [@Mr.Xcoder](https://codegolf.stackexchange.com/users/59487/mr-xcoder)
**Edit:** saved 7 bytes thanks to [@jferard](https://codegolf.stackexchange.com/users/72753/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)
```
[Try it online!](https://tio.run/##VY9NCoMwEIXXzSlmqW0ETV0pOYmEInWCAYliIrUbr24nai1lFvO9Nz/JDG/f9lasa4MadDTHBQMjUWYMXq3pEObKFKpgF6MJl8QoKclSRYNdqKnSJDIrA12lKFEKar2F8RH9NNolQahtkyxh9@rR@cezduhAQhVVmeJpzClzoiyQ4BuLwDk/1H2viD@d8i2OuXxXPD90WKyY7kc43@T0JTd1Hoz9mY5OG0ZjPR1/mvG3df0A)
[Answer]
## 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
```
Explanation: The elements are recursively extracted from the original array and unique values are appended to `b` while `c` is a flag to indicate whether the array had been successfully crushed.
[Answer]
# J, 54 bytes
```
[:<:@#[:".@":@(,`(+:@[,}.@])@.({.@]=[))/^:a:@".@":_,|.
```
[Try it online!](https://tio.run/##y/r/P03BVk8h2srGykE52kpJz0HJykFDJ0FD28ohWqdWzyFW00FPoxpI20ZraurHWSVaOYAVxevU6HGlJmfkK6QpaBgoqCgYaCr4OekppOYWlFQqFKeWwCRNFIwUDBUMYVwDCPz/HwA)
Not my best golf by any means. Surely there has to be a better way of converting a list with one item to an atom.
# Explanation
```
crush =. ,`(+:@[ , }.@])@.({.@] = [)/
times =. <:@# [: ".@":@crush^:a:@".@": _ , |.
```
### crush
This crushes an array once. It needs to be given the array in *reverse* since J's insert works right-to-left (something I learned today). This doesn't particularly matter, since all we need to output is the number of times we can crush the array.
```
,`(+:@[ , }.@])@.({.@] = [)/
                           /  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.
```
### times
This is fairly straightforward: apply crush to the array until our result converges, but there are a few issues I had to deal with that result in much more code than I anticipated.
First, when crushing reduces to a single element, that element is actually in a one item list (i.e. it is nonatomic), so the function is applied *again* resulting in overcounting. To fix this, I used a hack I came up with to reduce a single element list to an atom which is `".@":` (convert to string and then evaluate).
Second, `crush` errors on the empty list. I *think* you can define how a function should behave on receiving empty input with insert (`/`), but I couldn't find anything after a cursory look, so I'm using another workaround. This workaround is to prepend `_` (infinity) to the list since it will never affect the number of times the array is crushed (`_ > 2^64`). *However*, this results in a single element list consisting of `_` when given the empty list, so we need to convert to an atom *again* before crushing.
```
<:@# [: ".@":@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
```
[Answer]
# [Jelly](https://github.com/DennisMitchell/jelly), 21 bytes
```
ṪḤ,⁼?⁹⁸;µ/Ḋ$¹L’$?ÐĿL’
```
[Try it online!](https://tio.run/##y0rNyan8///hzlUPdyzRedS4x/5R485HjTusD23Vf7ijS@XQTp9HDTNV7A9POLIfxPr//3@0kQ4IGuoYxgIA "Jelly – Try It Online")
[Answer]
# [R](https://www.r-project.org/), ~~142~~ 75 bytes
```
function(l){while(any(z<-which(!diff(l)))){l[z]=l[z]*2
l=l[-z-1]
F=F+1}
+F}
```
[Try it online!](https://tio.run/##K/qfpmCjq/A/rTQvuSQzP08jR7O6PCMzJ1UjMa9So8pGF8hJztBQTMlMSwPKAUF1TnRVrC2I0DLiygEydKt0DWO53GzdtA1rubTdav@naSRrGGpqcoFpHRjLSAfBNtFB5hnpGKHwDXTAEK4WwjdB48NEMvNKUtNTizSA6v8DAA "R – Try It Online")
]