Tenga en cuenta que esta es una pregunta que se centra principalmente en estructuras de datos

Introducción

¡Bacefook quiere que la gente sea más amable! Como tal, ¡están implementando un nuevo sistema para sugerir amigos! Su tarea es ayudar a Bacefook a implementar su nuevo sistema de sugerencias.

Presupuesto:

Su programa debe ser un REPL (loop-eval-print leer) que soporta 3 tipos de comandos: FRIEND, SUGGESTy KNOW.

FRIEND X Y- Especifica eso Xy Yson amigos en la red social.

• Si X es amigo de Y, entonces Y es amigo de X

• Puede, pero no tiene que tener salida

• X siempre es amigo de X

KNOW X Y - Emite un valor verdadero si X e Y son amigos, de lo contrario, falso

• KNOW X X siempre dará como resultado un valor verdadero

SUGGEST X Y- Emite un valor verdadero si X e Y deben ser amigos, de lo contrario, falso X e Y deberían ser amigos si:

• X e Y no son amigos

• X e Y tienen al menos 1 amigo en común

Se le permite sustituir FRIEND, SUGGESTy KNOWcon sus propias cadenas, pero hay que mencionar lo que la cadena ha reemplazado con cada comando.

Su programa puede recibir entrada / salida de la forma que desee, siempre y cuando sea razonablemente fácil reconocer cómo funciona.

El número de personas en la red social Nestá entre 1 y 100,000, pero puede haber cualquier número de "enlaces de amigos" (bordes).

Si aún no lo ha notado, este es un problema de búsqueda de gráficos. La estructura de datos (probablemente) más fácil (y posiblemente más rápida) para implementar esto sería una matriz de adyacencia.

Casos de prueba

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

Aquí hay algunos casos de prueba más en forma de imagen

Condición de victoria

Este es el código de golf , ¡el código más corto gana!

SWI-Prolog, 62 47 41 bytes

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

Prolog no suele ser útil, pero cuando lo es es simplemente hermoso. Solíamos a+banotar que aes amigo b, a*bque asabe by a?bque bdebería sugerirse ao no. La primera línea simplemente dice que X*Yes verdad si bien X+Y, Y+Xo X == Yes cierto. Esto implementa la simetría de conocerse entre sí. Preguntar si debería haber una sugerencia es increíblemente simple. Sólo pedimos que si hay una Ztal que X*Yes falso y X*Z, y Y*Zes cierto. Exactamente como se describe en el desafío.

Si guarda esto como un archivo (p friends.pl. Ej. ) Y abre SWI-Prolog con este archivo ( prolog -l friends.pl), se lo colocará en un REPL.

Puedes afirmar amistades como esta:

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

Puede verificar si las personas se conocen entre sí o se deben hacer sugerencias:

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

PHP, 138133129 bytes

PHP supera a Mathematica, una ocurrencia rara.

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

impresiones 1para la verdad, cadena vacía para la falsedad. Ejecutar -nro probarlo en línea .
necesita PHP 7.1 para la asignación de la lista; nombres de usuario entre mayúsculas y minúsculas y deben excluir a, b, s.

Descompostura

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 tiene que recortarse porque incluye el carácter de nueva línea.
• array_intersect_keytiene que estar silenciado o generará advertencias para vacío $$ao $$b.
• +18 +15 bytes para todos los nombres de usuario: Reemplace $$acon $f[$a]y $$bcon $f[$b].

CMD (Lote), 50 + 20 + 135 = 205 bytes

• AMIGO.CMD

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

• SABER.CMD

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

  Impresiones 1para amigos, una línea en blanco para extraños.

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

  Impresiones 1o una línea en blanco. Creo que seis %s consecutivos podrían ser una nueva mejor marca personal.

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)

El uso es exactamente el mismo que el de la respuesta de ovs.

Python 3, 163 149 143 + 2 = 145 bytes

-6 bytes gracias a @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}

Guárdelo en un archivo y ejecútelo como python3 -i file.py
Usar
- en f("a", "b")lugar de FRIENDS a b
- en k("a", "b")lugar de KNOW a b
- en s("a", "b")lugar deSUGGEST a b

Salida de Falsey: 0, set (),
salida de False Truthy: conjunto no vacío, True

Pruébalo en línea

164 bytes cuando no se usa el intérprete de python como 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"])

Utiliza
- fpara FRIEND
- spara SUGGEST
- cualquier otra cosa paraKNOW

Pruébalo en línea

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

Define tres funciones principales F, Sy Kcon el comportamiento deseado. Por ejemplo, la secuencia de comandos

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]

es el último caso de prueba de la imagen vinculada en el OP; los Fcomandos no producen resultados (el punto y coma simple parece un pequeño precio a pagar por esto), mientras que los seis Sy los Kcomandos producen

True
True
False
False
True
True

como se desee.

En cualquier momento, fes la lista de pares ordenados de la forma {A, B}donde se Aconoce B, mientras que pes la lista de personas que aparecen en algún elemento de f. Llamando F@{A, B}suma los cuatro pares ordenados {A, B}, {B, A}, {A, A}, y {B, B}a f.

Además, en cualquier momento, mes la matriz de adyacencia del gráfico subyacente (una persona es adyacente a sí misma y a todos sus Famigos); las filas y columnas están indexadas por p, y iconvierte a una persona al número de fila / columna correspondiente. La función auxiliar atoma una matriz y dos personas como entradas y busca la entrada de la matriz cuyas "coordenadas" son las dos personas, devolviendo Truesi el número es positivo y Falsesi es cero. (También es posible llamar acuando una de las personas de entrada aún no es reconocida, por ejemplo, hacer una consulta SABER o SUGERIR antes de cualquier declaración de AMIGO, o preguntar sobre alguna persona pobre que no tiene amigos; esto arroja errores, pero la regla /._@__->0obliga a que la salida sea de Falsetodos modos)

Llamar, K[A, B]por lo tanto, busca si m[A, B]es positivo, lo que implementa el Kverbo now. El producto de matriz m.mes la matriz de longitud-2-ruta, que contiene el número de formas de ir de una persona a otra a lo largo de una ruta de longitud 2; esto permite S[A, B]implementar el Sverbo más feo, siempre que verifiquemos manualmente ( &&!K@##) que las personas de entrada no se conocen entre sí.

Dato divertido: de forma gratuita, esta aplicación nos permite declaramos camarillas de amigos-el comando F@{A, B, C, D}es equivalente a todos F@{A, B}, F@{A, C}, F@{A, D}, F@{B, C}, F@{B, D}, y F@{C, D}combinado.

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

Pruébalo en línea!

Como no pude encontrar la herramienta en línea repl para python 2, agregué el TIO Nexus (en formato REPL).

Consulta por opción y su posible salida

0 para Conocido - Ninguno

1 para amigos: verdadero o falso

2 para Sugerir: verdadero o falso

Ejemplo de uso y salida de muestra en un intérprete 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 (rn flags) = 160 bytes

Dado que sed es un lenguaje basado en expresiones regulares, no hay tipos primitivos, sin mencionar las estructuras de datos abstractos. Los datos de la red se almacenan como texto de formato libre, en este caso como enlaces amigos redundantes como A-B;B-A;etc., que luego se compara con varios patrones de expresiones regulares.

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

Pruébalo en línea!

Por diseño, sed ejecuta todo el script para cada línea de entrada. Recomiendo probar en modo interactivo, para ver la salida de un comando inmediatamente después de escribir.

Uso: no hay valores de verdad / falsedad en sed, por lo que la convención de salida que uso se toma prestada de bash, por lo que una cadena no vacía se considera verdadera y una cadena vacía como falsa.

• F X Ypara FRIEND X Y. No tiene salida.
• K X Ypara KNOW X Y. Produce 'K' como verdadero, y nada como falso.
• S X Ypara SUGGEST X Y. Produce 'S' como verdadero, y nada como falso.

Explicación:

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