Задание 4 ЕГЭ: кратчайший код для буквы

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

Пример

Для передачи сообщений, содержащих девять букв, используется неравномерный двоичный код. Кодовые слова известны для восьми букв: А – 11001, Б – 01, В – 111, Г – 11000, Д – 00, Е – 1101, З – 1001, И – 101.

Укажите кратчайшее кодовое слово для буквы Ж, при котором код будет удовлетворять условию Фано. Если таких кодов несколько, укажите код с наименьшим числовым значением.

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

Решение

Строим дерево по известным кодам. Код новой буквы должен попасть в свободную ветку: узел, который не начинается ни с одного известного кода и сам не является началом известного кода. Если свободны оба потомка одного узла, свободен и сам узел — код получается короче.

Свободные ветки: 1000. Самая короткая (а при равной длине — с наименьшим значением): 1000.

from itertools import product

known = ["11001", "01", "111", "11000", "00", "1101", "1001", "101"]
for n in range(1, 8):                     # сначала короткие коды
    found = [c for c in ("".join(p) for p in product("01", repeat=n))   # по возрастанию
             if all(not c.startswith(k) and not k.startswith(c) for k in known)]
    if found:
        print(found[0])
        break

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