Herausforderung

Wenn Sie eine Liste von Ganzzahlen erhalten haben, geben Sie die Liste dieser Ganzzahlen zurück, nachdem Sie wiederholt alle Paare benachbarter gleicher Elemente entfernt haben.

Beachten Sie, dass bei einem Lauf mit ungerader Länge und gleichen Zahlen einer von ihnen übrig bleibt und nicht Teil eines Paares ist.

Beispiel:

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

Zuerst sollten Sie , und entfernen 0, 0, um Folgendes zu erhalten:4, 41, 1

[0, 1, 2, 2, 0]

Nun sollten Sie entfernen 2, 2:

[0, 1, 0]

Und das ist das Endergebnis.

Testfälle

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

Wertung

Das ist Code-Golf , also gewinnt die kürzeste Antwort in jeder Sprache!

Gelee , 10 Bytes

Œgœ^/€FµÐL

Probieren Sie es online!

Wie es funktioniert

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

Netzhaut ,17 15 Bytes

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

Probieren Sie es online!

2 Bytes gespart dank Neil und Martin!

Ersetzt jedes Zahlenpaar durch nichts. Dieser Vorgang wird solange wiederholt, bis keine Änderungen mehr vorgenommen wurden.

Mathematica 29 Bytes

Dies entfernt wiederholt Paare gleicher benachbarter Elemente, a_,a_bis keine mehr vorhanden sind.

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

Python 2 , 57 Bytes

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

Probieren Sie es online!

Erstellt iterativ die Ausgabeliste, indem das nächste Element angehängt wird und das Ende abgeschnitten wird, wenn das angehängte Element dem vorherigen Element entspricht. Die Überprüfung des vorletzten Elements r[-2:-1]!=[x]ist umständlich, da die Liste möglicherweise nur eine Länge von 1 hat.

Gelee , 15 Bytes

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

Probieren Sie es online!

Erläuterung

Œ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 dank Meilen und behoben :)

JavaScript (ES6), 54 53 Bytes

1 Byte dank @ThePirateBay gespeichert

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

Naive rekursive Lösung, kann verbesserungsfähig sein.

Python 2 , 73 Bytes

Da ich nicht genug Reputation habe, um einen Kommentar abzugeben, habe ich @officialaimms Antwort so geändert, dass r! = [] Anstelle von len (r) verwendet wird, um ein Byte zu speichern. Sehr clevere Lösung für Sie, @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

Probieren Sie es online!

Es ist wieder viel zu spät ... warum bin ich überhaupt noch wach?

Python, 60 58 Bytes

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

Probieren Sie es online!

MATL , 7 Bytes

t"Y'oY"

In einigen Testfällen, in denen das Ergebnis leer ist, wird das Programm mit einem Fehler beendet, es wird jedoch in jedem Fall die richtige (leere) Ausgabe erzeugt.

Probieren Sie es online!Oder überprüfen Sie die Testfälle mit nicht leerer Ausgabe .

Erläuterung

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

Betrachten Sie die Eingabe

0 0 0 1 2 4 4 2 1 1 0

Jede Iteration entfernt Paare von aufeinanderfolgenden Paaren. Die erste Iteration reduziert das Array auf

0 1 2 2 0

Die zwei Werte 2 , die jetzt benachbart sind, waren im anfänglichen Array nicht benachbart. Aus diesem Grund ist eine zweite Iteration erforderlich, die Folgendes ergibt:

0 1 0

Weitere Iterationen lassen dies unverändert. Die Anzahl der erforderlichen Iterationen wird durch die Eingabegröße begrenzt.

Ein leeres Zwischenergebnis führt dazu, dass die Lauflängendecodierungsfunktion ( Y") in der aktuellen Version der Sprache fehlerhaft ist. Die Ausgabe ist jedoch nach Bedarf leer.

x86-Maschinencode (32-Bit-geschützter Modus), 36 Byte

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

Die obigen Bytes des Maschinencodes definieren eine Funktion, die ein Array als Eingabe annimmt, benachbarte Duplikate direkt komprimiert und ohne Rückgabe eines Ergebnisses zum Aufrufer zurückkehrt. Es folgt der __fastcallAufrufkonvention und übergibt die beiden Parameter in ECXundEDX Register sind.

Der erste Parameter (ECX ) ist ein Zeiger auf das erste Element im Array mit 32-Bit-Ganzzahlen (wenn das Array leer ist, kann es auf eine beliebige Stelle im Speicher verweisen). Der zweite Parameter ( EDX) ist ein Zeiger auf eine 32-Bit-Ganzzahl, die die Länge des Arrays enthält.

Die Funktion ändert bei Bedarf die Elemente des Arrays an Ort und Stelle und aktualisiert auch die Länge, um die neue Länge des komprimierten Arrays anzugeben. Dies ist eine ungewöhnliche Methode, um Eingaben vorzunehmen und Ausgaben zurückzugeben, aber in der Assemblersprache haben Sie wirklich keine andere Wahl. Wie in C werden Arrays in der Sprache tatsächlich als Zeiger auf das erste Element und eine Länge dargestellt . Das einzige, was hier ein bisschen seltsam ist, ist die Länge nach Bezug zu nehmen . Wenn wir das nicht machen würden, gäbe es keine Möglichkeit, das Array zu verkürzen. Der Code würde gut funktionieren, aber die Ausgabe würde Müll enthalten, da der Aufrufer nicht wissen würde, wo er das Drucken von Elementen aus dem komprimierten Array stoppen soll.

Ungolfed Assembler-Mnemonik:

; 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

Die Implementierung war von meiner C ++ 11-Antwort inspiriert , wurde jedoch in der Assembly akribisch umgeschrieben und hinsichtlich der Größe optimiert. Assembly ist eine viel bessere Golfsprache. :-)

Hinweis: Da dieser Code die Zeichenfolge Anweisungen verwendet, ist nicht davon ausgehen , dass die Richtungs - Markierung klar ist ( DF== 0). Dies ist in den meisten Betriebsumgebungen eine vernünftige Annahme, da das ABI normalerweise erfordert, dass DF klar ist. Wenn dies nicht garantiert werden kann, muss ein 1-Byte- CLDBefehl ( 0xFC) am Anfang des Codes eingefügt werden.

Es wird auch, wie erwähnt, ein 32-Bit-geschützter Modus angenommen - insbesondere ein "flaches" Speichermodell, bei dem das zusätzliche Segment ( ES) mit dem Datensegment ( ) identisch ist 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(%*

Ich setze s auf, .weil Batch verwirrt wird, wenn es nur Duplikate gibt. Ich muss auch verwenden, shift/1damit ich %0%s:~1%die Argumentliste auf das neue Array und die neue Schleife setzen kann.

Gelee , 12 Bytes

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

Ein monadischer Link, der Nummernlisten aufnimmt und zurückgibt.

Probieren Sie es online! oder sehen Sie sich eine Testsuite an

Wie?

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

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

Entfernt rekursiv Paare gleicher Zahlen, bis keine mehr vorhanden sind.

Probieren Sie es online!mit dem -QFlag, um das Ausgabearray zu formatieren.

Führen Sie alle Testfälle mit meinem WIP-CodePen aus.

05AB1E , 15 Bytes

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

Probieren Sie es online!

Erläuterung

[γʒ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#

Probieren Sie es online!

Erläuterung:

[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(!)[]

Probieren Sie es online!

Python 2 , 74 70 66 Bytes

• Danke @SteamyRoot für 4 Bytes: rstattlen(r) reicht es aus, die Leere der Liste / des Stapels zu überprüfen.
• Danke @ovs für 4 Bytes: besser wenn Bedingung [i]==r[-1:]

Python 2 , 66 Bytes

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

Probieren Sie es online!

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

Ich bin mir nicht sicher, ob dies der kürzeste ist.

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

Es gibt wahrscheinlich einen Ausweg aus all diesen Dingen cat, aber ich weiß es nicht.

Schale , 10 Bytes

ωoṁS↑o%2Lg

Probieren Sie es online!

Erläuterung

ω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 Bytes

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

Funktion, rufen Sie per Referenz an oder versuchen Sie es online .

schlägt bei leerer Eingabe fehl; einlegen $i&&oder $a&&vorher --$ifixieren.

V , 10 Bytes

òͨ.«©î±î*

Probieren Sie es online!

Komprimierte Regex: :%s/\(.\+\)\n\1\n*. Der optionale Zeilenumbruch ist so, dass er auch am Ende der Datei funktioniert. Wenn ich davon ausgehe, dass es nach dem Ende eine neue Zeile gibt, wären es 8 Bytes ... aber das scheint eine Strecke zu sein

dc , 84 78 Bytes

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

Probieren Sie es online!

Auspacken ein wenig aus der Reihenfolge in einem Versuch der Klarheit:

• [0syzdsz1<Olydsx0<Alx1+lz>M]dsMxfDas Hauptmakro Msetzt den Zähler yauf 0 zurück, ruft die Anzahl der Elemente auf dem Stapel ab, speichert diese im Register zund führt dann ein Makro aus, Owenn sich mindestens zwei Elemente auf dem Stapel befinden. Sobald der OVorgang abgeschlossen ist, wird der Zähler geladen yund in das Register kopiert, xbevor überprüft wird, ob er yungleich Null ist (was Stapel bedeutet). enthält Daten). In diesem Fall wird ein Makro ausgeführt A. Abschließend wird überprüft, ob die ursprüngliche Stapelgröße größer als die aktuelle Stapelgröße ist, und in diesem Fall eine erneute Ausführung durchgeführt. Sobald es fertig ist, druckt es den Stapel mit f.
• [dStrdStr!=Pz1<O]sOMakro Ospeichert die obersten zwei Elemente auf dem Stapel vorübergehend im Stapelt . Es vergleicht dann die beiden obersten Elemente und führt ein Makro aus, Pwenn sie nicht gleich sind. Schließlich wird geprüft, ob sich mindestens zwei Elemente auf dem Stapel befinden, und in diesem Fall wird es von selbst ausgeführt.
• [LtLtS.ly1+sy]sPMakro Pnimmt die beiden Gegenstände vom Stapel t, schiebt den oberen zurück auf den Hauptstapel und schiebt den folgenden auf den Stapel .. Dann wird der Zähler erhöhty .
• [L.ly1-dsy0<A]sAMakro Animmt Stapel .und verwandelt es zurück in den primären Stapel. Dabei wird der Zähler dekrementiert, ybis nichts mehr zu drücken ist.

Bearbeitet zur Erklärung und um 6 Bytes zu sparen, da ich die Größe des Stapels unnötig gespeichert habe.

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

Der obige Code definiert eine Funktion, fdie einen std::vector<int>Verweis aufnimmt , ihn an Ort und Stelle ändert, um benachbarte Duplikate gemäß der Spezifikation zu reduzieren, und dann zurückgibt.

Probieren Sie es online!

Bevor ich die Byteanzahl überprüfte, dachte ich, dass dies ziemlich schlanker Code war. Über 150 Bytes ist jedoch nicht so gut! Entweder bin ich nicht sehr gut im Golfen oder C ++ ist keine sehr gute Golfsprache…

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

PHP, 74 Bytes

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

Funktion c ruft durch Referenz auf, um das Array zu verkleinern. Probieren Sie es online aus .

Interessanterweise funktioniert dies in Php5.6, aber nicht in 7.

R , 57 54 Bytes

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

Probieren Sie es online!

Verwendet eine Lauflängencodierung, um Paare zu entfernen.

J , 38 Bytes

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

Probieren Sie es online!

GNU sed , 19 + 1 = 20 Bytes

+1 Byte für -rFlag.

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

Probieren Sie es online!

Pyth, 10 Bytes

Ein bisschen zu spät zur Party.

ueMf%hT2r8

Test Suite.