Это двадцать третий день Пришествия Кода. Сегодня мы будем искать самый дешевый способ перетасовки амфипод.
Как всегда, пожалуйста, попробуйте решить проблему, прежде чем искать решение. Для всех статей в этой серии ознакомьтесь с этим списком.
День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.