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

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

День 12: Часть 1

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

Без каких-либо ограничений ответ обычно был бы бесконечным, потому что в простом графе S->A<->B->E мы можем продолжать зацикливаться между A и B и создавать более уникальные пути. Итак, чтобы сделать это возможным, у нас есть ограничение. Мы можем посетить маленькие пещеры (обозначенные строчными буквами) только один раз.

Нам нужно хорошее представление нашего графа в памяти. Обычно удобным является список смежности, где для каждого узла мы помним его соседей.

Также нам нужно вспомнить, в каких небольших пещерах мы уже побывали:

На этот раз мы получаем три уникальных ввода для тестирования из AoC, что упрощает наше тестирование:

При синтаксическом анализе ввода мы транслируем однонаправленный ввод и сохраняем информацию о смежности для обоих узлов:

Обратите внимание, что вставки (строки 10 и 13) будут вставлены только в том случае, если ключ отсутствует на карте. Помимо этого, мы следим за тем, чтобы не создавать соединения, ведущие к «началу» и «концу».

Что касается решения, основная идея, которую нужно здесь реализовать, состоит в том, чтобы создать количество возможных путей, просто суммируя их. Возьмем пример графика из AoC:

    start
    /   \
c--A-----b--d
    \   /
     end

Количество путей, начинающихся с start, равно количеству путей, начинающихся с start->A плюс start->b. И мы можем продолжать применять эту идею. Количество путей, начинающихся с start->A, равно количеству путей, начинающихся с start->A->c, start->A->end, start->A->b. При этом мы уже достигли одного терминального состояния. Есть только один путь, который начинается с start->A->end, так как мы никогда не можем покинуть end.

Количество путей — это сумма путей, начинающихся у соседей узла. Со следующими исключениями: если сосед — небольшая пещера, и мы уже посетили ее (строка 4), то количество путей равно нулю (т.е. пропускаем соседа), если сосед — end (строка 6), то количество путей это один. В противном случае запоминаем, что посетили этого соседа, если это небольшая пещера, и количество путей, начинающихся с этого соседа, в сумме (строка 12).

Это оставляет нашу основную функцию с очень небольшим количеством кода:

Однако созданный нами интерфейс немного неуклюж. Во-первых, мы всегда начинаем с start, и, кроме того, Memory бесполезна для вызывающего абонента. Это просто детали реализации, которые мы упускаем. Итак, давайте исправим это:

День 12: Часть 2

Для части 2 у нас немного другое ограничение. Нам разрешают повторно посетить небольшую пещеру. Однако у нас есть время только для повторного посещения одной из пещер.

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

Если мы уже посетили эту пещеру (строка 9), мы разрешаем повторное посещение, если мы не посещали повторно ни одну другую пещеру (строка 10). Нам также нужно быть осторожными с откатом, и мы сначала отменяем повторный просмотр (строки 19–20).

Следуя той же логике сокрытия деталей, мы создаем функцию-оболочку:

И расширим наш main, чтобы напечатать оба результата:

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

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

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

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

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

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

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