Обратите внимание, что этот вопрос в первую очередь касается структур данных.

Введение

Bacefook хочет, чтобы люди были дружелюбнее! Таким образом, они внедряют новую систему, чтобы предложить друзьям! Ваша задача - помочь Bacefook внедрить их новую систему предложений.

Характеристики:

Ваша программа должна быть REPL (цикл чтения Eval-печати) поддерживает 3 типа команд: FRIEND, SUGGESTи KNOW.

FRIEND X Y- Указывает, что Xи Yесть друзья в социальной сети.

• Если X дружит с Y, то Y дружит с X

• Может, но не должен иметь выход

• Х всегда дружит с Х

KNOW X Y - Выведите истинное значение, если X и Y - друзья, иначе - ложь

• KNOW X X всегда будет выводить истинное значение

SUGGEST X Y- Выведите истинное значение, если X и Y должны быть друзьями, иначе ложно. X и Y должны быть друзьями, если:

• X и Y не друзья

• У X и Y есть как минимум 1 общий друг

Вы имеете право на замену FRIEND, SUGGESTи KNOWс вашими собственными строками, но вы должны отметить , что строка , которую вы заменили каждую команду с.

Ваша программа может принимать ввод-вывод любым желаемым способом, при условии, что это довольно легко понять, как она работает.

Число людей в социальной сети Nсоставляет от 1 до 100 000, но может быть любое количество «дружеских ссылок» (ребер).

Если вы еще не заметили, это проблема поиска графика. (Вероятно) самая простая (и, возможно, самая быстрая) структура данных для реализации этого - матрица смежности.

Контрольные примеры

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

Вот еще несколько тестов в форме изображения

Условие выигрыша

Это код-гольф , самый короткий код выигрывает!

SWI-Пролог, 62 47 41 байт

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

Пролог не слишком полезен, но когда это просто, это красиво. Мы будем использовать , a+bчтобы фиксировать , что aдружит с b, a*bчто aзнает , bи a?bчто bдолжно быть предложено aили нет. Первая строка просто говорит, что X*Yэто правда, если либо X+Y, Y+Xлибо X == Yэто правда. Это реализует симметрию знания друг друга. Спрашивать, должно ли быть предложение, невероятно просто. Мы просто спрашиваем, есть ли Zтакое, что X*Yявляется ложным X*Zи Y*Zявляется ли это правдой. Точно так же, как описано в задаче.

Если вы сохраните это как файл (например friends.pl) и откроете SWI-Prolog с этим файлом ( prolog -l friends.pl), вы попадете в REPL.

Вы можете утверждать дружбу, как это:

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

Вы можете проверить, знают ли люди друг друга, или следует сделать предложение:

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

PHP, 138 133 129 байт

PHP побеждает Mathematica - редкий случай.

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

печатает 1для правдивых, пустая строка для ложных. Запустите -nrили протестируйте его онлайн .
нужен PHP 7.1 для назначения списка; Имена пользователей чувствительны к регистру и должны исключать a, b, s.

сломать

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 должен быть обрезан, потому что он включает символ новой строки.
• array_intersect_keyдолжен быть отключен, иначе он выдаст предупреждения для пустых $$aили $$b.
• +18 +15 байт для всех имен пользователей: заменить $$aна $f[$a]и $$bна $f[$b].

CMD (пакетная обработка), 50 + 20 + 135 = 205 байт

• FRIEND.CMD

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

• KNOW.CMD

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

  Принты 1для друзей, пустая строка для незнакомцев.

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

  Отпечатки 1или пустая строка. Я думаю, что шесть последовательных %сек могут быть новым личным лучшим.

Python 3, 122 118 + 2 = 120 байт

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)

Использование в точности соответствует ответу ovs.

Python 3 163 149 143 + 2 = 145 байт

-6 байт благодаря @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}

Сохраните его в файл и запустите его как python3 -i file.py
Использовать
- f("a", "b")вместо FRIENDS a b
- k("a", "b")вместо KNOW a b
- s("a", "b")вместоSUGGEST a b

Вывод Falsey: 0, set (),
вывод False Truthy: непустой набор, True

Попробуйте онлайн

164 байта, когда не используется интерпретатор Python в качестве 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"])

Использует
- fдля FRIEND
- sдля SUGGEST
- что-нибудь еще дляKNOW

Попробуйте онлайн

Mathematica, 164 байта

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

Определяет три основные функции F, Sи Kс желаемым поведением. Например, последовательность команд

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]

последний контрольный пример из изображения, связанного с OP; то Fкоманды дают никакого вывода (единая точка с запятой , кажется небольшой плату за это), в то время как шесть Sи Kкоманды выхода

True
True
False
False
True
True

по желанию.

В любой момент, fэто список упорядоченных пар формы, {A, B}где Aзнает B, в то время pкак список людей, появляющихся в некотором элементе f. Вызов F@{A, B}добавляет четыре упорядоченные пары {A, B}, {B, A}, {A, A}и {B, B}к f.

Кроме того, в любой момент, mэто матрица смежности базового графа (человек соседствует с собой и со всеми своими Fобитателями); строки и столбцы индексируются pи iпреобразует человека в соответствующий номер строки / столбца. Вспомогательная функция aпринимает матрицу и двух человек в качестве входных данных и ищет запись матрицы, чьи «координаты» - это два человека, возвращая, Trueесли число положительное и Falseесли оно равно нулю. (Также возможно позвонить, aкогда один из людей ввода еще не распознан, например, сделать запрос KNOW или SUGGEST перед объявлениями FRIEND или спросить о каком-то бедном человеке, у которого нет друзей; это вызывает ошибки, но правило /._@__->0вынуждает вывод быть в Falseлюбом случае.)

Вызов K[A, B]поэтому ищет, m[A, B]является ли положительным, который реализует Kглагол now. Продукт матрицы m.m- это матрица длины-2-пути, содержащая количество путей перехода от одного человека к другому по пути длины 2; это позволяет S[A, B]реализовать Sглагол uggest, при условии, что мы дополнительно проверяем вручную ( &&!K@##), что входящие люди еще не знают друг друга.

Забавный факт: бесплатно, эта реализация позволяет объявить кликами друзей-команда F@{A, B, C, D}эквивалентна все F@{A, B}, F@{A, C}, F@{A, D}, F@{B, C}, F@{B, D}, и в F@{C, D}сочетании.

Python 2 , 118 байт

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

Попробуйте онлайн!

Поскольку я не смог найти онлайн-инструмент repl для python 2, я добавил TIO Nexus (в формате REPL).

Запрос на опцию и ее возможный вывод

0 для известного - нет

1 для друзей - правда или ложь

2 для Предложить - верно или неверно

Пример использования и пример вывода в интерпретаторе repl python.

>>> 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) = 160 байт

Поскольку sed - это язык на основе регулярных выражений, примитивных типов не существует, не говоря уже об абстрактных структурах данных. Сетевые данные хранятся в виде текста в произвольном формате, в данном случае в виде избыточных ссылок друзей, таких как A-B;B-A;и т. Д., Которые затем сопоставляются с различными шаблонами регулярных выражений.

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

Попробуйте онлайн!

По сути, sed запускает весь скрипт для каждой строки ввода. Я рекомендую тестировать в интерактивном режиме, чтобы увидеть вывод команды сразу после ввода.

Использование: в sed нет значений true / false, поэтому я использую выходное соглашение, заимствованное из bash, при этом непустая строка считается истинной, а пустая - ложной.

• F X Yдля FRIEND X Y. У него нет выхода.
• K X Yдля KNOW X Y. Выводит 'K' как правдивую, и ничего, кроме фальши.
• S X Yдля SUGGEST X Y. Вывод 'S' как правдивый, и ничего, как ложь.

Объяснение:

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