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

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

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

Сегодняшняя цель — работать с двоичными числами, а в части 1 цель — построить числа из наиболее часто встречающихся и наименее часто встречающихся битов. Так, например, при заданном списке из трех чисел 0b111, 0b100, 0b000 для первого бита наиболее часто встречающийся бит равен 1, для второго 0 и третьего 0. Таким образом, число, составленное из наиболее часто встречающихся битов, равно 0b100, а число, составленное из наименее частых битов 0b011.

Спецификация проблемы Advent of Code не указывала, что мы должны делать в случае ничьей, например. 0b111, 0b000. Поэтому мне пришлось принять решение, что 1 битов считаются более частыми. Таким образом, число, составленное из наиболее частых битов, будет 0b111, а число, составленное из наименее частых битов, будет 0b000.

Другой неуказанный аспект — это то, что происходит в таких случаях, как 0b101, 0b100, 0b111. Число состоит из наименее частых битов 0b010 или 0b110? Я снова сделал оценочный звонок и считаю нулевые случаи допустимой частотой, поэтому результат здесь будет 0b010.

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

Я расскажу, почему мы указываем ширину и почему мы указываем ее по-разному в двух версиях, но, как обычно, давайте начнем с тестов.

Единственное замечание здесь заключается в том, что динамическое указание битовой ширины в качестве параметра функции позволяет вводить входные данные с переменной шириной. Напротив, версия, которая принимает разрядность в качестве параметра шаблона, требует, чтобы все тестовые входные данные были одинаковыми.

Мы тестируем функцию epsilon_rate, но я не указал прототип ее функции. Причина в том, что мы можем вычислить скорость эпсилон из скорости гамма-излучения просто как ее дополнение. Обратите внимание, что это работает только потому, что мы считаем нулевую частоту допустимой частотой.

UINT32_MAX все 32 бита установлены в 1. Когда мы сдвигаем его, мы создаем последовательность нулей, начиная с самых младших битов (1111 << 2 == 1100). Инвертирование этого значения создает маску И, которая удалит все лишние биты, установленные в единицу, после вычисления дополнения.

// ex. for width = 4 and gamma_rate = 1010
UINT_MAX << 4           == 1111 1111 1111 1111 1111 1111 1111 0000
mask = ~(UINT_MAX << 4) == 0000 0000 0000 0000 0000 0000 0000 1111
~gamma_rate             == 1111 1111 1111 1111 1111 1111 1111 0101
~gamma_rate & mask      ==                                    0101

Прежде чем я покажу вам решение для коэффициента гаммы, мне нужно обсудить две вспомогательные функции:

Функция div2_roundup позволит нам проверить, какая частота выше. v&1 возвращает младший значащий бит, единицу, если число нечетное, и ноль, если число четное.

В функции has_bit_set мы сначала создаем число с одним битом, установленным в проверяемой позиции. Затем побитовое И вернет ненулевое значение, если бит установлен, и ноль, если нет. При преобразовании в логические значения ненулевые значения обрабатываются как ИСТИНА, а ноль рассматривается как ЛОЖЬ.

Внешний цикл (строка 3) перебирает биты. Поскольку нам нужно построить число слева направо, нам нужно перебирать биты от наиболее значащих до наименее значимых. Как только мы рассмотрим конкретный бит, мы должны подсчитать, сколько чисел имеет этот бит. Формулировка cnt_one >= div2_roundup(data.size()) представляет собой логическое выражение, которое возвращает истину, если половина или более чисел имеют этот бит, и ложь в противном случае. После этого мы используем преобразование bool в int:

  • если половина или более чисел имеют этот бит, установленный в 1, условие ИСТИНА, которое преобразуется в 1, поэтому мы добавляем 1 бит к результату
  • если у половины или более чисел этот бит установлен в 0, условие равно FALSE, которое преобразуется в 0, поэтому мы добавляем бит 0 к результату

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

Здесь у нас два этапа. Сначала мы вычисляем частоты (строки 5–10), обрабатывая ввод. Мы используем std::bitset<width>, что значительно упрощает эту задачу. Мы можем перебирать биты каждого числа и накапливать количество единиц, увиденных в каждой позиции. Однако std::bitset также заставляет нас передавать битовую ширину в качестве параметра шаблона. Построение результата (строки 11–14) идентично предыдущей версии.

Наконец, основная функция, и здесь я выбрал векторный вариант, так как он предъявляет дополнительные требования к основной функции, то есть к чтению входных данных в вектор:

Мы снова используем std::bitset для чтения двоичных чисел, вместо операции в std::ransform мы используем std::identity{}, которая возвращает все переданное ей, но затем мы проецируем каждое std::bitset с помощью функции-члена to_ulong(), которая возвращает прочитанные биты как беззнаковое длинное целое. Проекции — одна из новых возможностей std::ranges, появившихся в C++20.

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

Во второй части мы снова будем играть с битами. Задача состоит в том, чтобы выбрать два числа. Опять же, один будет следовать «наибольшему», а другой — «наименьшему» пути. Однако по мере поиска мы будем сужать наш выбор. Поэтому при выборе статуса oxygen_generator мы сначала выберем наиболее часто встречающийся первый бит. Это будет первый бит для статуса oxygen_generator. Затем мы сужаем наш выбор до наиболее часто встречающегося первого бита и выбираем из них наиболее часто встречающийся второй бит. Например:

0b1111, 0b1011, 0b1101, 0b0100
most_freq = 1, result = 1...
0bx111, 0bx011, 0bx101
most_freq = 1, result = 11..
0bxx11, 0bxx01
most_freq = 1 result = 111.
0bxxx1
most_freq = 1, result = 1111

Прежде чем мы перейдем к решению, давайте посмотрим на наши объявления:

И тест:

Если вы знакомы с алгоритмами сортировки, вы могли заметить что-то знакомое в описании проблемы. Действительно, это попахивает QuickSort.

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

Мы разделяем (используя std::partition) данные по значению текущего бита. Это означает, что все элементы до и после точки раздела имеют соответствующий бит одного и того же значения. В зависимости от того, какой из двух диапазонов (от начала до точки раздела или от точки раздела до конца) больше, мы либо рекурсивно используем oxygen_rating, который следует за наиболее распространенным (более длинный диапазон), либо co2_rating, который следует за наименее распространенным (более короткий диапазон).

Мы также рекурсивно используем только заданный поддиапазон, что означает, что мы рассматриваем только те элементы, которые имеют наиболее распространенный или наименее распространенный бит. Наконец, мы заканчиваем, когда у нас либо есть только один элемент, либо просмотрены все биты.

Наконец, мы должны рассмотреть крайний случай только с одним разделом. Это происходит, когда все числа имеют одинаковое значение бита. В таком случае точка раздела равна концу.

Чтобы собрать все это вместе, вот наша основная функция:

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

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

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

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

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

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

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