Наступил восьмой день Пришествия кода. Сегодня мы будем распутывать запутанные провода в стиле судоку, используя битовые манипуляции.
Как всегда, пожалуйста, попробуйте решить проблему, прежде чем искать решение. Для всех статей в этой серии ознакомьтесь с этим списком.
День8: Часть 1
Наша цель на сегодня — расшифровать зашифрованный семисегментный дисплей. Наши входные данные представляют собой серию строк, описывающих, какие сегменты дисплея горят:
aaa aaa aaa b c c b b c c b ddd ddd e f f e f e f f e f ggg ggg
Это отображение 876 будет закодировано как abcdefg acf abdefg. К сожалению, помимо работы с этим представлением, наш ввод также зашифрован. К счастью, скремблирование стабильно внутри каждой строки ввода, и все дисплеи для одного ввода зашифровываются одинаково. Весь ввод представляет собой серию строк в следующем формате:
Отображения перед разделителем служат информацией, которая должна позволить нам расшифровать скремблирование, отображения после разделителя — это те, которые мы стремимся расшифровать.
Для части 1 мы не будем решать всю проблему расшифровки ввода. Вместо этого нам нужно определить только уникальные номера. Это 1, 4, 7 и 8, потому что мы можем идентифицировать эти числа, основываясь только на количестве освещенных сегментов (2 сегмента для 1, 4 сегмента для 4, 3 сегмента для 7 и 7 сегментов для 8).
Однако даже с этой более простой задачей мы уже можем подготовиться к нашей предстоящей задаче декодирования ввода и удобного представления семисегментного дисплея:
Биты — это удобный способ выражения элементов, состоящих из элементов с двумя состояниями (включено/выключено). Однако нам нужно быть осторожными, потому что манипулирование битами может легко сделать код трудным для чтения. Одним из способов смягчения этой проблемы является подготовка именованных констант, с которыми легче работать, т. е. здесь мы назвали каждый сегмент и подготовили массив, представляющий освещенные сегменты для каждой из цифр.
Когда подготовка завершена, теперь мы можем проанализировать ввод, сначала тест:
И затем код разбора:
На этот раз мы не полагаемся на потоки и вместо этого анализируем строку символ за символом. Мы читаем символы нижнего регистра, пропускаем пробелы и определяем, когда мы передаем разделитель |. Выражение *it-'a' основано на том факте, что символы нижнего регистра кодируются как последовательный диапазон, поэтому 'c'-'a'==2 и 'a'+3=='d' .
После завершения синтаксического анализа ввода мы можем теперь прочитать весь ввод и использовать std::ranges::count_if для подсчета экземпляров одного, четырех, семи и восьми.
Чтобы подсчитать количество освещенных сегментов, мы используем std::popcount, который возвращает количество битов, установленных в 1.
День8: Часть 2
Время расшифровать входы. Мы будем использовать рудиментарную версию решения ограничений, чтобы определить, какой вход подключен к какому сегменту.
Решить проводку будет использовать логику, чтобы сузить возможные соединения. После того, как мы решили, какой вход подключен к какому сегменту, мы можем использовать эту информацию для декодирования числа (во входе после разделителя).
Когда тест готов, пришло время написать решатель. Нам понадобятся доменные переменные. Вы можете думать о них как о переменных с набором возможных значений. Смысл решения состоит в том, чтобы удалить невозможные значения из этих наборов, пока мы не достигнем единственного уникального решения. Наборы снова очень удобно представлять битами, поэтому мы используем uint8_t для представления набора из семи возможных соединений сегментов.
Давайте посмотрим, какую информацию мы можем извлечь из зашифрованного ввода.
Очевидное
Мы уже говорили о числах, которые имеют уникальные представления. Один, четыре, семь и восемь. Восьмерка не дает нам никакой информации, поскольку перечисляет все сегменты.
- для одного освещенные сегменты должны быть либо C, либо F
- для четырех освещенные сегменты должны быть либо B, C, D или F
- для семи освещенные сегменты должны быть либо A, C или F
Отрицательный
Можем рассмотреть и негатив.
- во-первых, неосвещенные сегменты не могут быть C или F
- для четырех неосвещенные сегменты не могут быть B, C, D или F
- для семи несветящиеся сегменты не могут быть A, C или F
Есть и немного скрытый негатив.
- для чисел с пятью светящимися сегментами неосвещенными сегментами являются B, C, E или F.
- для чисел с шестью светящимися сегментами неосвещенными сегментами являются C, D или E.
Уборка
Наконец, если у нас есть провод только с одним соединением, этот провод фиксирован, и мы знаем, что никакой другой провод не подключен к этому сегменту.
Мы инициализируем каждый провод (переменная домена) для подключения ко всем сегментам. Затем мы просматриваем каждый из наших входов и применяем указанную логику в зависимости от количества освещенных сегментов. Мы перебирали все провода и удаляли невозможные соединения. Наконец, мы делаем очистку (строки 50–59).
После этого мы ожидаем, что каждый провод будет подключен к одному сегменту, и выполним процесс перевода в функции декодирования.
После всей проделанной работы нам нужно только перебрать числа, чтобы вычислить сумму:
Ссылки и технические примечания
Репозиторий ежедневных решений доступен по адресу: https://github.com/HappyCerberus/moderncpp-aoc-2021.
Посмотрите в этом списке статьи о других днях появления кода.
И, пожалуйста, не забудьте попробовать Пришествие кода на себе.
Спасибо за чтение
Спасибо, что прочитали эту статью. Вам понравилось?
Я также публикую видео на YouTube. У тебя есть вопросы? Напишите мне в Twitter или LinkedIn.
