Su objetivo es calcular la intersección establecida de dos listas de enteros. La intersección se define como el grupo único de enteros no ordenados que se encuentra al menos una vez en ambas listas de entrada.

Entrada

La entrada puede estar en cualquier formato deseado (parámetro de función, stdio, etc.) y consta de dos listas de enteros. Es posible que no asuma nada sobre cada lista, aparte de que pueden contener cualquier número no negativo de enteros (es decir, no están clasificados, posiblemente pueden contener duplicados, pueden tener diferentes longitudes e incluso pueden estar vacíos). Se supone que cada número entero encajará en el tipo de entero con signo nativo de su idioma, puede tener más de 1 dígito decimal de longitud y está firmado.

Entrada de ejemplo:

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

Salida

La salida es cualquier lista de enteros que representa la intersección establecida de las dos listas en cualquier formato deseado (valor de retorno, stdio, etc.). No es necesario que se ordene la salida, aunque puede proporcionar una implementación que siempre se ordena. La salida debe formar un conjunto no ordenado válido (por ejemplo, no debe contener ningún valor duplicado).

Ejemplos de casos de prueba (tenga en cuenta que el orden de salida no es importante):

Las primeras dos líneas son las listas de entrada, la tercera línea es la salida. (empty)denota la lista vacía.

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

Puntuación

Este es el código de golf; La respuesta más corta en bytes gana.

Los agujeros de bucle estándar están prohibidos. Puede usar cualquier función incorporada que no esté diseñada para operaciones similares a las de un conjunto.

Funciones incorporadas prohibidas:

• establecer creación / eliminar duplicados
• establecer diferencia / intersección / unión
• Pruebas de membresía generalizadas (por ejemplo, algo similar a la inpalabra clave en Python, indexOffunciones similares, etc.). Tenga en cuenta que el uso de construcciones de "elemento foreach en la lista" está permitido (suponiendo que no violen ninguna de las otras restricciones), a pesar de que Python reutiliza la inpalabra clave para crear esta construcción.
• Estas incorporaciones prohibidas son "virales", es decir, si hay una función incorporada más grande que contenga alguna de estas subcaracterísticas, está igualmente prohibida (por ejemplo, filtrado por membresía en una lista).

Se permiten todos los elementos integrados que no están en la lista anterior (por ejemplo, clasificación, prueba de igualdad de enteros, lista anexar / eliminar por índice, filtrado, etc.).

Por ejemplo, tome los siguientes dos fragmentos de ejemplo (código similar a 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)

Le invitamos a implementar cualquiera de estas características de conjunto usted mismo y contarán para su puntaje.

Su solución debe completarse en un período de tiempo razonable (digamos, menos de un minuto en cualquier hardware que tenga para dos listas ~ 1000 de longitud cada una).

Haskell, 45 42 bytes

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

Pruébalo en línea!

Editar: -2 bytes gracias a @ Ørjan Johansen, -1 byte gracias a @dfeuer.

MATL , 18 bytes

YY_iti!=Xa)hStdfQ)

Pruébalo en línea!

Esto funciona en dos pasos. Primero se calcula la intersección, posiblemente con duplicados. Esto se basa en comparar todos los elementos de una matriz con todos los elementos de la otra y mantener elementos de la primera que están presentes en la segunda.

Luego se eliminan los duplicados. Para esto, se ordena la matriz del paso anterior y las entradas se mantienen si son diferentes de las anteriores. Se -infantepone un valor para que el primer valor (es decir, el más bajo) no se pierda.

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

Jalea, 13 bytes

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

Pruébalo en línea!

Cómo 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 se llama 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

En Lua regular, esto sería

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

Entonces, básicamente, estoy iterando sobre cada elemento de las dos tablas y solo almacenando los valores equivalentes. Al usar el valor como la clave ( k[w]=w), estoy eliminando todos los duplicados. Luego sacamos la nueva tabla iterando sobre el índice y el 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))

Sin usar indexOf, ya que no estoy convencido de que esté permitido.

Pyth, 12 11 bytes

eMrSsq#RQE8

Demostración

Explicación:

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

Invocación:

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

Salida:

4
56
3

No hay salida si la intersección está vacía. Este script no ordena y realiza una comprobación de cordura si el primer conjunto está vacío. Explicación:

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

Bonificación para saber: puede cambiar grep -o .para hacer esto con cadenas aleatorias en lugar 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)

Descarada respuesta no competitiva

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

o si te gusta en una ffunción aburrida

> 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

Las dos últimas líneas eliminan duplicados. La entrada es dos listas delimitadas por espacios separadas por una coma. La salida está delimitada por espacios en blanco.

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

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

Pruébalo en línea

Si se permiten duplicados en la salida, mi programa tendría 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
;

Esto evita el uso de {}objetos y dado que jq no tiene operaciones de bits, los emula con una matriz.

Pruébalo en línea!

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

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

Esto sin el uso de binsearch ... Pero no sé el gran O ... Unglofed y los 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

No se ejecutaron muchas pruebas, por lo que podría tener errores ...

Jalea , 12 bytes

pEÐfḢ€ĠḢ€$ị$

Pruébalo en línea!

Casco , 9 bytes

mo←←kIfE*

Pruébalo en línea!

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.

Mirando el código fuente de Husk en GitHub, k("keyon") se implementa como la composición de ordenar la lista y agrupar valores adyacentes, por lo que aunque no puedo encontrar la implementación de "groupOn", probablemente sea seguro asumir que no lo hace. No haga nada, ya que Haskell es un lenguaje funcional y la agrupación de valores iguales adyacentes es una operación bastante sencilla de reducción de una lista enlazada. (I puedo encontrar la puesta en práctica de k's otro tipo de firma 'keyby', que podría utilizar aquí cambiandoI a =, pero no sé Haskell así que no puedo decir cómo funciona exactamente.)

Además, una pequeña y agradable respuesta de Brachylog que se me ocurrió antes de darme cuenta de que no se permitieron operaciones de todo tipo: ⟨∋∈⟩ᵘ

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

Mejorado por Giuseppe

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

Probar en línea aquí aquí

Python3, 51 bytes

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

Si las listas de entrada pueden contener duplicados:

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

Pruébalo en línea!

Sin lujos, pero cumple con las reglas (creo).

Salida

[], []
[]

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