Задание 1. Схема дорог и таблица

Как узнать: слева схема дорог, где пункты обозначены буквами, справа таблица, где те же пункты обозначены номерами П1, П2, … и указаны длины дорог. Какой номер какой букве соответствует, неизвестно. Спрашивают длину дороги между двумя буквами.

Обычно задание решают на бумаге: считают, сколько дорог выходит из каждого пункта (это называется степенью вершины), и сопоставляют. Пункт со схемы, из которого выходят 4 дороги, это строка таблицы, где заполнено 4 клетки. Если степени у всех разные, всё решается за минуту.

Когда степени повторяются, удобно доверить перебор программе: перебрать все способы сопоставить буквы номерам и оставить те, при которых дороги на схеме и в таблице совпадают.

Пример

На схеме 7 пунктов и дороги между ними:

АГ, АД, АЕ, БЖ, ВД, ВЕ, ВЖ, ГЖ, ЕЖ

Таблица длин дорог (пустая клетка значит, что дороги нет):

Какова длина дороги из А в Г?

• frozenset это множество, которое можно положить в другое множество. Пара {3, 4} и пара {4, 3} для него одно и то же: дорога ведь в обе стороны.
• Перестановок 7! = 5040, программа проверяет их мгновенно.
• Сопоставлений может найтись несколько (схема бывает симметричной), поэтому ответы собираем в множество. В правильном задании ответ один.

Таблицу в словарь переписывают вручную: каждую дорогу один раз, по верхнему правому треугольнику таблицы.