Advent of Code 2020 D11 и язык Zig

Advent of Code — конкурс для программистов, о котором я уже писал ранее. К нему я возвращаюсь нерегулярно, но в этот раз совпало два момента.

Первый: язык Zig (но изучать мне показалось удобнее здесь). Этот язык, издалека и с большим прищуром похожий на Rust, на самом деле позиционирует себя как улучшенная версия C. Мне он понравился, несмотря на то, что я довольно быстро добился падения компилятора. Думаю, если в него добавить несколько современных функций и доработать, он со временем будет весьма успешен.

Второй: стрим на YouTube с решениями Advent of Code 2020 на языке Zig. Не буду упоминать канал, но его несложно найти; в реальности на YouTube едва ли наберётся десять каналов, где Zig упоминается.

Мне, как и любому любителю, не нравятся решения профессионалов (предполагая что ведущий стрима — хотя бы джун-профессионал в области программирования). Так и здесь — от зубодробительных циклов и головоломных операций с исходными данными (по-моему он решил делать все операции с текстом без конверсии в какой-либо иной тип…) меня довольно быстро разобрало раздражение, и захотелось решить задачку самому.

Задачка в следующем: на прямоугольном поле расположены стулья и пустые места между ними. За один раунд пустые стулья заполняются, если рядом с ними (в одном из понятных восьми направлений вверх, вниз и т. д.) нет занятых мест; если рядом с занятым местом больше четырёх занятых, оно освобождается; в остальных случаях состояние места не меняется.

Тут легко узнаётся игра в «жизнь», клеточные автоматы.

Исходные данные представлены в виде текста, разделенного на строки (длиной 10 для тестовых данных, 95 для реальных). В тексте L обозначает свободное место, # обозначает занятое место, а . обозначает проход, который никогда не будет занят.

Раунды заканчиваются тогда, когда состояние поля становится стабильным, то есть состояние клеток не меняется.

Учитывая, что Zig поддерживает опциональные типы (!) — хорошая замена C! — мне кажется более чем логичным представить эту доску в виде ?bool, то есть одного из трёх состояний: true, false, null.

Текстовый поток конвертируем в сплошной массив таких опциональных значений. Ширину массива можно подсчитать, разделив исходную строку по \n и взяв длину любого полученного фрагмента.

После этого создаём массив массивов: первый элемент в таком массиве будет исходным состоянием, а все последующие массивы получаются путём прохода по предыдущему состоянию; функция прохода выдаёт новое значение для каждой клетки, рассчитанное на основании предыдущих состояний.

Служебные функции:

  • функция равенства, сравнивающая два массива ?bool;

  • функция печати массива в нужном виде (для дебага);

  • функция, возвращающая количество занятых мест (это ответ для задачки).

Функция прохода принимает состояние поля (нужно же откуда-то брать состояние соседних клеток для расчёта нового состояния текущей), индекс текущей клетки в массиве и ширину массива.

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

  • состояние текущей клетки;

  • состояние соседних клеток;

  • ряд и колонку текущей клетки через деление нацело и остаток от деления (они удобнее в расчётах).

Дальше очевидное: если текущая клетка расположена во второй колонке, то можно посмотреть состояние соседней слева (потому что она существует всегда). Если клетка расположена в предпоследней строке в предпоследней колонке, то для неё точно существует сосед справа снизу… логика понятна.

В общем, решение задачи на императивном языке оказалось вполне приятным и заняло около 200 коротких строк, несмотря на некоторые несуразицы, типа того, что switch не в состоянии делать match по опциональным типам; может быть исправят в дальнейшем, потому что такое сделало бы решение заметно короче.

Язык порекомендую любопытствующим.