Что проверяет задание

Исполнитель преобразует число командами из короткого списка: прибавить константу, умножить, вычесть. Нужно найти, сколькими способами можно получить из числа A число B, иногда с дополнительным условием на промежуточные значения или на набор команд.

Определения

Команда исполнителя, элементарное преобразование текущего числа. Каждая команда увеличивает, уменьшает или умножает его по фиксированному правилу.

Программа, конечная последовательность команд. Две программы различны, если различаются как последовательности, даже если дают одно число.

Траектория, последовательность промежуточных значений от старта до финиша.

Количество программ, число различных траекторий (или различных последовательностей команд, это совпадает, если команды однозначно определяются переходом).

Запрещённая точка, значение, через которое проходить нельзя. Все траектории, содержащие его, отбрасывают.

Обязательная точка, значение, через которое пройти нужно. Тогда количество программ из A в B через C равно произведению чисел программ A → C и C → B, если C встречается один раз по пути. Если C может встречаться несколько раз, нужно уточнять: обычно имеют в виду «хотя бы раз» или «на траектории есть C», и тогда удобнее считать динамикой с признаком «C уже посещали».

Монотонность, если все команды неуменьшающие и старт меньше финиша, достаточно рассматривать значения между A и B. Обратные команды ломают это упрощение.

Динамический счётчик, величина K(x): сколько программ приводит из A в x. Тогда K(A) = 1, а для остальных x значение собирается с тех y, из которых одной командой получается x.

Почему важен порядок

Число способов попасть в B, не длина кратчайшей программы. Короткая программа, один из способов. Нужно суммировать все допустимые пути.

Умножение создаёт пропуски: не всякое число достижимо. Недостижимые значения имеют ноль программ.

Общий алгоритм решения

1. Выписать команды, старт, финиш и особые точки (запрет, обязательный проход, запрет повторов команд).
2. Определить множество значений, которые вообще имеют смысл: обычно отрезок между минимумом и максимумом по траектории.
3. Если команды обратимы однозначно, можно идти от финиша к старту; иначе надёжнее идти от старта вперёд.
4. Для каждого значения сложить количества программ с допустимых предшественников.
5. Наложить фильтр особых точек: для запрета не обновлять это значение; для обязательного прохода вести два слоя счётчиков.
6. Ответ, счётчик в финише (в нужном слое).

Программа построчно

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

Разберём программу на условии:

У исполнителя три команды: 1. Прибавить 1. 2. Прибавить 2. 3. Умножить на 2. Сколько существует программ, которые исходное число 3 преобразуют в число 11? Траектория вычислений не должна содержать число 7.

nelz = [7]

def f(cur, finish):
    if cur == finish:
        return 1
    if cur > finish or cur in nelz:
        return 0
    return f(cur + 1, finish) + f(cur + 2, finish) + f(cur * 2, finish)

print(f(3, 11))

nelz = [7] - список запрещённых чисел («нельзя»). Траектория не должна проходить через них. Подробно - в разделе «Запрещённая точка».

def f(cur, finish): - функция отвечает на вопрос «сколько программ переводят число cur в число finish». Подробно - в разделе «Функция f(cur, finish)».

if cur == finish: / return 1 - уже получили нужное число: это одна готовая программа.

if cur > finish or cur in nelz: / return 0 - число стало больше нужного (все команды только увеличивают, вернуться нельзя) или попали в запрещённое число: из этого состояния нет ни одной подходящей программы. Подробно - в разделе «Остановки рекурсии».

return f(cur + 1, finish) + f(cur + 2, finish) + f(cur * 2, finish) - первой командой может быть любая из трёх. После команды «Прибавить 1» мы оказываемся в числе cur + 1, и программ дальше f(cur + 1, finish); так же для двух других команд. Складываем. Подробно - в разделе «Сумма по командам».

print(f(3, 11)) - считаем программы из 3 в 11 и печатаем ответ.

Команды как выражения

Каждая команда превращает текущее число cur в новое. Запишем это выражением Python:

• «Прибавить 1» → cur + 1;
• «Прибавить 3» → cur + 3;
• «Вычесть 2» → cur - 2;
• «Умножить на 2» → cur * 2;
• «Возвести в квадрат» → cur ** 2 (** - возведение в степень);
• «Разделить нацело на 2» → cur // 2 (// - деление с отбрасыванием остатка).

Эти выражения и стоят внутри вызовов f(…, finish) в последней строке функции.

Функция f(cur, finish)

def f(cur, finish):
    ...

• def - объявление функции, f - её имя;
• cur («current», текущее) - число, которое сейчас на экране;
• finish - число, которое нужно получить;
• функция возвращает (return) количество программ, переводящих cur в finish.

Как она считает. Чтобы узнать, сколько программ ведёт из 3 в 11, функция спрашивает саму себя о соседних числах: сколько программ из 4 (после «Прибавить 1»), из 5 (после «Прибавить 2»), из 6 (после «Умножить на 2»). Те, в свою очередь, спрашивают о следующих числах - и так, пока не дойдут до 11 или не перелетят его. Ответы складываются обратно по цепочке.

Остановки рекурсии

Рекурсивная функция обязательно должна где-то остановиться, иначе она будет вызывать себя бесконечно. Остановок две:

    if cur == finish:
        return 1
    if cur > finish:
        return 0

• Дошли - cur == finish: программа найдена, возвращаем 1. Пустая программа (ни одной команды) тоже считается - именно она «лежит» в этой единице, когда начальное число уже равно конечному.
• Перелетели - cur > finish: если все команды только увеличивают число, из числа больше нужного уже не вернуться, программ 0.

Если команды только уменьшают число («Вычесть 1», «Вычесть 3»), знак меняется: if cur < finish: return 0.

Порядок проверок важен: сначала «дошли», потом «перелетели» - иначе можно отсечь подходящий случай.

Запрещённая точка

«Траектория вычислений не должна содержать число 7» - ни одно промежуточное число не может быть 7.

nelz = [7]

def f(cur, finish):
    if cur == finish:
        return 1
    if cur > finish or cur in nelz:
        return 0
    ...

cur in nelz - True, если текущее число есть в списке запрещённых. Попали в запрещённое число - путь обрывается, программ 0. Слово or («или») объединяет две причины остановиться в одну строку. Если запрещённых чисел несколько, их перечисляют в списке: nelz = [7, 12].

Сумма по командам

    return f(cur + 1, finish) + f(cur + 2, finish) + f(cur * 2, finish)

Любая программа начинается с какой-то команды. Разобьём все программы по первой команде:

• начинаются с «Прибавить 1» - после неё на экране cur + 1, дальше программ столько, сколько из cur + 1 в finish, то есть f(cur + 1, finish);
• начинаются с «Прибавить 2» - f(cur + 2, finish);
• начинаются с «Умножить на 2» - f(cur * 2, finish).

Группы не пересекаются, поэтому общее количество - сумма. Слагаемых столько же, сколько команд у исполнителя.

Обязательная точка

«Траектория содержит число 10» - путь обязательно проходит через 10. Разбиваем путь на две части: от начала до 10 и от 10 до конца.

print(f(4, 10) * f(10, 22))

Любой путь первой части можно продолжить любым путём второй части, поэтому количества перемножаются (правило произведения): если до 10 есть 5 путей, а после - 6, то всего 5 · 6 = 30 программ.

Если обязательных чисел два, частей три: f(start, a) * f(a, b) * f(b, finish), где a < b (для уменьшающих команд - a > b). Запрещённые числа учитываются в каждой части через тот же список nelz.

Программы и траектории

Программа - последовательность команд, траектория - последовательность получающихся чисел. Иногда разные команды дают одно число: из 2 команды «Прибавить 2» и «Умножить на 2» обе дают 4. Это две разные программы, но одна траектория.

Если спрашивают «сколько различных траекторий», одинаковые следующие числа считаем один раз - собираем их во множество:

def f(cur, finish):
    if cur == finish:
        return 1
    if cur > finish:
        return 0
    nexts = {cur + 1, cur + 2, cur * 2}
    total = 0
    for nxt in nexts:
        total += f(nxt, finish)
    return total

• {cur + 1, cur + 2, cur * 2} - множество следующих чисел; при cur = 2 в нём будут 3 и 4 - четвёрка один раз;
• цикл складывает количества траекторий для каждого различного следующего числа.

Ускорение: lru_cache

Когда программ миллионы, обычная рекурсия считает очень долго: одни и те же значения f(cur, finish) вычисляются заново тысячи раз. Декоратор lru_cache запоминает уже посчитанные ответы:

from functools import lru_cache

@lru_cache(None)
def f(cur, finish):
    ...

• from functools import lru_cache - подключаем инструмент из стандартного модуля functools;
• @lru_cache(None) - строка над def: функция запоминает результат для каждой пары аргументов, None - без ограничения на размер памяти;
• при повторном вызове с теми же cur и finish ответ берётся из памяти мгновенно.

Логика решения от этого не меняется - только скорость.