Одиннадцатый день Пришествия Кода. Сегодня мы будем симулировать мигающих осьминогов.

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

День 11: часть 1 и часть 2

Мы моделируем квадратную сетку сущностей (осьминогов). Мы моделируем систему шаг за шагом, следуя этим правилам:

  • каждый шаг уровень энергии каждого осьминога увеличивается на 1
  • когда осьминог достигает уровня энергии 10 или более, он мигает
  • мигающий осьминог увеличивает уровень энергии окружающих (во всех восьми направлениях) осьминогов на 1
  • осьминог может мигать только один раз на каждом этапе
  • все мигающие осьминоги заканчивают раунд с уровнем энергии 0

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

Начнем с объявлений и базового теста:

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

Простым способом решить эту проблему было бы зацикливание до тех пор, пока какой-либо осьминог мигает в предыдущем цикле (потенциально создавая больше осьминогов, которые могут мигать). Однако, несмотря на простоту, это также довольно медленно, и мы можем добиться большего.

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

Парсинг ввода идентичен Дню 9. Мы читаем введенный символ за символом, преобразуя цифры ASCII в их целые значения.

В тиковой функции мы сначала повышаем уровень энергии всех сущностей и запоминаем те, которые готовы вспыхнуть (строки 24–30). Вместо того, чтобы сжимать 2D-координату в одно число (строка 28), мы могли бы также использовать структуру для хранения 2D-координат, как мы сделали в День 5 со структурой Point.

Затем мы зацикливаемся, пока у нас есть осьминоги, готовые к миганию. Начнем с удаления одного элемента из набора, расшифровки координат и записи того, что этот осьминог вспыхнул (строки 33–38). После этого мы перебираем всех соседей. Обратите внимание на использование ssize_t (тип размера со знаком) и граничные условия для обработки осьминогов на границах сетки. Наконец, мы не трогаем уже промелькнувших осьминогов (строка 43), а если сосед переходит порог, добавляем его в список (строка 46).

Все, что нам нужно сделать в нашей основной функции, — это просуммировать количество вспышек за 100 тиков:

У нас также сразу есть решение для части 2 проблемы с этим подходом. Мы должны обнаружить первую итерацию, когда все осьминоги мигают. Однако мы уже знаем, сколько осьминогов промелькнуло. Это число, возвращаемое tick. Итак, мы сравниваем это с общим количеством осьминогов:

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

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

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

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

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

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

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