SandPile

Консольное приложение, которое моделирует абелеву песчаную кучу: читает начальное состояние из TSV-файла, шаг за шагом обваливает кучи на растущей сетке и сохраняет состояния картинками в BMP. Сетку храните в своей динамической памяти, BMP пишете сами — без сторонних библиотек и стандартных контейнеров.

Аргументы командной строки

--max-iter и --freq — целые неотрицательные числа. На неизвестный аргумент, отсутствие обязательного или некорректное значение программа пишет сообщение об ошибке и завершается с ненулевым кодом.

cmake -B build
cmake --build build
./build/labwork3 --input input/fractal.tsv --output out

Путь к бинарнику зависит от вашего CMakeLists.txt, здесь — для примера.

Начальное состояние

Каждая строка TSV — одна непустая ячейка: координата x, координата y и число песчинок, через табуляцию. Координаты помещаются в int16_t и бывают отрицательными, число песчинок — в uint64_t.

0	0	4
-2	-1	16
2	1	12

Начальная сетка — минимальный прямоугольник, в который попадают все перечисленные ячейки; остальные ячейки внутри него пустые. Для файла выше это $x \in [-2, 2]$, $y \in [-1, 1]$, то есть 5 × 3.

Правила модели

Программа останавливается, когда модель стабильна или выполнено --max-iter итераций.

Самый маленький пример — single-pile.tsv, 4 песчинки в точке (0, 0). За одну итерацию сетка 1 × 1 расширяется во все стороны до 3 × 3 и становится стабильной:

до:  4        после:  0 1 0
                      1 0 1
                      0 1 0

Сохранение состояний

• Итерации нумеруются с 1. При freq > 0 картинки сохраняются после итераций freq, 2 · freq, 3 · freq и так далее.
• Последнее состояние сохраняется всегда, даже если остановка пришлась между сохранениями. Если оно уже сохранено на последней итерации, второй раз его писать не нужно.
• При freq = 0 сохраняется только последнее состояние.
• Начальное состояние отдельно не сохраняется. Но если не выполнено ни одной итерации (стабильный вход или --max-iter 0), оно и есть последнее — его нужно сохранить.

Например, при --max-iter 10 --freq 3 картинки появятся после итераций 3, 6, 9 и 10. Как называть файлы, условие не задаёт: удобно по номеру итерации.

Формат картинки

Одна ячейка — один пиксель, размер картинки равен размеру сетки. Цвет зависит от числа песчинок:

На пиксель отводится не больше 4 бит, поэтому подходит BMP с палитрой и глубиной цвета 4 бита.

Примеры

Готовые файлы лежат в input/. Маленькие удобно проверять руками:

Крупные рисуют фрактальные узоры, как на иллюстрациях в Википедии. Запускайте их без --max-iter:

Теормин

Мягкие дедлайны

Максимум 12 баллов.

• Только стандартная библиотека C++, сторонние библиотеки запрещены. Чтение аргументов и запись BMP — свои.
• В приложении запрещены стандартные контейнеры (std::vector, std::deque, std::map и другие), строки (std::string), умные указатели, аллокаторы, std::pmr, строковые потоки (std::stringstream и родня) и std::valarray.
• C-функции управления памятью (malloc, calloc, realloc, free) тоже запрещены: память под сетку выделяйте через new[] и освобождайте через delete[], расширение — новый блок, копирование и освобождение старого.
• Сетка хранится в динамической памяти и растёт по мере надобности. Массив заранее заданного максимального размера не подходит.
• std::filesystem разрешён — пригодится, чтобы создать папку для картинок.
• В собственных тестах можно GoogleTest и всю стандартную библиотеку.
• Сборка — только CMake.
• CI собирает решение clang++-21 с санитайзерами (-fsanitize=address,undefined), но готовых тестов нет, так что ловят они ошибки только в ваших тестах. Перед сдачей прогоните программу на примерах из input/ с AddressSanitizer, UndefinedBehaviorSanitizer и LeakSanitizer: выход за границы, утечки и чтение неинициализированной памяти всплывут там.
• Стиль проверяет clang-tidy: функции, классы и структуры в CamelCase, переменные в lower_case, поля классов с _ на конце, константы и элементы перечислений в kCamelCase.