На 20-й день Адвента Кода мы расшифровываем координаты звездной рощи. Я призываю вас сначала попробовать решить ее самостоятельно https://adventofcode.com.
Вход
Наши входные данные сегодня представляют собой зашифрованное сообщение в виде ряда целых чисел. Мы примем его как std::list<int64_t>
.
Расшифровка сообщения
Наша цель в первой части — расшифровать сообщение, переупорядочив элементы в зависимости от их значений.
Каждый элемент должен переместиться на столько пробелов, сколько его значение (вправо для положительного и влево для отрицательного), в то время как мы обрабатываем элементы в их первоначальном порядке.
Это уже указывает нам на std::list
, так как он обеспечивает дешевое переупорядочение элементов через std::list::splice
и стабильность итератора.
Чтобы перемещать элементы, мы можем реализовать пару вспомогательных функций. Во-первых, обобщенное продвижение, которое также обеспечивает циклическую семантику, затем две вспомогательные функции, которые возвращают позицию для операции соединения. Один для положительных чисел и один для отрицательных.
Собирая это вместе, мы сначала запоминаем стабильный порядок элементов, затем, один за другим, находим правильное положение соединения для каждого элемента и соединяем его на место.
Код содержит одну оптимизацию. Поскольку перемещение элемента на size-1
оставит его на том же месте, достаточно переместить каждый элемент только на value%(size-1)
позиций.
Чтобы получить окончательные расшифрованные координаты, мы повторно используем вспомогательную функцию продвижения, чтобы выбрать 1000-й, 2000-й и 3000-й элементы, считая с нулевой позиции.
Не совсем расшифровано
Видимо, наши усилия были напрасными. Чтобы правильно расшифровать сообщение, нам нужно умножить каждый элемент на ключ дешифрования, а затем десять раз запустить фактический процесс переупорядочивания.
К счастью, это не влияет на наш подход. Несмотря на то, что ключ дешифрования является очень большим числом, у нас нет целочисленных переполнений на нашем входе (если бы они были, мы могли бы также применить нашу операцию по модулю к ключу дешифрования).
Повторно используя наше предыдущее решение, мы сначала корректируем ввод с помощью ключа расшифровки, а затем применяем нашу функцию shuffle_once
десять раз.
Ссылки
Репозиторий с полным решением (включая парсинг ввода) доступен здесь: https://github.com/HappyCerberus/moderncpp-aoc-2022.
Я ежедневно размещаю контент на современном C++ в Twitter, LinkedIn, Mastodon, Medium и Substack.