Tantangan

Diberikan daftar bilangan bulat, kembalikan daftar bilangan bulat ini setelah berulang kali menghapus semua pasangan item sama yang berdekatan.

Perhatikan bahwa jika Anda memiliki jangka ganjil dengan angka yang sama, salah satunya akan tetap, tidak menjadi bagian dari pasangan.

Contoh:

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

Pertama, Anda harus menghapus 0, 0, 4, 4dan 1, 1untuk mendapatkan:

[0, 1, 2, 2, 0]

Sekarang, Anda harus menghapus 2, 2:

[0, 1, 0]

Dan ini adalah hasil akhir.

Uji Kasus

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

Mencetak gol

Ini kode-golf , jadi jawaban tersingkat di setiap bahasa menang!

Jelly , 10 byte

Œgœ^/€FµÐL

Cobalah online!

Bagaimana itu bekerja

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

Retina ,17 15 byte

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

Cobalah online!

Disimpan 2 byte berkat Neil dan Martin!

Mengganti setiap pasangan angka dengan tidak ada. Proses ini berulang sampai tidak ada perubahan.

Mathematica 29 byte

Ini berulang kali menghilangkan pasangan elemen yang berdekatan yang sama, a_,a_sampai tidak ada yang tersisa.

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

Python 2 , 57 byte

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

Cobalah online!

Iteratif membangun daftar output dengan menambahkan elemen berikutnya, kemudian memotong akhirnya jika elemen menambahkan sama dengan yang sebelumnya. Memeriksa elemen kedua hingga terakhir r[-2:-1]!=[x]ternyata aneh karena daftar itu mungkin panjangnya hanya 1.

Jelly , 15 byte

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

Cobalah online!

Penjelasan

Œ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 berkat mil, dan diperbaiki :)

JavaScript (ES6), 54 53 byte

Disimpan 1 byte berkat @ThePirateBay

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

Solusi rekursif naif, mungkin dapat ditingkatkan.

Python 2 , 73 byte

Karena saya tidak memiliki reputasi yang cukup untuk berkomentar: Saya baru saja mengubah jawaban @officialaimm untuk menggunakan r! = [] Daripada len (r) untuk menyimpan byte. Solusi yang sangat pintar untuk Anda, @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

Cobalah online!

Sekali lagi, ini sudah terlambat ... mengapa saya masih bangun?

Python, 60 58 byte

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

Cobalah online!

MATL , 7 byte

t"Y'oY"

Untuk beberapa kasus uji di mana hasilnya kosong, program keluar dengan kesalahan, tetapi bagaimanapun juga menghasilkan output yang benar (kosong).

Cobalah online! Atau verifikasi kasus uji dengan output yang tidak kosong .

Penjelasan

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

Pertimbangkan input

0 0 0 1 2 4 4 2 1 1 0

Setiap iterasi menghilangkan pasangan pasangan yang berurutan. Iterasi pertama mengurangi array menjadi

0 1 2 2 0

Dua nilai 2yang sekarang berdekatan tidak berdekatan dalam array awal. Itu sebabnya diperlukan iterasi kedua, yang memberikan:

0 1 0

Iterasi lebih lanjut akan membuat ini tidak berubah. Jumlah iterasi yang diperlukan dibatasi oleh ukuran input.

Hasil antara kosong menyebabkan fungsi decoding run-length ( Y") kesalahan dalam versi bahasa saat ini; tetapi ouput kosong sesuai kebutuhan.

Kode Mesin x86 (mode terlindung 32-bit), 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

Byte kode mesin di atas mendefinisikan fungsi yang mengambil array sebagai input, meruntuhkan duplikat yang berdekatan di tempat, dan kembali ke pemanggil tanpa mengembalikan hasil. Ini mengikuti __fastcallkonvensi pemanggilan , melewati dua parameter di ECXdan EDXregister, masing-masing.

Parameter pertama ( ECX) adalah penunjuk ke elemen pertama dalam array bilangan bulat 32-bit (jika array kosong, ia dapat menunjuk ke mana saja dalam memori). Parameter kedua ( EDX) adalah pointer ke integer 32-bit yang berisi panjang array.

Fungsi ini akan mengubah elemen-elemen array di tempat, jika perlu, dan juga memperbarui panjang untuk menunjukkan panjang baru array yang diciutkan. Ini sedikit metode yang tidak biasa untuk mengambil input dan mengembalikan output, tetapi Anda benar-benar tidak punya pilihan lain dalam bahasa assembly. Seperti dalam C, array sebenarnya direpresentasikan dalam bahasa sebagai penunjuk ke elemen pertama dan panjang . Satu-satunya hal yang agak aneh di sini adalah mengambil panjang dengan referensi , tetapi jika kita tidak melakukan itu, tidak akan ada cara untuk mempersingkat array. Kode akan berfungsi dengan baik, tetapi hasilnya akan mengandung sampah, karena penelepon tidak akan tahu di mana harus berhenti mencetak elemen dari susunan yang diciutkan.

Mnemonik perakitan tidak dikumpulkan:

; 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

Implementasinya terinspirasi oleh jawaban C ++ 11 saya , tetapi ditulis ulang dengan cermat dalam perakitan, mengoptimalkan ukuran. Assembly adalah bahasa golf yang jauh lebih baik. :-)

Catatan: Karena kode ini menggunakan instruksi string, apakah mengasumsikan bahwa bendera arah jelas (DF == 0). Ini adalah asumsi yang masuk akal di sebagian besar lingkungan operasi, karena ABI biasanya mengharuskan DF jelas. Jika ini tidak dapat dijamin, maka CLDinstruksi 1-byte ( 0xFC) harus dimasukkan di bagian atas kode.

Ini juga, seperti yang disebutkan, mengasumsikan mode 32-bit yang dilindungi - khususnya, model memori "flat", di mana segmen tambahan ( ES) sama dengan segmen data ( DS).

Batch, 133 byte

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

Saya menetapkan s .karena Batch menjadi bingung jika hanya ada duplikat. Saya juga harus menggunakan shift/1sehingga saya bisa menggunakan %0%s:~1%untuk mengatur daftar argumen ke array dan loop baru.

Jelly , 12 byte

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

Tautan monadik yang mengambil dan mengembalikan daftar angka.

Cobalah online! atau lihat a test suite

Bagaimana?

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

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

Secara rekursif menghapus pasangan angka yang sama sampai tidak ada.

Cobalah online! dengan -Qbendera untuk memformat larik keluaran.

Jalankan semua test case menggunakan WIP CodePen saya.

05AB1E , 15 byte

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

Cobalah online!

Penjelasan

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

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

Cobalah online!

Penjelasan:

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

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

Cobalah online!

Python 2 , 74 70 66 byte

• Terima kasih @SteamyRoot untuk 4 byte: r bukannya len(r)cukup untuk memeriksa kekosongan daftar / tumpukan.
• Terima kasih @ovs untuk 4 byte: lebih baik jika kondisinya [i]==r[-1:]

Python 2 , 66 byte

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

Cobalah online!

Clojure, 100 byte

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

Tidak yakin apakah ini sesingkat mungkin.

Bash, 82 byte

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

Mungkin ada jalan keluar dari semua catitu, tapi saya tidak tahu itu.

Sekam , 10 byte

ωoṁS↑o%2Lg

Cobalah online!

Penjelasan

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

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

berfungsi, panggil dengan referensi atau coba online .

gagal untuk input kosong; masukkan $i&&atau $a&&sebelum --$iuntuk memperbaikinya.

V , 10 byte

òͨ.«©î±î*

Cobalah online!

Dikompresi Regex: :%s/\(.\+\)\n\1\n*. Newline opsional adalah agar berfungsi juga di akhir file. Jika saya berasumsi bahwa ada baris baru setelah akhir itu akan menjadi 8 byte ... tapi itu seperti peregangan

dc , 84 78 byte

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

Cobalah online!

Membongkar sedikit, rusak dalam beberapa upaya kejelasan:

• [0syzdsz1<Olydsx0<Alx1+lz>M]dsMxfMakro Mme-reset penghitung utama yke 0, mengambil jumlah item di stack, menyimpan ini di register z, lalu menjalankan makro Ojika setidaknya ada dua item di stack. Setelah Oselesai, ia memuat counter ydan menyalinnya ke dalam register xsebelum memeriksa untuk memastikan ytidak nol (artinya tumpukan .memiliki data). Jika ini masalahnya, ini berjalan makro A. Akhirnya memeriksa apakah ukuran tumpukan asli lebih besar dari ukuran tumpukan saat ini dan memutarkan ulang sendiri jika demikian. Setelah selesai, ia mencetak tumpukan dengan f.
• [dStrdStr!=Pz1<O]sOMakro Osementara menyimpan dua item teratas di tumpukan ke dalam tumpukan t. Kemudian membandingkan dua item teratas dan menjalankan makroP jika tidak sama. Akhirnya memeriksa apakah ada setidaknya dua item di stack, dan berjalan sendiri jika demikian.
• [LtLtS.ly1+sy]sPMakro Pmengambil dua item dari tumpukan t, mendorong yang atas kembali ke tumpukan utama, dan mendorong yang berikut ke tumpukan .. Itu kemudian menambah counter y.
• [L.ly1-dsy0<A]sAMakro Amengambil tumpukan .dan mengubahnya kembali ke tumpukan utama. Itu yang terjadi, decrementing countery sampai tidak ada yang tersisa untuk didorong.

Diedit untuk penjelasan, dan untuk bermain golf 6 byte karena saya tidak perlu menyimpan ukuran tumpukan.

C ++ 11, 161 byte

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

Kode di atas mendefinisikan suatu fungsi,, fyang mengambil std::vector<int>referensi, memodifikasinya untuk meruntuhkan duplikat yang berdekatan sesuai dengan spesifikasi, dan kemudian kembali.

Cobalah online!

Sebelum saya memeriksa jumlah byte, saya pikir ini kode yang cukup ramping. Lebih dari 150 byte, bagaimanapun, tidak begitu baik! Entah saya tidak pandai golf, atau C ++ bukan bahasa golf yang sangat baik ...

Tidak Disatukan:

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

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

Fungsi c memanggil dengan referensi untuk mengurangi array. Cobalah online .

Menariknya ini bekerja di Php5.6 tetapi tidak 7.

R , 57 54 byte

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

Cobalah online!

menggunakan pengodean run-length untuk menghapus pasangan.

J , 38 byte

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

Cobalah online!

GNU sed , 19 + 1 = 20 byte

+1 byte untuk -rbendera.

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

Cobalah online!

Pyth, 10 byte

Agak terlambat ke pesta.

ueMf%hT2r8

Test Suite.