Теория шести рукопожатий — социологическая теория, согласно которой любые два человека на Земле разделены не более, чем пятью уровнями общих знакомых (и, соответственно, шестью уровнями связей). Формальная математическая формулировка теории: диаметр графа знакомств не превышает 6. Мы не станем так сильно углубляться в дружественные связи и пока нам хватит только двух уровней. Напишите программу, которая по списку дружественных пар для каждого человека определяет список «друзей 2-го уровня».
Формат ввода
В каждой строке записывается два имени.
Окончанием ввода служит пустая строка.
Формат вывода:
Выведите список всех людей и их «друзей 2-го уровня» в формате «Человек: Друг1, Друг2, …».
Список людей и друзей в каждой строке требуется вывести в алфавитном порядке без повторений.
Пример
Ввод
Иванов Петров
Иванов Сергеев
Васильев Петров
Сергеев Яковлев
Петров Кириллов
Петров ЯковлевВывод
Васильев: Иванов, Кириллов, Яковлев
Иванов: Васильев, Кириллов, Яковлев
Кириллов: Васильев, Иванов, Яковлев
Петров: Сергеев
Сергеев: Петров
Яковлев: Васильев, Иванов, КирилловВвод
Николай Фёдор
Николай Женя
Фёдор Женя
Фёдор Илья
Илья ФёдорВывод
Женя: Илья
Илья: Женя, Николай
Николай: Илья
Фёдор:Решение
Довольно запутанная задача, которая вызывает затруднения у многих учащихся. Ее запутанность возникает от того, что в голове достаточно сложно формализовать понятие “друзья друзей”.
Чаще всего рассуждения идут по достаточно простой схеме:
Собираем в словарь прямых друзей, при этом не забываем, что строка “Иванов Сидоров” означает что у нас должно появиться две пары друзей – Иванов-Сидоров и Сидоров-Иванов.
После чего собираем словарь “друзей друзей”. Для этого надо для каждого друга собрать всех его прямых друзей.
Казалось бы на этом задача выполнена и тест должен пройти, но возникает проблема.
В списке, присутствует сам “виновник торжества”, а он себе другом быть не может. Поэтому надо позаботиться, о том, чтобы его исключить.
Но и это еще не все, тест все равно не проходит. А все потому, что есть неочевидное следствие прошлой проблемы – прямые друзья, оказавшиеся в списке друзей друзей, тоже должны быть исключены.
После исключения прямых друзей остается отсортировать и вывести список.
Посмотреть код
Решение
friends = {} # словарь прямых друзей
while pair := input():
friend1, friend2 = pair.split()
friends[friend1] = friends.get(friend1, set()) | set([friend2])
friends[friend2] = friends.get(friend2, set()) | set([friend1])
friends_of_friends = {} # словарь друзей друзей
for name in sorted(friends):
for person in friends[name]:
friends_of_friends[name] = friends_of_friends.get(
name, set()) | friends[person]
for name in friends_of_friends:
friends_of_friends[name].discard(name) # удаляем самого себя
friends_of_friends[name] -= friends[name] # удаляем прямых друзей
friends_of_friends[name] = sorted(friends_of_friends[name])
print(f'{name}: {", ".join(friends_of_friends[name])}')
Для чего первая строка кода? Множество subject нигде не используется и валидатор пропускает без него.
Осталось от предыдущих решений. Бывает, когда код переписываешь не с нуля. Убрал. Спасибо, что обратили внимание.
там был такой код
subjects = set() # множество имен pairs = [] # список пар друзей friends = dict() # словарь прямых друзей while pair := input().split(): pairs.append(pair) for pair in pairs: subjects |= set(pair) subjects = sorted(subjects)Возможно, это интересно посмотреть в разрезе эволюции решения.
Зачем два цикла for? Ведь удалить себя и прямых друзей и вывести полученный результат можно в рамках одного и того же цикла, тем более, что словарь отсортирован.
И еще замечание: нет необходимости в создании словаря “друзей друзей”. В цикле for достаточно для каждого человека получить множество (set) друзей друзей, удалить из множества лишних людей и вывести результат.
То есть, начиная с 8 строчки код будет таким:
ff_set = set()
for name in sorted(friends):
ff_set.clear()
for person in friends[name]:
ff_set = ff_set | friends[person]
ff_set.discard(name)
ff_set = ff_set – friends[name]
friends_of_friends = sorted(list(ff_set))
print(f'{name}: {“, “.join(friends_of_friends)}’)
Спасибо за дополнение. Лучше всего приводить решения целиком, чтобы другие люди могли скопировать и отладить.
По поводу вопросов зачем и замечания:
Вы правы и задачу можно решить короче. Но есть нюанс. По моим наблюдениям, это одна из самых сложных для решающих задач в теме. Очень многие в принципе не могут понять как ее решать. Моя же цель – рассказать доступным языком как это можно сделать. При этом я не ставлю перед собой целью обязательно показать самое лучшее решение. Приведенное решение выбрано потому, что оно разбивает алгоритм на этапы, каждый из которых проще понять.
Ваше решение прекрасно дополняет данный мною материал. Cпасибо, что поделились им.
Сначала написал одно решение, потом доработал для более хорошей читабельности, но не понимаю почему старый код работал неисправно. Кто знает?
Старый код:
friends1 = dict()
friends2 = dict()
while text := input():
text = text.split(‘ ‘)
if text[0] not in friends1:
friends1[text[0]] = set()
friends1[text[0]].add(text[1])
else:
friends1[text[0]].add(text[1])
if text[1] not in friends1:
friends1[text[1]] = set()
friends1[text[1]].add(text[0])
else:
friends1[text[1]].add(text[0])
friends1 = dict(sorted(friends1.items()))
for name in friends1:
for friend in friends1[name]:
if name not in friends2:
friends2[name] = set()
friends2[name] | friends1[friend]
else:
friends2[name] | friends1[friend]
friends2[name].remove(name)
for name in friends2:
print(f'{name}: {“, “.join(friends2[name])}’)
Выводит:
Васильев:
Иванов:
Кириллов:
Петров:
Сергеев:
Яковлев:
А вот так выглядит friends2:
{‘Петров’: set(), ‘Яковлев’: set(), ‘Кириллов’: set(), ‘Сергеев’: set(), ‘Васильев’: set(), ‘Иванов’: set()}
Почему то не хочет объединять два множества.
Новый код если у кого такая же ошибка:
friends1 = dict()
friends2 = dict()
while text := input():
text = text.split(‘ ‘)
if text[0] not in friends1:
friends1[text[0]] = set()
friends1[text[0]].add(text[1])
else:
friends1[text[0]].add(text[1])
if text[1] not in friends1:
friends1[text[1]] = set()
friends1[text[1]].add(text[0])
else:
friends1[text[1]].add(text[0])
friends1 = dict(sorted(friends1.items()))
for name in friends1:
for friend in friends1[name]:
friends2[name] = friends2.get(name, set()) | friends1[friend]
friends2[name].remove(name)
for name in friends2:
print(f'{name}: {“, “.join(friends2[name])}’)
friends2[name] | friends1[friend]
эта строка производит операцию с множествами, но никуда не сохраняет результат:
если ее исправить на
friends2[name] = friends2[name] | friends1[friend]
то объединение будет происходить.
для прохождения первого теста не хватает сортировки при выводе имен друзей по алфавиту. для прохождения второго теста надо искать другие огрехи в коде.
Не могу понять эту строчку friends[friend1] = friends.get(friend1, set()) | set([friend2]) и всё….
Словарю friends по ключу friend 1 создаётся значение(если ключа friend 1 нет в словаре friends) – Массив в котором находится friend 2 – тут логично и понятно но дальше увы, если в словаре friends сущесвтует ключ friend 1 с каким-то значением, то метод get просто вернёт его. Каким образом список значений в словаре дополняется понять не могу даже отдалённо. Получится что-то вроде “Значение по ключу Ф1 = значение по ключу Ф1”
friends[friend1] = friends.get(friend1, set()) | set([friend2])
Давайте разберем чуть подробнее.
Если сильно упрощать, в этой строке мы просим записать в словарь ОБЪЕДИНЕНИЕ результата операции friends.get() и friend2. Если словарь пуст, то запишется просто friend2, если словарь уже содержит информацию, то friend2 допишется к ней. Но так как это множество, допишется только в том, случае, если до сих пор friend2 там не было.
Уложил в голове, всё понятно. Очень признателен за объяснения