How hard can I crush my array?



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


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

Post Rock Garf Hunter

Posted 2017-08-26T18:37:24.910

Reputation: 55 382

What's the maximum input size we must support? – Jakob – 2017-08-26T18:53:47.513

5Should [1,1,2,4,8] return 1 or 4? – MooseBoys – 2017-08-27T00:02:17.177

@MooseBoys It is 1. – Post Rock Garf Hunter – 2017-08-27T00:30:44.387

Does the requirement that we must support all integers in the range from 0 to (1 << 64) - 1 invalidate all JavaScript answers, because 2**64-1>Number.MAX_SAFE_INTEGER? – None – 2017-08-27T07:07:16.440

2@ThePirateBay Ok I'll lower it. But for the record I think that Javascript is rather dumb in the way it handles ints. – Post Rock Garf Hunter – 2017-08-27T07:09:50.793

@WheatWizard. Well, theoretically, one may implement a BigInt class, but it will require more than thousand bytes I suppose. – None – 2017-08-27T07:30:13.970

2If you tried to crush [1 1 1 2] you would end up with [2 1 2] if you follow the spec exactly as written, but you could end up with [1 4] if you do it more intelligently. What should [1 1 1 2] result in? – latias1290 – 2017-08-27T13:02:38.010

4@latias1290. "In a crush we read the array left to right." – None – 2017-08-27T14:26:17.347

11Maybe it's just me but it took me a second to figure out why 0,0,0,0 was only 1. It might be an idea to explicitly mention somewhere that we're counting the number of times we have to loop through an array to fully crush it and not, as I initially thought, the total number of times we crush 2 numbers together. – Shaggy – 2017-08-27T17:06:28.350

@ThePirateBay TFW you "reject irrelevant information" then realize how relevant it truly is. – Magic Octopus Urn – 2017-08-27T21:49:37.397

1Shouldn't [4,0,0,0,4] give out 2 instead of 1? One crush to [4,0,0,4] and another to [4,0,4]. – Fabian Röling – 2017-08-28T12:46:53.377

@Fabian No it doesn't. It is crushed left to right so it only takes one crush. Try working it out on paper step by step. – Post Rock Garf Hunter – 2017-08-28T16:07:11.307

Oh, now I understand what you mean. It goes from [4,0,0,0,4] directly to [4,0,4]. I somehow thought that for example [4,0,0,0,0,4] would become [4,0,0,4] in the first step. Probably I played too much 2048. ;) – Fabian Röling – 2017-08-28T18:10:13.517



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

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
/* return value */
xor %eax, %eax
/* save our length in rcx */
push %rdi
pop %rcx
/* 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
/* make sure we're going forward */
/* 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. */
/* 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
/* 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 */

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.


Posted 2017-08-26T18:37:24.910

Reputation: 836


Pyth, 22 bytes


Verify all testcases.

Leaky Nun

Posted 2017-08-26T18:37:24.910

Reputation: 45 011

Jeebus! Do you first use a transpiler and then hand-edit it, or do you actually write Pyth from the beginning? – oligofren – 2017-08-27T11:02:48.967

2@oligofren the latter. – Leaky Nun – 2017-08-27T11:17:07.550


Haskell, 66 bytes

f x=x
g x|f x==x=0|1>0=1+g(f x)

Try it online!


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

Post Rock Garf Hunter

Posted 2017-08-26T18:37:24.910

Reputation: 55 382

1Shave off a byte by changing g(f x) to g$f x – ApproachingDarknessFish – 2017-08-27T01:21:07.420

3@ApproachingDarknessFish That doesn't work because + has higher precedence than $ – Post Rock Garf Hunter – 2017-08-27T01:36:49.227

Ah, my bad. Funny that I've never run into that error before. – ApproachingDarknessFish – 2017-08-27T01:43:56.463


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


Try it online! / with header/footer that check all test cases

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.


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


Posted 2017-08-26T18:37:24.910

Reputation: 741


JavaScript (ES6), 86 bytes


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



;[ [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) ))

Justin Mariner

Posted 2017-08-26T18:37:24.910

Reputation: 4 746

a.length>n is the same as a[n]!=[]._. In this case (since all items in the array are numbers larger than -1), it is the same as a[n]>-1. Also, a[i]==a[++i]&&x is the same as a[i]-a[++i]||x. – Luke – 2017-08-27T13:56:44.583

I think 1/a[i] also works to save another byte. – Neil – 2017-08-27T17:56:40.773


JavaScript, 67 bytes


Try it online!


Posted 2017-08-26T18:37:24.910


Nice! I thought I had golfed this as low as possible. – Rick Hitchcock – 2017-08-27T10:10:25.003


Brain-Flak, 144 bytes


Try it online!


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


Posted 2017-08-26T18:37:24.910

Reputation: 9 181


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

Ungolfed lambda

l -> {
        c = -1,
        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.


  • Bugfix thanks to Olivier Grégoire: boxed equality test


Posted 2017-08-26T18:37:24.910

Reputation: 2 428

Doesn't work when the longs don't hit the valueOf cache. Example: {128L, 128L}. That's because of l.get(i)==l.get(i-1), which should be replaced by l.get(i).equals(l.get(i-1)). – Olivier Grégoire – 2017-08-27T14:15:17.853

Wow, embarassing...luckily l.get(i)-l.get(i-1)==0 will work. Thanks! – Jakob – 2017-08-27T15:02:55.630


Python 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

Edit: saved 7 bytes thanks to @jferard

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

Try it online!

Halvard Hummel

Posted 2017-08-26T18:37:24.910

Reputation: 3 131


JavaScript (ES6), 83 bytes


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.


Posted 2017-08-26T18:37:24.910

Reputation: 95 035


JavaScript (ES6), 70 bytes



  a,                  //the input
  j=m=0,              //j is the index into t; m starts out falsey
  t=[]                //t will hold the crushed array
)=>>           //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:


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

Rick Hitchcock

Posted 2017-08-26T18:37:24.910

Reputation: 2 461

1Hm.. It seems that we came up with the pretty much same idea :). After golfing mine answer I realized it is very similar to yours. – None – 2017-08-27T04:22:01.657


Perl 5, 96 bytes

94 code, 2 for -pa


Try it online!


Posted 2017-08-26T18:37:24.910

Reputation: 7 671


J, 54 bytes


Try it online!

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.


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


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.


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


Posted 2017-08-26T18:37:24.910

Reputation: 3 526


Jelly, 21 bytes


Try it online!

Erik the Outgolfer

Posted 2017-08-26T18:37:24.910

Reputation: 38 134


R, 142 bytes


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

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

Try it online!


Posted 2017-08-26T18:37:24.910

Reputation: 21 077