Шестнадцатый день Пришествия Кода. Сегодня мы будем анализировать и оценивать пакеты данных, закодированные в компактном двоичном формате, который закодирован как текст. Веселье.

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

День 16

Сегодняшняя проблема заключается в том, что нам нужно многое обдумать. Во-первых, наши входные данные — это данные, закодированные в виде шестнадцатеричного текста, где каждый символ представляет собой цифру от 0 до F и представляет 4 бита данных. Чтобы проанализировать этот ввод, нам нужно следовать рекурсивному формату пакета.

Описание на AoC очень подробное, но сводится к трем типам пакетов:

  • буквальный пакет: [version:3][type:3 == 4]([literal_chunk:5])+
  • размер пакета оператора: [version:3][type:3][type:1 == 0][bit_length:15]([sub_packet])+
  • подсчитанный пакет оператора: [version:3][type:3][type:1 == 1][count:11]([sub_packet])+

Итак, в любом случае мы начинаем с шестибитного заголовка (3+3), состоящего из версии и типа. Если тип имеет значение четыре, у нас есть литерал. В противном случае у нас есть операторский пакет. Данные для литералов состоят из повторяющихся пятибитных фрагментов, где старший бит служит для обозначения последнего фрагмента (если он равен нулю), а оставшиеся 4 бита являются частью значения. Размер пакетов оператора указывает количество подпакетов, используя общее количество битов, которые должны быть прочитаны (пятнадцатибитное поле). Подсчитанные операторские пакеты указывают количество подпакетов, используя их количество (одиннадцатибитное поле).

Необычный битовый поток

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

Так что же это за идея? Что ж, представьте, что мы могли бы написать следующий код:

Такой интерфейс, несомненно, сделал бы написание решения сегодняшней проблемы приятным. Итак, давайте представим, что у нас есть этот BitStream, и приступим к реализации решения.

Представление пакетов

Нам нужно начать с представления рекурсивной структуры данных пакета:

Каждый пакет содержит литерал или субпакеты (строка 19). Подпакеты состоят из поля размера (длина в битах или количество), а затем вектора с фактическими пакетами. У нас также есть несколько вспомогательных функций, так как работа с std::variant громоздка.

Разбор

Предполагая, что у нас есть наш волшебный BitStream, давайте реализуем синтаксический анализ:

Для синтаксического анализа литералов мы зацикливаемся до тех пор, пока не встретим кусок с начальным нулем (строка 8), и продолжаем добавлять четыре бита значения к общему значению (строка 7).

Чтобы разобрать сам пакет, мы сначала читаем заголовок, а затем, в зависимости от типа, либо рассматриваем его как литерал, либо начинаем читать подпакеты. Обратите внимание, что для чтения определенного количества бит мы создаем SubBitStream, поэтому оператор ввода должен принимать BaseBitStream (это начинает определять, как именно должны работать классы BitStream).

Решение

Подводя итог версиям, мы можем рекурсивно пройтись по подпакетам:

Для части 2 мы должны интерпретировать все возможные значения поля типа и рассматривать весь пакет как числовое выражение со следующей семантикой:

  • тип 0: сумма подпакетов
  • тип 1: произведение подпакетов
  • тип 2: минимум подпакетов
  • тип 3: максимум подпакетов
  • тип 4 является литералом
  • тип 5: единица, если первый подпакет больше второго, иначе ноль
  • тип 6: единица, если первый подпакет меньше второго, иначе ноль
  • тип 7: единица, если первый подпакет равен второму, иначе ноль

Мы можем реализовать это напрямую, введя оператор преобразования в uint64_t:

Это преобразование вызовет рекурсивное расширение, так как каждое из подвыражений потребует, чтобы соответствующие подвыражения также были преобразованы в uint64_t.

Затем мы можем использовать эти два решения из функции main:

Битовый поток

Итак, теперь у нас есть полное, но не работающее решение. Пришло время реализовать недостающую часть, BitStream. Мы знаем, что нам понадобятся три класса: BaseBitStream, который будет использоваться для операторов входного потока, класс BitStream для представления потока и класс SubBitStream, который поддерживает ограничение на количество считанных битов.

Начнем с реализации базового класса с модификатором field_width.

Мы откладываем фактическое чтение до класса BitStream (строка 9). Далее, перегрузка оператора входного потока для field_width_mod позволяет нам установить ширину следующего поля (строка 12). Наконец, мы перегружаем оператор входного потока для любого целочисленного типа (строка 16), а затем либо читаем ограниченное количество битов, как запрошено (строка 19), либо всю ширину типа (строка 17).

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

Затем метод read_bits объединяет их и считывает запрошенное количество битов (строка 25).

Для SubBitStream мы дополнительно отслеживаем общий лимит битов для чтения:

Тесты

Наконец, поскольку сегодня мы делаем все в обратном порядке, пришло время тестов с использованием тестовых данных из AoC:

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

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

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

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

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

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

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