На двадесетия ден от Advent of Code дешифрираме координатите за горичката със звездни плодове. Насърчавам ви първо да опитате да го разрешите сами 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.

Публикувам ежедневно съдържание на Modern C++ в Twitter, LinkedIn, Mastodon, Medium и Substack.