Note this is a question primarily focusing on data-structures
Bacefook wants people to be friendlier! As such, they are implementing a new system to suggest friends! Your task is to help Bacefook to implement their new suggesting system.
Your program must be a REPL (read-eval-print loop) supporting 3 types of command:
FRIEND X Y - Specifies that
Y are friends in the social network.
If X is friends with Y, then Y is friends with X
Can, but doesn't have to have output
X is always friends with X
KNOW X Y - Output a truthy value if X and Y are friends, falsy otherwise
KNOW X Xwill always output a truthy value
SUGGEST X Y - Output a truthy value if X and Y should be friends, falsy otherwise. X and Y should be friends if:
X and Y are not friends
X and Y have at least 1 friend in common
You are allowed to replace
KNOW with your own strings, but you must mention what string you have replaced each command with.
Your program can take in input/produce output in any way desirable, as long as it is reasonably easy to recognize how it works.
The number of people in the social network
N is between 1 and 100,000, but there may be any number of "friend links" (edges).
If you haven't noticed yet, this is a graph searching problem. The (likely) easiest (and possibly fastest) data structure to implement this in would be an adjacency matrix.
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
This is code-golf, shortest code wins!