Observe que esta é uma pergunta focada principalmente em estruturas de dados
Introdução
Bacefook quer que as pessoas sejam mais amigáveis! Como tal, eles estão implementando um novo sistema para sugerir amigos! Sua tarefa é ajudar o Bacefook a implementar seu novo sistema de sugestões.
Especificações:
O programa deve ser um REPL (circular lê-eval-print) que suporta 3 tipos de comando: FRIEND
, SUGGEST
eKNOW
.
FRIEND X Y
- Especifica isso X
e Y
são amigos na rede social.
Se X é amigo de Y, Y é amigo de X
Pode, mas não precisa ter saída
X é sempre amigo de X
KNOW X Y
- Emita um valor verdadeiro se X e Y forem amigos, caso contrário, falsifique
KNOW X X
sempre produzirá um valor verdadeiro
SUGGEST X Y
- Crie um valor verdadeiro se X e Y forem amigos, caso contrário, falsifique. X e Y devem ser amigos se:
X e Y não são amigos
X e Y têm pelo menos 1 amigo em comum
Você está autorizado a substituir FRIEND
, SUGGEST
e KNOW
com suas próprias cordas, mas você deve mencionar o que corda tenha sido substituída cada comando com.
Seu programa pode receber / produzir saída da forma que desejar, desde que seja razoavelmente fácil reconhecer como ele funciona.
O número de pessoas na rede social N
está entre 1 e 100.000, mas pode haver qualquer número de "links de amigos" (arestas).
Se você ainda não percebeu, este é um problema de pesquisa de gráficos. A estrutura de dados (provavelmente) mais fácil (e possivelmente mais rápida) para implementar isso seria uma matriz de adjacência.
Casos de teste
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
Aqui estão mais alguns casos de teste em forma de imagem
Condição de vitória
Este é o código-golfe , o código mais curto vence!
{A, B, C, D}
?SUGGEST UK EU
.Respostas:
SWI-Prolog,
624741 bytesMuitas vezes, o prólogo não é útil, mas quando é, é simplesmente bonito. Usaremos
a+b
para notar quea
é amigob
,a*b
quea
sabeb
ea?b
queb
deve ser sugeridoa
ou não. A primeira linha simplesmente diz queX*Y
é verdade se querX+Y
,Y+X
ouX == Y
é verdade. Isso implementa a simetria de se conhecer. Perguntar se deve haver uma sugestão é incrivelmente simples. Nós apenas perguntar se existe umZ
tal queX*Y
é falso eX*Z
eY*Z
is true. Exactly as described in the challenge.Se você salvar isso como um arquivo (por exemplo
friends.pl
) e abrir o SWI-Prolog com este arquivo (prolog -l friends.pl
) you get dropped into a REPL.Você pode afirmar amizades como esta:
Você pode verificar se as pessoas se conhecem ou se devem fazer sugestões:
fonte
k(X,Y)
withX*Y
and the same withf
ands
using different operands. 21 bytes if I've counted correctly.f
.PHP,
138 133129 bytesPHP beats Mathematica - a rare occurence.
prints
1
for truthy, empty string for falsy. Run with-nr
or test it online.needs PHP 7.1 for the list assignment; user names are case sensitive and should exclude
a
,b
,s
.breakdown
$s
has to be trimmed because it includes the newline character.array_intersect_key
has to be muted or it would yield warnings for empty$$a
or$$b
.+18+15 bytes for all user names: Replace$$a
with$f[$a]
and$$b
with$f[$b]
.fonte
CMD (Batch), 50 + 20 + 135 = 205 bytes
FRIEND.CMD
KNOW.CMD
Prints
1
for friends, a blank line for strangers.SUGGEST.CMD
Prints
1
or a blank line. I think six consecutive%
s might be a new personal best.fonte
Python 3,
122118+2=120 bytesUsage is exactly the same as ovs's answer.
fonte
Python 3,
163149143+2=145 bytes-6 bytes thanks to @FelipeNardiBatista
Save it to a file and run it as
python3 -i file.py
Use
-
f("a", "b")
instead ofFRIENDS a b
-
k("a", "b")
instead ofKNOW a b
-
s("a", "b")
instead ofSUGGEST a b
Falsey output : 0, set(), False
Truthy output : non-empty set, True
Try it online
164 bytes when not using python interpreter as REPL:
Uses
-
f
forFRIEND
-
s
forSUGGEST
- anything else for
KNOW
Try it online
fonte
l.extend([(a,b),(b,a)])
, can't you just dol+=[(a,b),(b,a)]
? (I haven't tested this yet)UnboundLocalError
. Nice answer by the way!bool()
from thes
function, and use0
,{}
andFalse
as Falsey andTrue
and a not emptyset
as Truthy, you could save 6 bytesMathematica, 164 bytes
Defines three main functions
F
,S
, andK
with the desired behavior. For example, the sequence of commandsis the last test case from the image linked in the OP; the
F
commands yield no output (the single semicolon seems a small price to pay for this), while the sixS
andK
commands yieldas desired.
At any moment,
f
is the list of ordered pairs of the form{A, B}
whereA
knowsB
, whilep
is the list of people appearing in some element off
. CallingF@{A, B}
adds the four ordered pairs{A, B}
,{B, A}
,{A, A}
, and{B, B}
tof
.Also, at any moment,
m
is the adjacency matrix of the underlying graph (a person is adjacent to themselves and to all theirF
riends); the rows and columns are indexed byp
, andi
converts a person to the corresponding row/column number. The helper functiona
takes a matrix and two people as inputs and looks up the entry of the matrix whose "coordinates" are the two people, returningTrue
if the number is positive andFalse
if it's zero. (It's also possible to calla
when one of the input people isn't yet recognized—for example, making a KNOW or SUGGEST query before any FRIEND declarations, or asking about some poor person who has no friends; this throws errors, but the rule/._@__->0
forces the output to beFalse
anyway.)Calling
K[A, B]
therefore looks up whetherm[A, B]
is positive, which implements theK
now verb. The matrix productm.m
is the length-2-path matrix, containing the number of ways to go from one person to another along a path of length 2; this allowsS[A, B]
to implement theS
uggest verb, as long as we additionally check by hand (&&!K@##
) that the input people don't already know each other.Fun fact: for free, this implementation allows us to declare cliques of friends—the command
F@{A, B, C, D}
is equivalent to all ofF@{A, B}
,F@{A, C}
,F@{A, D}
,F@{B, C}
,F@{B, D}
, andF@{C, D}
combined.fonte
Python 2, 118 bytes
Try it online!
Since I couldnt find repl online tool for python 2, I've added the TIO Nexus(in REPL format).
Query for option and its possible output
0 for Known - None
1 for Friends - True or False
2 for Suggest - True or False
Example of usage and sample output in an repl python interpreter.
fonte
GNU sed, 158 + 2(rn flags) = 160 bytes
Since sed is a regex based language, there are no primitive types, not to mention abstract data structures. The network data is stored as free format text, in this case as redundant friend links like
A-B;B-A;
etc., which is then matched against various regex patterns.Try it online!
By design, sed runs the whole script for each input line. I recommend testing in interactive mode, to see the output of a command immediately after typing.
Usage: there are no truthy / falsy values in sed, so the output convention I use is borrowed from bash, whereby a non-empty string is considered as truthy, and an empty string as falsy.
F X Y
forFRIEND X Y
. It has no output.K X Y
forKNOW X Y
. Outputs 'K' as truthy, and nothing as falsy.S X Y
forSUGGEST X Y
. Outputs 'S' as truthy, and nothing as falsy.Explanation:
fonte