23.06 Количество программ из A в B где траектория вычислений N команда

Решение 1

def f(st, fn, cmd, a):
    if st in a or cmd > 25:
        return 0
    if st == fn and cmd == 25:
        return 1
    a.add(st)
    x, y, z = 0, 0, 0
    if st % 2 == 0:
        x = f(st // 2, fn, cmd + 1, a.copy())
    y = f(st + 1, fn, cmd + 1, a.copy())
    if st % 3 == 0:
        z = f(st + st // 3, fn, cmd + 1, a.copy())
    return x + y + z

Решение 2

В соавторстве с марафонцем

Примечание: при добавлении в массив b элементов массива a используется символ *, чтобы добавить в массив именно элементы массива а, а не создать дополнительную вложенность массивов. Например: есть массив a = [1, 2, 3]. Если выполнить операцию b.append([a, 4]), то массив b = [[[1, 2, 3], 4]]. Если выполнить b.append([*a, 4]), то массив b = [[1, 2, 3, 4]].

paths = [[1]]
for i in range(25):
    new_paths = []

    for path in paths:
        x = path[-1]
        if x % 2 == 0:
            if x // 2 not in path:
                new_paths.append([*path, x//2])
        if x % 3 == 0:
            if x + x // 3 not in path:
                new_paths.append([*path, x + x//3])
        if x + 1 not in path:
            new_paths.append([*path, x+1])
    paths = new_paths.copy()

ans = 0
k = []
for path in paths:
    if path[-1] == 60:
        k.append(path)
        ans += 1
print(ans)