Это двадцать третий день Пришествия Кода. Сегодня мы будем искать самый дешевый способ перетасовки амфипод.

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

День23

Сегодня наша задача — найти самый дешевый способ переупорядочить расположение элементов в «комнатах» с помощью соединительного «коридора». Стоимость переезда различается в зависимости от типа элемента, у нас:

  • Янтарные (A) амфиподы, с ценой шага 1
  • Бронзовые (Б) амфиподы, с ценой 10 шага
  • Медные (С) амфиподы, с ценой шага 100
  • Пустынные (D) амфиподы, с ценой шага 1000

Для части 1 у нас их по 2 в каждой комнате, с точками, обозначающими изначально пустой коридор:

#############
#...........#
###B#C#B#D###
  #A#D#C#A#
  #########

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

К счастью, у нас есть некоторые ограничения на возможные ходы:

  • если мы переместим амфипода в коридор, он останется там, пока не сможет добраться до конечного пункта назначения (комнаты, в которую он входит)
  • мы не можем перемещать амфипод во «входное» пространство, то есть пространство прямо перед комнатой
  • мы можем переместить амфипода в комнату только в том случае, если это комната назначения и нет «посетителей» (нет амфипод другого типа)

С учетом этих ограничений можно провести исчерпывающий поиск.

Комната

Начнем с представления комнаты. Как минимум, нам понадобятся операции push() (добавить элемент в комнату и сообщить стоимость) и pop() (удалить элемент из комнаты и сообщить стоимость). И посмотреть на верхний элемент, метод top().

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

auto room = Room{'A', {'C', 'B'}};

Основная сложность заключается в тщательном обновлении размера и количества фиксированных элементов (я столкнулся с ошибкой, которую не учёл в тестах).

Головоломка

Теперь, когда у нас есть детали управления комнатами, мы можем сосредоточиться на самом поиске. Есть две операции, которые мы можем выполнить с жадностью, поскольку они гарантированно оптимальны:

  • перемещение амфипода из коридора в комнату назначения
  • перемещение амфипода с верха одной комнаты в комнату назначения

Когда у нас нет доступных жадных ходов, остается только попытаться переместить одного из неправильно размещенных амфиподов из комнаты в коридор. Именно здесь мы проведем исчерпывающий поиск, поскольку будем пробовать все возможные позиции для всех доступных для перемещения амфиподов:

Для жадных операций проходим все занятые места в коридоре/верхах комнат, в которых есть посетители (строки 9/26) и проверяем, можем ли мы передвинуть эту амфиподу через зал — ничего не мешает (строки 16/32) а затем рассчитайте стоимость переезда.

Наш исчерпывающий поиск является рекурсивным. Сначала применяем все жадные операции (строки 29–34). Затем переходите к испробованию всех возможностей перемещения амфиподы из комнаты в коридор (строки 42–45), проверяя, не мешает ли что-нибудь (строка 48). Наконец, мы создаем копию состояния с этим изменением и рекурсией (строки 50, 51, 54).

Поскольку нам нужно сообщить только стоимость, мы обновляем минимум и сообщаем об этом, если находим какие-либо жизнеспособные пути к решению (строки 60–63).

Основной

Поскольку наступала усталость от решения, сегодня я не удосужился разобрать ввод:

Прошу прощения за не особо умное или красивое решение сегодня. Тем не менее, он по-прежнему безопасно работает менее одной секунды.

Ссылки и технические примечания

Репозиторий ежедневных решений доступен по адресу: https://github.com/HappyCerberus/moderncpp-aoc-2021.

Посмотрите в этом списке статьи о других днях появления кода.

И, пожалуйста, не забудьте попробовать Пришествие кода на себе.

Спасибо за чтение

Спасибо, что прочитали эту статью. Вам понравилось?

Я также публикую видео на YouTube. У тебя есть вопросы? Напишите мне в Twitter или LinkedIn.