Seu objetivo é calcular a interseção definida de duas listas de números inteiros. A interseção é definida como o único grupo não ordenado de números inteiros encontrado pelo menos uma vez na lista de entradas.

Entrada

A entrada pode estar em qualquer formato desejado (parâmetro de função, stdio, etc.) e consiste em duas listas de números inteiros. Muitos não assumem nada sobre cada lista, exceto que eles podem conter um número não negativo de números inteiros (ou seja, eles não são classificados, possivelmente podem conter duplicatas, podem ter comprimentos diferentes e podem até estar vazios). Supõe-se que cada número inteiro se encaixe no tipo de número inteiro assinado nativo do seu idioma, pode ter mais de 1 dígito decimal e está assinado.

Exemplo de entrada:

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

Resultado

A saída é qualquer lista de números inteiros representando a interseção definida das duas listas para qualquer formato desejado (valor de retorno, stdio, etc.). Não há requisito para que a saída seja classificada, mas você pode fornecer uma implementação que sempre é classificada. A saída deve formar um conjunto não ordenado válido (por exemplo, não deve conter valores duplicados).

Exemplos de casos de teste (observe que a ordem da saída não é importante):

As duas primeiras linhas são as listas de entrada, a terceira linha é a saída. (empty)denota a lista vazia.

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

Pontuação

Isso é código de golfe; a resposta mais curta em bytes vence.

Furos de loop padrão são proibidos. Você pode usar quaisquer recursos internos não projetados para operações do tipo conjunto.

Recursos internos proibidos:

• definir criação / remover duplicatas
• definir diferença / interseção / união
• Teste de associação generalizada (por exemplo, algo semelhante à inpalavra - chave em Python, indexOffunções semelhantes, etc). Observe que o uso de construções "foreach item in list" é permitido (supondo que elas não violem nenhuma das outras restrições), apesar do Python reutilizar a inpalavra-chave para criar essa construção.
• Esses embutidos proibidos são "virais", ou seja, se houver um embutido maior contendo algum desses sub-recursos, é igualmente proibido (por exemplo, filtragem por associação em uma lista).

Quaisquer embutidos que não estejam na lista acima são permitidos (por exemplo, classificação, teste de igualdade de números inteiros, inclusão / remoção de lista por índice, filtragem etc.).

Por exemplo, pegue os seguintes dois trechos de exemplo (código semelhante ao 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)

Você pode implementar qualquer um desses recursos semelhantes a um conjunto e eles contarão para sua pontuação.

Sua solução deve ser concluída em um período de tempo razoável (digamos, menos de um minuto em qualquer hardware que você tenha para duas listas com comprimento de 1000 cada).

Haskell, 45 42 bytes

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

Experimente online!

Edit: -2 bytes graças a Ørjan Johansen, -1 byte graças a @dfeuer.

MATL , 18 bytes

YY_iti!=Xa)hStdfQ)

Experimente online!

Isso funciona em duas etapas. Primeiro, a interseção é calculada, possivelmente com duplicatas. Isso se baseia na comparação de todos os elementos de uma matriz com todos os elementos da outra e na manutenção dos elementos da primeira que estão presentes na segunda.

Em seguida, as duplicatas são removidas. Para isso, a matriz da etapa anterior é classificada e as entradas são mantidas se diferentes da anterior. Um -infvalor é anexado para que o primeiro valor (ou seja, o mais baixo) não seja perdido.

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

Gelatina, 13 bytes

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

Experimente online!

Como funciona

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

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

que é chamado como

> 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

Em Lua normal, isso seria

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

Então, basicamente, eu estou iterando sobre cada elemento das duas tabelas e armazenando apenas os valores equivalentes. Usando o valor como a chave ( k[w]=w), estou eliminando todas as duplicatas. Em seguida, produzimos a nova tabela iterando sobre o índice e o valor depairs

JavaScript (ES6), 66 bytes

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

Sem usar indexOf, pois não estou convencido de que seja permitido.

Pitão, 12 11 bytes

eMrSsq#RQE8

Demonstração

Explicação:

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 + núcleo GNU, 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")

Invocação:

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

Resultado:

4
56
3

Nenhuma saída se a interseção estiver vazia. Este script não classifica e verifica a integridade se o primeiro conjunto estiver vazio. Explicação:

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

Bônus a saber: você pode mudar grep -o .para fazer isso com seqüências aleatórias em vez de números.

Perl 6, 26 37 bytes

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

uso

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

Resposta não competitiva atrevida

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

ou se você gosta de uma ffunção chata e velha

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

As duas últimas linhas removem duplicatas. A entrada são duas listas delimitadas por espaço, separadas por vírgula. A saída é delimitada por espaço em branco.

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

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

Experimente online

Se duplicatas na saída forem permitidas, meu programa será de 42 bytes.

Jq 1.5 , 99 bytes

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

Expandido

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
;

Isso evita o uso de {}objetos e, como o jq não possui operações de bit, ele os emula com uma matriz.

Experimente online!

Axioma, 411 bytes

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

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

Axioma, 257 bytes

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)

Isso sem o uso de binsearch ... Mas eu não conheço o grande O ... Unglofed e resultados:

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

Não foram executados muitos testes, portanto podem ser corrigidos ...

Gelatina , 12 bytes

pEÐfḢ€ĠḢ€$ị$

Experimente online!

Casca , 9 bytes

mo←←kIfE*

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

Observando o código-fonte da Husk no GitHub, k("keyon") é implementado como a composição da classificação da lista e do agrupamento de valores adjacentes, portanto, embora eu não consiga encontrar a implementação do "groupOn", é provável que seja seguro assumir que ele não é ' Não faça nada instável, já que Haskell é uma linguagem funcional e o agrupamento de valores iguais adjacentes é uma operação bastante simples de reduzir sobre uma lista vinculada. (Eu posso encontrar a implementação do koutro tipo de assinatura "keyby", que eu poderia usar aqui mudando Ipara =, mas não conheço Haskell, então não sei dizer exatamente como ele funciona.)

Além disso, uma boa e pequena resposta Brachylog que eu criei antes de perceber que operações de todos os tipos eram proibidas: ⟨∋∈⟩ᵘ

R, 141 83 bytes

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

Melhorado por Giuseppe

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

Experimente on-line aqui aqui

Python3, 51 bytes

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

Se as listas de entrada puderem conter duplicatas:

Python3, 67 bytes

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

PHP ,78, 77 bytes

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

Experimente online!

Sem frescura, mas em conformidade com as regras (eu acho).

Resultado

[], []
[]

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