#x86 Machine Code, 36 bytes
52
8B 12
8D 44 91 FC
8B F9
8D 71 04
3B F0
77 10
A7
75 F9
83 EF 04
4A
4A
A5
3B F8
75 FB
97
EB E7
58
89 10
C3
The above bytes of machine code define a function that takes an array as input, collapses adjacent duplicates in-place, and returns to the caller without returning a result. It follows the __fastcall
calling convention, passing the two parameters in the ECX
and EDX
registers, respectively.
The first parameter (ECX
) is a pointer to the first element in the array of 32-bit integers (if the array is empty, it can point anywhere in memory). The second parameter (EDX
) is a pointer to a 32-bit integer that contains the length of the array.
The function will modify the elements of the array in-place, if necessary, and also update the length to indicate the new length of the collapsed array. This is a bit of an unusual method for taking input and returning output, but you really have no other choice in assembly language. As in C, arrays are actually represented in the language as a pointer to the first element and a length. The only thing a bit weird here is taking the length by reference, but if we didn't do that, there would be no way to shorten the array. The code would work fine, but the output would contain garbage, because the caller wouldn't know where to stop printing elements from the collapsed array.
Ungolfed assembly mnemonics:
; void __fastcall CollapseAdjacentDuplicates(int * ptrArray, int * ptrLength);
; ECX = ptrArray ; ECX = fixed ptr to first element
; EDX = ptrLength
push edx ; save pointer to the length
mov edx, [edx] ; EDX = actual length of the array
lea eax, [ecx+edx*4-4] ; EAX = fixed ptr to last element
FindAdjacentPairs:
mov edi, ecx ; EDI = ptr to element A
lea esi, [ecx+4] ; ESI = ptr to element B
FindNext:
cmp esi, eax ; is ptr to element B at end?
ja Finished ; if we've reached the end, we're finished
cmpsd ; compare DWORDs at ESI and EDI, set flags, and increment both by 4
jne FindNext ; keep looping if this is not a pair
; Found an adjacent pair, so remove it from the array.
sub edi, 4 ; undo increment of EDI so it points at element A
dec edx ; decrease length of the array by 2
dec edx ; (two 1-byte DECs are shorter than one 3-byte SUB)
RemoveAdjacentPair:
movsd ; move DWORD at ESI to EDI, and increment both by 4
cmp edi, eax ; have we reached the end?
jne RemoveAdjacentPair ; keep going until we've reached the end
xchg eax, edi ; set new end by updating fixed ptr to last element
jmp FindAdjacentPairs ; restart search for adjacent pairs from beginning
Finished:
pop eax ; retrieve pointer to the length
mov [eax], edx ; update length for caller
ret
The implementation was inspired by my C++11 answer, but meticulously rewritten in assembly code, optimizing for size. Assembly is a much better golfing language. :-)
Note: Because this code uses the string instructions, is does assume that the direction flag is clear (DF
== 0). This is a reasonable assumption in most operating environments, as the ABI typically requires that DF is clear. If this cannot be guaranteed, then a 1-byte CLD
instruction needs to be inserted at the top of the code.