Задание 4 ЕГЭ: длина закодированного слова

Условие Фано: длина кода слова. Тема номера — условие фано. Ниже — пример с ответом и решением; кнопкой под ним можно решить такую же задачу с другими числами, ответ проверится сразу.

Пример

По каналу связи передаются сообщения, содержащие только буквы из набора: К, Л, О, П, Т. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: К – 11, Л – 00, О – 100. Для двух оставшихся букв П и Т кодовые слова неизвестны. Какое количество двоичных знаков требуется для кодирования слова ПОТОЛОК, если известно, что оно закодировано минимально возможным количеством двоичных знаков?

Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.

Решение

Сколько раз буквы встречаются в слове ПОТОЛОК: О — 3, К — 1, Л — 1, П — 1, Т — 1.

Нарисуем дерево известных кодов. Свободны ветки, которые не начинаются ни с одного известного кода и сами не являются началом известного кода: 01, 101. Каждую неизвестную букву нужно поместить в одну из этих веток; если в ветку попадает несколько букв, ветку делим. Частым буквам выгодно дать короткие коды; буквы, которых нет в слове, всё равно должны получить код.

Один из оптимальных вариантов: П – 01, Т – 101. Длина кода слова: 3·3 (О) + 2 (К) + 2 (Л) + 2 (П) + 3 (Т) = 18.

Проверим перебором всех кодов длиной до 4 знаков для неизвестных букв.

from itertools import product

known = {"К": "11", "Л": "00", "О": "100"}
word = "ПОТОЛОК"
unknown = "ПТ"
codes = ["".join(p) for n in range(1, 5) for p in product("01", repeat=n)]

def fano(c, used):   # c не начало другого кода и другой код не начало c
    return all(not a.startswith(c) and not c.startswith(a) for a in used)

best = None

def search(i, used, total):
    global best
    if best is not None and total >= best:   # уже не лучше найденного
        return
    if i == len(unknown):
        best = total
        return
    for c in codes:
        if fano(c, used):
            search(i + 1, used + [c], total + len(c) * word.count(unknown[i]))

search(0, list(known.values()), sum(len(known[ch]) for ch in word if ch in known))
print(best)

Решить такую задачу — новый вариант с проверкой