SQL HowTo: укрощаем рекурсию в лабиринте (Advent of Code 2024, Day 16: Reindeer Maze)

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

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

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

• Решение Day 1: Historian Hysteria (регулярные выражения и условная агрегация)

• Решение Day 2: Red-Nosed Reports (логические агрегаты)

• Решение Day 3: Mull It Over («чистые» регулярки)

• Решение Day 4: Ceres Search (работа с массивами)

• Решение Day 5: Print Queue (поиск в словаре и массивах, сортировка «пузырьком»)

• Решение Day 6: Guard Gallivant (рекурсивные циклы и их контроль)

• Решение Day 7: Bridge Repair («экспоненциальная» рекурсия)

• Решение Day 8: Resonant Collinearity (генерация и подсчет уникальных комбинаций)

• Решение Day 9: Disk Fragmenter (оптимизируем рекурсию)

• Решение Day 10: Hoof It (поиск «в ширину» внутри цикла)

• Решение Day 11: Plutonian Pebbles (агрегация внутри рекурсии)

• Решение Day 12: Garden Groups (волновой алгоритм и подсчет границ)

• Решение Day 13: Claw Contraption (пошагово решаем СЛУ)

• Решение Day 14: Restroom Redoubt (находим «елочку» с помощью центра масс)

• Решение Day 15: Warehouse Woes (играем в сокобан с помощью json-карты и типа point)

• Решение Day 16: Reindeer Maze (укрощаем рекурсию в лабиринте)

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

############### #.......#....E# #.#.###.#.###.# #.....#.#...#.# #.###.#####.#.# #.#.#.......#.# #.#.#####.###.# #...........#.# ###.#.#####.#.# #...#.....#.#.# #.#.#.###.#.#.# #.....#...#.#.# #.###.#.#.#.#.# #S..#.....#...# ###############

 ############### #.......#....E# #.#.###.#.###^# #.....#.#...#^# #.###.#####.#^# #.#.#.......#^# #.#.#####.###^# #..>>>>>>>>v#^# ###^#.#####v#^# #>>^#.....#v#^# #^#.#.###.#v#^# #^....#...#v#^# #^###.#.#.#v#^# #S..#.....#>>^# ###############

################# #...#...#...#..E# #.#.#.#.#.#.#.#.# #.#.#.#...#...#.# #.#.#.#.###.#.#.# #...#.#.#.....#.# #.#.#.#.#.#####.# #.#...#.#.#.....# #.#.#####.#.###.# #.#.#.......#...# #.#.###.#####.### #.#.#...#.....#.# #.#.#.#####.###.# #.#.#.........#.# #.#.#.#########.# #S#.............# #################

################# #...#...#...#..E# #.#.#.#.#.#.#.#^# #.#.#.#...#...#^# #.#.#.#.###.#.#^# #>>v#.#.#.....#^# #^#v#.#.#.#####^# #^#v..#.#.#>>>>^# #^#v#####.#^###.# #^#v#..>>>>^#...# #^#v###^#####.### #^#v#>>^#.....#.# #^#v#^#####.###.# #^#v#^........#.# #^#v#^#########.# #S#>>^..........# #################

############### #.......#....O# #.#.###.#.###O# #.....#.#...#O# #.###.#####.#O# #.#.#.......#O# #.#.#####.###O# #..OOOOOOOOO#O# ###O#O#####O#O# #OOO#O....#O#O# #O#O#O###.#O#O# #OOOOO#...#O#O# #O###.#.#.#O#O# #O..#.....#OOO# ###############

################# #...#...#...#..O# #.#.#.#.#.#.#.#O# #.#.#.#...#...#O# #.#.#.#.###.#.#O# #OOO#.#.#.....#O# #O#O#.#.#.#####O# #O#O..#.#.#OOOOO# #O#O#####.#O###O# #O#O#..OOOOO#OOO# #O#O###O#####O### #O#O#OOO#..OOO#.# #O#O#O#####O###.# #O#O#OOOOOOO..#.# #O#O#O#########.# #O#OOO..........# #################

Часть 1

Давайте начнем решение с очевидной части — уже привычного по предыдущим задачам серии преобразования входных данных в матрицу:

WITH RECURSIVE matrix AS MATERIALIZED (   SELECT     array_agg(regexp_split_to_array(line[1], '')) m   FROM     regexp_matches(       $$ ############### #.......#....E# #.#.###.#.###.# #.....#.#...#.# #.###.#####.#.# #.#.#.......#.# #.#.#####.###.# #...........#.# ###.#.#####.#.# #...#.....#.#.# #.#.#.###.#.#.# #.....#...#.#.# #.###.#.#.#.#.# #S..#.....#...# ############### $$     , '(?:^|[\r\n])(#[^\r\n]*#)(?=$|[\r\n])'     , 'g'     )       WITH ORDINALITY y(line, y) )

Попробуем решить задачу нахождения минимального по стоимости пути наиболее простым и очевидным способом — прямым моделированием всех возможных путей. Для этого воспользуемся уже знакомым нам типом point и возможностью легко реализовать умножение векторов. — из каждой текущей точки будем пытаться «шагнуть» налево от текущего направления движения, направо или продолжим идти прямо:

, r AS (   SELECT     x   , y   , '(1,0)'::point d -- вначале олень стоит "на восток", то есть вправо   , 0 score   FROM     matrix   , generate_subscripts(m, 1) y   , generate_subscripts(m, 2) x   WHERE     m[y][x] = 'S'    -- находим стартовую клетку UNION ALL   SELECT     T.*   FROM     r   , matrix   , LATERAL (       SELECT         pn[0]::integer x       , pn[1]::integer y       , dn d       , r.score + 1 + 1000 * (v[1] <> 0)::integer -- при повороте - +1000       FROM         point(x, y) p       , LATERAL ( -- "шагаем" в трех направлениях сразу           SELECT             v            -- вектор изменения направления           , d * v dn     -- новое направление           , p + d * v pn -- новая позиция           FROM             unnest(ARRAY[               '(0, -1)' -- поворот налево             , '(+1, 0)' -- движение прямо - сохранение текущего направления             , '(0, +1)' -- поворот направо             ]::point[]) v         ) v       WHERE         m[pn[1]::integer][pn[0]::integer] <> '#' -- в новой позиции не должно быть стены     ) T   WHERE     m[r.y][r.x] <> 'E' ) CYCLE x, y SET is_cycle USING path -- блокируем зачикливание

… и найдем среди всех приводящих в конечную точку минимальную стоимость:

SELECT   min(score) FROM   r , matrix WHERE   m[y][x] = 'E';

В принципе, это вполне нормальное решение для небольших лабиринтов, а вот для больших… В общем, даже за час оно не досчитывается.

Оптимизируем перебор узлов

У алгоритма выше ровно три проблемы:

• в каждой точке ветвления, откуда можно пойти дальше несколькими способами, количество путей умножается на 2 или 3 — то есть возрастает экспоненциально

• в рамках защиты от зацикливания CYCLE ... USING path в этом столбце PostgreSQL записывает все-все клетки, которые мы прошли, даже если они находились «в тоннеле», и никакого ветвления там быть не могло

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

Во-первых, заметим, что при таких величинах (1 за шаг «прямо» и 1000 за поворот) мы можем свести задачу к «за какое минимальное количество поворотов» можно достигнуть конечной точки.

Во-вторых, повороты могут происходить только в клетках, на принадлежащих «тоннелям», отметим на схеме их X:

############### #X.X...X#X...X# #.#.###.#.###.# #X.X.X#.#X.X#.# #.###.#####.#.# #.#.#X...X.X#.# #.#.#####.###.# #X.X.X...X.X#.# ###.#.#####.#.# #X.X#X...X#.#.# #.#.#.###.#.#.# #X.X.X#X.X#.#.# #.###.#.#.#.#.# #X..#X.X.X#X.X# ###############

Как можно заметить, таких точек существенно меньше всех доступных для прохода.

Давайте отберем сначала начальную и конечную точки, даже если в них нет разветвлений, все стены, и проходы вне «тоннеля» (то есть есть свободная клетка и слева или справа, и сверху или снизу).

Отбросим все «стеновые» клетки, сосчитав их количество слева и сверху до каждой интересующей нас проходимой клетки:

, poi AS MATERIALIZED (   SELECT     x   , y   , grpx   , grpy   FROM     (       SELECT         *       , sum(wall::integer) OVER(PARTITION BY x ORDER BY y) grpx -- группа по X       , sum(wall::integer) OVER(PARTITION BY y ORDER BY x) grpy -- группа по Y       FROM         (           SELECT             x           , y           , m[y][x] = '#' wall           FROM             matrix           , generate_subscripts(m, 1) y           , generate_subscripts(m, 2) x           WHERE             m[y][x] IN ('S', 'E', '#') OR -- отбираем старт, финиш и все стены             (               m[y][x] = '.' AND -- проходные клетки отбираем только вне тоннеля               (m[y][x - 1] <> '#' OR m[y][x + 1] <> '#') AND               (m[y - 1][x] <> '#' OR m[y + 1][x] <> '#')             )         ) T     ) T   WHERE     NOT wall -- стены нам не нужны )

группы по X     | группы по Y ###############   ############### #1.1...1#2...2#   #1.1...1#1...1# #.#.###.#.###.#   #.#.###.#.###.# #1.1.1#.#3.3#.#   #1.1.2#.#1.2#.# #.###.#####.#.#   #.###.#####.#.# #.#.#3...3.3#.#   #.#.#2...2.2#.# #.#.#####.###.#   #.#.#####.###.# #1.1.1...1.1#.#   #1.2.3...2.3#.# ###.#.#####.#.#   ###.#.#####.#.# #1.1#2...2#.#.#   #2.2#3...3#.#.# #.#.#.###.#.#.#   #.#.#.###.#.#.# #1.1.1#2.2#.#.#   #2.2.3#5.3#.#.# #.###.#.#.#.#.#   #.###.#.#.#.#.# #1..#2.2.2#2.2#   #2..#3.5.3#3.1# ###############   ###############

Заметим, что принадлежность к одной группе означает возможность «добежать» от одной клетки до другой из этой же группы по прямой, без поворотов.

Соберем для каждой клетки массивы координат клеток, куда из нее можно попасть по той же горизонтальной/вертикальной линии, не пересекая стен (исключив ее саму функцией array_remove, конечно):

, stepline AS MATERIALIZED (   SELECT     x sx   , y sy   , array_remove(array_agg(x) OVER(PARTITION BY y, grpy), x) _tx   , array_remove(array_agg(y) OVER(PARTITION BY x, grpx), y) _ty   FROM     poi )

sx | sy | _tx         | _ty  2 |  2 | {4,8}       | {8,4}  2 |  4 | {4,6}       | {2,8}  2 |  8 | {12,4,6,10} | {2,4}  2 | 10 | {4}         | {12,14}  2 | 12 | {6,4}       | {10,14}  2 | 14 | {}          | {10,12}     -- отсюда некуда ходить по горизонтали  4 |  2 | {2,8}       | {4}  4 |  4 | {2,6}       | {2}  4 |  8 | {12,2,6,10} | {12,10}  4 | 10 | {2}         | {12,8}  4 | 12 | {6,2}       | {8,10}  6 |  4 | {4,2}       | {6}  6 |  6 | {10,12}     | {4}  6 |  8 | {12,4,2,10} | {12,14,10}  6 | 10 | {10}        | {12,14,8}  6 | 12 | {2,4}       | {14,8,10}  6 | 14 | {10,8}      | {12,8,10}  8 |  2 | {2,4}       | {}          -- а отсюда - по вертикали  8 | 12 | {10}        | {14}  8 | 14 | {10,6}      | {12} 10 |  2 | {14}        | {4} 10 |  4 | {12}        | {2} 10 |  6 | {12,6}      | {8} 10 |  8 | {12,4,2,6}  | {6} 10 | 10 | {6}         | {14,12} 10 | 12 | {8}         | {14,10} 10 | 14 | {6,8}       | {10,12} 12 |  4 | {10}        | {6} 12 |  6 | {10,6}      | {4} 12 |  8 | {4,2,6,10}  | {14} 12 | 14 | {14}        | {8} 14 |  2 | {10}        | {14} 14 | 14 | {12}        | {2}

Сформируем теперь все возможные прямые отрезки пути, вычислим их «стоимость» и результирующее направление движения от точки к точке (чтобы в дальнейшем было удобнее работать с ними, превратим координаты клеток в text):

, segline AS MATERIALIZED (   SELECT     point(sx, sy)::text s        -- текстовое представление координат ячеек   , point(tx, ty)::text t   , CASE                         -- направление движения       WHEN tx > sx THEN '(1,0)'  -- вправо       WHEN tx < sx THEN '(-1,0)' -- влево       WHEN ty > sy THEN '(0,1)'  -- вниз       WHEN ty < sy THEN '(0,-1)' -- вверх     END d   , abs(tx - sx) + abs(ty - sy) score -- "стоимость" сегмента - разность координат   FROM     (       SELECT         sx       , sy       , unnest(_tx) tx -- возможные шаги по горизонтали       , sy ty       FROM         stepline     UNION ALL       SELECT         sx       , sy       , sx sy       , unnest(_ty) ty -- возможные шаги по вертикали       FROM         stepline     ) T )

Для наших путей важно не только «где» мы стоим, но и «как» — то есть в какую сторону смотрим. Давайте соберем все возможные пары состояний, которые могут быть достигнуты «за одно действие» — либо поворот «за 1000», либо перемещение по прямой к какой-то из соседних узловых клеток:

, dir AS MATERIALIZED (   SELECT     unnest(ARRAY[ -- направления "смотрения"       '(1,0)'  -- вправо     , '(0,1)'  -- вниз     , '(-1,0)' -- влево     , '(0,-1)' -- вверх     ]::point[]) d ) , onestep AS MATERIALIZED (   SELECT     point(x, y)::text s   , ds.d::text ds   , point(x, y)::text t   , dt.d::text dt   , 1000 score -- поворот на месте "за 1000"   FROM     poi   , dir ds   , dir dt   WHERE     dt.d[0] <> ds.d[0] AND -- это поворот, не разворот на 180     dt.d[1] <> ds.d[1] UNION ALL   SELECT     s   , d ds   , t   , d dt   , score     -- шаг по прямой к соседнему узлу   FROM     segline )

Чтобы не обращаться каждый раз к матрице, вычислим заранее за один проход позиции начальной и конечной клеток, воспользовавшись min(...) FILTER(...) для определения каждой из координат:

, init AS MATERIALIZED (   SELECT     point(       min(x) FILTER(WHERE m[y][x] = 'S')     , min(y) FILTER(WHERE m[y][x] = 'S')     )::text s -- координаты стартовой клетки   , point(       min(x) FILTER(WHERE m[y][x] = 'E')     , min(y) FILTER(WHERE m[y][x] = 'E')     )::text e -- координаты конечной клетки   FROM     matrix   , generate_subscripts(m, 1) y   , generate_subscripts(m, 2) x   WHERE     m[y][x] IN ('S', 'E') )

Теперь у нас все готово к формированию рекурсивного шага:

1. Если на предыдущем шаге мы не шли прямо, а поворачивались, то второй раз делать это снова не имеет смысла — запомним признак поворота в столбце turn.

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

3. После вычисления всех новых путей с помощью bool_or(p = e) OVER() проставляем сразу на всех записях шага признак финальности.

, r AS (   SELECT     e                         -- протаскиваем целевую точку сквозь все шаги   , s p                       -- текущая точка - стартовая   , '(1,0)' d                 -- исходно смотрим направо   , 0::bigint score           -- накопленная стоимость пути   , FALSE turn                -- признак поворота на предыдущем шаге   , ARRAY[s || ':(1,0)'] path -- уже достигнутый путь   , FALSE fin                 -- признак достижения конечной точки на данном шаге   FROM     init UNION ALL   (     WITH tmp AS (       SELECT DISTINCT ON (state) -- уникализируем пути по достигнутому состоянию         e       , os.t p                   -- новая достигнутая точка       , os.dt d                  -- новое направление       , r.score + os.score score -- "стоимость" уже пройденного пути       , os.t = os.s turn         -- признак поворота       , r.path || state path       FROM         r       JOIN         onestep os           ON (os.s, os.ds) = (r.p, r.d)       , LATERAL (           SELECT os.t || ':' || os.dt state -- состояние - это "куда пришли" + "куда смотрим"         ) T       WHERE         p <> e AND             -- пока не пришли куда надо         state <> ALL(path) AND -- исключаем зацикливание пути         ( -- если на предыдущем шаге поворачивались, то на этом надо "шагать"           NOT turn OR           os.t <> os.s         ) AND         NOT fin                -- выход из рекурсии - достижение конечной точки       ORDER BY         state, r.score + os.score     )     SELECT       *     , bool_or(p = e) OVER() fin -- признак достижения конечной точки     FROM       tmp   ) )

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

WITH RECURSIVE matrix AS MATERIALIZED (   SELECT     array_agg(regexp_split_to_array(line[1], '')) m   FROM     regexp_matches(       $$ ############### #.......#....E# #.#.###.#.###.# #.....#.#...#.# #.###.#####.#.# #.#.#.......#.# #.#.#####.###.# #...........#.# ###.#.#####.#.# #...#.....#.#.# #.#.#.###.#.#.# #.....#...#.#.# #.###.#.#.#.#.# #S..#.....#...# ############### $$     , '(?:^|[\r\n])(#[^\r\n]*#)(?=$|[\r\n])'     , 'g'     )       WITH ORDINALITY y(line, y) ) , poi AS MATERIALIZED (   SELECT     x   , y   , grpx   , grpy   FROM     (       SELECT         *       , sum(wall::integer) OVER(PARTITION BY x ORDER BY y) grpx -- группа по X       , sum(wall::integer) OVER(PARTITION BY y ORDER BY x) grpy -- группа по Y       FROM         (           SELECT             x           , y           , m[y][x] = '#' wall           FROM             matrix           , generate_subscripts(m, 1) y           , generate_subscripts(m, 2) x           WHERE             m[y][x] IN ('S', 'E', '#') OR -- отбираем старт, финиш и все стены             (               m[y][x] = '.' AND -- проходные клетки отбираем только вне тоннеля               (m[y][x - 1] <> '#' OR m[y][x + 1] <> '#') AND               (m[y - 1][x] <> '#' OR m[y + 1][x] <> '#')             )         ) T     ) T   WHERE     NOT wall -- стены нам не нужны ) , stepline AS MATERIALIZED (   SELECT     x sx   , y sy   , array_remove(array_agg(x) OVER(PARTITION BY y, grpy), x) _tx   , array_remove(array_agg(y) OVER(PARTITION BY x, grpx), y) _ty   FROM     poi ) , segline AS MATERIALIZED (   SELECT     point(sx, sy)::text s        -- текстовое представление координат ячеек   , point(tx, ty)::text t   , CASE                         -- направление движения       WHEN tx > sx THEN '(1,0)'  -- вправо       WHEN tx < sx THEN '(-1,0)' -- влево       WHEN ty > sy THEN '(0,1)'  -- вниз       WHEN ty < sy THEN '(0,-1)' -- вверх     END d   , abs(tx - sx) + abs(ty - sy) score -- "стоимость" сегмента - разность координат   FROM     (       SELECT         sx       , sy       , unnest(_tx) tx -- возможные шаги по горизонтали       , sy ty       FROM         stepline     UNION ALL       SELECT         sx       , sy       , sx sy       , unnest(_ty) ty -- возможные шаги по вертикали       FROM         stepline     ) T ) , dir AS MATERIALIZED (   SELECT     unnest(ARRAY[ -- направления "смотрения"       '(1,0)'  -- вправо     , '(0,1)'  -- вниз     , '(-1,0)' -- влево     , '(0,-1)' -- вверх     ]::point[]) d ) , onestep AS MATERIALIZED (   SELECT     point(x, y)::text s   , ds.d::text ds   , point(x, y)::text t   , dt.d::text dt   , 1000 score -- поворот на месте "за 1000"   FROM     poi   , dir ds   , dir dt   WHERE     dt.d[0] <> ds.d[0] AND -- это поворот, не разворот на 180     dt.d[1] <> ds.d[1] UNION ALL   SELECT     s   , d ds   , t   , d dt   , score     -- шаг по прямой к соседнему узлу   FROM     segline ) , init AS MATERIALIZED (   SELECT     point(       min(x) FILTER(WHERE m[y][x] = 'S')     , min(y) FILTER(WHERE m[y][x] = 'S')     )::text s -- координаты стартовой клетки   , point(       min(x) FILTER(WHERE m[y][x] = 'E')     , min(y) FILTER(WHERE m[y][x] = 'E')     )::text e -- координаты конечной клетки   FROM     matrix   , generate_subscripts(m, 1) y   , generate_subscripts(m, 2) x   WHERE     m[y][x] IN ('S', 'E') ) , r AS (   SELECT     e                         -- протаскиваем целевую точку сквозь все шаги   , s p                       -- текущая точка - стартовая   , '(1,0)' d                 -- исходно смотрим направо   , 0::bigint score           -- накопленная стоимость пути   , FALSE turn                -- признак поворота на предыдущем шаге   , ARRAY[s || ':(1,0)'] path -- уже достигнутый путь   , FALSE fin                 -- признак достижения конечной точки на данном шаге   FROM     init UNION ALL   (     WITH tmp AS (       SELECT DISTINCT ON (state) -- уникализируем пути по достигнутому состоянию         e       , os.t p                   -- новая достигнутая точка       , os.dt d                  -- новое направление       , r.score + os.score score -- "стоимость" уже пройденного пути       , os.t = os.s turn         -- признак поворота       , r.path || state path       FROM         r       JOIN         onestep os           ON (os.s, os.ds) = (r.p, r.d)       , LATERAL (           SELECT os.t || ':' || os.dt state -- состояние - это "куда пришли" + "куда смотрим"         ) T       WHERE         p <> e AND             -- пока не пришли куда надо         state <> ALL(path) AND -- исключаем зацикливание пути         ( -- если на предыдущем шаге поворачивались, то на этом надо "шагать"           NOT turn OR           os.t <> os.s         ) AND         NOT fin                -- выход из рекурсии - достижение конечной точки       ORDER BY         state, r.score + os.score     )     SELECT       *     , bool_or(p = e) OVER() fin -- признак достижения конечной точки     FROM       tmp   ) ) SELECT   min(score) FROM   r WHERE   p = e;

Результат мы получаем всего за 33.5 секунды:

Часть 2

Во второй части нас просят подсчитать количество клеток, через которые проходят все пути с (одинаковой) минимальной стоимостью.

Заметим, что любой альтернативный путь той же стоимости должен на каком-то из шагов «сливаться» (попадать в ту же точку с тем же направлением и той же накопленной стоимостью) что и любой найденный нами минимальный путь.

Давайте сначала возьмем этот самый путь, найденный вместе со стоимостью в первой части, и превратим в цепь узловых точек:

, path AS (   SELECT     i   , split_part(path[i - 1], ':', 1) s  -- из какой точки шли   , split_part(path[i - 1], ':', 2) ds -- из какого направления   , split_part(path[i], ':', 1) t      -- в какую точку   , split_part(path[i], ':', 2) dt     -- в какое направление   FROM     (       SELECT         path -- произвольный путь минимальной стоимости       FROM         r       WHERE         fin AND         p = e       ORDER BY         score       LIMIT 1     )   , generate_subscripts(path, 1) i )

Для второго примера из условия (17x17) результат будет выглядеть так:

 i | s       | ds     | t       | dt  1 |         |        | (2,16)  | (1,0)  2 | (2,16)  | (1,0)  | (2,16)  | (0,-1)  3 | (2,16)  | (0,-1) | (2,6)   | (0,-1)  4 | (2,6)   | (0,-1) | (2,6)   | (1,0)  5 | (2,6)   | (1,0)  | (4,6)   | (1,0)  6 | (4,6)   | (1,0)  | (4,6)   | (0,1)  7 | (4,6)   | (0,1)  | (4,16)  | (0,1)  8 | (4,16)  | (0,1)  | (4,16)  | (1,0)  9 | (4,16)  | (1,0)  | (6,16)  | (1,0) 10 | (6,16)  | (1,0)  | (6,16)  | (0,-1) 11 | (6,16)  | (0,-1) | (6,14)  | (0,-1) 12 | (6,14)  | (0,-1) | (6,14)  | (1,0) 13 | (6,14)  | (1,0)  | (12,14) | (1,0) 14 | (12,14) | (1,0)  | (12,14) | (0,-1) 15 | (12,14) | (0,-1) | (12,12) | (0,-1) 16 | (12,12) | (0,-1) | (12,12) | (1,0) 17 | (12,12) | (1,0)  | (14,12) | (1,0) 18 | (14,12) | (1,0)  | (14,12) | (0,-1) 19 | (14,12) | (0,-1) | (14,10) | (0,-1) 20 | (14,10) | (0,-1) | (14,10) | (1,0) 21 | (14,10) | (1,0)  | (16,10) | (1,0) 22 | (16,10) | (1,0)  | (16,10) | (0,-1) 23 | (16,10) | (0,-1) | (16,2)  | (0,-1)

два альтернативных лучших пути #################  ################# #...#...#...#..E#  #...#...#...#..E# #.#.#.#.#.#.#.#^#  #.#.#.#.#.#.#.#^# #.#.#.#...#...#^#  #.#.#.#...#...#^# #.#.#.#.###.#.#^#  #.#.#.#.###.#.#^# #A>A#.#.#.....#^#  #B>B#.#.#.....#^# #^#v#.#.#.#####^#  #^#v#.#.#.#####^# #^#v..#.#.#....^#  #^#v..#.#.#B>>>B# #^#v#####.#.###^#  #^#v#####.#^###.# #^#v#.......#A>A#  #^#v#..B>>>B#...# #^#v###.#####^###  #^#v###^#####.### #^#v#...#..A>A#.#  #^#v#B>B#.....#.# #^#v#.#####^###.#  #^#v#^#####.###.# #^#v#A>>>>>A..#.#  #^#v#^........#.# #^#v#^#########.#  #^#v#^#########.# #S#A>A..........#  #S#B>B..........# #################  #################

Заметим, что даже в примере альтернативные пути «сливаются» в точке (последняя B в правом пути), которая не является узловой для первого из них. А это значит, что нам необходимо восстановить не только узловые точки, но и все промежуточные состояния с накопленной «стоимостью»:

, pathex AS (   SELECT     p   , d   , sum(stepscore) OVER(ORDER BY i) score -- вычисляем накопительный итог   FROM     (       SELECT DISTINCT ON (p, d)   -- уникализируем состояния         *       FROM         (           SELECT             row_number() OVER() i -- нумеруем состояния           , point(x, y)::text p           , dt d           , CASE               WHEN s IS NULL THEN 0               WHEN s = t THEN 1000               ELSE 1             END stepscore         -- стоимость шага           FROM             path           , generate_series((coalesce(s, t)::point)[0]::integer, (t::point)[0]::integer, coalesce(nullif((ds::point)[0]::integer, 0), 1)) x -- генерируем шаги по X           , generate_series((coalesce(s, t)::point)[1]::integer, (t::point)[1]::integer, coalesce(nullif((ds::point)[1]::integer, 0), 1)) y -- генерируем шаги по Y         ) T       ORDER BY         p, d, i     ) T )

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

Теперь цепочка состояний нашего пути выглядит так:

p      | d      | score (2,16) | (1,0)  |    0 (2,16) | (0,-1) | 1000 (2,15) | (0,-1) | 1001 (2,14) | (0,-1) | 1002 (2,13) | (0,-1) | 1003 (2,12) | (0,-1) | 1004 (2,11) | (0,-1) | 1005 (2,10) | (0,-1) | 1006 (2,9)  | (0,-1) | 1007 (2,8)  | (0,-1) | 1008 (2,7)  | (0,-1) | 1009 (2,6)  | (0,-1) | 1010 (2,6)  | (1,0)  | 2010 (3,6)  | (1,0)  | 2011 ...

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

, paths AS (   SELECT     path   FROM     r   WHERE     (path[array_length(path, 1)], score) IN ( -- состояние и стоимость в последней точке совпадают с нашими       SELECT         p || ':' || d       , score       FROM         pathex     ) )

Остается лишь повторить операцию по превращению каждого такого пути в набор точек и узнать количество уникальных среди них:

SELECT   count(DISTINCT p) -- подсчитываем количество уникальных клеток FROM   paths , LATERAL ( -- превращаем каждый путь между узлами в набор проходимых клеток     SELECT       point(x, y)::text p     FROM       (         SELECT           split_part(path[i - 1], ':', 1) s         , split_part(path[i - 1], ':', 2) ds         , split_part(path[i], ':', 1) t         , split_part(path[i], ':', 2) dt         FROM           generate_subscripts(path, 1) i       ) T     , generate_series((coalesce(s, t)::point)[0]::integer, (t::point)[0]::integer, coalesce(nullif((ds::point)[0]::integer, 0), 1)) x     , generate_series((coalesce(s, t)::point)[1]::integer, (t::point)[1]::integer, coalesce(nullif((ds::point)[1]::integer, 0), 1)) y   ) T;

Итого, полный вид итогового запроса для второй части:

-- explain (analyze, costs off) WITH RECURSIVE matrix AS MATERIALIZED (   SELECT     array_agg(regexp_split_to_array(line[1], '')) m   FROM     regexp_matches(       $$ ################# #...#...#...#..E# #.#.#.#.#.#.#.#.# #.#.#.#...#...#.# #.#.#.#.###.#.#.# #...#.#.#.....#.# #.#.#.#.#.#####.# #.#...#.#.#.....# #.#.#####.#.###.# #.#.#.......#...# #.#.###.#####.### #.#.#...#.....#.# #.#.#.#####.###.# #.#.#.........#.# #.#.#.#########.# #S#.............# ################# $$     , '(?:^|[\r\n])(#[^\r\n]*#)(?=$|[\r\n])'     , 'g'     )       WITH ORDINALITY y(line, y) ) , poi AS MATERIALIZED (   SELECT     x   , y   , grpx   , grpy   FROM     (       SELECT         *       , sum(wall::integer) OVER(PARTITION BY x ORDER BY y) grpx -- группа по X       , sum(wall::integer) OVER(PARTITION BY y ORDER BY x) grpy -- группа по Y       FROM         (           SELECT             x           , y           , m[y][x] = '#' wall           FROM             matrix           , generate_subscripts(m, 1) y           , generate_subscripts(m, 2) x           WHERE             m[y][x] IN ('S', 'E', '#') OR -- отбираем старт, финиш и все стены             (               m[y][x] = '.' AND -- проходные клетки отбираем только вне тоннеля               (m[y][x - 1] <> '#' OR m[y][x + 1] <> '#') AND               (m[y - 1][x] <> '#' OR m[y + 1][x] <> '#')             )         ) T     ) T   WHERE     NOT wall -- стены нам не нужны ) , stepline AS MATERIALIZED (   SELECT     x sx   , y sy   , array_remove(array_agg(x) OVER(PARTITION BY y, grpy), x) _tx   , array_remove(array_agg(y) OVER(PARTITION BY x, grpx), y) _ty   FROM     poi ) , segline AS MATERIALIZED (   SELECT     point(sx, sy)::text s        -- текстовое представление координат ячеек   , point(tx, ty)::text t   , CASE                         -- направление движения       WHEN tx > sx THEN '(1,0)'  -- вправо       WHEN tx < sx THEN '(-1,0)' -- влево       WHEN ty > sy THEN '(0,1)'  -- вниз       WHEN ty < sy THEN '(0,-1)' -- вверх     END d   , abs(tx - sx) + abs(ty - sy) score -- "стоимость" сегмента - разность координат   FROM     (       SELECT         sx       , sy       , unnest(_tx) tx -- возможные шаги по горизонтали       , sy ty       FROM         stepline     UNION ALL       SELECT         sx       , sy       , sx sy       , unnest(_ty) ty -- возможные шаги по вертикали       FROM         stepline     ) T ) , dir AS MATERIALIZED (   SELECT     unnest(ARRAY[ -- направления "смотрения"       '(1,0)'  -- вправо     , '(0,1)'  -- вниз     , '(-1,0)' -- влево     , '(0,-1)' -- вверх     ]::point[]) d ) , onestep AS MATERIALIZED (   SELECT     point(x, y)::text s   , ds.d::text ds   , point(x, y)::text t   , dt.d::text dt   , 1000 score -- поворот на месте "за 1000"   FROM     poi   , dir ds   , dir dt   WHERE     dt.d[0] <> ds.d[0] AND -- это поворот, не разворот на 180     dt.d[1] <> ds.d[1] UNION ALL   SELECT     s   , d ds   , t   , d dt   , score     -- шаг по прямой к соседнему узлу   FROM     segline ) , init AS MATERIALIZED (   SELECT     point(       min(x) FILTER(WHERE m[y][x] = 'S')     , min(y) FILTER(WHERE m[y][x] = 'S')     )::text s -- координаты стартовой клетки   , point(       min(x) FILTER(WHERE m[y][x] = 'E')     , min(y) FILTER(WHERE m[y][x] = 'E')     )::text e -- координаты конечной клетки   FROM     matrix   , generate_subscripts(m, 1) y   , generate_subscripts(m, 2) x   WHERE     m[y][x] IN ('S', 'E') ) , r AS (   SELECT     e                         -- протаскиваем целевую точку сквозь все шаги   , s p                       -- текущая точка - стартовая   , '(1,0)' d                 -- исходно смотрим направо   , 0::bigint score           -- накопленная стоимость пути   , FALSE turn                -- признак поворота на предыдущем шаге   , ARRAY[s || ':(1,0)'] path -- уже достигнутый путь   , FALSE fin                 -- признак достижения конечной точки на данном шаге   FROM     init UNION ALL   (     WITH tmp AS (       SELECT DISTINCT ON (state) -- уникализируем пути по достигнутому состоянию         e       , os.t p                   -- новая достигнутая точка       , os.dt d                  -- новое направление       , r.score + os.score score -- "стоимость" уже пройденного пути       , os.t = os.s turn         -- признак поворота       , r.path || state path       FROM         r       JOIN         onestep os           ON (os.s, os.ds) = (r.p, r.d)       , LATERAL (           SELECT os.t || ':' || os.dt state -- состояние - это "куда пришли" + "куда смотрим"         ) T       WHERE         p <> e AND             -- пока не пришли куда надо         state <> ALL(path) AND -- исключаем зацикливание пути         ( -- если на предыдущем шаге поворачивались, то на этом надо "шагать"           NOT turn OR           os.t <> os.s         ) AND         NOT fin                -- выход из рекурсии - достижение конечной точки       ORDER BY         state, r.score + os.score     )     SELECT       *     , bool_or(p = e) OVER() fin -- признак достижения конечной точки     FROM       tmp   ) ) , path AS (   SELECT     split_part(path[i - 1], ':', 1) s  -- из какой точки шли   , split_part(path[i - 1], ':', 2) ds -- из какого направления   , split_part(path[i], ':', 1) t      -- в какую точку   , split_part(path[i], ':', 2) dt     -- в какое направление   FROM     (       SELECT         path -- произвольный путь минимальной стоимости       FROM         r       WHERE         fin AND         p = e       ORDER BY         score       LIMIT 1     )   , generate_subscripts(path, 1) i ) , pathex AS (   SELECT     p   , d   , sum(stepscore) OVER(ORDER BY i) score -- вычисляем накопительный итог   FROM     (       SELECT DISTINCT ON (p, d)   -- уникализируем состояния         *       FROM         (           SELECT             row_number() OVER() i -- нумеруем состояния           , point(x, y)::text p           , dt d           , CASE               WHEN s IS NULL THEN 0               WHEN s = t THEN 1000               ELSE 1             END stepscore         -- стоимость шага           FROM             path           , generate_series((coalesce(s, t)::point)[0]::integer, (t::point)[0]::integer, coalesce(nullif((ds::point)[0]::integer, 0), 1)) x -- генерируем шаги по X           , generate_series((coalesce(s, t)::point)[1]::integer, (t::point)[1]::integer, coalesce(nullif((ds::point)[1]::integer, 0), 1)) y -- генерируем шаги по Y         ) T       ORDER BY         p, d, i     ) T ) , paths AS (   SELECT     path   FROM     r   WHERE     (path[array_length(path, 1)], score) IN ( -- состояние и стоимость в последней точке совпадают с нашими       SELECT         p || ':' || d       , score       FROM         pathex     ) ) SELECT   count(DISTINCT p) -- подсчитываем количество уникальных клеток FROM   paths , LATERAL ( -- превращаем каждый путь между узлами в набор проходимых клеток     SELECT       point(x, y)::text p     FROM       (         SELECT           split_part(path[i - 1], ':', 1) s         , split_part(path[i - 1], ':', 2) ds         , split_part(path[i], ':', 1) t         , split_part(path[i], ':', 2) dt         FROM           generate_subscripts(path, 1) i       ) T     , generate_series((coalesce(s, t)::point)[0]::integer, (t::point)[0]::integer, coalesce(nullif((ds::point)[0]::integer, 0), 1)) x     , generate_series((coalesce(s, t)::point)[1]::integer, (t::point)[1]::integer, coalesce(nullif((ds::point)[1]::integer, 0), 1)) y   ) T;

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