Тринадцатый день Пришествия Кода. Сегодня мы будем складывать прозрачную бумагу, используя диапазоны C++20.

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

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

Наши входные данные — это ряд точек на 2D-плоскости и инструкции по свертыванию. Сначала немного упростим задачу. Мы всегда сворачиваемся только в одном направлении, поэтому двумерная природа проблемы не имеет значения.

Давайте посмотрим, что происходит, когда мы складываем одно число.

0 1 2 3 4 5 6 7 8 9
  x           x x

Если мы сложим эти три числа (один, семь и восемь), используя число пять, мы отразим числа вокруг числа пять как центр. И мы всегда отражаем только к нулю.

0 1 2 3 4 5 6 7 8 9
  x o o   |   - -

Это приводит нас к простой формуле: center — (number-center) или 2*center — number. Складывая бумагу, мы применяем эту формулу к значению x или y каждой точки.

С этим покончено, теперь мы можем начать с нашего обычного: объявлений и начальных тестов. Мы будем повторно использовать тип данных Point из Day5.

В наших тестах мы также проверяем функцию fold, которая складывает одно число:

Функция fold реализует упомянутую формулу, и мы также позаботимся о том, чтобы не сворачиваться в отрицательные числа:

Для синтаксического анализа мы повторно используем код для синтаксического анализа точек из Day5, а затем используем его для чтения первого раздела ввода:

Обратите внимание на вызов clear() (строка 31), который удаляет badbit из потока. Если бы мы этого не сделали, последующие вызовы getline завершились бы неудачей без попытки чтения. Чтобы прочитать вторую часть ввода, мы проверяем префикс каждой строки, а затем преобразуем конец строки в число (для правильного синтаксического анализа мы должны проверять, удалось ли преобразование).

Для сгиба, как сказано, проходим по всем точкам и применяем сгиб к соответствующей координате:

Обратите внимание, что нам нужно вставить свернутые элементы в новый unordered_set, так как небезопасно изменять unordered_set во время итерации по нему.

Тогда наша основная функция остается очень простой:

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

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

Сначала нам нужно расширить функцию сгиба для обработки всех сгибов:

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

Мы фильтруем складки по оси (строки 2 и 4), а затем выбираем минимальное число (строки 3 и 5). Обратите внимание, что фильтр работает лениво и происходит только тогда, когда алгоритм min_element перебирает элементы.

Теперь мы можем построить 2D-сетку (строка 7) и пройтись по точкам, установив для соответствующих пикселей значение # (строка 9).

Это снова делает нашу основную функцию очень простой:

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

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

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

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

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

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

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