Однократный проход и количества

Что таблица ниже сделает со строкой 111220? Головка начинает в ближайшей пустой ячейке справа, в q0.

Если в рабочем состоянии каждая команда пишет символ и сдвигает головку в одну сторону, машина проходит строку один раз, и каждая ячейка меняется сама по себе. Здесь в q1 0 → 2, 1 → 0, 2 → 1, головка идёт влево до пустой ячейки. Из 111220 получится 000112.

rules = {    ('q0', 'λ'): ('λ', 'L', 'q1'),    ('q1', 'λ'): ('λ', 'S', 'q1'),    ('q1', '0'): ('2', 'L', 'q1'),    ('q1', '1'): ('0', 'L', 'q1'),    ('q1', '2'): ('1', 'L', 'q1'),}print(run_tm('111220', rules, 6))

После этой замены в строке три нуля, две единицы и одна двойка. Сколько каких цифр было до?

Если разные символы превращаются в разные, по результату можно точно сказать, сколько каких символов было во входе. Конечный ноль был единицей, конечная единица — двойкой, конечная двойка — нулём. Значит, во входе три единицы, две двойки и один ноль. Порядок символов восстанавливать не нужно.

А если таблица заменяет 5 и 7 на 1, а 9 на 0? Какая строка дала результат 101101?

Если два исходных символа дают один и тот же результат, по результату известна только их общая численность. Каждая конечная единица — пятёрка или семёрка, каждый ноль — точно девятка. Разных подходящих строк здесь 2⁴ = 16.

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

При той же замене результат из 9 символов чередуется: соседние цифры разные. Какая наименьшая сумма цифр могла быть во входе?

Условие на результат задаёт количества: чередование из 9 символов — это пять единиц и четыре нуля или четыре единицы и пять нулей. Единица выгоднее всего из пятёрки, ноль — только из девятки, поэтому лучше больше единиц: 5 · 5 + 4 · 9 = 61. Строка 595959595 даёт 101010101.

from itertools import productrules = {    ('q0', 'λ'): ('λ', 'L', 'q1'),    ('q1', 'λ'): ('λ', 'S', 'q1'),    ('q1', '5'): ('1', 'L', 'q1'),    ('q1', '7'): ('1', 'L', 'q1'),    ('q1', '9'): ('0', 'L', 'q1'),}best = Nonefor digits in product('579', repeat=9):    word = ''.join(digits)    result, pos, steps = run_tm(word, rules, 9)    if '00' not in result and '11' not in result:        s = sum(int(d) for d in word)        if best is None or s < best:            best = sprint(best)

Строка длины 10 из цифр 0, 1, 2 прошла замену 0 → 2, 1 → 0, 2 → 1, сумма цифр результата — 12. Какое наибольшее число двоек могло быть во входе?

Сумму результата выражают через количества входа, а наибольшее или наименьшее ищут по границам. Пусть во входе a нулей и c двоек. Нули дают двойки, двойки — единицы, единицы — нули: сумма 2a + c = 12, то есть c = 12 − 2a. Двоек больше всего при наименьшем a, но нулей и двоек вместе не больше 10. При a = 0 вышло бы c = 12, при a = 1 — c = 10 и 11 символов. При a = 2 — c = 8, ровно 10 символов: подходит.

Ответ 8. Проверка: 0022222222 → 2211111111, сумма 2 + 2 + 8 = 12.

• Однократный проходкаждая ячейка меняется сама по себе
• Количествапо результату — без порядка символов
• Два в одинизвестна только сумма их количеств
• Условие на результатзадаёт количества: чередование, сумма
• Условие на вход«больше» и «не меньше» дают разные ответы
• Проверкавход, на котором ответ достигается