Collapse Adjacent Duplicates

Question

Challenge

Given a list of integers, return the list of these integers after repeatedly removing all pairs of adjacent equal items.

Note that if you have an odd-length run of equal numbers, one of them will remain, not being part of a pair.

Example:

[0, 0, 0, 1, 2, 4, 4, 2, 1, 1, 0]

First, you should remove 0, 0, 4, 4, and 1, 1 to get:

[0, 1, 2, 2, 0]

Now, you should remove 2, 2:

[0, 1, 0]

And this is the final result.

Test Cases

[] -> []
[1] -> [1]
[1, 1] -> []
[1, 2] -> [1, 2]
[11, 11, 11] -> [11]
[1, 22, 1] -> [1, 22, 1]
[-31, 46, -31, 46] -> [-31, 46, -31, 46]
[1, 0, 0, 1] -> []
[5, 3, 10, 10, 5] -> [5, 3, 5]
[5, 3, 3, 3, 5] -> [5, 3, 5]
[0, -2, 4, 4, -2, 0] -> []
[0, 2, -14, -14, 2, 0, -1] -> [-1]
[0, 0, 0, 1, 2, 4, 4, 2, 1, 1, 0] -> [0, 1, 0]
[3, 5, 4, 4, 8, 26, 26, 8, 5] -> [3]
[-89, 89, -87, -8, 8, 88] -> [-89, 89, -87, -8, 8, 88]

Scoring

This is code-golf, so the shortest answer in each language wins!

Answer 1

Jelly, 10 bytes

Œgœ^/€FµÐL

Try it online!

How it works

Œgœ^/€FµÐL  Main link. Argument: A (array)

       µ    Combine all links to the left into a chain.
Œg              Group all adjacent equal items.
    /€          Reduce each group by...
  œ^                symmetric multiset difference.
                In each step, this maps ([], n) to [n] and ([n], n) to [], so the
                group is left with a single item if its length is odd, and no items
                at all if its length if even.
      F         Flatten the resulting array of singleton and empty arrays.
        ÐL  Apply the chain until the results are no longer unique. Return the last
            unique result.

Answer 2

Mathematica 29 bytes

This repeatedly removes pairs of equal adjacent elements, a_,a_ until there are none left.

#//.{b___,a_,a_,c___}:>{b,c}&

Answer 3

Retina, 17 15 bytes

+m`^(.+)¶\1$¶?

Try it online!

Saved 2 bytes thanks to Neil and Martin!

Replaces each pair of numbers with nothing. This process loops until no changes are made.

Answer 4

Python 2, 57 bytes

r=[]
for x in input():r+=x,;r[-2:]*=r[-2:-1]!=[x]
print r

Try it online!

Iteratively constructs the output list by appending the next element, then chopping off the end if the appending element equals the one before it. Checking the second-to-last element r[-2:-1]!=[x] turns out awkward because it's possible the list has length only 1.

Answer 5

Jelly, 15 bytes

Œr;ṪḂ$$€x/€FµÐL

Try it online!

Explanation

Œr;ṪḂ$$€x/€FµÐL  Main Link
Œr               Run-length encode
  ;              Concatenate (?)
       €         For each element
   ṪḂ$$          Is the last element odd?
          €      For each element    // Non-breaking alternative
        x/       Reduce by repeating // for run-length decode
           F     Flatten
            µ    (New monadic link)
             ÐL  Repeat until results are no longer unique

-1 byte thanks to miles, and fixed :)

Answer 6

JavaScript (ES6), 54 53 bytes

Saved 1 byte thanks to @ThePirateBay

f=a=>1/a.find(q=>q==a[++i],i=-2)?f(a,a.splice(i,2)):a

Naive recursive solution, may be improvable.

Answer 7

Python 2, 73 bytes

Since I do not have enough reputation to comment: I just changed @officialaimm 's answer to use r!=[] instead of len(r) to save a byte. Very clever solution to you, @officialaimm !

r=[]                            # create list that will hold final results. A new list is important because it needs to be removable.
for i in input():               
 if r!=[]and r[-1]==i:r.pop()   # Ensure that we have at least 1 char added to the list (r!=[])... or that the last character of our final result isn't the current character being scanned. If that is, well, remove it from the final list because we do not want it anymore
 else:r+=[i]                    # Shorthand for r.append(i). This adds i to the final result
print r

Try it online!

It is, again, way too late... why am I even still up?

Answer 8

Python, 60 58 bytes

f=lambda a:a and(a[:1]+f(a[1:]))[2*(a[:1]==f(a[1:])[:1]):]

Try it online!

Answer 9

MATL, 7 bytes

t"Y'oY"

For some of the test cases where the result is empty the program exits with an error, but in any case it produces the correct (empty) output.

Try it online! Or verify the test cases with non-empty output.

Explanation

t     % Implicit input. Duplicate
"     % For each (i.e. do as many times as input size)
  Y'  %   Run-length encode. Gives array of values and array of run lengths
  o   %   Parity, element-wise. Reduces run-lengths to either 0 or 1
  Y"  %   Run-length decode. Gives array of values appearing 0 or 1 times;
      %   that is, removes pairs of consecutive values
      % Implicit end. Implicit display

Consider input

0 0 0 1 2 4 4 2 1 1 0

Each iteration removes pairs of consecutive pairs. The first iteration reduces the array to

0 1 2 2 0

The two values 2 that are now adjacent were not adjacent in the initial array. That's why a second iteration is needed, which gives:

0 1 0

Further iterations will leave this unchanged. The number of required iterations is upper-bounded by the input size.

An empty intermediate result causes the run-length decoding function (Y") to error in the current version of the language; but the ouput is empty as required.

Answer 10

x86 Machine Code (32-bit protected mode), 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, 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 (0xFC) needs to be inserted at the top of the code.

It also, as noted, assumes 32-bit protected mode—specifically, a "flat" memory model, where the extra segment (ES) is the same as the data segment (DS).

Answer 11

Batch, 133 bytes

@set s=.
:l
@if "%1"=="%2" (shift/1)else set s=%s% %1
@shift/1
@if not "%1"=="" goto l
@if not "%s:~2%"=="%*" %0%s:~1%
@echo(%*

I set s to . because Batch gets confused if there are only duplicates. I also have to use shift/1 so that I can use %0%s:~1% to set the argument list to the new array and loop.

Answer 12

Jelly, 12 bytes

ŒgṁLḂ$$€ẎµÐL

A monadic link taking and returning lists of numbers.

Try it online! or see a test suite

How?

ŒgṁLḂ$$€ẎµÐL - Link: list
         µÐL - perform the chain to the left until no changes occur:
Œg           -   group runs (yield a list of lists of non-zero-length equal runs)
      $€     -   last two links as a monad for €ach run:
     $       -     last two links as a monad:
   L         -       length (of the run)
    Ḃ        -       modulo 2 (1 if odd, 0 if even)
  ṁ          -     mould (the run) like (1 or 0) (yields a list of length 1 or 0 lists)
        Ẏ    -   tighten (make the list of lists into a single list)

Answer 13

Japt, 34 bytes

ó¥ k_l vîò k_l É}Ãc
ó¥ l ¥Ul ?U:ß

Recursively removes pairs of equal numbers until none exist.

Try it online! with the -Q flag to format the output array.

Run all test cases using my WIP CodePen.

Answer 14

05AB1E, 15 bytes

[γʒgÉ}€нÐγ‚€gË#

Try it online!

Explanation

[γʒgÉ}€нÐγ‚€gË#
[               # Start infinite loop
 γ              # Group Array into consecutive equal elements
  ʒgÉ}          # Keep the subarrays with an uneven amount of elements
      €н        # Keep only the first element of each subarray
        Ð       # Triplicate the result on the stack
         γ      # Group the top element into consecutive equal elements
          ‚     # Wrap the top two items of the stack in an array
           €g   # Get the length of each subarray
             Ë# # Break if they are equal
                # Implicit print          

Answer 15

05AB1E, 13 bytes

[DγʒgÉ}€нDŠQ#

Try it online!

Explanation:

[DγʒgÉ}€нDŠQ# Implicit input
[             Start infinite loop
 D            Duplicate
  γ           Split into chunks of equal elements
   ʒ  }       Filter by
    g           Length
     É          Odd? (0=falsy 1=truthy)
       €      Foreach command
        н     Head
         D    Duplicate
          Š   Push c, a, b
           Q  Equal? (0=falsy 1=truthy)
            # Break if true (i.e. equal to 1)

Answer 16

Haskell, 33 bytes

a!(b:c)|a==b=c
a!b=a:b
foldr(!)[]

Try it online!

Answer 17

Python 2, 74 70 66 bytes

• Thanks @SteamyRoot for 4 bytes: r instead of len(r) is enough to check emptiness of the list/stack.
• Thanks @ovs for 4 bytes: better if condition [i]==r[-1:]

Python 2, 66 bytes

r=[]
for i in input():
 if[i]==r[-1:]:r.pop()
 else:r+=[i]
print r

Try it online!

Answer 18

Husk, 9 bytes

ωoṁ?I↓2εg

Try it online!

A bit shorter than Zgarb's existing answer.

Explanation

ωoṁ?I↓2εg
ωo        apply the following till a fixed point:
        g group adjacent values
   ?   ε  if the group is a singleton list
    I     leave as is 
     ↓2   otherwise drop 2 elements
  ṁ       concatenate the results of that

Answer 19

Clojure, 100 bytes

#(loop[i % j[]](if(= i j)i(recur(mapcat(fn[p](repeat(mod(count p)2)(last p)))(partition-by + i))i)))

Not sure if this is the shortest possible.

Answer 20

Bash, 82 bytes

cat>b
while cat b>a
perl -pe 's/(\d+) \1( |$)//g' a>b
! diff a b>c
do :
done
cat a

There's probably a way out of all those cats, but I don't know it.

Answer 21

Husk, 10 bytes

ωoṁS↑o%2Lg

Try it online!

Explanation

ωoṁS↑o%2Lg
ω           Repeat until fixed point
 o          the following two functions:
         g   a) group adjacent elements
  ṁ          b) map over groups and concatenate:
        L     length of group
     o%2      mod 2
   S↑         take that many elements of group

Answer 22

PHP, 81 bytes

    function f(&$a){for($i=count($a);--$i;)$a[$i]-$a[$i-1]||array_splice($a,$i-1,2);}

function, call by reference or try it online.

fails for empty input; insert $i&& or $a&& before --$i to fix.

Answer 23

V, 10 bytes

òͨ.«©î±î*

Try it online!

Compressed Regex: :%s/\(.\+\)\n\1\n*. The optional newline is so that it works at the end of the file also. If I assume that there is a newline after the end it would be 8 bytes... but that seems like a stretch

Answer 24

dc, 84 78 bytes

[L.ly1-dsy0<A]sA[LtLtS.ly1+sy]sP[dStrdStr!=Pz1<O]sO[0syzdsz1<Oly0<Azlz>M]dsMxf

Try it online!

Unpacking it a bit, out of order in some attempt at clarity:

• [0syzdsz1<Olydsx0<Alx1+lz>M]dsMxf The main macro M resets counter y to 0, retrieves the number of items on the stack, stores this in register z, then runs macro O if there are at least two items on the stack. Once O finishes, it loads counter y and copies it into register x before checking to make sure y is nonzero (meaning stack . has data). If this is the case, it runs macro A. Finally it checks whether the original stack size is larger than the current stack size and reruns itself if so. Once it has finished, it prints the stack with f.
• [dStrdStr!=Pz1<O]sO Macro O temporarily stores the top two items on the stack into stack t. It then compares the top two items and runs macro P if they are not equal. Finally it checks whether or not there are at least two items on the stack, and runs itself if so.
• [LtLtS.ly1+sy]sP Macro P takes the two items from stack t, pushes the top one back onto the main stack, and pushes the following one onto stack .. It then increments counter y.
• [L.ly1-dsy0<A]sA Macro A takes stack . and turns it back into the primary stack. It does that, decrementing counter y until there's nothing left to push.

Edited for explanation, and to golf off 6 bytes as I was needlessly storing the size of the stack.

Answer 25

C++11, 161 bytes

#include<vector>
#include<algorithm>
using V=std::vector<int>;void f(V&v){V::iterator i;while((i=std::adjacent_find(v.begin(),v.end()))!=v.end())v.erase(i,i+2);}

The above code defines a function, f, that takes a std::vector<int> by reference, modifies it in place to collapse adjacent duplicates according to the specification, and then returns.

Try it online!

Before I checked the byte count, I thought this was pretty svelte code. Over 150 bytes is, however, not so good! Either I'm not very good at golfing, or C++ is not a very good golfing language…

Ungolfed:

#include <vector>
#include <algorithm>

using V = std::vector<int>;

void f(V& v)
{
   V::iterator i;

   // Use std::adjacent_find to search the entire vector for adjacent duplicate elements.
   // If an adjacent pair is found, this returns an iterator to the first element of the
   // pair so that we can erase it. Otherwise, it returns v.end(), and we stop.
   while ((i=std::adjacent_find(v.begin(), v.end())) != v.end())
   {
        v.erase(i, i+2);   // erase this adjacent pair
   }
}

Answer 26

PHP, 74 bytes

function c(&$a){foreach($a as$k=>$v)$a[$k+1]===$v&&array_splice($a,$k,2);}

Function c calls by reference to reduce array. Try it online.

Interestingly this works in Php5.6 but not 7.

Answer 27

R, 57 54 bytes

l=rle(scan());while(any(x<-!l$l%%2))l=rle(l$v[!x]);l$v

Try it online!

uses a run-length encoding to remove pairs.

Answer 28

J, 38 bytes

;@(<@($~2|#)/.~0+/\@,}.~:}:)^:(0<#)^:_

Try it online!

Answer 29

GNU sed, 19 + 1 = 20 bytes

+1 byte for -r flag.

:
s/\b(\S+ )\1//g
t

Try it online!

Answer 30

Pyth, 10 bytes

Bit late to the party.

ueMf%hT2r8

Test Suite.