Одиннадцатый день Пришествия Кода. Сегодня мы будем симулировать мигающих осьминогов.
Как всегда, пожалуйста, попробуйте решить проблему, прежде чем искать решение. Для всех статей в этой серии ознакомьтесь с этим списком.
День 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.