Schnittpunkt zweier Listen festlegen

10

Ihr Ziel ist es, den festgelegten Schnittpunkt zweier Ganzzahllisten zu berechnen. Der Schnittpunkt ist definiert als die eindeutige ungeordnete Gruppe von Ganzzahlen, die mindestens einmal in beiden Eingabelisten gefunden wird.

Eingang

Die Eingabe kann in jedem gewünschten Format (Funktionsparameter, stdio usw.) erfolgen und besteht aus zwei Listen von Ganzzahlen. Sie nehmen viele nichts anderes an, als dass sie eine nicht negative Anzahl von Ganzzahlen enthalten (dh sie sind unsortiert, enthalten möglicherweise Duplikate, haben unterschiedliche Längen und sind möglicherweise sogar leer). Es wird davon ausgegangen, dass jede Ganzzahl in den muttersprachlichen Ganzzahltyp Ihrer Sprache passt, mehr als eine Dezimalstelle lang sein kann und vorzeichenbehaftet ist.

Beispieleingabe:

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

Ausgabe

Die Ausgabe ist eine beliebige listähnliche Anzahl von Ganzzahlen, die den festgelegten Schnittpunkt der beiden Listen in einem beliebigen Format (Rückgabewert, Standard usw.) darstellen. Es ist nicht erforderlich, dass die Ausgabe sortiert wird. Sie können jedoch auch eine Implementierung bereitstellen, die zufällig immer sortiert ist. Die Ausgabe muss eine gültige ungeordnete Menge bilden (z. B. darf sie keine doppelten Werte enthalten).

Beispieltestfälle (beachten Sie, dass die Reihenfolge der Ausgabe nicht wichtig ist):

Die ersten beiden Zeilen sind die Eingabelisten, die dritte Zeile ist die Ausgabe. (empty)bezeichnet die leere Liste.

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

Wertung

Das ist Code Golf; Die kürzeste Antwort in Bytes gewinnt.

Standardschlupflöcher sind verboten. Sie können alle integrierten Funktionen verwenden, die nicht für satzähnliche Vorgänge ausgelegt sind.

Verbotene integrierte Funktionen:

  • Festlegen der Erstellung / Entfernung von Duplikaten
  • Differenz / Schnittpunkt / Vereinigung einstellen
  • Verallgemeinerte Mitgliedschaftstests (z. B. alles, was dem inSchlüsselwort in Python ähnelt , indexOfähnliche Funktionen usw.). Beachten Sie, dass die Verwendung von "foreach item in list" -Konstrukten zulässig ist (vorausgesetzt, sie verstoßen nicht gegen eine der anderen Einschränkungen), obwohl Python das inSchlüsselwort zum Erstellen dieses Konstrukts erneut verwendet.
  • Diese verbotenen integrierten Funktionen sind "viral". Wenn also eine größere integrierte Funktion eine dieser Unterfunktionen enthält, ist dies ebenfalls verboten (z. B. Filtern nach Mitgliedschaft in einer Liste).

Alle integrierten Funktionen, die nicht in der obigen Liste enthalten sind, sind zulässig (z. B. Sortieren, Testen der Ganzzahlgleichheit, Anhängen / Entfernen der Liste nach Index, Filtern usw.).

Nehmen Sie zum Beispiel die folgenden zwei Beispielausschnitte (Python-ähnlichen Code):

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

Sie können diese Set-ähnlichen Funktionen gerne selbst implementieren und sie werden für Ihre Punktzahl angerechnet.

Ihre Lösung sollte in angemessener Zeit abgeschlossen sein (z. B. weniger als eine Minute auf der Hardware, die Sie für zwei Listen mit einer Länge von jeweils 1000 haben).

helloworld922
quelle
5
Übrigens sind Verwirrung und Missverständnisse bei do X ohne Y häufig , weshalb sie offiziell eine der Dinge sind, die beim Schreiben von Herausforderungen vermieden werden sollten .
Dennis
2
@Dennis Ja, ich denke, dieses Problem ist wirklich eines davon geworden :( Als ich es zum ersten Mal schrieb, hatte ich gehofft, dass es ein interessantes Problem sein könnte, aber sobald ich anfing, einen Regelsatz auszuarbeiten, hätte ich die Herausforderung einfach beenden sollen.
helloworld922
Ist ein eingebautes Programm zur Ausführung der Lauflängencodierung zulässig?
isaacg
Das sollte gehen.
helloworld922
1
Kann die Ausgabe Duplikate enthalten?
Adám

Antworten:

7

Haskell, 45 42 Bytes

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

Probieren Sie es online aus!

Bearbeiten: -2 Bytes dank @ Ørjan Johansen, -1 Bytes dank @dfeuer.

Nimi
quelle
Dies ist bei expliziter Rekursion 2 Byte kürzer .
Ørjan Johansen
@ ØrjanJohansen, 1 mehr .
Feuer
4

MATL , 18 Bytes

YY_iti!=Xa)hStdfQ)

Probieren Sie es online aus!

Dies funktioniert in zwei Schritten. Zuerst wird der Schnittpunkt berechnet, möglicherweise mit Duplikaten. Dies basiert auf dem Vergleich aller Elemente eines Arrays mit allen Elementen des anderen und dem Beibehalten der Elemente des ersten, die im zweiten vorhanden sind.

Dann werden Duplikate entfernt. Dazu wird das Array aus dem vorherigen Schritt sortiert und Einträge werden beibehalten, wenn sie sich vom vorherigen unterscheiden. Ein -infWert wird vorangestellt, damit der erste (dh niedrigste) Wert nicht verloren geht.

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
Luis Mendo
quelle
4

Gelee, 13 Bytes

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

Probieren Sie es online aus!

Wie es funktioniert

Ṃ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.
Dennis
quelle
@isaacg Jetzt behoben.
Dennis
3

Golflua , 68 Zeichen

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

das heißt als

> 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

In der regulären Lua wäre dies

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

Im Grunde genommen iteriere ich also über jedes Element der beiden Tabellen und speichere nur die entsprechenden Werte. Indem k[w]=wich den Wert als Schlüssel ( ) verwende, entferne ich alle Duplikate. Wir geben dann die neue Tabelle aus, indem wir über den Index und den Wert von iterierenpairs

Kyle Kanos
quelle
3

JavaScript (ES6), 66 Byte

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

Ohne zu verwenden indexOf, da ich nicht davon überzeugt bin, dass es erlaubt ist.

Neil
quelle
3

Pyth, 12 11 Bytes

eMrSsq#RQE8

Demonstration

Erläuterung:

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.
isaacg
quelle
Sortieren und rle spart ein Byte.
Jakube
@ Jakube Ich würde sagen, rle ist ein eingebautes Gerät, das Duplikate entfernt.
isaacg
Duplikate werden nur entfernt, wenn Sie sie zuvor sortieren und anschließend die Anzahl der Rle entfernen. Es ist ein bisschen in einer Grauzone, aber ich denke, es wird ein Wörterbuch verwendet. Es ist im Grunde eine Menge, die zusätzliche Daten für jedes Element speichert.
Jakube
@ Jakube OP sagt, es ist in Ordnung. Vielen Dank!
isaacg
2

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

Aufruf:

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

Ausgabe:

4
56
3

Keine Ausgabe, wenn die Kreuzung leer ist. Dieses Skript sortiert nicht und führt eine Überprüfung der Integrität durch, wenn der erste Satz leer ist. Erläuterung:

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

Zu wissender Bonus: Sie können grep -o .dies auch mit zufälligen Zeichenfolgen anstelle von Zahlen ändern .

Rexkogitans
quelle
2

Perl 6, 26 37 Bytes

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

Verwendungszweck

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

Freche, nicht konkurrierende Antwort

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

oder wenn Sie es in einer langweiligen alten fFunktion mögen

> 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)
Hotkeys
quelle
Ich habe meine Antwort aktualisiert, um .unique
Hotkeys
1
Sie brauchen das nicht wirklich, invertwenn Sie stattdessen die Werte nehmen. 24 Bytes
Jo King
2

Netzhaut , 63 Bytes

In den letzten beiden Zeilen werden Duplikate entfernt. Die Eingabe besteht aus zwei durch Leerzeichen getrennten Listen, die durch ein Komma getrennt sind. Die Ausgabe ist durch Leerzeichen getrennt.

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

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

Probieren Sie es online aus

Wenn Duplikate in der Ausgabe zulässig sind, würde mein Programm 42 Bytes umfassen.

mbomb007
quelle
2

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

Erweitert

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
;

Dies vermeidet die Verwendung {} Objekten und da jq keine Bitoperationen hat, werden diese mit einem Array emuliert.

Probieren Sie es online aus!

jq170727
quelle
2

Axiom, 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 und 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
RosLuP
quelle
2

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

Dies ohne die Verwendung von Binsearch ... Aber ich kenne das große O nicht ... Unglofed und Ergebnisse:

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

Nicht viele Tests ausgeführt, könnte also abgehört werden ...

RosLuP
quelle
2

Gelee , 12 Bytes

pEÐfḢ€ĠḢ€$ị$

Probieren Sie es online aus!

HyperNeutrino
quelle
In Tio 3,1,2,4,3,1,1,1,1,3 geben Eingabe und 3 Eingabe die Ausgabe [1,2,3] anstelle von [3] zurück
RosLuP
@ RosLuP Versuchen Sie [3]statt3
HyperNeutrino
Meiner Meinung nach wäre es in Ordnung, wenn das Ergebnis der Überschneidung von 2 Listen (wie in anderen Fällen) [] zurückkehrt, wenn das Ergebnis ungültig ist, [1] wenn 2 Listen 1 gemeinsam haben
RosLuP
@RosLuP Ich kann nicht anders, so gibt Jelly aus. Leer für[] und das Element für Singleton-Listen. Sie können auf die Wiki-Seite (Atome) gehen und das integrierte Python Stringify anhängen, aber das macht meine Antwort länger und strenge E / A ist dumm
HyperNeutrino
Es wäre für mich in Ordnung, wenn es nur Eingabelisten auf [] Weise (Beispiel [1], [1,2,3] [], [], [] usw.) akzeptieren und die Listenausgabe nur auf Listen [] Weise ausgeben würde (als seine Eingabe). Wenn die Klammern für die Liste {} oder () sind, wiederholen Sie die obige Sprache für die richtige. Dies ist nur für das, was ich denke, die Frage möglicherweise anders sagen und alles ist in
Ordnung
2

Schale , 9 Bytes

mo←←kIfE*

Probieren Sie es online aus!

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.

Im Quellcode von Husk auf GitHub wird k("keyon") als Zusammensetzung zum Sortieren der Liste und Gruppieren benachbarter Werte implementiert. Obwohl ich die Implementierung von "groupOn" nicht finden kann, ist es wahrscheinlich sicher anzunehmen, dass dies nicht der Fall ist. Da Haskell eine funktionale Sprache ist und das Gruppieren benachbarter gleicher Werte eine ziemlich einfache Operation zum Reduzieren einer verknüpften Liste ist, ist nichts zu tun. (Ich kann die Implementierung der kanderen Typensignatur "keyby" finden, die ich hier durch Ändern verwenden könnteI zu =, aber ich weiß nicht, Haskell , so kann ich nicht sagen , wie das genau funktioniert.)

Außerdem eine nette kleine Brachylog-Antwort, die ich mir ausgedacht hatte, bevor mir klar wurde, dass Set-Operationen aller Art nicht erlaubt waren: ⟨∋∈⟩ᵘ

Nicht verwandte Zeichenfolge
quelle
2

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

Verbessert von Giuseppe

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

Versuchen Sie es online Hier Hier

db
quelle
Das scheint nicht zu funktionieren. Ich versuche wahrscheinlich, es falsch zu verwenden, also sollten Sie vielleicht einen Link zu Try It Online angeben! Zeigen, wie man es benutzt und demonstrieren, dass es die Anforderungen der Herausforderung erfüllt. (Eine Erklärung der Antwort würde auch nicht schaden.)
Unrelated String
Sie können keine Eingaben annehmen aund bsind vordefiniert. Sie müssen Eingaben akzeptieren, indem Sie sie entweder als Funktionsargumente oder von STDIN verwenden.
Giuseppe
1
Ich denke, Golfspieler wäre es, dies einfach zu einer Funktion wie dieser zu machen
Giuseppe
1
@db Der "Header" benennt die im Abschnitt "Code" definierte anonyme Funktion (anonyme Funktionen sind vollkommen akzeptabel), und die Fußzeile ruft sie dann auf. Die Abschnitte Header, Code und Footer sind alle ein Teil des Codes, aber nur der Teil im Abschnitt "Code" zählt für Bytes :-)
Giuseppe
1

Python3, 51 Bytes

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

Wenn die Eingabelisten Duplikate enthalten können:

Python3, 67 Bytes

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

PHP ,7877 Bytes

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

Probieren Sie es online aus!

Kein Schnickschnack, aber regelkonform (glaube ich).

Ausgabe

[], []
[]

[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]
[]
640 KB
quelle