Sollen wir Freunde sein?

30

Beachten Sie, dass dies eine Frage ist, die sich hauptsächlich auf konzentriert

Einführung

Bacefook möchte, dass die Leute freundlicher sind! Als solche implementieren sie ein neues System, um Freunde vorzuschlagen! Ihre Aufgabe ist es, Bacefook bei der Implementierung des neuen Vorschlagsystems zu helfen.

Spezifikationen:

Ihr Programm muss ein REPL (read-eval-print Schleife) unterstützt 3 Arten von Befehl sein: FRIEND, SUGGESTund KNOW.

FRIEND X Y- Gibt an, dass Xund YFreunde im sozialen Netzwerk sind.

  • Wenn X mit Y befreundet ist, dann ist Y mit X befreundet

  • Kann, muss aber keine Ausgabe haben

  • X ist immer mit X befreundet

KNOW X Y - Geben Sie einen Wahrheitswert aus, wenn X und Y befreundet sind, andernfalls ist dies falsch

  • KNOW X X Gibt immer einen Wahrheitswert aus

SUGGEST X Y- Geben Sie einen Wahrheitswert aus, wenn X und Y befreundet sein sollen, andernfalls ist dies falsch. X und Y sollten Freunde sein, wenn:

  • X und Y sind keine Freunde

  • X und Y haben mindestens 1 Freund gemeinsam

Sie sind zu ersetzen , erlaubt FRIEND, SUGGESTund KNOWmit Ihren eigenen Saiten, aber man muss erwähnen , welche Zeichenfolge Sie jeden Befehl mit ersetzt haben.

Ihr Programm kann auf jede gewünschte Weise Eingaben / Ausgaben erzeugen, solange es einigermaßen einfach zu erkennen ist, wie es funktioniert.

Die Anzahl der Personen im sozialen Netzwerk Nliegt zwischen 1 und 100.000, es kann jedoch eine beliebige Anzahl von "Friend-Links" (Kanten) geben.

Wenn Sie es noch nicht bemerkt haben, handelt es sich um ein Problem bei der Suche nach Diagrammen. Die (wahrscheinlich) einfachste (und möglicherweise schnellste) Datenstruktur, um dies zu implementieren, wäre eine Adjazenzmatrix.

Testfälle

FRIEND A B
FRIEND A C
FRIEND B D
SUGGEST A B -> Falsy, as they are friends
SUGGEST A D -> Truthy, as they share B as a common friend
SUGGEST C D -> Falsy, they do not share a common friend
KNOW D B -> Truthy, they are friends
KNOW B C -> Falsy, not friends
=============
FRIEND Tom Tim
KNOW Tom Tim -> Truthy
KNOW Tim Tom -> Truthy
KNOW Tom Kit -> Falsy
=============
KNOW Tim Kit -> Falsy
FRIEND Tim Tom
KNOW Tim Kit -> Falsy
FRIEND Tom Kit
SUGGEST Tim Kit -> Truthy
=============
FRIEND X Y
SUGGEST X Y -> Falsy since X is friends with X

Hier noch ein paar Testfälle in Bildform

Gewinnbedingung

Das ist , der kürzeste Code gewinnt!

Thunda
quelle
Können wir zum Beispiel damit beginnen, eine Liste aller Personen im Netzwerk einzugeben, wie zum Beispiel {A, B, C, D}?
Greg Martin
2
Es wäre viel hilfreicher, die Testfälle in Textform zu haben.
Greg Martin
1
Können wir nach dem Befehl FRIEND eine Ausgabe haben?
Ovs
7
SUGGEST UK EU.
WBT
1
@Thunda in Python erfordert für die Verwendung der integrierten REPL zwei zusätzliche Zeichen im Befehl. Sollten Sprachen wie diese diese zusätzlichen Bytes zur Gesamtlänge des Programms hinzufügen?
Quintopia

Antworten:

44

SWI-Prolog, 62 47 41 Bytes

X*Y:-X+Y;Y+X;X==Y.
X?Y:-not(X*Y),X*Z,Y*Z.

Prolog ist nicht allzu oft nützlich, aber wenn es ist, ist es einfach wunderschön. Wir werden verwenden a+b, um zu notieren, dass amit befreundet ist b, a*bdas aweiß bund a?bdas vorgeschlagen werden bsollte aoder nicht. Die erste Zeile sagt einfach, dass X*Yentweder wahr X+Yist Y+Xoder X == Ywahr ist. Dies setzt die Symmetrie des gegenseitigen Erkennens um. Es ist unglaublich einfach zu fragen, ob es einen Vorschlag geben sollte. Wir bitten nur , wenn es eine ist , Zso dass X*Yfalsch ist und X*Zund Y*Zist wahr. Genau wie in der Challenge beschrieben.

Wenn Sie dies als Datei speichern (zB friends.pl) und SWI-Prolog mit dieser Datei öffnen ( prolog -l friends.pl), werden Sie in eine REPL abgelegt.

Sie können Freundschaften wie diese behaupten:

assert('a' + 'b').
assert('a' + 'c').
assert('b' + 'd').

Sie können überprüfen, ob die Leute sich kennen oder ob Vorschläge gemacht werden sollten:

'a'*'b'.
'a'?'d'.
orlp
quelle
Sie sollen eine Reihe von Bytes speichern können , ersetzen k(X,Y)mit X*Yund das gleiche mit fund sverschiedenen Operanden verwenden. 21 Bytes, wenn ich richtig gezählt habe.
Emigna
Ich bin mir nicht sicher, wie sie mit Behauptungen umgehen, also bin ich mir nicht sicher f.
Emigna
12
Furzt vollständig durch die Datenstruktur, die einen Teil der Frage darstellt. Tolle.
Thunda
@Emigna Ich habe es implementiert, aber es hat nicht so viel gespart, wie Sie gezählt haben.
Orlp
Getestet habe ich es wie dies bei 41 Bytes. Ich habe keine REPL, um es zu versuchen, also weiß ich nicht, ob es dort anders funktioniert.
Emigna
15

PHP, 138 133 129 Bytes

PHP schlägt Mathematica - ein seltenes Ereignis.

for(;$s=fgets(STDIN);$s>G?print$$a[$b]?$s<L:$s>L&&@array_intersect_key($$a,$$b):$$a[$b]=$$b[$a]=1)[,$a,$b]=explode(" ",trim($s));

druckt 1für wahrheitsgemäße, leere Zeichenfolge für falsch. Laufen Sie mit -nroder testen Sie es online .
benötigt PHP 7.1 für die Listenzuordnung; Benutzernamen Groß- und Kleinschreibung und sollte ausschließen a, b, s.

Nervenzusammenbruch

for(;$s=fgets(STDIN);                       # loop through input
    $s>G                                        # 2. evaluate command
        ?print$$a[$b]
            # command KNOW: true if $$a[$b]
            ?$s<L
            # command SUGGEST: true if !$$a[$b] and array_intersect_key returns truthy
            :$s>L&&@array_intersect_key($$a,$$b)
        # command FRIEND: set keys in $$a and $$b
        :$$a[$b]=$$b[$a]=1
)
    [,$a,$b]=explode(" ",trim($s));             # 1. parse user names to $a and $b
  • $s muss gekürzt werden, da es das Newline-Zeichen enthält.
  • array_intersect_keymuss stumm geschaltet werden oder es würde Warnungen für leer $$aoder ergeben $$b.
  • +18 +15 Bytes für alle Benutzernamen: Ersetzen Sie $$amit $f[$a]und $$bmit $f[$b].
Titus
quelle
12

CMD (Batch), 50 + 20 + 135 = 205 Bytes

  • FRIEND.CMD

    @for %%f in (%1.%1 %1.%2 %2.%2 %2.%1)do @set %%f=1
    
  • KNOW.CMD

    @call echo(%%%1.%2%%
    

    Drucke 1für Freunde, eine leere Zeile für Fremde.

  • SUGGEST.CMD

    @call set k=0%%%1.%2%%
    @set k=1&if %k%==0 for /f "tokens=2 delims=.=" %%f in ('set %1.')do @call set k=%%k%%%%%%f.%2%%
    @echo(%k:~1,1%
    

    Druckt 1oder eine leere Zeile. Ich denke, sechs aufeinanderfolgende %s könnten eine neue persönliche Bestzeit sein.

Neil
quelle
Das ist verrückt, großartig. Gute Lösung.
AdmBorkBork
6

Python 3, 122 118 + 2 = 120 Bytes

l={}
def f(*r):l[r]=l[r[::-1]]=1
k=lambda a,b:a==b or(a,b)in l
s=lambda a,b:1-k(a,b)and any(k(a,z)&k(b,z)for z,_ in l)

Die Verwendung entspricht genau der Antwort von ovs.

orlp
quelle
1
Es ist für mich ziemlich offensichtlich, aber die Anforderungen besagen, dass Sie angeben müssen, wie Sie REPL verwenden und mit welchen Befehlen. Kann für diejenigen nützlich sein, die Python nicht kennen. (Übrigens ist dies genau die Methode, die ich verwendet hätte.)
Quintopia
6

Python 3, 163 149 143 + 2 = 145 Bytes

-6 Bytes dank @FelipeNardiBatista

l=[]
def f(a,b):l.extend([(a,b),(b,a)])
k=lambda a,b:a==b or(a,b)in l
s=lambda a,b:k(a,b)-1and{c for c,d in l if d==a}&{c for c,d in l if d==b}

Speichern Sie es in einer Datei und führen Sie es als python3 -i file.py
Verwenden
- f("a", "b")anstelle FRIENDS a b
- k("a", "b")anstelle KNOW a b
- s("a", "b")anstelle von ausSUGGEST a b

Falsche Ausgabe: 0, set (), Falsche
Wahrheitsausgabe: nicht leere Menge, True

Probieren Sie es online aus


164 Bytes, wenn kein Python-Interpreter als REPL verwendet wird:

f=[]
while 1:c,a,b=input().split();i=(a,b)in f;f+=c=="f"and[(a,b),(b,a)]or[(i+(a==b),-i+1and{c for c,d in f if d==a}&{c for c,d in f if d==b})];print(f[-1][c=="s"])

Verwendet
- ffür FRIEND
- sfür SUGGEST
- alles andere fürKNOW

Probieren Sie es online aus

ovs
quelle
Die Vorschlagsfunktion für den zweiten Link ist
fehlerhaft
@Thunda repariert es
ovs
Korrigieren Sie mich, wenn mir etwas fehlt, aber l.extend([(a,b),(b,a)])können Sie es nicht einfach tun l+=[(a,b),(b,a)]? (Ich habe dies noch nicht getestet)
HyperNeutrino
Oh sorry, ich habe meinen Fehler bemerkt, der einen Fehler verursacht UnboundLocalError. Schöne Antwort übrigens!
HyperNeutrino
Wenn Sie bool()aus der sFunktion entfernen und verwenden 0, {}und Falseals Falsey und Trueund setals Truthy nicht leer , können Sie 6 Bytes sparen
Felipe Nardi Batista
5

Mathematica, 164 Bytes

f={}
p:=Union@@f
i=Position[p,#][[1,1]]&
m:=Outer[Boole@MemberQ[f,{##}]&,p,p]
a=(#[[i@#2,i@#3]]/._@__->0)>0&
F=(f=#~Tuples~2~Join~f;)&
K=m~a~##&
S=a[m.m,##]&&!K@##&

Definiert drei Hauptfunktionen F, Sund Kmit dem gewünschten Verhalten. Zum Beispiel die Befehlsfolge

F@{David, Bob}
F@{Bob, Alex}
F@{Alex, Kitty}
F@{Daniel, David}
F@{David, Kit}
S[David, Alex]
S[Bob, Kitty]
S[David, Kitty]
S[David, Bob]
K[David, Bob]
F@{Kit, Kitty}
S[David, Kitty]

ist der letzte Testfall aus dem im OP verknüpften Bild; Die FBefehle liefern keine Ausgabe (das einzelne Semikolon scheint dafür einen geringen Preis zu zahlen), während die Befehle 6 Sund 4 eine Ausgabe Kliefern

True
True
False
False
True
True

wie gewünscht.

Zu jeder Zeit fist die Liste von geordneten Paaren der Form , {A, B}wo Aweiß B, während pdie Liste von Personen in einem Elemente zu erscheinen f. Der Aufruf F@{A, B}fügt die vier geordneten Paare {A, B}, {B, A}, {A, A}, und {B, B}zu f.

Zu jedem Zeitpunkt mbefindet sich auch die Adjazenzmatrix des zugrunde liegenden Graphen (eine Person grenzt an sich selbst und an alle ihre FFreunde). Die Zeilen und Spalten werden durch indiziert pund ikonvertieren eine Person in die entsprechende Zeilen- / Spaltennummer. Die Hilfsfunktion animmt eine Matrix und zwei Personen als Eingaben und sucht nach dem Eintrag der Matrix, deren "Koordinaten" die beiden Personen sind, und gibt zurück, Truewenn die Zahl positiv ist und Falsewenn sie Null ist. (Sie können auch anrufen, awenn eine der eingegebenen Personen noch nicht erkannt wurde, z. B. vor einer FREUND-Deklaration eine KNOW- oder SUGGEST-Abfrage durchführen oder nach einer armen Person fragen, die keine Freunde hat. Dies führt zu Fehlern, aber der Regel /._@__->0erzwingt die Ausgabe Falsetrotzdem.)

Der Aufruf K[A, B]prüft daher, ob m[A, B]positiv ist, was das KJetzt-Verb umsetzt . Das Matrixprodukt m.mist die Länge-2-Pfad-Matrix, die die Anzahl der Wege enthält, die auf einem Pfad der Länge 2 von einer Person zur anderen gehen. Dies ermöglicht S[A, B]die Implementierung des Suggest-Verbs, sofern zusätzlich von Hand ( &&!K@##) geprüft wird, ob sich die eingegebenen Personen noch nicht kennen.

Spaßtatsache: kostenlos, diese Implementierung ermöglicht es uns , Cliquen zu erklären Freunde-der Befehl F@{A, B, C, D}entspricht allen F@{A, B}, F@{A, C}, F@{A, D}, F@{B, C}, F@{B, D}, und F@{C, D}kombiniert.

Greg Martin
quelle
2

Python 2 , 118 Bytes

F=[]
def s(f,c):c=set(c);r=c in F;return F.append(c)if f%2 else not r^(4 in[len(x|c)for x in F])if f else 2>len(c)or r

Probieren Sie es online!

Da ich kein Repl-Online-Tool für Python 2 finden konnte, habe ich das TIO Nexus (im REPL-Format) hinzugefügt.

Abfrage nach Option und möglicher Ausgabe

0 für Bekannt - Keine

1 für Freunde - Richtig oder falsch

2 für Suggest - True oder False

Anwendungsbeispiel und Beispielausgabe in einem Repl-Python-Interpreter.

>>> F=[]
>>> def s(f,c):c=set(c);r=c in F;return F.append(c)if f%2 else not r^(4 in[len(x|c)for x in F])if f else 2>len(c)or r
...
>>> s(1,['A','B'])
>>> s(1,['A','C'])
>>> s(1,['B','D'])
>>> s(2,['A','B'])
False
>>> s(2,['A','D'])
True
>>> s(2,['C','D'])
False
>>> s(0,['D','B'])
True
>>> s(0,['D','C'])
False
Keerthana Prabhakaran
quelle
0

GNU sed , 158 + 2 (rn Flags) = 160 Bytes

Da sed eine auf Regex basierende Sprache ist, gibt es keine primitiven Typen, ganz zu schweigen von abstrakten Datenstrukturen. Die Netzwerkdaten werden als Freiformat-Text gespeichert, in diesem Fall als redundante Friend-Links A-B;B-A;usw., die dann mit verschiedenen Regex-Mustern abgeglichen werden.

G
/^F/{s:. (.+) (.+)\n:\1-\1;\1-\2;\2-\1;\2-\2;:;h}
/^K |^S /{s:(.) (.+) (.+)\n.*\2-\3.*:\1:;/^K$/p}
/^S /s:(.) (.+) (.+)\n.*(.+)-(\2.*\4-\3|\3.*\4-\2).*:\1:p

Probieren Sie es online!

Sed führt standardmäßig das gesamte Skript für jede Eingabezeile aus. Ich empfehle, im interaktiven Modus zu testen, um die Ausgabe eines Befehls unmittelbar nach der Eingabe zu sehen.

Verwendung: In sed gibt es keine Wahrheits- / Falsch-Werte. Die von mir verwendete Ausgabekonvention stammt aus bash, wobei eine nicht leere Zeichenfolge als wahr und eine leere Zeichenfolge als falsch betrachtet wird.

  • F X Yfür FRIEND X Y. Es hat keine Ausgabe.
  • K X Yfür KNOW X Y. Gibt 'K' als wahr und nichts als falsch aus.
  • S X Yfür SUGGEST X Y. Gibt "S" als wahr und nichts als falsch aus.

Erläuterung:

G
# append stored network data, if any, to the current input line
/^F/{
# if command is 'F' (FRIEND), for ex. 'F X Y'
   s:. (.+) (.+)\n:\1-\1;\1-\2;\2-\1;\2-\2;:
   # generate friend links, for ex. 'X-X;X-Y;Y-X;Y-Y'
   h
   # store updated network data
}
/^K |^S /{
# if command is either 'K' (KNOW) or 'S' (SUGGEST), for ex. 'K X Y'
   s:(.) (.+) (.+)\n.*\2-\3.*:\1:
   # search friend link 'X-Y'. If found, delete pattern except the command letter.
   /^K$/p
   # if only letter K left, print it (command is 'K', 'X' and 'Y' are friends)
}
/^S /
# if command is 'S', for ex. 'S X Y', but 'X' and 'Y' aren't friends
   s:(.) (.+) (.+)\n.*(.+)-(\2.*\4-\3|\3.*\4-\2).*:\1:p
   # search if 'X' and 'Y' have a friend in common (for ex. 'C'), and if so print
   #letter S. The search is for ex. 'C-X.*C-Y' and 'C-Y.*C-X'.
Seshoumara
quelle