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.
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, because2**64-1>Number.MAX_SAFE_INTEGER
? – None – 2017-08-27T07:07:16.4402@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 only1
. 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