Ваша цель - вычислить пересечение множества двух списков целых чисел. Пересечение определяется как уникальная неупорядоченная группа целых чисел, найденная хотя бы один раз в обоих входных списках.

вход

Входные данные могут быть в любом желаемом формате (параметр функции, stdio и т. Д.) И состоят из двух списков целых чисел. Многие не предполагают, что в каждом списке есть что-то еще, кроме того, что они могут содержать любое неотрицательное число целых чисел (т.е. они не отсортированы, возможно, могут содержать дубликаты, могут иметь разную длину и даже могут быть пустыми). Предполагается, что каждое целое число будет соответствовать целочисленному типу вашего языка со знаком, может иметь длину более 1 десятичного знака и быть подписанным.

Пример ввода:

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

Вывод

Выходными данными являются любые списки целых чисел, представляющие пересечение множества двух списков с любым требуемым форматом (возвращаемое значение, stdio и т. Д.). Нет необходимости сортировать выходные данные, хотя вы можете предоставить реализацию, которая всегда сортируется. Выходные данные должны формировать допустимый неупорядоченный набор (например, он не должен содержать повторяющихся значений).

Примеры тестовых случаев (обратите внимание, что порядок вывода не важен):

Первые две строки - это входные списки, третья строка - это выходные данные. (empty)обозначает пустой список.

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

счет

Это код гольф; кратчайший ответ в байтах побеждает.

Стандартные лазейки запрещены. Вы можете использовать любые встроенные функции, не предназначенные для операций, подобных множеству.

Запрещенные встроенные функции:

• установить создание / удаление дубликатов
• установить разность / пересечение / объединение
• Обобщенное тестирование членства (например, что-либо похожее на inключевое слово в Python, подобные indexOfфункции и т. Д.). Обратите внимание, что допускается использование конструкций «foreach item in list» (при условии, что они не нарушают никаких других ограничений), несмотря на то, что Python повторно использует inключевое слово для создания этой конструкции.
• Эти запрещенные встроенные функции являются «вирусными», т. Е. Если имеется более крупный встроенный модуль, содержащий какие-либо из этих подфункций, он также запрещается (например, фильтрация по членству в списке).

Разрешены любые встроенные модули, отсутствующие в приведенном выше списке (например, сортировка, проверка целочисленного равенства, добавление / удаление списка по индексу, фильтрация и т. Д.).

Например, возьмем следующие два примера фрагментов (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)

Вы можете самостоятельно реализовать любую из этих функций, подобных множеству, и они будут учитываться при подсчете очков.

Ваше решение должно быть выполнено за разумное время (скажем, менее чем за минуту на любом оборудовании, которое у вас есть для двух списков ~ длина 1000 каждый).

Haskell, 45 42 байта

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

Попробуйте онлайн!

Редактировать: -2 байта благодаря @ Örjan Johansen, -1 байт благодаря @dfeuer.

MATL , 18 байт

YY_iti!=Xa)hStdfQ)

Попробуйте онлайн!

Это работает в два этапа. Сначала вычисляется пересечение, возможно, с дубликатами. Это основано на сравнении всех элементов одного массива со всеми элементами другого и сохранении элементов первого, которые присутствуют во втором.

Затем дубликаты удаляются. Для этого сортируется массив из предыдущего шага, и записи сохраняются, если они отличаются от предыдущего. -infЗначение предваряется таким образом , что первый (то есть самое низкое) значение не теряется.

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

Желе, 13 байт

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

Попробуйте онлайн!

Как это работает

Ṃ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 символов

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

который называется как

> 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

В обычном Lua это было бы

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

В общем, я перебираю каждый элемент двух таблиц и сохраняю только эквивалентные значения. Используя значение в качестве ключа ( k[w]=w), я удаляю все дубликаты. Затем мы выводим новую таблицу, перебирая индекс и значениеpairs

JavaScript (ES6), 66 байт

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

Без использования indexOf, так как я не уверен, что это разрешено.

Pyth, 12 11 байтов

eMrSsq#RQE8

демонстрация

Объяснение:

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 байта

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

Призвание:

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

Вывод:

4
56
3

Нет выходных данных, если пересечение пусто. Этот скрипт не сортирует и проверяет работоспособность, если первый набор пуст. Объяснение:

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

Бонус, чтобы знать: вы можете изменить это, grep -o .чтобы сделать это со случайными строками вместо чисел.

Perl 6, 26 37 байт

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

Применение

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

Нахальный неконкурентный ответ

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

или если вам нравится это в скучной старой fфункции

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

Сетчатка , 63 байта

Последние две строки удаляют дубликаты. Входные данные представляют собой два списка, разделенных пробелами, разделенных запятой. Выходные данные разделяются пробелами.

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

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

Попробуйте онлайн

Если дубликаты в выводе разрешены, моя программа будет 42 байта.

Jq 1,5 , 99 байт

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

расширенный

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
;

Это позволяет избежать использования {}объектов и, поскольку jq не имеет битовых операций, это эмулирует их с массивом.

Попробуйте онлайн!

Аксиома, 411 байт

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)

разгрызть и проверить

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

Аксиома, 257 байт

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)

Это без использования binsearch ... Но я не знаю, большой O ... Unglofed и результаты:

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

Не выполнено много тестов, поэтому может быть прослушан ...

Желе , 12 байт

pEÐfḢ€ĠḢ€$ị$

Попробуйте онлайн!

Шелуха , 9 байт

mo←←kIfE*

Попробуйте онлайн!

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.

Глядя в исходный код Husk на GitHub, k("keyon") реализован как композиция сортировки списка и группировки смежных значений, поэтому, хотя я не могу найти реализацию "groupOn", вероятно, можно с уверенностью предположить, что это не так. ничего не делать, поскольку Haskell - это функциональный язык, а группировка смежных равных значений - довольно простая операция сокращения со списком ссылок. (Я могу найти реализацию kсигнатуры другого типа "keyby", которую я мог бы использовать здесь, изменив Iна =, но я не знаю Haskell, поэтому не могу сказать, как именно это работает.)

Кроме того, хороший ответ Brachylog, который я придумал, прежде чем я понял, что операции над множествами всех видов запрещены: ⟨∋∈⟩ᵘ

Р, 141 83 байта

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

Улучшено Джузеппе

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

Попробуй онлайн Вот Вот

Python3, 51 байт

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

Если входные списки могут содержать дубликаты:

Python3, 67 байт

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

PHP ,7877 байт

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

Попробуйте онлайн!

Без излишеств, но в соответствии с правилами (я думаю).

Вывод

[], []
[]

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