Это шестнадцатый день Адвента Кода, и сегодня мы сбрасываем давление в вулкане. Я призываю вас сначала попробовать решить ее самостоятельно https://adventofcode.com.
Вход
Наши входные данные сегодня — это список клапанов, каждый из которых имеет указанную скорость потока и соседние клапаны.
Однако нам нужно обработать его дальше, прежде чем мы сможем работать с этим вводом. Нам нужно отфильтровать клапаны с ненулевым расходом, поскольку стоит посетить только их, а также нам нужно рассчитать минимальные расстояния между всеми узлами (мы можем использовать алгоритм Флойда-Уоршалла).
Нахождение максимального расхода
Максимальный расход будет получен из пути, который посещает некоторые из клапанов с ненулевым расходом, оставаясь при этом в пределах ограничения времени.
Мы можем использовать простой поиск в глубину, используя предварительно рассчитанные минимальные расстояния. Помимо поиска пути, мы должны быть осторожны с правильным расчетом расхода на основе открытых в данный момент клапанов.
Это исследует все пути. Однако из-за небольшого количества клапанов это не проблема.
У нас есть слоны
Во второй части мы получаем слона-помощника. К счастью, это не сильно усложняет дело.
Вместо того, чтобы пытаться имитировать, как мы по очереди со слоном, мы можем позволить слону попытаться закрыть все открытые клапаны, когда мы вычислим наш первоначальный максимум (соответствующий тому, что клапаны больше не закрываются).
Обратите внимание, что этот метод грубой силы очень медленный (~ 50 секунд на моей машине). Мы могли бы значительно ускорить его, используя битовую игру вместо неупорядоченных контейнеров.
Кроме того, я уверен, что есть более разумное решение, не основанное на поиске в глубину.
Ссылки
Репозиторий с полным решением (включая парсинг ввода) доступен здесь: https://github.com/HappyCerberus/moderncpp-aoc-2022.
Я ежедневно размещаю контент на современном C++ в Twitter, LinkedIn, Mastodon, Medium и Substack.
