На 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.