# 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 , so the shortest answer in each language wins!

• Sandbox for those who can see deleted posts Jul 21, 2017 at 20:53
• It doesn't matter, they are all equal. The meaning of this phrase is that [14, 14, 14] collapses to [14] Jul 21, 2017 at 21:01
• Misread the challenge, sorry. Thought you had to remove all pairs of numbers increasing by 1 (1,2, 11,12, etc.) Jul 21, 2017 at 21:02
• Can we take input as a delimited string? Jul 21, 2017 at 21:18
• Could you add a test case such as -89,89,-87,-8,-88? Both my (unposted) Japt solution and Fry's Retina solution fail there, outputting --87,8. Jul 21, 2017 at 21:55

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

• Using Ẏ instead of F would make you support lists in your list too. Jul 22, 2017 at 11:37
• No, œ^ relies on integer-to-array promotion here. Since 1D arrays don't get promoted to 2D arrays, it won't work for anything except an array of numbers. Jul 22, 2017 at 17:53
• Heh...I mean you could've just used ŒgWẎ$œ^/$€ẎµÐL...oh wait that's too naive. :P Jul 22, 2017 at 17:59

# Mathematica 29 bytes

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

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


# 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. • Worked up an identical solution in Japt before spotting this. Unfortunately, we both fail on inputs such as -89 89 -87 -88 -88, which outputs --87. Jul 21, 2017 at 21:46 • @Shaggy Thanks, I corrected it by adding a boundary check and using _ to denote negatives, as is common in some languages. Jul 21, 2017 at 21:55 • I've since discovered that this'll also fail on _89 89 _87 _8 _88, outputting _89 89 _87 8. Sorry :\ Jul 21, 2017 at 21:58 • @Shaggy Don't be sorry! Thanks for finding the problem! I added another boundary check to fix that case. Jul 21, 2017 at 22:45 • @FryAmTheEggman Not sure whether that's what Neil meant but you could then also use m to turn the \bs into ^ and $. Jul 22, 2017 at 7:40

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

• Awesome answer, well done :) Jul 23, 2017 at 2:19

Œ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 :) • @FryAmTheEggman Fixed; thanks! Jul 21, 2017 at 21:26 • I'm not sure if throwing an error and leaving the output empty counts as a correct solution. You program throws ValueError: not enough values to unpack (expected 2, got 0) for test case [1,2,2,1]. Also note that empty output is different from [] and 2 is different from [2]. – user72349 Jul 21, 2017 at 21:56 • 13 bytes with Œr;ṪḂ$$€ŒṙµÐL. To avoid the error, replace Œṙ with x/€F since run-length decode is throwing an error when given an empty list. To see the output as a list, tacking ŒṘ will show it. Jul 21, 2017 at 23:10
• @ThePirateBay Jelly's representation of an empty list is - empty, of one item - just that item, and of multiple items - a bracketed and comma separated list. The submission is of a link (function) not a full program (much like a lambda would be in Python) - to see a more "normal" view place ÇŒṘ in the footer to call the last link (Ç) and print a Python representation (ŒṘ). The error might not be acceptable however. Jul 21, 2017 at 23:43
• @JonathanAllan. Ok, I realized that Jelly's string representation of a list is acceptable. The main point of my first comment is to mention that the error is thrown when the list become empty.
– user72349
Jul 21, 2017 at 23:56

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

• You can check current and previous element instead of current and next one, so you can replace i=0 with i=-2 and i-1 with i which is -1 byte in total.
– user72349
Jul 21, 2017 at 21:18
• @guest44851 Thanks, but... wouldn't that mean I'd need to change it to i+1? (I tried this before with moving the ++ as well and couldn't figure it out, though I only had about a minute to do so) Jul 21, 2017 at 22:19
• You can see that it works properly.
– user72349
Jul 21, 2017 at 22:41
• @ThePirateBay By golly, you're right! But how? Jul 22, 2017 at 0:32

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

# Python, 60 58 bytes

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


Try it online!

• [a[0]] is a[:1]
– xnor
Jul 23, 2017 at 19:18
• @xnor So it is. Thanks! Jul 23, 2017 at 20:14

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

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

• Could you add an explanation? I'd like to understand how you beat me so soundly. :P Jul 25, 2017 at 15:11
• @Dennis Sure! I had forgotten. Done :-) Jul 25, 2017 at 15:33
• Ah, RLE pushes two arrays. That's useful. Jul 25, 2017 at 15:46

# 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

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

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

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

• I have to ask ... why? Good answer ... but why? Jul 22, 2017 at 0:05
• @Zacharý Because it's there.
– Neil
Jul 22, 2017 at 0:23
• @Zacharý In part, a good reason to golf in non-golfing languages is because this might actually be useful. No one is going to fire up a Jelly interpreter in real life to do this, but they might need to do it in a batch file! Jul 25, 2017 at 16:04
• Oh. that makes sense. Jul 25, 2017 at 17:21

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

• ṁLḂ$$€ is equivalent to ḣLḂ$$€ which is equivalent to ṫḊ¿€3$ which you can replace with ṫḊ¿€3 here to form a dyad/nilad pair. Jul 22, 2017 at 11:40 • That does not work with, for example, an input with a run of length 4. What is the input to the dequeue at each iteration of the while loop? Jul 22, 2017 at 12:43 • You are supposed to be left with a list with 0 or 1 elements. If len(x) == 1, then Ḋ will return [] while if len(x) == 0 Ḋ will return 0, both being falsy values. The input to Ḋ is of course the current value, and ṫ will have the current value as left argument and 3 as the right. If len(x) == 4, then it would be the same as ṫ3ṫ3 or ṫ5 leaving you with []. Jul 22, 2017 at 12:46 • I can see what it is supposed to do, but is x in your description there really the current value? Try this out for size. Jul 22, 2017 at 12:49 • To be honest I do not know if that is the code or a bug :) Jul 22, 2017 at 12:49 # 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. # 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  # 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)  # Haskell, 33 bytes a!(b:c)|a==b=c a!b=a:b foldr(!)[]  Try it online! # 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! • If the purpose of len(r) is just to check whether or not the list is empty, you should be able to replace it by just r, I think? Jul 22, 2017 at 13:47 • Oh yes, Thanks. Jul 22, 2017 at 13:55 • 66 bytes – ovs Jul 23, 2017 at 13:49 • @ovs Thanks a lot, that is awesome! (y) Jul 23, 2017 at 13:58 • Alternative 66 bytes long version, though only requiring three lines. Nov 9, 2017 at 17:21 # 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  ## 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. ## 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.

## Husk, 10 bytes

ωoṁS↑o%2Lg


Try it online!

## Explanation

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


# 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. # 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 # 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. # 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 } }  • C++ isn't the best golfing language. Nice use of std::adjacent_find! I wonder if you implemented this function yourself if it would be shorter, since you can remove #include <algorithm> as well Jul 26, 2017 at 17:55 • @musicman523 My first attempt did implement it by hand, although I used a little bit different algorithm. I was adapting the implementation of std::unique to do what I needed. But it takes a lot of code to do all the logic, and when I happened across std::adjacent_find, it was pretty obvious that that was a winner in terms of code size. Jul 27, 2017 at 9:35 # 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.

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. # J, 38 bytes ;@(<@($~2|#)/.~0+/\@,}.~:}:)^:(0<#)^:_


Try it online!

# GNU sed, 19 + 1 = 20 bytes

+1 byte for -r flag.

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


Try it online!

# Pyth, 10 bytes

Bit late to the party.

ueMf%hT2r8
`

Test Suite.