Второй день Пришествия кода. Сегодня мы будем работать со структурой и посмотрим на оператора космического корабля.
Как всегда, пожалуйста, попробуйте решить проблему, прежде чем искать решение. Для всех статей в этой серии ознакомьтесь с этим списком.
День 2: Часть 1
Нам даются инструкции в текстовом виде. Формат основан на строке с одной командой в каждой строке, при этом каждая команда формируется из направления и числового значения.
forward 10 down 2 up 1
Синтаксический анализ текста — одна из областей, в которых стандартная библиотека C++ не особенно хороша. Средства высокого уровня не очень эффективны, а средства низкого уровня не особенно просты в использовании. Я буду придерживаться средств высокого уровня, но укажу, где код особенно неэффективен.
Нам понадобится способ отслеживать позицию при разборе ввода. Самый простой способ — создать простую структуру с двумя полями: depth, которое настраивается с помощью команд up и down, и distance, на которое влияет команда forward.
Мы можем упростить себе задачу и работать с каждой строкой отдельно. Поскольку каждая команда преобразуется в дельту позиции, мы можем проанализировать строку и вернуть Position. Затем внешний код может добавить дельту к рабочему положению.
Как и в День 1, мы начнем с написания тестов для этой функции синтаксического анализа строк:
Обратите внимание, что этот код теперь требует, чтобы Position было сопоставимо из-за EXEPECT_EQ. Мы можем быстро исправить это, добавив в нашу структуру оператор космического корабля по умолчанию. Реализация по умолчанию предоставляет лексикографический компаратор, но нам нужны только == и !=.
Теперь пришло время реализовать синтаксический анализ строки:
Сначала мы находим пробел, отделяющий команду от числа (строка 2), затем преобразуем число в целое число (строка 3) и возвращаем другую дельту позиции на основе команды.
Если бы нас заботила производительность, мы бы работали с std::string_view. К сожалению, в настоящее время стандартная библиотека не предлагает средств для преобразования std::string_view в число (напрямую), и нам пришлось бы написать обертку вокруг std::from_chars.
С учетом сказанного, пока мы принудительно копируем std::string , все команды, которые мы анализируем, должны удобно вписываться в оптимизацию небольшой строки. Таким образом, даже с копиями мы не должны выделять память, а стоимость должна быть эквивалентна использованию std::string_view.
Чтобы проанализировать весь ввод, мы переходим построчно и вызываем наш код разбора строки. Но сначала тестовый код:
Одна вещь, которую мы все еще упускаем, — это способ сложить дельты позиций вместе. Мы можем добавить operator+= в нашу структуру Position, чтобы нам не приходилось вручную вносить изменения.
С помощью синтаксического анализатора строк и Position с поддержкой operator += весь код синтаксического анализа значительно упрощается:
Мы идем построчно, пока не достигнем конца файла, применяем наш анализатор строк к каждой строке и добавляем результат к промежуточному итогу.
День 2: Часть 2
Вторая часть задачи представляет интересный поворот. Вместо того, чтобы up и down обозначали прямое движение, они меняют направление, а затем forward применяют это направление.
До сих пор наш код не имел состояния, и каждая строка интерпретировалась изолированно. Введение направления изменяет значение forward. Следовательно, мы должны отслеживать направление, изменив наш код синтаксического анализа строки, чтобы он сохранял состояние. Но давайте начнем с настройки нашей структуры Position.
Перемещение необработанных операций в функции-члены сделает наш код синтаксического анализа более понятным для чтения.
Этот тест также определяет интерфейс того, как мы предоставляем состояние синтаксическому анализатору строк. У нас есть другие варианты, и, например, этот код синтаксического анализа также может быть функцией-членом нашей структуры position: pos.parse(line).
При всей этой подготовке наш парсер строк очень похож на вариант из части 1:
И собираем все это вместе тоже очень похожим образом:
Мы по-прежнему вызываем анализатор строк для каждой строки, как и раньше. Однако на этот раз мы переходим в состояние, которое сохраняется при всех вызовах.
Наконец, поскольку я не показывал ее в первой части, давайте посмотрим на нашу основную функцию, которая очень похожа на Day1.
Ссылки и технические примечания
Репозиторий ежедневных решений доступен по адресу: https://github.com/HappyCerberus/moderncpp-aoc-2021.
Для получения статей о других днях Advent of Code ознакомьтесь с этим списком.
И, пожалуйста, не забудьте попробовать Пришествие кода на себе.
Спасибо за чтение
Спасибо, что прочитали эту статью. Вам понравилось?
Я также публикую видео на YouTube. У тебя есть вопросы? Напишите мне в Twitter или LinkedIn.
