Идет девятнадцатый день Пришествия кода, и мы ищем оптимальный план создания робота. Я призываю вас сначала попробовать решить ее самостоятельно https://adventofcode.com.
Вход
Наш вклад сегодня представляет собой серию чертежей. Мы создадим пользовательский тип для представления схемы и примем входные данные как std::vector<Blueprint>.
В поисках наилучшего результата
Цель на сегодня — определить максимальное количество жеодов, которое мы можем собрать, учитывая чертеж конкретного робота.
Поскольку мы ищем оптимальный результат, наш самый простой подход — это полный перебор; однако это создает проблему. В любой момент у нас есть до пяти вариантов: построить одного из четырех роботов или просто добыть. При 24 единицах времени это означает пять в степени двадцать четыре, что совершенно невозможно.
Нам потребуется значительное сокращение пространства поиска, и для начала мы сможем избежать создания ненужных роботов. Примечательно, что, поскольку мы можем построить только одного робота в единицу времени, никогда не нужно иметь больше производящих роботов, чем стоимость создания одного робота.
Мы можем закодировать эту логику в структуру данных State, которая предоставит методы для определения того, можем ли мы построить робота, должны ли мы построить робота и, наконец, модифицирующие методы для создания робота и майнинга.
С этим мы можем построить наш алгоритм поиска.
Чтобы еще больше уменьшить пространство поиска, мы можем жадно строить геодезических роботов и даже роботов из обсидиана (что особенно важно для второй части). Жадно строить роботов из обсидиана немного опасно, так как может быть крайний случай, когда это не оптимальный ход; тем не менее, это сработало для моего ввода.
Ссылки
Репозиторий с полным решением (включая парсинг ввода) доступен здесь: https://github.com/HappyCerberus/moderncpp-aoc-2022.
Я ежедневно размещаю контент на современном C++ в Twitter, LinkedIn, Mastodon, Medium и Substack.
