Решение задач Advent of Code 2024 с использованием PostgreSQL демонстрирует мощь SQL, выходящую за рамки стандартных представлений. Для моделирования игры «Сокобан» (перемещение ящиков по складу) использованы возможности JSON для представления карты склада и тип
Основная идея решения заключается в рекурсивном моделировании шагов робота. Карта склада представлена в виде JSONB-словаря, где ключами являются координаты ячеек, а значениями — типы ячеек (стена, ящик, пустое место). Движения робота моделируются как последовательность изменений координат, с учетом столкновений со стенами и необходимости толкать ящики.
В первой части задачи, с одинарными ящиками, рекурсивный шаг включает поиск первой свободной клетки в направлении движения робота и перемещение ящика, если он находится на пути. Оптимизация запроса достигается за счет материализации CTE
Вторая часть задачи усложняется из-за удвоенной ширины склада и ящиков. Теперь необходимо учитывать, что робот может толкать сразу несколько ящиков, соединенных в горизонтальную или вертикальную линию. Вертикальное движение требует рекурсивного поиска всех связанных ящиков, чтобы определить, возможно ли их перемещение без столкновений со стенами.
point для координат. Изображение носит иллюстративный характер
Основная идея решения заключается в рекурсивном моделировании шагов робота. Карта склада представлена в виде JSONB-словаря, где ключами являются координаты ячеек, а значениями — типы ячеек (стена, ящик, пустое место). Движения робота моделируются как последовательность изменений координат, с учетом столкновений со стенами и необходимости толкать ящики.
В первой части задачи, с одинарными ящиками, рекурсивный шаг включает поиск первой свободной клетки в направлении движения робота и перемещение ящика, если он находится на пути. Оптимизация запроса достигается за счет материализации CTE
arena и path, что позволяет избежать повторного вычисления регулярных выражений на каждом шаге рекурсии. Вторая часть задачи усложняется из-за удвоенной ширины склада и ящиков. Теперь необходимо учитывать, что робот может толкать сразу несколько ящиков, соединенных в горизонтальную или вертикальную линию. Вертикальное движение требует рекурсивного поиска всех связанных ящиков, чтобы определить, возможно ли их перемещение без столкновений со стенами.
