Помогите решить лабораторную работу в универе Python
Задача 2.3 (Числа Эрдеша)
PC/UValDs: 110206/10044
Венгерский ученый Пауль Эрдеш (Paul Erdus, 1913-1966) был одним из самых известных математиков XX века. Любой математик, имевший честь быть соавтором Эрдеша, глубоко уважаем.
К сожалению, не у всех была возможность написать статью совместно с Эрдешем, лучшее, что они могли сделать, - это опубликовать статью с кем-либо, кто опубликовал научную статью в соавторстве с Эрдешем. Это дало начало так называемым числам Эрдеша. Автор, публиковавшийся совместно с Эрдешем, имеет число Эрдеша 1. Автор, не публиковавшийся с Эрдешем, но публиковавшийся совместно с кем-либо, кто имеет число Эрдеша 1, получал число Эрдеша 2 и т. д.
Ваша задача - написать программу, которая рассчитывает числа Эрдеша для данного множества статей и ученых.
Входные данные
Первая строка входных данных содержит число сценариев. Каждый сценарий состоит из базы данных статей и из списка имен. Он начинается со строки вида Р N, где Р и N- натуральные числа. За этой строкой следует база данных статей из Р строк, каждая из которых содержит описание одной статьи, выглядящее так:
Smith, M.N. , Martin, G. , Erdos, P. : Newtonian forms of prime factors
После Р статей идут N строк с именами. Такая строка с именем имеет следующий формат:
Martin, G.
Выходные данные
Для каждого сценария вы должны вывести строку, содержащую "Scenario /'" (где I - это номер сценария), и имена авторов вместе с их числами Эрдеша для всех авторов из списка имен. Авторы должны выводиться в том же порядке, в котором они были в списке имен. Число Эрдеша основано на статьях из базы данных статей этого сценария. Авторы, которые не имеют никакого отношения к Эрдешу судя по статьям данной базы данных, имеют число Эрдеша " infinity".
Пример входных данных
1
4 3
Smith, M.N., Martin, G., Erdos, P.: Newtonian forms of prime factors
Erdos, P., Reisig, W.: Stuttering in petri nets
Smith, M.N., Chen, X.: First order derivates in structured programming
Jablonski, Т., Hsueh, Z.: Selfstabilizing data structures
Smith, M.N.
Hsueh, Z.
Chen, X.
Соответствующие выходные данные
Scenario 1
Smith, M.N. 1
Hsueh, Z. infinity
Chen, X. 2
Мой код выдаёт везде "Infinity", кроме Scenario: 1. В чём ошибка?
def calculate_erdos_number(database, names):
graph = {} # граф соавторств
erdos_numbers = {} # числа Эрдеша для каждого автора
# Инициализация чисел Эрдеша
for name in names:
erdos_numbers[name] = float('inf')
# Построение графа соавторств
for article in database:
authors = article.split(':')[0].split(',')
for i in range(len(authors)):
for j in range(i + 1, len(authors)):
author1 = authors[i].strip()
author2 = authors[j].strip()
if author1 not in graph:
graph[author1] = set()
if author2 not in graph:
graph[author2] = set()
graph[author1].add(author2)
graph[author2].add(author1)
# Поиск чисел Эрдеша для каждого автора
visited = set() # посещенные авторы
queue = [] # очередь для обхода в ширину
# Начальные авторы (те, у которых число Эрдеша равно 1)
for name in names:
if name in graph:
erdos_numbers[name] = 1
queue.append(name)
visited.add(name)
# Обход в ширину для нахождения чисел Эрдеша
while queue:
current_author = queue.pop(0)
for neighbor in graph[current_author]:
if neighbor not in visited:
erdos_numbers[neighbor] = erdos_numbers[current_author] + 1
queue.append(neighbor)
visited.add(neighbor)
return erdos_numbers
# Чтение входных данных
num_scenarios = int(input())
scenarios = []
for _ in range(num_scenarios):
num_articles, num_names = map(int, input().split())
articles = []
for _ in range(num_articles):
articles.append(input())
names = [input().strip() for _ in range(num_names)]
scenarios.append((articles, names))
# Выполнение сценариев
for i, (articles, names) in enumerate(scenarios, start=1):
erdos_numbers = calculate_erdos_number(articles, names)
print(f"Scenario {i}")
for name in names:
if erdos_numbers[name] == float('inf'):
print(f"{name} infinity")
else:
print(f"{name} {erdos_numbers[name]}")
Ответы (1 шт):
Я нашёл две ошибки:
- Неверно разобраны авторы статей. Разбиение по запятым приводит к
['Erdos', 'P.', 'Reisig', 'W.']
. Авторов было два, разобраны они на четыре строки, которые следует объединить попарно:
def parse_authors(authors):
return tuple(map(
', '.join,
zip(*(iter(map(str.strip, authors.split(','))), ) * 2)
))
...
# authors = article.split(':')[0].split(',')
authors = parse_authors(article[:article.index(':')])
- Выделение непосредственных соавторов сделано с ошибкой:
# if name in graph:
if name in graph['Erdos, P.']:
Если хорошенько почистить получится такое:
import collections
def parse_authors(authors):
return tuple(map(
', '.join,
zip(*(iter(map(str.strip, authors.split(','))), ) * 2)
))
def calculate_erdos_number(articles, names):
# Построение графа соавторств
graph = {}
for article in articles:
coauthors = parse_authors(article[:article.index(':')])
for a in coauthors:
for b in coauthors:
graph.setdefault(a, set()).add(b)
erdos_numbers = {'Erdos, P.': 0} # числа Эрдеша для каждого автора
queue = collections.deque(['Erdos, P.']) # очередь для обхода в ширину
while queue:
author = queue.pop()
erdos_number = erdos_numbers[author] + 1
for coauthor in graph[author]:
if coauthor not in erdos_numbers:
erdos_numbers[coauthor] = erdos_number
queue.append(coauthor)
return erdos_numbers
def main():
for i in range(int(input())):
n, p = map(int, input().split())
articles = [input() for _ in range(n)]
names = [input().strip() for _ in range(p)]
erdos_numbers = calculate_erdos_number(articles, names)
print(f"Scenario {i + 1}")
for name in names:
print(f"{name} {erdos_numbers.get(name, 'infinity')}")
main()