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