Длина и память программы

Дополнительный урок — для продвинутых: такие условия редки.

Сколько программ переводят 2 в 12 командами «+1» и «×2» ровно за пять команд?

Если условие ограничивает программу целиком — длину, последнюю команду, число умножений, — одного текущего числа мало: в состояние добавляют то, что нужно помнить о прошлом. Из 6 в 12 за одну команду попасть можно, а за две — нельзя: «6, и осталась одна команда» и «6, и осталось две» — разные вопросы.

При заданной длине считают по паре «число, сколько команд осталось»; успех — когда команды кончились ровно в цели. Каждая команда уменьшает остаток на 1.

from functools import cache  @cachedef f(x, y, left):    if left == 0:        return 1 if x == y else 0    if x >= y:        return 0    return f(x + 1, y, left - 1) + f(x * 2, y, left - 1)  print(f(2, 12, 5))

А если из 2 в 12 нужно пройти через 6 ровно за пять команд?

При общей длине участки зависят друг от друга: перебирают, сколько команд уходит на первый участок, и складывают произведения. Обычное произведение 3 · 2 = 6 посчитало бы программы любой длины.

from functools import cache  @cachedef f(x, y, left):    if left == 0:        return 1 if x == y else 0    if x >= y:        return 0    return f(x + 1, y, left - 1) + f(x * 2, y, left - 1)  print(sum(f(2, 6, k) * f(6, 12, 5 - k) for k in range(6)))

Что ещё, кроме числа, бывает нужно помнить?

Состояние — всё, что нужно знать о прошлом, чтобы считать будущее. Ограничение на одно число проверяют по самому числу; ограничение на программу целиком добавляет в состояние ещё одну величину.

Команды «+1» и «−1». Сколько программ переводят 2 в 4?

Если число может вернуться туда, где уже было, программ бесконечно много — пока условие не ограничит длину или числа. Перед 2 → 3 → 4 можно пройти круг 2 → 3 → 2 один раз, два, сколько угодно: все эти программы разные.

Поэтому в таких задачах всегда есть рамка: ровно L команд или числа в заданных пределах. Её и переносят в функцию — отсечение «x > y» здесь не годится, а @cache не спасает от бесконечной рекурсии: ответ запоминается, только когда вызов уже завершился.

Команды «+1» и «×2». Сколько программ переводят 2 в 20, если нельзя умножать дважды подряд?

Запрет повтора подряд хранят в состоянии как последнюю команду. Из 8, полученного умножением, умножать нельзя, а из 8, полученного прибавлением, — можно.

from functools import cache  @cachedef g(x, y, last):    if x > y:        return 0    if x == y:        return 1    result = g(x + 1, y, 1)    if last != 2:        result += g(x * 2, y, 2)    return result  print(g(2, 20, 0))

В начале последней команды нет — передаём 0. Без запрета программ было бы 30.

Из 1 командами «+1» и «×2» выполняют не больше четырёх команд. Какое наименьшее число получить нельзя?

Вопрос «сколько чисел» — не «сколько программ»: одинаковые числа считают один раз. Поэтому хранят не счётчик, а множество чисел, полученных за 0, 1, 2, 3 и 4 команды:

current = {1}reached = {1}for step in range(4):    current = {y for x in current for y in (x + 1, x * 2)}    reached |= currentprint(sorted(reached))print(min(n for n in range(1, 100) if n not in reached))

Ответ 11. В подсчёте программ множество не годится: оно склеило бы разные программы с одинаковым результатом.

Команды «+3» и «−2», старт 1, цель 6, ровно пять команд, число на экране всегда положительное. Сколько программ?

Если команды двигают число в обе стороны, рамку задаёт условие — длина и пределы чисел, а не «число больше цели». Из 7 командой «−2» можно вернуться к 5, поэтому ветку выше цели не обрывают.

def f(x, left):    if x <= 0:        return 0    if left == 0:        return 1 if x == 6 else 0    return f(x + 3, left - 1) + f(x - 2, left - 1)  print(f(1, 5))

• Ровно L командчисло и сколько команд осталось
• Длина по участкамсумма произведений по длине первого участка
• Не подрядчисло и последняя команда
• Сколько чиселмножество, а не счётчик
• Возвратынужна рамка: длина или пределы
• Обе стороныне обрывать ветку выше цели