Should we be friends?

Question

Note this is a question primarily focusing on data-structures

Introduction

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.

Specifications:

Your program must be a REPL (read-eval-print loop) supporting 3 types of command: FRIEND, SUGGEST and KNOW.

FRIEND X Y - Specifies that X and 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 X will 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 FRIEND, SUGGEST and 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.

Test cases

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

Here's some more test cases in image form

Win condition

This is code-golf, shortest code wins!

Answer 1

SWI-Prolog, 62 47 41 bytes

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

Prolog isn't too often useful, but when it is it's just beautiful. We'll use a+b to notate that a is friends with b, a*b that a knows b and a?b that b should be suggested to a or not. The first line simply says that X*Y is true if either X+Y, Y+X or X == Y is true. This implements the symmetry of knowing eachother. Asking if there should be a suggestion is incredibly simple. We just ask if there is a Z such that X*Y is false and X*Z and Y*Z is true. Exactly as described in the challenge.

If you save this as a file (e.g. friends.pl) and open SWI-Prolog with this file (prolog -l friends.pl) you get dropped into a REPL.

You can assert friendships like this:

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

You can check if people know eachother or suggestion should be made:

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

Answer 2

PHP, 138 133 129 bytes

PHP beats Mathematica - a rare occurence.

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

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

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

Answer 3

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

  Prints 1 for friends, a blank line for strangers.

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

  Prints 1 or a blank line. I think six consecutive %s might be a new personal best.

Answer 4

Python 3, 163 149 143+2=145 bytes

-6 bytes thanks to @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}

Save it to a file and run it as python3 -i file.py
Use
- f("a", "b") instead of FRIENDS a b
- k("a", "b") instead of KNOW a b
- s("a", "b") instead of SUGGEST 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:

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

Uses
- f for FRIEND
- s for SUGGEST
- anything else for KNOW

Try it online

Answer 5

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)

Usage is exactly the same as ovs's answer.

Answer 6

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

Defines three main functions F, S, and K with the desired behavior. For example, the sequence of commands

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]

is 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 six S and K commands yield

True
True
False
False
True
True

as desired.

At any moment, f is the list of ordered pairs of the form {A, B} where A knows B, while p is the list of people appearing in some element of f. Calling F@{A, B} adds the four ordered pairs {A, B}, {B, A}, {A, A}, and {B, B} to f.

Also, at any moment, m is the adjacency matrix of the underlying graph (a person is adjacent to themselves and to all their Friends); the rows and columns are indexed by p, and i converts a person to the corresponding row/column number. The helper function a takes a matrix and two people as inputs and looks up the entry of the matrix whose "coordinates" are the two people, returning True if the number is positive and False if it's zero. (It's also possible to call a 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 be False anyway.)

Calling K[A, B] therefore looks up whether m[A, B] is positive, which implements the Know verb. The matrix product m.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 allows S[A, B] to implement the Suggest 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 of F@{A, B}, F@{A, C}, F@{A, D}, F@{B, C}, F@{B, D}, and F@{C, D} combined.

Answer 7

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

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.

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

Answer 8

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.

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

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 for FRIEND X Y. It has no output.
• K X Y for KNOW X Y. Outputs 'K' as truthy, and nothing as falsy.
• S X Y for SUGGEST X Y. Outputs 'S' as truthy, and nothing as falsy.

Explanation:

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