Графы и таблицы

Что проверяет номер

Есть схема дорог, где пункты подписаны буквами, и таблица длин дорог, где пункты подписаны номерами. Таблицу и схему рисовали независимо, поэтому пункт П3 может оказаться любой буквой. Надо понять, какой номер какой букве соответствует, и прочитать из таблицы нужную длину.

Этот номер можно решить двумя способами. Руками нужно внимательно рассуждать, и это хорошо для понимания. Автокодом нужно только переписать дороги и соседей, а буквы расставит программа. На экзамене лучше автокод: он быстрее, и в нём почти негде ошибиться.

Типы задач

Таблица всегда симметричная: дорога из А в Б и из Б в А одна и та же, поэтому записана дважды. Пустая клетка значит, что дороги нет.

Способ руками: степени пунктов

Степень пункта это число дорог, которые из него выходят. На схеме считаем линии у буквы, в таблице считаем заполненные клетки в строке. Степень не зависит от того, как подписан пункт, поэтому по ней буквы и номера можно связать.

Разберём пример. Нужно найти сумму длин дорог A–B и E–F.

Считаем степени в таблице: П1 это 3, П2 это 1, П3 это 2, П4 это 3, П5 это 3, П6 это 2. Теперь идём от особенных пунктов к их соседям:

1. Степень 1 только у F и у П2. Значит, F = П2.
2. Единственный сосед F это E, а единственный сосед П2 это П4. Значит, E = П4.
3. Соседи E это F, D и C, а соседи П4 это П2, П6 и П1. Степень D равна 2, степень C равна 3, и у П6 степень 2, а у П1 степень 3. Значит, D = П6 и C = П1.
4. Сосед D, кроме E, это B, а сосед П6, кроме П4, это П5. Значит, B = П5.
5. Остался один пункт: A = П3.

Читаем таблицу. Дорога A–B это П3–П5, длина 12. Дорога E–F это П4–П2, длина 6. Ответ 12 + 6 = 18.

Если получилось два варианта

Иногда два пункта неразличимы, например, у них одинаковые степени и одинаковые соседи. Граф симметричный, поэтому подойдут оба соответствия. Это нормально: в правильной задаче ответ у них один и тот же, выбирай любое.

Автокод: самый крутой способ

А теперь то же самое, только думает программа. Идея простая: перебираем все способы расставить буквы по номерам и оставляем те, где каждая дорога со схемы есть в таблице. Пунктов на экзамене от 5 до 8, это самое большее 40320 вариантов, и компьютер проверит их мгновенно.

Нужно сделать только две вещи:

1. Переписать дороги со схемы в roads.
2. Переписать таблицу в conns: для каждого пункта одной строкой номера его соседей. В нашей таблице П1 связан с 3, 4 и 5, поэтому первая строка '345'.

from itertools import permutations

roads = 'AB AC BC BD DE CE EF'.split()
conns = ['345', '4', '15', '126', '136', '45']

for p in permutations('ABCDEF'):    # p[i] — буква пункта i+1
    if all(str(p.index(x) + 1) in conns[p.index(y)] for x, y in roads):
        print(*p)

Вывод C F A E B D. Читается так: П1 это C, П2 это F, П3 это A, П4 это E, П5 это B, П6 это D.

Осталось посмотреть в таблицу. Дорога A–B это П3–П5, длина 12. Дорога E–F это П4–П2, длина 6. Ответ 18, как и руками, только теперь мы ничего не рассуждали.

Что происходит в коде

• permutations('ABCDEF') перебирает все порядки букв. Первая буква в p это П1, вторая это П2.
• p.index(x) находит место буквы в порядке, считая с нуля. Поэтому номер пункта это p.index(x) + 1.
• conns[p.index(y)] это соседи пункта y. Проверяем, что среди них есть пункт x.
• all(...) даёт True, только если есть все дороги со схемы.

Если соответствий два, напечатаются две строки. Бери любую: ответ по таблице получится один и тот же.

Практика

Схема дорог ниже, найди сумму длин дорог B–C и D–E. В заготовке уже всё есть, кроме соседей. Здесь пункты B и C неразличимы, поэтому соответствий будет два, но ответ один.

from itertools import permutations
roads = 'AB AC BC BD CD DE'.split()
conns = []   # впиши соседей каждого пункта, например '345'
for p in permutations('ABCDE'):
    if all(str(p.index(x) + 1) in conns[p.index(y)] for x, y in roads):
        print(*p)

Ловушки перед экзаменом