Wyzwanie

Biorąc pod uwagę listę liczb całkowitych, zwróć listę tych liczb całkowitych po wielokrotnym usuwaniu wszystkich par sąsiadujących równych elementów.

Zauważ, że jeśli masz nieparzystą serię równych liczb, jedna z nich pozostanie, nie będąc częścią pary.

Przykład:

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

Po pierwsze, należy usunąć 0, 0, 4, 4i 1, 1otrzymujemy:

[0, 1, 2, 2, 0]

Teraz powinieneś usunąć 2, 2:

[0, 1, 0]

I to jest wynik końcowy.

Przypadki testowe

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

Punktacja

To jest golf golfowy , więc wygrywa najkrótsza odpowiedź w każdym języku!

Galaretka , 10 bajtów

Œgœ^/€FµÐL

Wypróbuj online!

Jak to działa

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

Siatkówka ,17 15 bajtów

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

Wypróbuj online!

Zaoszczędzono 2 bajty dzięki Neilowi ​​i Martinowi!

Zastępuje każdą parę liczb niczym. Ten proces zapętla się, dopóki nie zostaną wprowadzone żadne zmiany.

Mathematica 29 bajtów

Powoduje to wielokrotne usuwanie par równych sąsiadujących elementów, a_,a_dopóki nie zostaną żadne.

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

Python 2 , 57 bajtów

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

Wypróbuj online!

Iteracyjnie konstruuje listę wyjściową, dodając następny element, a następnie odcinając koniec, jeśli dołączany element jest równy pierwszemu. Sprawdzanie drugiego do ostatniego elementu r[-2:-1]!=[x]okazuje się niewygodne, ponieważ możliwe jest, że lista ma tylko 1 długość.

Galaretka , 15 bajtów

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

Wypróbuj online!

Wyjaśnienie

Œ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 bajt dzięki milom i naprawiono :)

JavaScript (ES6), 54 53 bajtów

Zapisano 1 bajt dzięki @ThePirateBay

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

Naiwne rozwiązanie rekurencyjne może być ulepszalne.

Python 2 , 73 bajty

Ponieważ nie mam wystarczającej reputacji, aby móc komentować: właśnie zmieniłem odpowiedź @officialaimm, aby użyć r! = [] Zamiast len ​​(r), aby zapisać bajt. Bardzo sprytne rozwiązanie, @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

Wypróbuj online!

Znowu jest o wiele za późno ... dlaczego jeszcze nie śpię?

Python, 60 58 bajtów

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

Wypróbuj online!

MATL , 7 bajtów

t"Y'oY"

W przypadku niektórych przypadków testowych, w których wynik jest pusty, program kończy działanie z błędem, ale w każdym przypadku generuje poprawne (puste) wyjście.

Wypróbuj online! Lub sprawdź przypadki testowe z niepustymi danymi wyjściowymi .

Wyjaśnienie

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

Rozważ wejście

0 0 0 1 2 4 4 2 1 1 0

Każda iteracja usuwa pary kolejnych par. Pierwsza iteracja zmniejsza tablicę do

0 1 2 2 0

Dwie wartości, 2które są teraz sąsiadujące, nie były sąsiadujące w początkowej tablicy. Dlatego potrzebna jest druga iteracja, która daje:

0 1 0

Dalsze iteracje pozostaną niezmienione. Liczba wymaganych iteracji jest ograniczona przez rozmiar wejściowy.

Pusty wynik pośredni powoduje funkcję dekodowania długości przebiegu (Y" błąd ) w bieżącej wersji języka; ale wyjście jest puste zgodnie z wymaganiami.

Kod maszynowy x86 (32-bitowy tryb chroniony), 36 bajtów

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

Powyższe bajty kodu maszynowego definiują funkcję, która pobiera tablicę jako dane wejściowe, zwija sąsiadujące duplikaty w miejscu i wraca do dzwoniącego bez zwracania wyniku. Jest zgodny z __fastcallkonwencją wywoływania , przekazując odpowiednio dwa parametry w rejestrach ECXi EDX.

Pierwszy parametr ( ECX) jest wskaźnikiem do pierwszego elementu w tablicy 32-bitowych liczb całkowitych (jeśli tablica jest pusta, może wskazywać w dowolnym miejscu w pamięci). Drugi parametr ( EDX) jest wskaźnikiem do 32-bitowej liczby całkowitej zawierającej długość tablicy.

Funkcja zmodyfikuje elementy tablicy w miejscu, jeśli to konieczne, a także zaktualizuje długość, aby wskazać nową długość zwiniętej tablicy. Jest to nieco niezwykła metoda pobierania i zwracania danych wyjściowych, ale tak naprawdę nie ma innego wyboru w języku asemblera. Podobnie jak w C, tablice są w rzeczywistości reprezentowane w języku jako wskaźnik do pierwszego elementu i długości . Jedyną dziwną rzeczą jest tutaj odniesienie się do długości , ale gdybyśmy tego nie zrobili, nie byłoby sposobu na skrócenie tablicy. Kod działałby dobrze, ale dane wyjściowe zawierałyby śmieci, ponieważ program wywołujący nie wiedziałby, gdzie zatrzymać drukowanie elementów ze zwiniętej tablicy.

Mnemoniki do montażu bez golfa:

; 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

Implementacja została zainspirowana przez moją odpowiedzią w C ++ 11 , ale skrupulatnie przepisana w asemblerze, optymalizując rozmiar. Montaż jest znacznie lepszym językiem golfa. :-)

Uwaga: Ponieważ kod używa instrukcji łańcuchów, to nie zakładamy, że flaga kierunek jest jasny ( DF== 0). Jest to rozsądne założenie w większości środowisk operacyjnych, ponieważ ABI zazwyczaj wymaga, aby DF było jasne. Jeśli nie można tego zagwarantować, należy wstawić 1-bajtową CLDinstrukcję ( 0xFC) na górze kodu.

Jak już wspomniano, zakłada również 32-bitowy tryb chroniony - w szczególności „płaski” model pamięci, w którym dodatkowy segment ( ES) jest taki sam jak segment danych ( DS).

Partia, 133 bajty

@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(%*

Ustawiłem s, .ponieważ Batch jest zdezorientowany, jeśli są tylko duplikaty. Muszę również użyć, shift/1aby móc %0%s:~1%ustawić listę argumentów na nową tablicę i pętlę.

Galaretka , 12 bajtów

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

Monadyczny link pobierający i zwracający listy liczb.

Wypróbuj online! lub zobacz zestaw testowy

W jaki sposób?

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

Japt , 34 bajty

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

Rekurencyjnie usuwa pary równych liczb, dopóki nie istnieją.

Wypróbuj online! z -Qflagą, aby sformatować tablicę wyjściową.

Uruchom wszystkie przypadki testowe, używając mojego WIP CodePen.

05AB1E , 15 bajtów

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

Wypróbuj online!

Wyjaśnienie

[γʒ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 bajtów

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

Wypróbuj online!

Wyjaśnienie:

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

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

Wypróbuj online!

Python 2 , 74 70 66 bajtów

• Dzięki @SteamyRoot za 4 bajty: rzamiast len(r)wystarczy sprawdzić pustkę listy / stosu.
• Dzięki @ovs za 4 bajty: lepiej, jeśli warunek [i]==r[-1:]

Python 2 , 66 bajtów

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

Wypróbuj online!

Clojure, 100 bajtów

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

Nie jestem pewien, czy jest to najkrótszy możliwy.

Bash, 82 bajty

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

Prawdopodobnie jest na to wyjście cat , ale nie wiem o tym.

Łuska , 10 bajtów

ωoṁS↑o%2Lg

Wypróbuj online!

Wyjaśnienie

ω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

PHP, 81 bajtów

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

zadzwoń przez referencję lub wypróbuj online .

kończy się niepowodzeniem dla pustych danych wejściowych; włóż $i&&lub $a&&przed --$inaprawić.

V , 10 bajtów

òͨ.«©î±î*

Wypróbuj online!

Sprężone Regex: :%s/\(.\+\)\n\1\n*. Opcjonalny znak nowej linii działa tak, że działa również na końcu pliku. Jeśli założę, że po końcu jest nowa linia, będzie to 8 bajtów ... ale wydaje się, że to odcinek

dc , 84 78 bajtów

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

Wypróbuj online!

Trochę rozpakowuję, nie działa w próbie jasności:

• [0syzdsz1<Olydsx0<Alx1+lz>M]dsMxfGłówne makro Mresetuje licznik ydo 0, pobiera liczbę elementów na stosie, przechowuje to w rejestrze z, a następnie uruchamia makro, Ojeśli na stosie znajdują się co najmniej dwa elementy. Po Ozakończeniu ładuje licznik yi kopiuje go do rejestru xprzed sprawdzeniem, aby upewnić się, że yjest niezerowy (co oznacza, że ​​stos .zawiera dane). W takim przypadku uruchamia makro A. Na koniec sprawdza, czy oryginalny rozmiar stosu jest większy niż bieżący rozmiar stosu, a następnie uruchamia się ponownie, jeśli tak jest. Po zakończeniu drukuje stos za pomocą f.
• [dStrdStr!=Pz1<O]sOMakro Otymczasowo przechowuje dwa najlepsze elementy na stosie w stos t. Następnie porównuje dwa górne elementy i uruchamia makro, Pjeśli nie są one równe. Na koniec sprawdza, czy na stosie znajdują się co najmniej dwa elementy, i uruchamia się, jeśli tak jest.
• [LtLtS.ly1+sy]sPMakro Pbierze dwa elementy ze stosu t, odkłada górny z powrotem na główny stos i przesuwa następny na stos .. Następnie zwiększa licznik y.
• [L.ly1-dsy0<A]sAMakro Apobiera stos .i zamienia go z powrotem w stos główny. Robi to, zmniejszając licznik, ydopóki nie zostanie nic do popchnięcia.

Edytowane dla wyjaśnienia i do gry w golfa z 6 bajtów, ponieważ niepotrzebnie zapisywałem rozmiar stosu.

C ++ 11, 161 bajtów

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

Powyższy kod definiuje funkcję, fktóra pobiera std::vector<int>referencję, modyfikuje ją w celu zwinięcia sąsiadujących duplikatów zgodnie ze specyfikacją, a następnie zwraca.

Wypróbuj online!

Zanim sprawdziłem liczbę bajtów, pomyślałem, że to dość prosty kod. Ponad 150 bajtów nie jest jednak tak dobre! Albo nie jestem zbyt dobry w golfie, albo C ++ nie jest zbyt dobrym językiem golfowym…

Nie golfowany:

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

PHP, 74 bajty

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

Wywołania funkcji c przez odniesienie w celu zmniejszenia tablicy. Wypróbuj online .

Co ciekawe, działa to w Php5.6, ale nie 7.

R , 57 54 bajtów

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

Wypróbuj online!

używa kodowania długości przebiegu do usuwania par.

J , 38 bajtów

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

Wypróbuj online!

GNU sed , 19 + 1 = 20 bajtów

+1 bajt dla -rflagi.

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

Wypróbuj online!

Pyth, 10 bajtów

Trochę późno na imprezę.

ueMf%hT2r8

Pakiet testowy.