В этой челлендж-серии статей попробуем использовать 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 раза дольше, но все равно меньше минуты: