Решение задачи про муравья
Этот проект содержит решение задачи про муравья, выполненное на языке Rust.
К сравнению с решением "в лоб" (rust-ant-puzzle-straightforward), предлагаю данное решение задачи рекурсивным методом, задействующее в среднем значительно меньше ресурсов машины - как ЦПУ, так и ОЗУ. Например, заменим начальные координаты муравья на (0; 0) и разрешим ему достигать ячеек с сумой цифр координат 35:
const X: i64 = 0;
const Y: i64 = 0;
const STEPS: u16 = 35;Данный способ справится за доли секунды без значительных затрат ресурсов системы. В то время как решение "в лоб" может занять несколько минут (чуть более 10 минут на одном ядре 2,9Гц) и задействовать более 12Гб оперативной памяти для учета посещенных ячеек. Кстати, результат при такой постановке задачи будет равен 117_109_345 ;).
Решение расчитано на диапазон координат, соответствующий значениям i64, и ограничением дистанции передвижения значениями u16.
В случае острой необходимости предлагаю подменить типы переменных на динамически расширяемые, что позволит решить задачу ближе к её описанию в части "бесконечной" координатной сетки.
Идея метода состоит в "замощении" области перемещения муравья, расположенной в положительной четверти координатной плоскости, рекурсивно квадратными фрагментами со стороной равной степени 10 с вычесленным количеством возможных в его пределах шагов. После чего, при необходимости, результат соответственно отражается на отрицательные координаты.
Для области подсчитывается количество возможных перемещений при доступном максимальном расстоянии от начала пути. Так область 10x10 полностью заполняется при максимальном расстояние 18 и более. При этом при преодалении значением расстоянии значений 9n-1 происходит переполнение и рекурсивно заполняются соседние квадраты. При преодолении границы переполнения масштаб увеличивается: рассматривается область 100x100 как область размерности 10, заполненная областями размерности 10, обработываемые на уровне рекурсии ниже. Результаты вычислений кешируются для уменьшения вычислительных затрат.
Для области 100x100 заполнение происходит уже за 36 и более шагов. Переполнение происходит при значениях 18n-1
Условие задачи:
На бесконечной координатной сетке находится муравей. Муравей может перемещаться на 1 клетку вверх (x,y+1), вниз (x,y-1), влево (x-1,y), вправо (x+1,y), по одной клетке за шаг.
Клетки, в которых сумма цифр в координате X плюс сумма цифр в координате Y больше чем 25 недоступны муравью. Например, клетка с координатами (59, 79) недоступна, т.к. 5+9+7+9=30, что больше 25.
Сколько клеток может посетить муравей если его начальная позиция (1000,1000), (включая начальную клетку).