23.01 Количество программ из A в B

Решение рекурсией

Определим функцию f(a, b), которая будет вызывать саму себя. Она подсчитает количество программ, преобразующих число a в b. Функция возвращает:

• 0, если a > b или если в процессе встречается запрещённое число 7, так как такая траектория точно не будет подходящей и ее не нужно учитывать в подсчете количества траекторий;
• 1, если a == b, так как единица означает, что мы нашли путь, который число А может превратить в число B выполнив все условия задачи;
• сумму значений для трёх возможных переходов (+3, +1 к каждому разряду числа), если a < b, так как такая траектория еще не нарушила условия задачи и может стать подходящей.

d = set() # Создание списка
def f(a,c):
    if c > 9: # Если число команд больше 9, то вернуть 0
        return 0
    if c == 9: # Если число команд равно 9, то вернуть список
        d.add(a)
        return d
    str1 = str(a)
    str2 = ""
    for i in str1: # Увеличение разрядов числа
        if int(i) < 9: # Если разряд числа не равен 9, то увеличим его на 1
            str2 += str(int(i) + 1)
        else:
            str2 += i
    str2 = int(str2)
    if c < 9: # Если число команд меньше 9, то продолжать выполнение команд
        f(a + 3, c + 1)
        f(str2, c + 1)
f(81, 0) # Запуск программы для поиска значений
print(len(d))