Tujuan Anda adalah untuk menghitung persimpangan set dua daftar bilangan bulat. Persimpangan didefinisikan sebagai kelompok bilangan bulat unik tanpa urutan yang ditemukan setidaknya satu kali dalam kedua daftar input.

Memasukkan

Input mungkin dalam format apa pun yang diinginkan (parameter fungsi, stdio, dll.), Dan terdiri dari dua daftar bilangan bulat. Anda banyak yang tidak berasumsi apa-apa tentang setiap daftar selain mereka mungkin mengandung jumlah bilangan bulat non-negatif (yaitu mereka tidak disortir, mungkin berisi duplikat, mungkin memiliki panjang yang berbeda, dan bahkan mungkin kosong). Diasumsikan bahwa setiap bilangan bulat akan sesuai dengan tipe bilangan bulat bertanda asli bahasa Anda, mungkin lebih dari 1 digit desimal, dan ditandatangani.

Input contoh:

1 4 3 9 8 8 3 7 0
10 1 4 4 8 -1

Keluaran

Outputnya berupa daftar seperti bilangan bulat yang mewakili persimpangan set dari dua daftar ke format yang diinginkan (nilai pengembalian, stdio, dll.). Tidak ada persyaratan bahwa output diurutkan, meskipun Anda dipersilakan untuk memberikan implementasi yang kebetulan selalu diurutkan. Output harus membentuk himpunan tidak terurut yang valid (mis. Tidak boleh mengandung nilai duplikat apa pun).

Contoh kasus uji (perhatikan bahwa urutan output tidak penting):

Dua baris pertama adalah daftar input, baris ketiga adalah output. (empty)menunjukkan daftar kosong.

(empty)
(empty)
(empty)

1000
(empty)
(empty)

3 1 2 4 3 1 1 1 1 3
3 1 -1 0 8 3 3 1
1 3

1 2 1
3 3 4
(empty)

Mencetak gol

Ini adalah kode golf; jawaban terpendek dalam byte menang.

Lubang loop standar dilarang. Anda dapat menggunakan fitur bawaan yang tidak dirancang untuk operasi seperti set.

Fitur bawaan yang terlarang:

• mengatur pembuatan / menghapus duplikat
• atur perbedaan / persimpangan / gabungan
• Pengujian keanggotaan umum (mis. Apa pun yang mirip dengan inkata kunci dengan Python, indexOf-seperti fungsi, dll). Perhatikan bahwa penggunaan konstruksi "foreach item in list" diperbolehkan (dengan asumsi mereka tidak melanggar salah satu dari pembatasan lain), meskipun fakta bahwa Python menggunakan kembali inkata kunci untuk membuat konstruksi ini.
• Built-in terlarang ini adalah "viral", yaitu jika ada built-in yang lebih besar yang mengandung salah satu dari sub-fitur ini, ia juga dilarang (misalnya, memfilter berdasarkan keanggotaan dalam daftar).

Setiap bawaan yang tidak ada dalam daftar di atas diizinkan (mis. Penyortiran, pengujian kesetaraan bilangan bulat, daftar ditambahkan / dihapus berdasarkan indeks, pemfilteran, dll.).

Misalnya, ambil dua contoh snippet berikut (kode mirip-Python):

# prohibited: filters by testing if each value in tmpList is a member of listA
result = tmpList.filter(listA)

# ok: filtering by a lambda which manually iterates over listA and checks for equality
def my_in_func(val, slist):
    for a in slist:
        if(val == a):
            return True
    return False
result = filter(lambda v: my_in_func(val, listA), tmpList)

Anda dipersilakan untuk mengimplementasikan sendiri fitur-fitur seperti set ini dan mereka akan dihitung untuk skor Anda.

Solusi Anda harus diselesaikan dalam jumlah waktu yang wajar (katakanlah, kurang dari satu menit pada perangkat keras apa pun yang Anda miliki untuk dua daftar ~ masing-masing panjangnya 1000).

Haskell, 45 42 byte

y#(e:s)=[e|any(==e)y,all(/=e)s]++y#s
_#x=x

Cobalah online!

Sunting: -2 byte terima kasih kepada @ Ørjan Johansen, -1 byte terima kasih kepada @dfeuer.

MATL , 18 byte

YY_iti!=Xa)hStdfQ)

Cobalah online!

Ini bekerja dalam dua langkah. Pertama persimpangan dihitung, mungkin dengan duplikat. Ini didasarkan pada membandingkan semua elemen dari satu array dengan semua elemen yang lain, dan menjaga elemen yang pertama yang ada di kedua.

Kemudian duplikat dihapus. Untuk ini, array dari langkah sebelumnya diurutkan, dan entri disimpan jika berbeda dari sebelumnya. Suatu -infnilai didahului sehingga nilai pertama (yaitu terendah) tidak hilang.

YY_                 % push -infinity
   it               % take first input. Duplicate
     i!             % take second input. Transpose
        =           % test all combinations of elements of the two inputs for equality
        Xa          % row vector that contains true for elements of first array that 
                    % are present in the second, possibly duplicated
          )         % index into first array to keep only those elements. Now we need
                    % to remove duplicates
           h        % append -infinity
            S       % sort
             tdf    % duplicate. Find entries that differ from the preceding
                Q)  % add 1 and index into array to keep only non-duplicates

Jelly, 13 byte

=S¥Ðf
ṂrṀ{ç³ç

Cobalah online!

Bagaimana itu bekerja

ṂrṀ{ç³ç  Main link. Arguments: A (list 1), B (list 2)

Ṃ        Yield m, the minimum of A.
  Ṁ{     Yield M, the maxmimum of A.
 r       Create an inclusive range from m to M.
    f³   Apply the helper link with right argument A.
      f  Apply the helper link with right argument B.


=S¥Ðf    Helper link. Arguments: n (integer in range), L (list, A or B)

=        Test all elements of L for equality with n.
 S       Add the results.
  ¥      Combine the two previous links into a dyadic chain.
   Ðf    Filter by the result of the sums.

golflua , 68 karakter

\f(a,b)k={}~@_,v p(a)~@_,w p(b)?w==v k[w]=w$$$~@_,v p(k)I.w(v," ")$$

yang disebut sebagai

> f({1,2,3,4},{3,4,5})
3 4
> f({3,1,2,4,3,1,1,1,1,3},{3,1,-1,0,8,3,3,1})
3 1

Dalam Lua biasa, ini akan menjadi

function foo(a,b)
   local k={}
   for i,v in pairs(a)
      for j,w in pairs(b)
         if v==w then
            k[v] = v
         end
      end
   end
   for i,v in pairs(k)
      print(v," ")
   end
end

Jadi pada dasarnya saya mengulangi setiap elemen dari dua tabel dan hanya menyimpan nilai yang setara. Dengan menggunakan nilai sebagai kunci ( k[w]=w), saya menghilangkan semua duplikat. Kami kemudian menampilkan tabel baru dengan mengulangi indeks & nilaipairs

JavaScript (ES6), 66 byte

(a,b)=>a.filter((e,i)=>b.some(f=>e==f)&a.slice(0,i).every(f=>e-f))

Tanpa menggunakan indexOf, karena saya tidak yakin itu diizinkan.

Pyth, 12 11 byte

eMrSsq#RQE8

Demonstrasi

Penjelasan:

eMrSsq#RQE8
               Implicit: Q is one of the lists.
     q#RQE     For every element in the first list, filter the second list on
               equality with that element.
    s          Concatenate. We now have the intersection, with duplicates.
  rS      8    Sort and run length encode, giving counts and elements.
eM             Take just the elements.

bash + GNU coreutils, 184 Bytes

[ -z "$1" ] && exit
p='{if(a[$0]++==0)print $0}'
while read A; do
while read B; do
[ $A = $B ] && echo $A
done < <(grep -oP '\d*'<<<$1|awk "$p")
done < <(grep -oP '\d*'<<<$2|awk "$p")

Doa:

./codegolf.sh '12 4 654 12 3 56' '4 4 56 33 3 3 3'

Keluaran:

4
56
3

Tidak ada output jika persimpangan kosong. Script ini tidak mengurutkan dan membuat kewarasan memeriksa apakah set pertama kosong. Penjelasan:

[ -z "$1" ] && exit  # Exit if first set is empty
p='{if(a[$0]++==0)print $0}' # The AWK program we will use
while read A; do   # read the list with two
while read B; do   # encapsulated loops
[ $A = $B ] && echo $A   # if they match, then print
done < <(grep -oP '\d*'<<<$1|awk "$p")
done < <(grep -oP '\d*'<<<$2|awk "$p")
# the process substitution greps the numbers and pipes them to awk. Our awk program makes them unique without sorting; it uses associative arrays with index names same as lines (our numbers here).

Bonus untuk diketahui: Anda dapat mengubah grep -o .untuk melakukan ini dengan string acak, bukan angka.

Perl 6, 26 37 byte

{%(@^a.grep(any(@^b)):p.invert).keys}

pemakaian

> my &f = {%(@^a.grep(any(@^b)):p.invert).keys}
-> @a, @b { #`(Block|559823336) ... }
> f([3,1,2,4,3,1,1,1,1,3], [3,1,-1,0,8,3,3,1])
(1 3)

Jawaban tidak bersaing yang kurang ajar

> [3,1,2,4,3,1,1,1,1,3] ∩ [3,1,-1,0,8,3,3,1]
set(3, 1)

atau jika Anda seperti itu dalam membosankan ol' ffungsi

> my &f = &infix:<∩>
sub infix:<∩> (|p is raw) { #`(Sub+{<anon|130874592>}+{Precedence}|102325600) ... }
> f([3,1,2,4,3,1,1,1,1,3], [3,1,-1,0,8,3,3,1])
set(3, 1)

Retina , 63 byte

Dua baris terakhir menghapus duplikat. Input adalah dua daftar yang dibatasi ruang yang dipisahkan oleh koma. Outputnya dibatasi spasi.

+`( -?\d+)\b(.*,.*)\1\b
$1_$2
-?\d+\b|_|,

+`(-?\d+)(.*)\1
$1$2

Cobalah online

Jika duplikat dalam output diizinkan, program saya akan menjadi 42 byte.

Jq 1,5 , 99 byte

def f(a;b):(a+b|min)as$m|[range($m;a+b|max)|[]]|.[a[]-$m][0]=1|.[b[]-$m][1]=1|.[[[1,1]]]|map(.+$m);

Diperluas

def f(a;b):
     (a+b|min) as $m         # find smallest value in either array
   | [range($m;a+b|max)|[]]  # create array of [] for indices [min,max]
   | .[ a[]-$m ][0]=1        # store 1 in [0] at corresponding indices of a
   | .[ b[]-$m ][1]=1        # store 1 in [1] at corresponding indices of b
   | .[[[1,1]]]              # find all the indices where we stored a 1 for a and b
   | map(.+$m)               # convert back from indices to values
;

Ini menghindari menggunakan {}objek dan karena jq tidak memiliki operasi bit ini mengemulasi mereka dengan array.

Cobalah online!

Aksioma, 411 byte

b(x,v)==(l:=1;h:=#v;repeat(l>h=>break;m:=(l+h)quo 2;x<v.m=>(h:=m-1);x>v.m=>(l:=m+1);return m);0);g(a,b)==(if #a>#b then(v:=a;w:=b)else(v:=b;w:=a);c:=sort(v);for x in w repeat(if binSearch(x,c)~=0 then return 1);0)
f(a:List INT,b:List INT):List INT==(r:List INT:=[];#a*#b=0=>r;x:=sort(a);y:=sort(b);i:=1;repeat(i>#x=>break;v:=x.i;binSearch(v,y)=0=>(i:=i+1);r:=concat(r,v);while i<=#x and x.i=v repeat i:=i+1);r)

ungolf dan tes

--suppose v.1<=v.2<=....<=v.#v as the default function sort() produce
--   binary serch of x in v, return the index i with v.i==x
--   return 0 if that index not exist
--traslated in Axiom from C  book
--Il Linguaggio C, II Edizione 
--Brian W.Kerninghan, Dennis M.Ritchie
binSearch(x,v)==
    l:=1;h:=#v
    repeat
       l>h=>break
       m:=(l+h)quo 2
       x<v.m=>(h:=m-1) 
       x>v.m=>(l:=m+1)
       return m
    0

--N*log(N)+n*log(n)+N*n*log(n) so it is N*n*log(n) or n*N*log(N)
ListIntersection(a:List INT,b:List INT):List INT==
    r:List INT:=[];#a*#b=0=>r
    x:=sort(a);y:=sort(b)
    i:=1
    repeat
        i>#x=>break
        v:=x.i
        binSearch(v,y)=0=>(i:=i+1)
        r:=concat(r,v)
        while i<=#x and x.i=v repeat i:=i+1
    r

(5) -> f([],[])
   (5)  []
                                                       Type: List Integer
(6) -> f([1000],[])
   (6)  []
                                                       Type: List Integer
(7) -> f([3,1,2,4,3,1,1,1,1,3],[3,1,-1,0,8,3,3,1])
   (7)  [1,3]
                                                       Type: List Integer
(8) -> f([1,2,1],[3,3,4])
   (8)  []
                                                       Type: List Integer

Aksioma, 257 byte

W(x,y)==>while x repeat y;f(a,b)==(r:List INT:=[];#a*#b=0=>r;x:=sort(a);y:=sort(b);i:=1;j:=1;repeat(j>#y=>break;W(i<=#x and x.i<y.j,i:=i+1);i>#x=>break;W(j<=#y and y.j<x.i,j:=j+1);j>#y=>break;v:=y.j;if x.i=v then(r:=concat(r,v);W(j<=#y and y.j=v,j:=j+1)));r)

Ini tanpa menggunakan binsearch ... Tetapi saya tidak tahu O besar ... Tidak digabungkan dan hasilnya:

--N*log(N)+n*log(n)+???
ListIntersection(a:List INT,b:List INT):List INT==
    r:List INT:=[];#a*#b=0=>r
    x:=sort(a);y:=sort(b)
    i:=1;j:=1
    repeat
        j>#y=>break
        while i<=#x and x.i<y.j repeat i:=i+1
        i>#x=>break
        while j<=#y and y.j<x.i repeat j:=j+1
        j>#y=>break
        v:=y.j;if x.i=v then 
                        r:=concat(r,v)
                        while j<=#y and y.j=v repeat j:=j+1
    r

(3) -> f([3,1,2,4,3,1,1,1,1,3],[3,1,-1,0,8,3,3,1])
   (3)  [1,3]
                                                       Type: List Integer
(4) -> f([],[])
   (4)  []
                                                       Type: List Integer
(5) -> f([1,2,1],[3,3,4])
   (5)  []
                                                       Type: List Integer

Tidak dieksekusi banyak tes sehingga bisa disadap ...

Jelly , 12 byte

pEÐfḢ€ĠḢ€$ị$

Cobalah online!

Sekam , 9 byte

mo←←kIfE*

Cobalah online!

m            Map
 o←←         taking the first element from the first element
    kI       over lists of identical values from
        *    the Cartesian product of the two input lists
      f      filtered by
       E     both elements of a pair being equal.

Melihat dalam kode sumber Husk di GitHub, k("keyon") diimplementasikan sebagai komposisi pengurutan daftar dan pengelompokan nilai-nilai yang berdekatan, jadi walaupun saya tidak dapat menemukan implementasi "groupOn", mungkin aman untuk mengasumsikan bahwa ia tidak t melakukan apa pun setty, karena Haskell adalah bahasa fungsional dan pengelompokan nilai-nilai yang sama berdekatan adalah operasi mengurangi-over-a-linked-daftar yang cukup mudah. (Saya dapat menemukan implementasi kjenis tanda tangan lain "keyby", yang dapat saya gunakan di sini dengan mengubahI ke =, tapi saya tidak tahu Haskell jadi saya tidak bisa mengatakan bagaimana tepatnya kerjanya.)

Juga, jawaban Brachylog kecil yang menyenangkan yang saya buat sebelum saya menyadari bahwa semua jenis operasi tidak diizinkan: ⟨∋∈⟩ᵘ

R, 141 83 byte

l=sapply(strsplit(readLines(file("stdin"))," "),as.numeric)
r=rle(sort(unlist(l)))[[2]]
r[sapply(r,function(x)any(x==l[[1]])&any(x==l[[2]]))]

Ditingkatkan oleh Giuseppe

function(a,b){r=rle(sort(c(a,b)))[[2]];r[sapply(r,function(x)any(x==a)&any(x==b))]}

Coba online sini sini

Python3, 51 byte

lambda a,b:[v for v in a if{n:1 for n in b}.get(v)]

Jika daftar input dapat berisi duplikat:

Python3, 67 byte

lambda a,b:list({v:1 for v in a if {n:1 for n in b}.get(v)}.keys())

PHP ,78, 77 byte

function($a,$b){foreach($a as$x)foreach($b as$y)$x==$y?$c[$x]=$x:0;return$c;}

Cobalah online!

Tanpa embel-embel, tetapi sesuai aturan (saya pikir).

Keluaran

[], []
[]

[1000], []
[]

[3,1,2,4,3,1,1,1,1,3], [3,1,-1,0,8,3,3,1]
[3,1]

[1,2,1], [3,3,4]
[]