Zauważ, że to pytanie dotyczy przede wszystkim struktur danych

Wprowadzenie

Bacefook chce, aby ludzie byli bardziej przyjaźni! W związku z tym wdrażają nowy system sugerowania znajomych! Twoim zadaniem jest pomóc Bacefook we wdrożeniu nowego systemu sugerowania.

Dane techniczne:

Twój program musi być REPL (pętla odczytu eval-print) wspieranie 3 rodzaje polecenie: FRIEND, SUGGESTi KNOW.

FRIEND X Y- Określa, że Xi Ysą przyjaciółmi w sieci społecznej.

• Jeśli X jest przyjacielem Y, to Y jest przyjacielem X

• Może, ale nie musi mieć danych wyjściowych

• X zawsze przyjaźni się z X

KNOW X Y - Wypisuje prawdę, jeśli X i Y są przyjaciółmi, w przeciwnym razie fałsz

• KNOW X X zawsze wyświetli prawdziwą wartość

SUGGEST X Y- Wypisuje prawdę, jeśli X i Y powinny być przyjaciółmi, w przeciwnym razie fałsz. X i Y powinny być przyjaciółmi, jeśli:

• X i Y nie są przyjaciółmi

• X i Y mają co najmniej 1 wspólnego znajomego

Masz prawo do wymiany FRIEND, SUGGESToraz KNOWz własnych strun, ale trzeba wspomnieć, co ciąg wymianie każdą komendę.

Twój program może przyjmować dane wejściowe / wyjściowe w dowolny pożądany sposób, o ile można dość łatwo rozpoznać, jak to działa.

Liczba osób w sieci społecznościowej Nwynosi od 1 do 100 000, ale może istnieć dowolna liczba „linków do znajomych” (krawędzi).

Jeśli jeszcze tego nie zauważyłeś, jest to problem z wyszukiwaniem wykresów. (Prawdopodobnie) najłatwiejszą (i prawdopodobnie najszybszą) strukturą danych, w której można to zaimplementować, byłaby macierz przylegania.

Przypadki testowe

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

Oto kilka innych przypadków testowych w formie obrazu

Warunek wygranej

To jest golf golfowy , wygrywa najkrótszy kod!

SWI-Prolog, 62 47 41 bajtów

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

Prolog nie jest zbyt często przydatny, ale kiedy jest, jest po prostu piękny. Będziemy używać a+bdo notowania, że asą to znajomi b, a*bktórzy awiedzą bi a?bże bnależy to zasugerować alub nie. Pierwszy wiersz po prostu mówi, że X*Yjest prawdziwa, czy też X+Y, Y+Xczy X == Yto prawda. To implementuje symetrię wzajemnego poznania się. Pytanie o sugestię jest niezwykle proste. My po prostu zapytać, czy nie jest Ztak, że X*Yjest fałszywa, a X*Zi Y*Zto prawda. Dokładnie tak, jak opisano w wyzwaniu.

Jeśli zapiszesz to jako plik (np. friends.pl) I otworzysz SWI-Prolog za pomocą tego pliku ( prolog -l friends.pl), zostaniesz przeniesiony do REPL.

Możesz zawrzeć takie przyjaźnie:

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

Możesz sprawdzić, czy ludzie się znają, lub sugestię:

'a'*'b'.
'a'?'d'.

PHP, 138 133 129 bajtów

PHP pokonuje Mathematica - rzadkie zjawisko.

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

drukuje 1dla prawdy, pusty ciąg dla fałszu. Uruchom go -nrlub przetestuj online .
wymaga PHP 7.1 do przypisania listy; nazwy użytkowników są wielkość liter i należy wykluczyć a, b, s.

awaria

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 musi zostać przycięty, ponieważ zawiera znak nowej linii.
• array_intersect_keymusi zostać wyciszony, aby wygenerował ostrzeżenie o pustym $$alub $$b.
• +18 +15 bajtów dla wszystkich nazw użytkowników: Wymień $$asię $f[$a]i $$bz $f[$b].

CMD (partia), 50 + 20 + 135 = 205 bajtów

• FRIEND.CMD

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

• KNOW.CMD

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

  Nadruki 1dla przyjaciół, pusta linia dla nieznajomych.

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

  Wydruki 1lub pusta linia. Myślę, że sześć kolejnych %może być nowym osobistym rekordem.

Python 3, 122 118 + 2 = 120 bajtów

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)

Użycie jest dokładnie takie samo jak odpowiedź ovs.

Python 3, 163 149 143 + 2 = 145 bajtów

-6 bajtów dzięki @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}

Zapisz go do pliku i uruchom jako python3 -i file.py
Użyj
- f("a", "b")zamiast FRIENDS a b
- k("a", "b")zamiast KNOW a b
- s("a", "b")zamiastSUGGEST a b

Wyjście Falsey: 0, set (),
Wyjście False Truthy: niepuste, True

Wypróbuj online

164 bajty, gdy nie używasz interpretera Pythona jako REPL:

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

Wykorzystuje
- fza FRIEND
- sza SUGGEST
- cokolwiek innego doKNOW

Wypróbuj online

Mathematica, 164 bajty

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@##&

Określa trzy główne funkcje F, Si Kz pożądanym zachowaniu. Na przykład sekwencja poleceń

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]

jest ostatnim przypadkiem testowym z obrazu połączonego w PO; te Fkomendy wydajność bez wyjścia (pojedynczy średnik zdaje małą cenę za to zapłacić), natomiast sześć Si Kpoleceń wydajnością

True
True
False
False
True
True

zgodnie z życzeniem.

W dowolnym momencie fjest lista uporządkowanych par postaci, o {A, B}której Awie B, a plista osób pojawiających się w jakimś elemencie f. Wywołanie F@{A, B}dodaje cztery pary uporządkowane {A, B}, {B, A}, {A, A}, i {B, B}do f.

Ponadto, w dowolnym momencie, mjest macierz przylegania podstawowego wykresu (osoba przylega do siebie i wszystkich swoich Fprzyjaciół); wiersze i kolumny są indeksowane przez pi ikonwertuje osobę na odpowiedni numer wiersza / kolumny. Funkcja pomocnika aprzyjmuje macierz i dwie osoby jako dane wejściowe i wyszukuje pozycję macierzy, której „współrzędne” to dwie osoby, zwracane, Truejeśli liczba jest dodatnia, a Falsejeśli zero. (Można również zadzwonić, agdy jedna z osób wejściowych nie jest jeszcze rozpoznana - na przykład, zadając WIEDZIE lub SUGEROWANE zapytanie przed deklaracjami PRZYJACIELA lub pytając o jakąś biedną osobę, która nie ma przyjaciół; to rzuca błędy, ale reguła /._@__->0i tak wymusza wyjście False.)

Wywołanie K[A, B]sprawdza zatem, czy m[A, B]jest dodatnie, co implementuje Kteraz czasownik. Iloczyn macierzy jest macierzą m.mo długości 2 ścieżek, zawierającą liczbę sposobów przejścia od jednej osoby do drugiej wzdłuż ścieżki o długości 2; pozwala to S[A, B]na implementację Snajgorszego czasownika, o ile dodatkowo sprawdzamy ręcznie ( &&!K@##), czy ludzie, których dane wejściowe jeszcze się nie znają.

Ciekawostka: za darmo, to realizacja pozwala nam zadeklarować klik przyjaciół-komenda F@{A, B, C, D}jest odpowiednikiem wszystkich F@{A, B}, F@{A, C}, F@{A, D}, F@{B, C}, F@{B, D}, i F@{C, D}łączone.

Python 2 , 118 bajtów

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

Wypróbuj online!

Ponieważ nie mogłem znaleźć narzędzia online do replikacji dla Pythona 2, dodałem TIO Nexus (w formacie REPL).

Zapytanie o opcję i jej możliwe wyjście

0 dla Znanych - Brak

1 dla przyjaciół - prawda lub fałsz

2 dla Sugeruj - prawda lub fałsz

Przykład użycia i przykładowe dane wyjściowe w interpreterie python repl.

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

GNU sed , 158 + 2 (flagi rn) = 160 bajtów

Ponieważ sed jest językiem opartym na wyrażeniach regularnych, nie ma prymitywnych typów, nie wspominając już o abstrakcyjnych strukturach danych. Dane sieciowe są przechowywane jako tekst w dowolnym formacie, w tym przypadku jako nadmiarowe linki znajomych, A-B;B-A;itp., Które są następnie dopasowywane do różnych wzorców wyrażeń regularnych.

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

Wypróbuj online!

Z założenia sed uruchamia cały skrypt dla każdego wiersza wprowadzania. Polecam testowanie w trybie interaktywnym, aby zobaczyć wynik polecenia natychmiast po wpisaniu.

Zastosowanie: w sed nie ma żadnych wartości prawda / fałsz, więc konwencja wyjściowa, której używam, jest zapożyczona z bash, przy czym niepusty ciąg jest uważany za prawdziwy, a pusty ciąg jako fałsz.

• F X Ydla FRIEND X Y. Nie ma wyjścia.
• K X Ydla KNOW X Y. Wykazuje „K” jako prawdę, a nic tak jak fałsz.
• S X Ydla SUGGEST X Y. Wykazuje „S” jako prawdę, a nic tak jak fałsz.

Wyjaśnienie:

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