Ssylka

Сокобан в PostgreSQL: JSON и Point для складских задач

Решение задач Advent of Code 2024 с использованием PostgreSQL демонстрирует мощь SQL, выходящую за рамки стандартных представлений. Для моделирования игры «Сокобан» (перемещение ящиков по складу) использованы возможности JSON для представления карты склада и тип point для координат.
Сокобан в PostgreSQL: JSON и Point для складских задач
Изображение носит иллюстративный характер

Основная идея решения заключается в рекурсивном моделировании шагов робота. Карта склада представлена в виде JSONB-словаря, где ключами являются координаты ячеек, а значениями — типы ячеек (стена, ящик, пустое место). Движения робота моделируются как последовательность изменений координат, с учетом столкновений со стенами и необходимости толкать ящики.

В первой части задачи, с одинарными ящиками, рекурсивный шаг включает поиск первой свободной клетки в направлении движения робота и перемещение ящика, если он находится на пути. Оптимизация запроса достигается за счет материализации CTE arena и path, что позволяет избежать повторного вычисления регулярных выражений на каждом шаге рекурсии.

Вторая часть задачи усложняется из-за удвоенной ширины склада и ящиков. Теперь необходимо учитывать, что робот может толкать сразу несколько ящиков, соединенных в горизонтальную или вертикальную линию. Вертикальное движение требует рекурсивного поиска всех связанных ящиков, чтобы определить, возможно ли их перемещение без столкновений со стенами.


Новое на сайте

18247Зачем мозг в фазе быстрого сна стирает детали воспоминаний? 18246Мог ли древний яд стать решающим фактором в эволюции человека? 18245Тайна колодца Мурсы: раны и днк раскрыли судьбу павших солдат 18244Битва за миллиардный сэндвич без корочки 18243Почему ваши расширения для VS Code могут оказаться шпионским по? 18242Как подать заявку FAFSA на 2026-27 учебный год и получить финансовую помощь? 18241Мог ли взлом F5 раскрыть уязвимости нулевого дня в продукте BIG-IP? 18240CVS завершает поглощение активов обанкротившейся сети Rite Aid 18239Nvidia, BlackRock и Microsoft покупают основу для глобального ИИ за $40 миллиардов 18238Действительно ли только род Homo создавал орудия труда? 18237Инженерный триумф: сотрудник Rivian вырастил тыкву-победителя 18236Процент с прибыли: как инвесторы создали новый источник финансирования для... 18235Почему синхронизируемые ключи доступа открывают двери для кибератак на предприятия?