Twoim celem jest obliczenie ustawionego przecięcia dwóch list liczb całkowitych. Przecięcie jest zdefiniowane jako unikalna nieporządkowana grupa liczb całkowitych znaleziona co najmniej raz na obu listach wejściowych.

Wejście

Dane wejściowe mogą być w dowolnym pożądanym formacie (parametr funkcji, stdio itp.) I składają się z dwóch list liczb całkowitych. Wielu nie zakłada niczego na temat każdej listy poza tym, że mogą zawierać nieujemną liczbę liczb całkowitych (tzn. Są nieposortowane, prawdopodobnie mogą zawierać duplikaty, mogą mieć różne długości, a nawet mogą być puste). Zakłada się, że każda liczba całkowita będzie pasować do natywnego typu liczb całkowitych w twoim języku, może być dłuższa niż 1 cyfra dziesiętna i są podpisane.

Przykładowe dane wejściowe:

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

Wynik

Dane wyjściowe są dowolnymi listowymi liczbami całkowitymi reprezentującymi ustawione przecięcie dwóch list do dowolnego pożądanego formatu (zwracana wartość, stdio itp.). Nie ma wymogu sortowania danych wyjściowych, ale można podać implementację, która zawsze jest sortowana. Dane wyjściowe muszą stanowić prawidłowy niez uporządkowany zestaw (np. Nie może zawierać żadnych zduplikowanych wartości).

Przykładowe przypadki testowe (zauważ, że kolejność danych wyjściowych nie jest ważna):

Pierwsze dwa wiersze to listy wejściowe, trzeci wiersz to wynik. (empty)oznacza pustą listę.

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

Punktacja

To jest kod golfowy; najkrótsza odpowiedź w bajtach wygrywa.

Standardowe otwory na pętle są zabronione. Możesz używać dowolnych wbudowanych funkcji nieprzeznaczonych do operacji podobnych do zestawu.

Zabronione wbudowane funkcje:

• ustaw tworzenie / usuwanie duplikatów
• ustaw różnicę / przecięcie / połączenie
• Uogólnione testowanie członkostwa (np. Cokolwiek podobnego do insłowa kluczowego w Pythonie, indexOffunkcje podobne do itp.). Zauważ, że użycie konstrukcji „foreach item in list” jest dozwolone (zakładając, że nie naruszają one żadnych innych ograniczeń), pomimo faktu, że Python ponownie używa insłowa kluczowego do stworzenia tego konstruktu.
• Te zabronione wbudowane elementy są „wirusowe”, tzn. Jeśli istnieje większa wbudowana zawierająca którąkolwiek z tych podfunkcji, jest to podobnie zabronione (np. Filtrowanie według członkostwa na liście).

Dozwolone są wszystkie wbudowania niewymienione na powyższej liście (np. Sortowanie, testowanie równości w liczbach całkowitych, dodawanie / usuwanie listy według indeksu, filtrowanie itp.).

Na przykład weźmy następujące dwa przykładowe fragmenty (kod podobny do języka 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)

Możesz sam zaimplementować dowolne z tych zestawów funkcji, które będą się liczyć do twojego wyniku.

Twoje rozwiązanie powinno zakończyć się w rozsądnym czasie (powiedzmy, mniej niż minutę na dowolnym sprzęcie dla dwóch list ~ długość 1000 każda).

Haskell, 45 42 bajtów

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

Wypróbuj online!

Edycja: -2 bajty dzięki @ Ørjan Johansen, -1 bajtów dzięki @dfeuer.

MATL , 18 bajtów

YY_iti!=Xa)hStdfQ)

Wypróbuj online!

Działa to w dwóch etapach. Najpierw obliczane jest skrzyżowanie, prawdopodobnie z duplikatami. Polega to na porównaniu wszystkich elementów jednej tablicy ze wszystkimi elementami drugiego i zachowaniu elementów pierwszego, które są obecne w drugim.

Następnie duplikaty są usuwane. W tym celu tablica z poprzedniego kroku jest sortowana, a wpisy są zachowywane, jeśli różnią się od poprzednich. -infWartość jest poprzedzany tak, że pierwszy (czyli najniższy) wartość nie jest stracone.

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

Galaretka, 13 bajtów

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

Wypróbuj online!

Jak to działa

Ṃ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 znaków

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

który nazywa się jako

> 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

W zwykłym Lua byłoby to

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

Więc w zasadzie iteruję każdy element dwóch tabel i przechowuję tylko równoważne wartości. Używając wartości jako key ( k[w]=w), eliminuję wszystkie duplikaty. Następnie generujemy nową tabelę, iterując indeks i wartośćpairs

JavaScript (ES6), 66 bajtów

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

Bez użycia indexOf, ponieważ nie jestem przekonany, że jest to dozwolone.

Pyth, 12 11 bajtów

eMrSsq#RQE8

Demonstracja

Wyjaśnienie:

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 bajtów

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

Wezwanie:

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

Wynik:

4
56
3

Brak danych wyjściowych, jeśli skrzyżowanie jest puste. Ten skrypt nie sortuje i sprawdza, czy pierwszy zestaw jest pusty. Wyjaśnienie:

[ -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 wiedzieć: Możesz zmienić, grep -o .aby zrobić to z losowymi ciągami zamiast liczb.

Perl 6, 26 37 bajtów

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

stosowanie

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

Bezczelna niekonkurencyjna odpowiedź

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

lub jeśli ci się podoba w nudnej ffunkcji ol '

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

Siatkówka , 63 bajty

Ostatnie dwa wiersze usuwają duplikaty. Dane wejściowe to dwie rozdzielane spacjami listy oddzielone przecinkiem. Dane wyjściowe są rozdzielane białymi znakami.

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

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

Wypróbuj online

Jeśli duplikaty danych wyjściowych są dozwolone, mój program będzie miał 42 bajty.

Jq 1,5 , 99 bajtów

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

Rozszerzony

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
;

Pozwala to uniknąć używania {}obiektów, a ponieważ jq nie ma operacji bitowych, emuluje je za pomocą tablicy.

Wypróbuj online!

Aksjomat, 411 bajtów

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)

golf i test

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

Aksjomat, 257 bajtów

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)

To bez użycia binsearch ... Ale nie znam wielkiego O ... Unglofed i wyników:

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

Nie wykonałem wielu testów, więc mógł zostać uszkodzony ...

Galaretka , 12 bajtów

pEÐfḢ€ĠḢ€$ị$

Wypróbuj online!

Łuska , 9 bajtów

mo←←kIfE*

Wypróbuj 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.

Patrząc w kodzie źródłowym kHuska na GitHub, („keyon”) jest zaimplementowany jako skład sortowania listy i grupowania sąsiednich wartości, więc chociaż nie mogę znaleźć implementacji „groupOn”, prawdopodobnie bezpiecznie jest założyć, że tak nie jest t rób cokolwiek, ponieważ Haskell jest językiem funkcjonalnym, a grupowanie sąsiednich równych wartości jest dość prostą operacją zmniejszania nad połączoną listą. (I można znaleźć realizację k„s inny rodzaj podpisu«keyby», które mógłbym wykorzystać tutaj, zmieniając Isię =, ale nie wiem, Haskell, więc nie mogę powiedzieć, jak dokładnie to działa).

Również miła, mała odpowiedź Brachyloga, którą wymyśliłam, zanim zdałam sobie sprawę, że wszystkie operacje na zestawach zostały odrzucone: ⟨∋∈⟩ᵘ

R, 141 83 bajty

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

Ulepszony przez Giuseppe

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

Wypróbuj online tutaj tutaj

Python3, 51 bajtów

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

Jeśli listy wejściowe mogą zawierać duplikaty:

Python3, 67 bajtów

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

PHP ,78, 77 bajtów

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

Wypróbuj online!

Bez fanaberii, ale zgodne z regułami (myślę).

Wynik

[], []
[]

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