Информатичка совсем озверела и задала реализовать игру «жизнь». При этом у неё есть система автотестирования, входные и выходные данные должны быть в XML. Конечно же система автотестирования проверяет только отсутствие смерти или зависания, а потом училка уже вручную будет смотреть.
Мало того, если игра будет реализована через стандартный алгоритм, то больше тройки не поставит. А мамка за тройку запретит за комп садиться, и я не смогу посмотреть поней. :'( .
Думаю, что можно реализовать игру через быстрые преобразования Фурье.
Базовый алгоритм представляю себе примерно так:
1. Формируем матрицу суммирования (filter), где 1 стоят в ячейках, сумму которых нам нужно получить (8 единиц, остальные нули). Выполняем над матрицей прямое преобразование Фурье (это нужно сделать только 1 раз).
2. Выполняем прямое преобразование Фурье над матрицей с содержимым игрового поля.
3. Перемножаем каждый элемент результата на соответствующий элемент матрицы «суммирования» из пункта 1.
4. Выполняем обратное преобразование Фурье — и получаем матрицу с нужной нам суммой количества соседей для каждой клетки.
Я думаю использовать python (ЯП можно выбирать свободно) и библиотеку fft из пакета numpy.
В правильном ли направлении я иду или есть более короткий путь? Может, уже есть готовые скрипты на питоне, которые я мог бы просто переписать?
