Решение задачи #34. Python Яндекс CodeRun, Космический мусорщик

Вариант решения задачи на языке программирования Python с Яндекс CodeRun.
Категория: Алгоритмы.
Название задачи: Космический мусорщик.
Сложность: Средняя.
Статус решения: "Решено".

Условие задачи:

В околоземном космическом пространстве накопилось много мусора, поэтому ученые сконструировали специальный аппарат – ловушку для космического мусора. Для того, чтобы хорошо собирать мусор, этот аппарат должен двигаться по достаточно сложной траектории, сжигая собранный по пути мусор. Ловушка может передвигаться в пространстве по 6 направлениям: на север (N), на юг (S), на запад (W), на восток (E), вверх (U) и вниз (D). Движением ловушки управляет процессор. Программа движения задаётся шестью правилами движения, которые соответствуют каждому из указанных направлений. Каждое такое правило представляет собой строку символов из множества {N, S, W, E, U, D}.

Команда ловушки — это пара из символа направления и параметра – целого положительного числа M. При исполнении такой команды ловушка в соответствии со своей программой выполняет следующее. Если параметр больше 1, то она перемещается на один метр в направлении, которое указано в команде, а затем последовательно выполняет команды, заданные правилом для данного направления, с параметром меньше на 1. Если же параметр равен 1, то просто перемещается на один метр в указанном направлении.

Тогда при выполнении команды S(3) мусорщик выполнит следующие действия:
1) переместится на 1 метр в направлении S
2) выполнит последовательно команды N(2), U(2), S(2), D(2), D(2), U(2), S(2), E(2).
Если далее проанализировать действия мусорщика при выполнении команд из пункта 2, получим, что в целом он совершит следующие перемещения:

SNNUUSNUSDDUSEDWEDDWEDUUSNUSDDUSEE

По заданной команде определите, какое общее количество перемещений на один метр совершит ловушка при выполнении заданной команды. В приведенном примере это количество равно 34.

Решение:

Python

# Считываем правила движения для каждого направления
rules = {}
directions = ['N', 'S', 'W', 'E', 'U', 'D']
for direction in directions:
    rules[direction] = input().strip()  # Сохраняем правило для каждого направления

# Считываем команду ловушки: направление и параметр
command_input = input().strip()
command_direction, command_param = command_input.split()
command_param = int(command_param)

# Создаем словарь для хранения уже вычисленных значений (мемоизация)
memo = {}

# Рекурсивная функция для подсчета количества перемещений
def count_moves(direction, param):
    # Если параметр равен 1, то совершается только одно перемещение
    if param == 1:
        return 1
    
    # Формируем уникальный ключ для мемоизации
    key = (direction, param)
    
    # Если результат уже был вычислен ранее, возвращаем его
    if key in memo:
        return memo[key]
    
    # Перемещение на один метр в текущем направлении
    total_moves = 1
    
    # Добавляем перемещения из правила для текущего направления
    for next_direction in rules[direction]:
        total_moves += count_moves(next_direction, param - 1)
    
    # Сохраняем результат в мемоизацию и возвращаем его
    memo[key] = total_moves
    return total_moves

# Вычисляем количество перемещений для заданной команды
result = count_moves(command_direction, command_param)

# Выводим результат
print(result)

Объяснение кода

Ввод данных:
Первые шесть строк содержат правила движения для каждого из шести направлений (N, S, W, E, U, D). Эти правила сохраняются в словаре rules, где ключ — это направление, а значение — строка с последовательностью символов.

Затем считывается команда ловушки, которая состоит из символа направления и целого числа (параметра). Этот параметр определяет глубину рекурсии.

Мемоизация:
Для ускорения вычислений используется словарь memo. Он хранит уже вычисленные значения для пар (направление, параметр), чтобы избежать повторного выполнения одних и тех же вычислений.

Рекурсивная функция count_moves:
Если параметр равен 1, ловушка совершает только одно перемещение, поэтому функция сразу возвращает 1.
Если параметр больше 1, функция добавляет одно перемещение (в текущем направлении) и рекурсивно обрабатывает каждое направление из соответствующего правила. Для этого она вызывает себя с уменьшенным параметром (param - 1) для каждого символа в правиле.

Результат сохраняется в словаре memo, чтобы избежать повторных вычислений.

Пример работы программы:
NUUSDD
NUSDD
DWED
DWED
UUSNUSDD
USEE
S 3

Источник решения: hdhai.com