Votre objectif est de calculer l'intersection définie de deux listes d'entiers. L'intersection est définie comme le groupe unique non ordonné d'entiers trouvé au moins une fois dans les deux listes d'entrée.

Contribution

L'entrée peut être dans n'importe quel format souhaité (paramètre de fonction, stdio, etc.) et se compose de deux listes d'entiers. Vous êtes nombreux à ne pas supposer quoi que ce soit sur chaque liste, sinon qu'ils peuvent contenir un nombre non négatif d'entiers (c'est-à-dire qu'ils ne sont pas triés, peuvent éventuellement contenir des doublons, peuvent avoir des longueurs différentes et peuvent même être vides). Il est supposé que chaque entier rentrera dans le type d'entier natif signé de votre langue, qu'il pourra comporter plus de 1 chiffre décimal et qu'il sera signé.

Exemple d'entrée:

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

Production

La sortie est une liste entière d'entiers représentant l'intersection définie des deux listes dans le format souhaité (valeur de retour, stdio, etc.). Il n'est pas nécessaire que la sortie soit triée, mais vous êtes invité à fournir une implémentation qui se trouve toujours être triée. La sortie doit former un ensemble non ordonné valide (par exemple, elle ne doit contenir aucune valeur en double).

Exemples de cas de test (notez que l'ordre de sortie n'est pas important):

Les deux premières lignes sont les listes d'entrée, la troisième ligne est la sortie. (empty)désigne la liste vide.

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

Notation

C'est le golf de code; la réponse la plus courte en octets l'emporte.

Les trous de boucle standard sont interdits. Vous pouvez utiliser toutes les fonctionnalités intégrées non conçues pour des opérations de type ensemble.

Fonctions intégrées interdites:

• création / suppression de doublons
• définir la différence / intersection / union
• Test d'appartenance généralisé (par exemple, quelque chose de similaire au inmot - clé dans Python, des indexOffonctions similaires , etc.). Notez que l'utilisation des constructions "foreach item in list" est autorisée (en supposant qu'elles ne violent aucune des autres restrictions), malgré le fait que Python réutilise le inmot - clé pour créer cette construction.
• Ces éléments intégrés interdits sont "viraux", c'est-à-dire que s'il existe un élément intégré plus grand contenant l'une de ces sous-fonctionnalités, il est également interdit (par exemple, filtrage par appartenance à une liste).

Tous les éléments intégrés ne figurant pas dans la liste ci-dessus sont autorisés (par exemple, tri, test d'égalité des nombres entiers, ajout / suppression de liste par index, filtrage, etc.).

Par exemple, prenez les deux exemples d'extraits suivants (code de type 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)

Vous êtes invités à implémenter vous-même l'une de ces fonctionnalités de type ensemble et elles compteront pour votre score.

Votre solution devrait se terminer dans un délai raisonnable (disons, moins d'une minute sur le matériel que vous avez pour deux listes ~ longueur 1000 chacune).

Haskell, 45 42 octets

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

Essayez-le en ligne!

Edit: -2 octets grâce à @ Ørjan Johansen, -1 octet grâce à @dfeuer.

MATL , 18 octets

YY_iti!=Xa)hStdfQ)

Essayez-le en ligne!

Cela fonctionne en deux étapes. L'intersection est d'abord calculée, éventuellement avec des doublons. Ceci est basé sur la comparaison de tous les éléments d'un tableau avec tous les éléments de l'autre et sur la conservation des éléments du premier présents dans le second.

Ensuite, les doublons sont supprimés. Pour cela, le tableau de l'étape précédente est trié et les entrées sont conservées si différentes de la précédente. Une -infvaleur est ajoutée avant que la première valeur (c'est-à-dire la plus basse) ne soit perdue.

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

Gelée, 13 octets

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

Essayez-le en ligne!

Comment ça fonctionne

Ṃ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 caractères

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

qui s'appelle comme

> 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

Dans Lua régulière, ce serait

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

Donc, fondamentalement, j'itère sur chaque élément des deux tables et ne stocke que les valeurs équivalentes. En utilisant la valeur comme clé ( k[w]=w), j'élimine tous les doublons. Nous sortons ensuite la nouvelle table en itérant sur l' indice et la valeur depairs

JavaScript (ES6), 66 octets

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

Sans utiliser indexOf, car je ne suis pas convaincu que ce soit permis.

Pyth, 12 11 octets

eMrSsq#RQE8

Manifestation

Explication:

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 octets

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

Invocation:

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

Production:

4
56
3

Aucune sortie si l'intersection est vide. Ce script ne trie pas et vérifie la validité si le premier ensemble est vide. Explication:

[ -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 à savoir: vous pouvez changer pour grep -o .le faire avec des chaînes aléatoires au lieu de chiffres.

Perl 6, 26 37 octets

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

usage

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

Réponse non compétitive effrontée

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

ou si vous aimez dans un ennuyeux ol » ffonction

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

Rétine , 63 octets

Les deux dernières lignes suppriment les doublons. L'entrée est constituée de deux listes séparées par des espaces séparées par une virgule. La sortie est séparée par des espaces.

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

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

Essayez-le en ligne

Si les doublons dans la sortie sont autorisés, mon programme serait de 42 octets.

Jq 1,5 , 99 octets

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

Étendu

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
;

Cela évite d'utiliser des {}objets et puisque jq n'a pas d'opérations sur les bits, cela les émule avec un tableau.

Essayez-le en ligne!

Axiome, 411 octets

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

Axiome, 257 octets

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)

Ceci sans l'utilisation de binsearch ... Mais je ne connais pas le grand O ... Unglofed et les résultats:

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

Pas exécuté beaucoup de tests donc pourrait être buggé ...

Gelée , 12 octets

pEÐfḢ€ĠḢ€$ị$

Essayez-le en ligne!

Husk , 9 octets

mo←←kIfE*

Essayez-le en ligne!

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.

La recherche dans le code source de Husk sur GitHub, k("keyon") est implémentée comme la composition du tri de la liste et du regroupement des valeurs adjacentes, donc bien que je ne puisse pas réellement trouver l'implémentation de "groupOn", il est probablement sûr de supposer qu'il ne fonctionne pas ' t ne rien faire, car Haskell est un langage fonctionnel et le regroupement de valeurs égales adjacentes est une opération assez simple de réduction sur une liste liée. (Je peux trouver l'implémentation de kl'autre type de signature "keyby", que je pourrais utiliser ici en changeantI en =, mais je ne connais pas Haskell, donc je ne peux pas dire exactement comment cela fonctionne.)

Aussi, une belle petite réponse Brachylog que j'ai trouvée avant de réaliser que les opérations de set de toutes sortes étaient interdites: ⟨∋∈⟩ᵘ

R, 141 83 octets

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

Amélioré par Giuseppe

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

Essayez en ligne ici ici

Python3, 51 octets

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

Si les listes d'entrée peuvent contenir des doublons:

Python3, 67 octets

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

PHP ,78, 77 octets

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

Essayez-le en ligne!

Pas de fioritures, mais conforme aux règles (je pense).

Production

[], []
[]

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