Обратный обход: как решить задачу без перемещения ящиков

Как решить задачу о перемещении ящиков без перемещения ящиков

Представьте: у вас есть миллионы ящиков, и нужно выполнить сотни тысяч операций перемещения. Стандартное решение работает 7 секунд, но есть способ сократить время до 100 миллисекунд. Секрет — в обратном обходе. В этой статье я покажу, как это сделать, и объясню, почему иногда лучшая оптимизация — не ускорять операцию, а вообще её исключить.

Постановка задачи: что нужно на самом деле

Задача из Advent of Code 2022, день 5: есть стопки ящиков и инструкции вида move 4 from 2 to 1. Нужно применить все инструкции и вывести верхний ящик каждой стопки. В обычном случае это просто, но в нашем входном файле 86 000 строк, 30 000 инструкций, и некоторые перемещают десятки тысяч ящиков за раз. Суммарно это более полумиллиарда операций. Если симулировать всё в лоб, время выполнения становится огромным.

Ключевой вопрос: что именно требуется получить? Только верхний ящик каждой стопки, а не всё конечное состояние. Это меняет всё.

Первая попытка: наивное решение

Моё первое решение было прямолинейным: массивы для стопок, и для перемещения блока ящиков я использовал splice(), разворачивал блок и добавлял в целевую стопку. Код работал, но время выполнения составляло около 7 секунд. Вот пример на Python:

def solve_naive(stacks, moves):
    for count, src, dst in moves:
        # забираем блок из исходной стопки
        block = stacks[src][-count:]
        # разворачиваем, так как ящики переносятся по одному
        block.reverse()
        # добавляем в целевую стопку
        stacks[dst].extend(block)
        # удаляем из исходной
        del stacks[src][-count:]
    return ''.join(stack[-1] for stack in stacks)

Это даёт правильный ответ, но слишком медленно. Нужно было что-то менять.

Вторая попытка: ссылки вместо копирования

Я попробовал не копировать ящики, а хранить ссылки на диапазоны исходных данных. Каждая стопка представлялась как {array, start, end, reversed}. Перемещение меняло эти ссылки, а не сами данные. Время упало до ~2 секунд, но всё ещё много. Проблема в том, что диапазоны разбиваются на мелкие куски, и всё равно приходится перебирать много элементов.

Ключевая идея: обратный обход

Подсказка пришла из фильма «Довод» (Tenet), где время идёт назад. Вместо того чтобы моделировать перемещения вперёд, я начал с конечных позиций верхних ящиков и пошёл назад по инструкциям. Для каждой инструкции я отслеживал, откуда взялась текущая позиция. Это позволяет не перемещать ящики вообще.

Но сначала нужно скорректировать инструкции: некоторые перемещают больше ящиков, чем есть в стопке. Поэтому я делаю один проход вперёд, отслеживая только размеры стопок (целые числа):

# sizes — список размеров стопок
sizes = [len(stack) for stack in initial_stacks]
moves = []
for count, src, dst in raw_moves:
    count = min(count, sizes[src])
    sizes[src] -= count
    sizes[dst] += count
    moves.append((count, src, dst))

Теперь у нас есть реальное количество ящиков, которое перемещает каждая инструкция. Затем для каждой конечной позиции (верх каждой стопки) идём назад:

def trace_back(moves, stacks_count):
    # результат для каждой стопки
    result = []
    for stack_idx in range(stacks_count):
        curr_stack = stack_idx
        depth = 0  # 0 — верхний ящик
        for count, src, dst in reversed(moves):
            if count == 0:
                continue
            if curr_stack == dst:
                if depth < count:
                    # ящик был перемещён из src
                    curr_stack = src
                    depth = count - 1 - depth
                else:
                    # ящик остался в dst, но глубина уменьшилась
                    depth -= count
            elif curr_stack == src:
                # ящик был в src, глубина увеличилась
                depth += count
        result.append((curr_stack, depth))
    return result

Здесь curr_stack — номер стопки, в которой находился ящик на текущем шаге, а depth — расстояние от верха. Для каждой конечной позиции мы проходим все инструкции назад, но каждая операция занимает константное время. Итого сложность O(стопки × инструкции), что в нашем случае около 300 000 операций — мгновенно.

Результат: 100 мс вместо 7 секунд

После реализации на JavaScript время упало до ~89 мс. Портировав на Python, я получил 100–200 мс. Это в 70 раз быстрее. Главное — я не нашёл способ ускорить перемещение ящиков, я просто перестал их перемещать.

Практические выводы

Что делать прямо сейчас:

• Проанализируйте задачу: что именно требуется на выходе? Часто не нужно вычислять всё промежуточное состояние.
• Попробуйте решить задачу с конца: обратный обход часто упрощает логику и сокращает вычисления.
• Используйте ссылки и индексы вместо копирования данных, когда это возможно.
• Оптимизируйте не операцию, а необходимость её выполнения.

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

Попробуйте применить обратный обход в своей следующей задаче — и вы увидите, как время выполнения падает в разы. Удачи!