Приглашение на вечеринку можно переслать не дальше чем через k знакомств. Функция within_hops(graph, start, k) должна вернуть множество всех, до кого приглашение дойдёт за не больше чем k шагов, не считая самого start. В функции две ошибки — найдите и исправьте их.
graph = {"я": ["Оля", "Пётр"], "Оля": ["Рома"], "Рома": ["Сеня"]}
within_hops(graph, "я", 2) # {"Оля", "Пётр", "Рома"}Заготовка задачи обновилась с тех пор, как вы сохранили свой код.
Сбросить редактор к заготовке? Ваш код будет удалён.
from collections import deque
def within_hops(graph: dict[str, list[str]], start: str, k: int) -> set[str]:
"""Все, до кого можно дойти не больше чем за k шагов (без start)."""
dist = {start: 0}
queue = deque([start])
while queue:
person = queue.pop()
if dist[person] == k:
continue # дальше пересылать нельзя
for friend in graph.get(person, []):
if friend not in dist:
dist[friend] = dist[person] + 1
queue.append(friend)
return {p for p, d in dist.items() if 0 < d < k}Вывод обрезан: показаны первые строки.
GRAPH = {"я": ["Оля", "Пётр"], "Оля": ["Рома"], "Рома": ["Сеня"]}
def test_example():
"""Пример: k = 2"""
got = within_hops(GRAPH, "я", 2)
assert got == {"Оля", "Пётр", "Рома"}, f"получено {got!r}"
def test_k_zero():
"""k = 0 — никого"""
got = within_hops(GRAPH, "я", 0)
assert got == set(), f"получено {got!r}"
def test_k_one():
"""k = 1 — только прямые знакомые"""
got = within_hops(GRAPH, "я", 1)
assert got == {"Оля", "Пётр"}, f"получено {got!r}"
def test_large_k():
"""Большое k — все достижимые"""
got = within_hops(GRAPH, "я", 100)
assert got == {"Оля", "Пётр", "Рома", "Сеня"}, f"получено {got!r}"
def test_start_excluded_in_cycle():
"""Сам start не входит в ответ, даже если до него есть цикл"""
graph = {"a": ["b"], "b": ["a", "c"]}
got = within_hops(graph, "a", 3)
assert got == {"b", "c"}, f"получено {got!r}"
def test_short_path_wins():
"""Кратчайший путь учитывается, даже если длинная ветка просмотрена бы первой"""
graph = {"s": ["a", "b"], "b": ["c"], "c": ["d"], "a": ["d"], "d": ["e"]}
got = within_hops(graph, "s", 3)
assert got == {"a", "b", "c", "d", "e"}, f"получено {got!r} — e достижим за 3 шага: s → a → d → e"
def test_isolated():
"""У start нет знакомых"""
got = within_hops({}, "один", 5)
assert got == set(), f"получено {got!r}"Можно решать и в своём редакторе: «Скопировать с тестами» и запустите python3 within_hops.py — тесты те же, результат покажет ✓ / ✗ и итог.
Сравните код с поиском в ширину из главы: в каком порядке должны обрабатываться люди — по мере удаления от start?
Поиск в ширину держится на очереди: первым пришёл — первым обслужен. Какой конец deque забирает pop()?
Что делает сравнение 0 < d < k с людьми ровно на расстоянии k?
from collections import deque
def within_hops(graph: dict[str, list[str]], start: str, k: int) -> set[str]:
"""Все, до кого можно дойти не больше чем за k шагов (без start)."""
dist = {start: 0}
queue = deque([start])
while queue:
person = queue.popleft()
if dist[person] == k:
continue # дальше пересылать нельзя
for friend in graph.get(person, []):
if friend not in dist:
dist[friend] = dist[person] + 1
queue.append(friend)
return {p for p, d in dist.items() if 0 < d <= k}