В этой челлендж-серии статей попробуем использовать PostgreSQL как среду для решения задач Advent of Code 2024.

Возможно, SQL не самый подходящий для этого язык, зато мы рассмотрим его различные возможности, о которых вы могли и не подозревать.

Многие слышали о классической игре сокобан, а кто-то наверняка играл в "Мудрого крота" из Роботландии. В этой части мы будем двигать ящики по складу, используя возможности json[b] и геометрического типа point.

Оригинальная постановка задачи и ее перевод:

Advent of Code 2024, Day 15: Warehouse Woes

--- День 15: Проблемы на складе ---

Вы снова оказываетесь внутри своей собственной мини-подводной лодки! Каждый Историк ведёт свою мини-подводную лодку в разном направлении; может быть, у Шефа тоже есть где-то здесь своя собственная подлодка?

Вы поднимаете глаза и видите, как мимо вас проплывает огромная стая рыб-фонарей. При более близком рассмотрении они кажутся довольно встревоженными, поэтому вы подъезжаете на своей мини-подводной лодке, чтобы посмотреть, сможете ли вы помочь.

Поскольку популяции рыб-фонарей быстро растут, им нужно много еды, и эту еду нужно где-то хранить. Вот почему эти рыбы-фонарики построили сложные складские комплексы, управляемые роботами!

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

Сейчас ни один из фонарных рыб не настолько смел, чтобы подплыть к непредсказуемому роботу, чтобы выключить его. Однако, если бы вы могли предвидеть движения робота, возможно, они смогли бы найти безопасный вариант.

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

Например:

##########
#..O..O.O#
#......O.#
#.OO..O.O#
#..O@..O.#
#O#..O...#
#O..O..O.#
#.OO.O.OO#
#....O...#
##########

<vv>^<v^>v>^vv^v>v<>v^v<v<^vv<<<^><<><>>v<vvv<>^v^>^<<<><<v<<<v^vv^v>^
vvv<<^>^v^^><<>>><>^<<><^vv^^<>vvv<>><^^v>^>vv<>v<<<<v<^v>^<^^>>>^<v<v
><>vv>v^v^<>><>>>><^^>vv>v<^^^>>v^v^<^^>v^^>v^<^v>v<>>v^v^<v>v^^<^^vv<
<<v<^>>^^^^>>>v^<>vvv^><v<<<>^^^vv^<vvv>^>v<^^^^v<>^>vvvv><>>v^<<^^^^^
^><^><>>><>^^<<^^v>>><^<v>^<vv>>v>>>^v><>^v><<<<v>>v<v<v>vvv>^<><<>^><
^>><>^v<><^vvv<^^<><v<<<<<><^v<<<><<<^^<v<^^^><^>>^<v^><<<^>>^v<v^v<v^
>^>>^v>vv>^<<^v<>><<><<v<<v><>v<^vv<<<>^^v^>^^>>><<^v>>v^v><^^>>^<>vv^
<><^^>^^^<><vvvvv^v<v<<>^v<v>v<<^><<><<><<<^^<<<^<<>><<><^^^>^^<>^>v<>
^^>vv<^v^v<vv>^<><v<^v>^^^>>>^^vvv^>vvv<>>>^<^>>>>>^<<^v>^vvv<>^<><<v>
v^^>>><<^^<>>^v^<v^vv<>v^<<>^<^v^v><^<<<><<^<v><v<>vv>>v><v^<vv<>v^<<^

Когда робот (@) пытается двигаться, если на пути есть какие-либо ящики (O), робот также попытается толкнуть эти ящики. Однако, если это действие заставит робота или ящик врезаться в стену (#), вместо этого ничего не сдвинется, включая робота. Их начальные положения показаны на карте в верхней части документа, который вам дал фонарик.

Остальная часть документа описывает движения (^вверх, vвниз, <влево, >вправо), которые робот попытается выполнить по порядку. (Движения образуют одну большую последовательность; они разбиты на несколько строк только для того, чтобы упростить копирование и вставку. Переходы на новую строку в последовательности движений следует игнорировать.)

Вот небольшой пример для начала:

########
#..O.O.#
##@.O..#
#...O..#
#.#.O..#
#...O..#
#......#
########

<^^>>>vv<v>>v<<

Если бы робот попытался выполнить заданную последовательность ходов, он бы передвигал коробки следующим образом:

Начальное состояние:
########
#..O.O.#
##@.O..#
#...O..#
#.#.O..#
#...O..#
#......#
########

Двигаемся влево <:
########
#..O.O.#
##@.O..#
#...O..#
#.#.O..#
#...O..#
#......#
########

Двигаемся вверх ^:
########
#.@O.O.#
##..O..#
#...O..#
#.#.O..#
#...O..#
#......#
########

Двигаемся вверх ^:
########
#.@O.O.#
##..O..#
#...O..#
#.#.O..#
#...O..#
#......#
########

Двигаемся вправо >:
########
#..@OO.#
##..O..#
#...O..#
#.#.O..#
#...O..#
#......#
########

Двигаемся вправо >:
########
#...@OO#
##..O..#
#...O..#
#.#.O..#
#...O..#
#......#
########

Двигаемся вправо >:
########
#...@OO#
##..O..#
#...O..#
#.#.O..#
#...O..#
#......#
########

Двигаемся вниз v:
########
#....OO#
##..@..#
#...O..#
#.#.O..#
#...O..#
#...O..#
########

Двигаемся вниз v:
########
#....OO#
##..@..#
#...O..#
#.#.O..#
#...O..#
#...O..#
########

Двигаемся влево <:
########
#....OO#
##.@...#
#...O..#
#.#.O..#
#...O..#
#...O..#
########

Двигаемся вниз v:
########
#....OO#
##.....#
#..@O..#
#.#.O..#
#...O..#
#...O..#
########

Двигаемся вправо >:
########
#....OO#
##.....#
#...@O.#
#.#.O..#
#...O..#
#...O..#
########

Двигаемся вправо >:
########
#....OO#
##.....#
#....@O#
#.#.O..#
#...O..#
#...O..#
########

Двигаемся вниз v:
########
#....OO#
##.....#
#.....O#
#.#.O@.#
#...O..#
#...O..#
########

Двигаемся влево <:
########
#....OO#
##.....#
#.....O#
#.#O@..#
#...O..#
#...O..#
########

Двигаемся влево <:
########
#....OO#
##.....#
#.....O#
#.#O@..#
#...O..#
#...O..#
########

В более крупном примере перемещений гораздо больше; после того, как робот завершит эти перемещения, склад будет выглядеть следующим образом:

##########
#.O.O.OOO#
#........#
#OO......#
#OO@.....#
#O#.....O#
#O.....OO#
#O.....OO#
#OO....OO#
##########

Фонарики используют собственную систему позиционирования товаров (GPS для краткости) для отслеживания местонахождения ящиков. Координата GPS ящика равна 100-кратному ее расстоянию от верхнего края карты плюс ее расстояние от левого края карты. (Этот процесс не останавливается на настенных плитках; измеряйте все расстояние до краев карты.)

Таким образом, показанный ниже прямоугольник находится на расстоянии 1от верхнего края карты и 4от левого края карты, что дает координату GPS 100 * 1 + 4 = 104.

#######
#...O..
#......

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

Предскажите движение робота и коробок на складе. После того, как робот закончит движение, какова сумма GPS-координат всех коробок?

--- Часть вторая ---

Рыбы-фонарики используют вашу информацию, чтобы найти безопасный момент, чтобы заплыть и выключить неисправного робота! Как раз когда они начинают готовить фестиваль в вашу честь, начинают поступать сообщения о том, что второй складской робот также неисправен.

Планировка этого склада на удивление похожа на ту, которой вы только что помогли. Есть одно ключевое отличие: все, кроме робота, в два раза шире! Список движений робота не меняется.

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

Если плитка — #, новая карта вместо этого содержит ##.
Если плитка — O, новая карта вместо этого содержит[].
Если плитка — ., новая карта вместо этого содержит...
Если плитка — @, новая карта вместо этого содержит @..

Это создает новую карту склада, которая будет в два раза шире и с широкими ящиками, которые обозначены как []. (Робот не меняет размер.)

Более крупный вариант из предыдущего примера теперь будет выглядеть так:

####################
##....[]....[]..[]##
##............[]..##
##..[][]....[]..[]##
##....[]@.....[]..##
##[]##....[]......##
##[]....[]....[]..##
##..[][]..[]..[][]##
##........[]......##
####################

Поскольку коробки теперь в два раза шире, но робот по-прежнему имеет тот же размер и скорость, коробки можно выровнять так, чтобы они напрямую толкали две другие коробки одновременно. Например, рассмотрим такую ситуацию:

#######
#...#.#
#.....#
#..OO@#
#..O..#
#.....#
#######

<vv<<^^<<^^

После соответствующего изменения размера этой карты робот будет перемещаться по этим полям следующим образом:

Начальное состояние:
##############
##......##..##
##..........##
##....[][]@.##
##....[]....##
##..........##
##############

Двигаемся влево <:
##############
##......##..##
##..........##
##...[][]@..##
##....[]....##
##..........##
##############

Двигаемся вниз v:
##############
##......##..##
##..........##
##...[][]...##
##....[].@..##
##..........##
##############

Двигаемся вниз v:
##############
##......##..##
##..........##
##...[][]...##
##....[]....##
##.......@..##
##############

Двигаемся влево <:
##############
##......##..##
##..........##
##...[][]...##
##....[]....##
##......@...##
##############

Двигаемся влево <:
##############
##......##..##
##..........##
##...[][]...##
##....[]....##
##.....@....##
##############

Двигаемся вверх ^:
##############
##......##..##
##...[][]...##
##....[]....##
##.....@....##
##..........##
##############

Двигаемся вверх ^:
##############
##......##..##
##...[][]...##
##....[]....##
##.....@....##
##..........##
##############

Двигаемся влево <:
##############
##......##..##
##...[][]...##
##....[]....##
##....@.....##
##..........##
##############

Двигаемся влево <:
##############
##......##..##
##...[][]...##
##....[]....##
##...@......##
##..........##
##############

Двигаемся вверх ^:
##############
##......##..##
##...[][]...##
##...@[]....##
##..........##
##..........##
##############

Двигаемся вверх ^:
##############
##...[].##..##
##...@.[]...##
##....[]....##
##..........##
##..........##
##############

Этот склад также использует GPS для определения местоположения коробок. Для этих более крупных коробок расстояния измеряются от края карты до ближайшего края рассматриваемой коробки. Таким образом, коробка, показанная ниже, имеет расстояние 1от верхнего края карты и 5от левого края карты, что приводит к координате GPS 100 * 1 + 5 = 105.

##########
##...[]...
##........

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

####################
##[].......[].[][]##
##[]...........[].##
##[]........[][][]##
##[]......[]....[]##
##..##......[]....##
##..[]............##
##..@......[].[][]##
##......[][]..[]..##
####################

Сумма GPS-координат этих ящиков составляет 9021.

Предскажите движение робота и коробок на этом новом, увеличенном складе. Какова сумма окончательных координат GPS всех коробок?

Часть 1

Поскольку от нас в задаче требуется пошаговое моделирование процесса, то запрос точно окажется рекурсивным.

Для начала, уже традиционно, с помощью регулярных выражений сформируем карту в виде jsonb-словаря и схему пути робота в виде списка точек с единичными координатами (тип point):

WITH RECURSIVE src AS (
  SELECT $$
########
#..O.O.#
##@.O..#
#...O..#
#.#.O..#
#...O..#
#......#
########

<^^>>>vv<v>>v<<
$$
)
, arena AS (
  SELECT
    (
      array_agg(point(x, y))
        FILTER(WHERE c = '@')
    )[1] bot -- позиция робота (единственная по условию)
  , jsonb_object(
      array_agg(point(x, y) ORDER BY x, y)
        FILTER(WHERE c NOT IN ('.', '@'))::text[] -- ключ - координаты ячейки
    , array_agg(c ORDER BY x, y)
        FILTER(WHERE c NOT IN ('.', '@'))         -- значение - тип ячейки
    ) map -- карта помещения со стенами и ящиками
  , sqrt(max(x * y))::integer sz -- линейный размер карты
  FROM
    regexp_matches(                          -- выделяем и нумеруем строки #...#
      (TABLE src)
    , '(?:^|[\r\n])(#[^\r\n]+#)(?:$|[\r\n])'
    , 'g'
    )
      WITH ORDINALITY y(line, y)
  , regexp_split_to_table(                   -- разбиваем каждую строку на символы
      line[1]
    , ''
    )
      WITH ORDINALITY x(c, x)
)
, path AS (
  SELECT
    i
  , CASE d[1]
      WHEN '<' THEN '(-1,0)'
      WHEN '>' THEN '(+1,0)'
      WHEN '^' THEN '(0,-1)'
      WHEN 'v' THEN '(0,+1)'
    END::point d -- перемещение робота на каждом шаге
  FROM
    regexp_matches(
      (TABLE src)
    , '[<>^v]'
    , 'g'
    )
      WITH ORDINALITY p(d, i)
)

Для для определения координаты робота при агрегации мы воспользовались конструкцией (array_agg(...))[1], и должны получить вот такой результат:

bot : point   | (3,3)
map : jsonb   | {
    "(1,1)": "#", "(1,2)": "#", "(1,3)": "#", "(1,4)": "#", "(1,5)": "#", "(1,6)": "#", "(1,7)": "#", "(1,8)": "#"
  , "(2,1)": "#", "(2,3)": "#", "(2,8)": "#"
  , "(3,1)": "#", "(3,5)": "#", "(3,8)": "#"
  , "(4,1)": "#", "(4,2)": "O", "(4,8)": "#"
  , "(5,1)": "#", "(5,3)": "O", "(5,4)": "O", "(5,5)": "O", "(5,6)": "O", "(5,8)": "#"
  , "(6,1)": "#", "(6,2)": "O", "(6,8)": "#"
  , "(7,1)": "#", "(7,8)": "#", "(8,1)": "#"
  , "(8,2)": "#", "(8,3)": "#", "(8,4)": "#", "(8,5)": "#", "(8,6)": "#", "(8,7)": "#", "(8,8)": "#"
  }
sz  : integer | 8

   i   |   d
bigint | point
     1 | (-1,0)
     2 | (0,-1)
     3 | (0,-1)
     4 | (1,0)
     5 | (1,0)
     6 | (1,0)
     7 | (0,1)
     8 | (0,1)
     9 | (-1,0)
    10 | (0,1)
    11 | (1,0)
    12 | (1,0)
    13 | (0,1)
    14 | (-1,0)
    15 | (-1,0)

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

Если это окажется стена, то ничего не меняется - ни состояние карты, ни позиция робота. Если же клетка будет свободна, то робот точно "шагнет", а на карте мы или должны "переставить" туда ящик, если он находится в будущей позиции робота, или ничего не менять, если перед роботом свободная клетка:

, r AS (
  SELECT
    0::bigint i        -- номер шага
  , bot                -- позиция робота
  , NULL::point dir    -- направление шага
  , map                -- состояние карты
  , NULL::text cell    -- клетка-без-ящика в направлении
  , NULL::boolean wall -- в направлении движения мешает стена
  , sz                 -- "протаскиваем" размер, чтобы не вычитывать каждый раз
  FROM
    arena
UNION ALL
  SELECT
    path.i
  , CASE
      WHEN T.wall THEN bot -- если двигаться мешает стена, оставляем робота на месте
      ELSE bot + d         -- иначе - смещаем в нужном направлении
    END
  , d
  , CASE -- меняем состояние карты, только когда перед роботом ящик, но стена не мешает
      WHEN T.wall THEN map
      WHEN map ->> (bot + d)::text = 'O' THEN
        map - (bot + d)::text || ('{"' || T.cell::text || '":"O"}')::jsonb
      ELSE map
    END
  , T.cell
  , T.wall
  , sz
  FROM
    r
  JOIN
    path
      ON path.i = r.i + 1
  LEFT JOIN
    LATERAL ( -- находим первую незанятую ящиком клетку в направлении движения
      SELECT
        cell
      , (map ->> cell) IS NOT DISTINCT FROM '#' wall
      FROM
        generate_series(1, sz) s
      , LATERAL (
          SELECT (bot + d * point(s, 0))::text cell -- умножение вектора
        ) c
      WHERE
        (map ->> cell) IS DISTINCT FROM 'O'
      LIMIT 1
    ) T
      ON TRUE
)

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

map                                            -- текущее состояние карты
  - (bot + d)::text                            -- освобождаем место для робота
                                               --  - удаляем ключ новой позиции
  || ('{"' || T.cell::text || '":"O"}')::jsonb -- ставим ящик в найденную позицию
                                                -- - добавляем json с ключом ее координат

По итогу рекурсии получим цепочку смен позиций робота и состояний карты:

   i   |  bot  |  dir   |  map  | cell  |  wall
bigint | point | point  | jsonb | text  | boolean
     0 | (3,3) |        | {...} |       |
     1 | (3,3) | (-1,0) | {...} | (2,3) | t
     2 | (3,2) | (0,-1) | {...} | (3,2) | f
     3 | (3,2) | (0,-1) | {...} | (3,1) | t
     4 | (4,2) | (1,0)  | {...} | (5,2) | f
     5 | (5,2) | (1,0)  | {...} | (7,2) | f
     6 | (5,2) | (1,0)  | {...} | (8,2) | t
     7 | (5,3) | (0,1)  | {...} | (5,7) | f
     8 | (5,3) | (0,1)  | {...} | (5,8) | t
     9 | (4,3) | (-1,0) | {...} | (4,3) | f
    10 | (4,4) | (0,1)  | {...} | (4,4) | f
    11 | (5,4) | (1,0)  | {...} | (6,4) | f
    12 | (6,4) | (1,0)  | {...} | (7,4) | f
    13 | (6,5) | (0,1)  | {...} | (6,5) | f
    14 | (5,5) | (-1,0) | {...} | (4,5) | f
    15 | (5,5) | (-1,0) | {...} | (3,5) | t

Остается только взять состояние json-карты с последнего шага и вычислить координаты всех ключей-клеток с роботами (O):

SELECT
  sum(cell[0] + 100 * cell[1])
FROM
  (
    SELECT
      key::point - point(1, 1) cell -- нормализуем координаты ячейки
    FROM
      jsonb_each((                  -- "разворачиваем" json-объект
        SELECT
          map
        FROM
          r
        ORDER BY
          i DESC
        LIMIT 1
      ))
    WHERE
      value = '"O"'                 -- отбираем только ключи с координатами ящиков
  ) T;

В таком виде вычисление занимает около 30 секунд, и основные затраты пришлись, внезапно, на множественное перевычисление regexp_matches для каждого из 20 тысяч шагов:

С таким поведением мы уже сталкивались в одном из прошлых решений и помним, что надо сделать - добавить MATERIALIZED к CTE arena и path:

WITH RECURSIVE src AS (
  SELECT $$
########
#..O.O.#
##@.O..#
#...O..#
#.#.O..#
#...O..#
#......#
########

<^^>>>vv<v>>v<<
$$
)
, arena AS MATERIALIZED (
  SELECT
    (
      array_agg(point(x, y))
        FILTER(WHERE c = '@')
    )[1] bot -- позиция робота (единственная по условию)
  , jsonb_object(
      array_agg(point(x, y) ORDER BY x, y)
        FILTER(WHERE c NOT IN ('.', '@'))::text[] -- ключ - координаты ячейки
    , array_agg(c ORDER BY x, y)
        FILTER(WHERE c NOT IN ('.', '@'))         -- значение - тип ячейки
    ) map -- карта помещения со стенами и ящиками
  , sqrt(max(x * y))::integer sz -- линейный размер карты
  FROM
    regexp_matches(                          -- выделяем и нумеруем строки #...#
      (TABLE src)
    , '(?:^|[\r\n])(#[^\r\n]+#)(?:$|[\r\n])'
    , 'g'
    )
      WITH ORDINALITY y(line, y)
  , regexp_split_to_table(                   -- разбиваем каждую строку на символы
      line[1]
    , ''
    )
      WITH ORDINALITY x(c, x)
)
, path AS MATERIALIZED (
  SELECT
    i
  , CASE d[1]
      WHEN '<' THEN '(-1,0)'
      WHEN '>' THEN '(+1,0)'
      WHEN '^' THEN '(0,-1)'
      WHEN 'v' THEN '(0,+1)'
    END::point d -- перемещение робота на каждом шаге
  FROM
    regexp_matches(
      (TABLE src)
    , '[<>^v]'
    , 'g'
    )
      WITH ORDINALITY p(d, i)
)
, r AS (
  SELECT
    0::bigint i        -- номер шага
  , bot                -- позиция робота
  , NULL::point dir    -- направление шага
  , map                -- состояние карты
  , NULL::text cell    -- клетка-без-ящика в направлении
  , NULL::boolean wall -- в направлении движения мешает стена
  , sz
  FROM
    arena
UNION ALL
  SELECT
    path.i
  , CASE
      WHEN T.wall THEN bot -- если двигаться мешает стена, оставляем робота на месте
      ELSE bot + d         -- иначе - смещаем в нужном направлении
    END
  , d
  , CASE -- меняем состояние карты, только когда перед роботом ящик, но стена не мешает
      WHEN T.wall THEN map
      WHEN map ->> (bot + d)::text = 'O' THEN
        map - (bot + d)::text || ('{"' || T.cell::text || '":"O"}')::jsonb
      ELSE map
    END
  , T.cell
  , T.wall
  , sz
  FROM
    r
  JOIN
    path
      ON path.i = r.i + 1
  LEFT JOIN
    LATERAL ( -- находим первую незанятую ящиком клетку в направлении движения
      SELECT
        cell
      , (map ->> cell) IS NOT DISTINCT FROM '#' wall
      FROM
        generate_series(1, sz) s
      , LATERAL (
          SELECT (bot + d * point(s, 0))::text cell -- умножение вектора
        ) c
      WHERE
        (map ->> cell) IS DISTINCT FROM 'O'
      LIMIT 1
    ) T
      ON TRUE
)
SELECT
  sum(cell[0] + 100 * cell[1])
FROM
  (
    SELECT
      key::point - point(1, 1) cell -- нормализуем координаты ячейки
    FROM
      jsonb_each((                  -- "разворачиваем" json-объект
        SELECT
          map
        FROM
          r
        ORDER BY
          i DESC
        LIMIT 1
      ))
    WHERE
      value = '"O"'                 -- отбираем только ключи с координатами ящиков
  ) T;

В таком виде вычисление занимает уже только 25 секунд.

Часть 2

Если таким непростым получилось решение для первой, более простой, части - что же нас ждет во второй?..

Во-первых, у нас теперь удвоилась ширина склада и объектов на нем, а робот остался прежним:

, arena AS MATERIALIZED (
  SELECT
    (
      array_agg(point(x, y))
        FILTER(WHERE c = '@')
    )[1] bot
  , jsonb_object(
      array_agg(point(x, y) ORDER BY x, y)
        FILTER(WHERE c NOT IN ('.', '@'))::text[]
    , array_agg(c ORDER BY x, y)
        FILTER(WHERE c NOT IN ('.', '@'))
    ) map
  , sqrt(max(x * y))::integer * 2 sz -- удвоим линейный размер
  FROM
    regexp_matches(
      regexp_replace(
        regexp_replace(
          regexp_replace(
            (TABLE src)
          , '([^\r\n])'
          , '\1\1' -- удвоим все символы
          , 'g')
        , '@@'     -- робота вернем к "одинарному" размеру
        , '@.'
        )
      , 'OO'       -- ящики преобразуем к "левой-правой" сторонам
      , '[]'
      , 'g'
      )
    , '(?:^|[\r\n])(#[^\r\n]+#)(?:$|[\r\n])'
    , 'g'
    )
      WITH ORDINALITY y(line, y)
  , regexp_split_to_table(
      line[1]
    , ''
    )
      WITH ORDINALITY x(c, x)
)

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

В-третьих, при движении по вертикали ящики могут "зацеплять соседей".

Решим задачу в два приема - сначала научимся "двигать" ящики, а потом уже определять, что и можно ли сдвинуть.

Основная канва рекурсии останется той же, только вместо одной ячейки будем "двигать" сразу наборы координат:

, r AS (
  SELECT
    0::bigint i
  , bot
  , map
  , sz
  , NULL::text[] blkold -- тут координаты клеток, где находятся двигаемые ящики
  , NULL::jsonb blknew  -- тут их состояние (координаты и содержимое) после сдвига
  , NULL::boolean wall
  FROM
    arena
UNION ALL
  SELECT
    path.i
  , CASE
      WHEN T.wall THEN bot
      ELSE bot + d
    END
  , CASE
      WHEN T.wall THEN map
      WHEN T.blkold IS NOT NULL THEN
        map - T.blkold || T.blknew -- новое состояние карты
      ELSE map
    END
  , sz
  , T.blkold
  , T.blknew
  , T.wall
  FROM
    r
  JOIN
    path
      ON path.i = r.i + 1
  LEFT JOIN
    LATERAL (
      -- ... magic!
    ) T
      ON TRUE
)

Для определения набора двигаемых ящиков разделим алгоритм на три кейса, которые заставим отрабатывать последовательно до первого выполнившегося условия с помощью такой конструкции:

(
  SELECT ... WHERE condA
)
UNION ALL
(
  SELECT ... WHERE condB
)
UNION ALL
(
  SELECT ... WHERE condC
)
LIMIT 1

В направлении движения робота находится не ящик

В этом случае карту никак менять не понадобится - робот или шагнет, или упрется в стену:

SELECT
  '{}'::text[] blkold
, '{}'::jsonb blknew
, map ->> (bot + d)::text = '#' wall                        -- ... зато может быть стена
WHERE
  coalesce((map ->> (bot + d)::text), '') NOT IN ('[', ']') -- в направлении шага нет ящика ...

Горизонтальное движение

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

WITH h AS (
  SELECT
    cell
  , map ->> cell = '#' wall
  FROM
    generate_series(1, sz) s
  , LATERAL (
      SELECT (bot + d * point(s, 0))::text cell
    ) c
  WHERE
    coalesce(map ->> cell, '') NOT IN ('[', ']')
  LIMIT 1
)
SELECT
  *
FROM
  (
    SELECT
      array_agg(cellold)::text[] blkold -- старые координаты
    , jsonb_object(
        array_agg(cellnew)::text[]
      , array_agg(map ->> cellold::text)::text[]
      ) blknew                          -- новые состояния
    , (SELECT wall FROM h) wall         -- признак наличия стены на новых координатах
    FROM
      h
    , generate_series(
        (bot[0] + d[0])::integer
      , (cell::point)[0]::integer - d[0]::integer
      , d[0]::integer
      ) x                                      -- сегмент x-координат от робота до ячейки
    , point(x, bot[1]) cellold                 -- старые координаты
    , point(x + d[0]::integer, bot[1]) cellnew -- новые координаты
  ) T
WHERE
  d[1] = 0 -- условие горизонтального движения

Вертикальное движение

Это самая сложная часть - тут нам необходимо пустить рекурсивную "волну", как мы это делали в задаче про огораживание растений, чтобы найти весь сегмент "цепляющихся" ящиков, а потом проверить, не "наедет" ли какой-то из них на стену:

WITH RECURSIVE w AS ( -- рекурсивная "волна"
  SELECT
    0 n
  , ARRAY[bot + d] || (            -- клетка прямо перед роботом
      bot + d +
      CASE map ->> (bot + d)::text -- и "парная" ей сторона ящика
        WHEN '[' THEN '(+1,0)'
        WHEN ']' THEN '(-1,0)'
      END::point
    ) wave
UNION ALL
  SELECT
    n + 1
  , wave || front || frontpair -- присоединяем к "волне" прямо зацепившиеся и парные стороны ящиков
  FROM
    w
  , LATERAL (
      SELECT
        array_agg(cellnew) front
      , array_agg(cellpair) frontpair
      FROM
        unnest(wave) cellold
      , point(cellold[0], cellold[1] + d[1]) cellnew
      , LATERAL (
          SELECT
            cellnew + CASE map ->> cellnew::text
              WHEN '[' THEN '(+1,0)'
              WHEN ']' THEN '(-1,0)'
            END::point cellpair
        ) c0
      WHERE
        cellnew::text <> ALL(wave::text[]) AND
        map ->> cellnew::text IN ('[', ']')
    ) T
  WHERE
    front IS NOT NULL -- продалжаем, пока есть что зацеплять
)
SELECT
  wave::text[] blkold
, blknew
, wall
FROM
  ( -- волна на последнем шаге
    SELECT
      wave
    FROM
      w
    ORDER BY
      n DESC
    LIMIT 1
  ) w
, LATERAL ( -- "пересобираем" координаты
    SELECT
      jsonb_object(
        array_agg(cellnew)::text[]
      , array_agg(map ->> cellold::text)::text[]
      ) blknew
    , bool_or(map ->> cellnew::text = '#') wall -- хоть где-то в новых координатах есть стена
    FROM
      unnest(wave) cellold
    , point(cellold[0], cellold[1] + d[1]::integer) cellnew
  ) T
WHERE
  d[0] = 0 -- -- условие вертикального движения

Соберем весь запрос вместе:

WITH RECURSIVE src AS (
  SELECT $$
##########
#..O..O.O#
#......O.#
#.OO..O.O#
#..O@..O.#
#O#..O...#
#O..O..O.#
#.OO.O.OO#
#....O...#
##########

<vv>^<v^>v>^vv^v>v<>v^v<v<^vv<<<^><<><>>v<vvv<>^v^>^<<<><<v<<<v^vv^v>^
vvv<<^>^v^^><<>>><>^<<><^vv^^<>vvv<>><^^v>^>vv<>v<<<<v<^v>^<^^>>>^<v<v
><>vv>v^v^<>><>>>><^^>vv>v<^^^>>v^v^<^^>v^^>v^<^v>v<>>v^v^<v>v^^<^^vv<
<<v<^>>^^^^>>>v^<>vvv^><v<<<>^^^vv^<vvv>^>v<^^^^v<>^>vvvv><>>v^<<^^^^^
^><^><>>><>^^<<^^v>>><^<v>^<vv>>v>>>^v><>^v><<<<v>>v<v<v>vvv>^<><<>^><
^>><>^v<><^vvv<^^<><v<<<<<><^v<<<><<<^^<v<^^^><^>>^<v^><<<^>>^v<v^v<v^
>^>>^v>vv>^<<^v<>><<><<v<<v><>v<^vv<<<>^^v^>^^>>><<^v>>v^v><^^>>^<>vv^
<><^^>^^^<><vvvvv^v<v<<>^v<v>v<<^><<><<><<<^^<<<^<<>><<><^^^>^^<>^>v<>
^^>vv<^v^v<vv>^<><v<^v>^^^>>>^^vvv^>vvv<>>>^<^>>>>>^<<^v>^vvv<>^<><<v>
v^^>>><<^^<>>^v^<v^vv<>v^<<>^<^v^v><^<<<><<^<v><v<>vv>>v><v^<vv<>v^<<^
$$
)
, arena AS MATERIALIZED (
  SELECT
    (
      array_agg(point(x, y))
        FILTER(WHERE c = '@')
    )[1] bot
  , jsonb_object(
      array_agg(point(x, y) ORDER BY x, y)
        FILTER(WHERE c NOT IN ('.', '@'))::text[]
    , array_agg(c ORDER BY x, y)
        FILTER(WHERE c NOT IN ('.', '@'))
    ) map
  , sqrt(max(x * y))::integer * 2 sz -- удвоим размер
  FROM
    regexp_matches(
      regexp_replace(
        regexp_replace(
          regexp_replace(
            (TABLE src)
          , '([^\r\n])'
          , '\1\1' -- удвоим все символы
          , 'g')
        , '@@'     -- робота вернем к "одинарному" размеру
        , '@.'
        )
      , 'OO'       -- ящики преобразуем к "левой-правой" сторонам
      , '[]'
      , 'g'
      )
    , '(?:^|[\r\n])(#[^\r\n]+#)(?:$|[\r\n])'
    , 'g'
    )
      WITH ORDINALITY y(line, y)
  , regexp_split_to_table(
      line[1]
    , ''
    )
      WITH ORDINALITY x(c, x)
)
, path AS MATERIALIZED (
  SELECT
    i
  , CASE d[1]
      WHEN '<' THEN '(-1,0)'
      WHEN '>' THEN '(+1,0)'
      WHEN '^' THEN '(0,-1)'
      WHEN 'v' THEN '(0,+1)'
    END::point d
  FROM
    regexp_matches(
      (TABLE src)
    , '[<>^v]'
    , 'g'
    )
      WITH ORDINALITY p(d, i)
)
, r AS (
  SELECT
    0::bigint i
  , bot
  , map
  , sz
  , NULL::text[] blkold -- тут координаты клеток, где находятся двигаемые ящики
  , NULL::jsonb blknew  -- тут их состояние (координаты и содержимое) после сдвига
  , NULL::boolean wall
  FROM
    arena
UNION ALL
  SELECT
    path.i
  , CASE
      WHEN T.wall THEN bot
      ELSE bot + d
    END
  , CASE
      WHEN T.wall THEN map
      WHEN T.blkold IS NOT NULL THEN
        map - T.blkold || T.blknew -- новое состояние карты
      ELSE map
    END
  , sz
  , T.blkold
  , T.blknew
  , T.wall
  FROM
    r
  JOIN
    path
      ON path.i = r.i + 1
  LEFT JOIN
    LATERAL (
      ( -- перед роботом не ящик
        SELECT
          '{}'::text[] blkold
        , '{}'::jsonb blknew
        , map ->> (bot + d)::text = '#' wall                        -- ... зато может быть стена
        WHERE
          coalesce((map ->> (bot + d)::text), '') NOT IN ('[', ']') -- в направлении шага нет ящика ...
      )
      UNION ALL
      ( -- движение по горизонтали
        WITH h AS (
          SELECT
            cell
          , map ->> cell = '#' wall
          FROM
            generate_series(1, sz) s
          , LATERAL (
              SELECT
                (bot + d * point(s, 0))::text cell
            ) c
          WHERE
            coalesce(map ->> cell, '') NOT IN ('[', ']')
          LIMIT 1
        )
        SELECT
          *
        FROM
          (
            SELECT
              array_agg(cellold)::text[] blkold -- старые координаты
            , jsonb_object(
                array_agg(cellnew)::text[]
              , array_agg(map ->> cellold::text)::text[]
              ) blknew                          -- новые состояния
            , (SELECT wall FROM h) wall         -- признак наличия стены на новых координатах
            FROM
              h
            , generate_series(
                (bot[0] + d[0])::integer
              , (cell::point)[0]::integer - d[0]::integer
              , d[0]::integer
              ) x                                      -- сегмент x-координат от робота до ячейки
            , point(x, bot[1]) cellold                 -- старые координаты
            , point(x + d[0]::integer, bot[1]) cellnew -- новые координаты
          ) T
        WHERE
          d[1] = 0 -- условие горизонтального движения
      )
      UNION ALL
      ( -- движение по вертикали
        WITH RECURSIVE w AS (
          SELECT
            0 n
          , ARRAY[bot + d] || (            -- клетка прямо перед роботом
              bot + d +
              CASE map ->> (bot + d)::text -- и "парная" ей сторона ящика
                WHEN '[' THEN '(+1,0)'
                WHEN ']' THEN '(-1,0)'
              END::point
          ) wave
        UNION ALL
          SELECT
            n + 1
          , wave || front || frontpair -- присоединяем к "волне" прямо зацепившиеся и парные стороны ящиков
          FROM
            w
          , LATERAL (
              SELECT
                array_agg(cellnew) front
              , array_agg(cellpair) frontpair
              FROM
                unnest(wave) cellold
              , point(cellold[0], cellold[1] + d[1]) cellnew
              , LATERAL (
                  SELECT
                    cellnew + CASE map ->> cellnew::text
                      WHEN '[' THEN '(+1,0)'
                      WHEN ']' THEN '(-1,0)'
                    END::point cellpair
                ) c0
              WHERE
                cellnew::text <> ALL(wave::text[]) AND
                map ->> cellnew::text IN ('[', ']')
            ) T
          WHERE
            front IS NOT NULL -- продалжаем, пока есть что зацеплять
        )
        SELECT
          wave::text[] blkold
        , blknew
        , wall
        FROM
          ( -- волна на последнем шаге
            SELECT
              wave
            FROM
              w
            ORDER BY
              n DESC
            LIMIT 1
          ) w
        , LATERAL ( -- "пересобираем" координаты
            SELECT
              jsonb_object(
                array_agg(cellnew)::text[]
              , array_agg(map ->> cellold::text)::text[]
              ) blknew
            , bool_or(map ->> cellnew::text = '#') wall -- хоть где-то в новых координатах есть стена
            FROM
              unnest(wave) cellold
            , point(cellold[0], cellold[1] + d[1]::integer) cellnew
          ) T
        WHERE
          d[0] = 0 -- -- условие вертикального движения
      )
      LIMIT 1
    ) T
      ON TRUE
)
SELECT
  sum(cell[0] + 100 * cell[1])
FROM
  (
    SELECT
      key::point - point(1, 1) cell
    FROM
      jsonb_each((
        SELECT
          map
        FROM
          r
        ORDER BY
          i DESC
        LIMIT 1
      ))
    WHERE
      value = '"["'
  ) T;

Несмотря на существенно возросшую сложность запроса, на решение уходит лишь чуть больше времени - 27 секунд:

SQL HowTo: играем в сокобан с помощью json-карты и типа point (Advent of Code 2024, Day 15: Warehouse Woes)