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 по опциональным типам; может быть
исправят в дальнейшем, потому что такое сделало бы решение заметно короче.
Язык порекомендую любопытствующим.