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

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

В этой части рассмотрим некоторые "грабли", на которые можно наступить, реализуя рекурсивные алгоритмы на 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 (агрегация внутри рекурсии)

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

2333133121414131402

0..111....22222

00...111...2...333.44.5555.6666.777.888899

0..111....22222
02.111....2222.
022111....222..
0221112...22...
02211122..2....
022111222......

00...111...2...333.44.5555.6666.777.888899
009..111...2...333.44.5555.6666.777.88889.
0099.111...2...333.44.5555.6666.777.8888..
00998111...2...333.44.5555.6666.777.888...
009981118..2...333.44.5555.6666.777.88....
0099811188.2...333.44.5555.6666.777.8.....
009981118882...333.44.5555.6666.777.......
0099811188827..333.44.5555.6666.77........
00998111888277.333.44.5555.6666.7.........
009981118882777333.44.5555.6666...........
009981118882777333644.5555.666............
00998111888277733364465555.66.............
0099811188827773336446555566..............

00...111...2...333.44.5555.6666.777.888899
0099.111...2...333.44.5555.6666.777.8888..
0099.1117772...333.44.5555.6666.....8888..
0099.111777244.333....5555.6666.....8888..
00992111777.44.333....5555.6666.....8888..

Часть 1

Решение этой задачи достаточно сложно для понимания "сходу", поэтому давайте разберем его детально пошагово.

Для начала получим из входной "карты" занятых блоков. Автонумерацию строк нам поможет получить уже знакомый по решениям предыдущих задач функционал WITH ORDINALITY, а ID файла - половина номера в каждой нечетной позиции:

WITH map AS (
  SELECT
    sz::::integer -- размер сегмента
  , n             -- порядковый номер сегмента
  , CASE
      WHEN n % 2 = 1 THEN n / 2
    END fid       -- ID файла
  FROM
    regexp_split_to_table( -- разбиение в таблицу ...
      '2333133121414131402'
    , ''                   -- ... по отдельным символам
    )
      WITH ORDINALITY T(sz, n)
)

sz |  n | fid
 2 |  1 |   0
 3 |  2 |
 3 |  3 |   1
 3 |  4 |
 1 |  5 |   2
 3 |  6 |
 3 |  7 |   3
 1 |  8 |
 2 |  9 |   4
 1 | 10 |
 4 | 11 |   5
 1 | 12 |
 4 | 13 |   6
 1 | 14 |
 3 | 15 |   7
 1 | 16 |
 4 | 17 |   8
 0 | 18 |
 2 | 19 |   9

Теперь превратим нашу карту сегментов в две карты-массива отдельных блоков - представления дискового пространства и "файловых" блоков в порядке перемещения (обратном):

, blk AS (
  SELECT
    array_agg(fid ORDER BY n) blkdsk       -- собираем все блоки в прямом порядке
  , array_agg(fid ORDER BY n DESC)         -- собираем в обратном порядке ...
      FILTER(WHERE fid IS NOT NULL) blkfil -- ... только занятые файлами блоки
  FROM
    map
  , unnest(array_fill(NULL::integer, ARRAY[sz::integer])) -- размножим запись sz раз
)

blkdsk : {0,0,NULL,NULL,NULL,1,1,1,NULL,NULL,NULL,2,NULL,NULL,NULL,3,3,3,NULL,4,4,NULL,5,5,5,5,NULL,6,6,6,6,NULL,7,7,7,NULL,8,8,8,8,9,9}
blkfil : {9,9,8,8,8,8,7,7,7,6,6,6,6,5,5,5,5,4,4,3,3,3,2,1,1,1,0,0}

Здесь мы воспользовались array_fill для формирования заполненного NULL массива длины sz для каждой записи сегмента, и тут же "развернули" его в sz записей, "размножив" исходный сегмент нужное нам число раз.

Собственно, остается лишь вычислить искомую контрольную сумму, используя в рекурсивном (не забываем добавить WITH RECURSIVE перед map) "цикле" два указателя на позиции в каждом из массивов:

, r AS (
  SELECT
    1 posdsk -- позиция блока "на диске"
  , 1 posfil -- позиция "перемещаемого" файлового блока
  , 0::bigint checksum
UNION ALL
  SELECT
    posdsk + 1 -- позиция "на диске" увеличивается каждый раз
  , posfil + (blkdsk[posdsk] IS NULL)::integer -- позиция "файла" - только если "дисковый" блок пуст
  , checksum + (posdsk - 1) * coalesce(blkdsk[posdsk], blkfil[posfil])
  FROM
    r
  , blk
  WHERE
    posdsk <= array_length(blkfil, 1) -- вычислять надо до исчерпания всех файловых блоков
)

posdsk | posfil | checksum
     1 |      1 |        0
     2 |      1 |        0
     3 |      1 |        0
     4 |      2 |       18
     5 |      3 |       45
     6 |      4 |       77
     7 |      4 |       82
     8 |      4 |       88
     9 |      4 |       95
    10 |      5 |      159
    11 |      6 |      231
    12 |      7 |      311
    13 |      7 |      333
    14 |      8 |      417
    15 |      9 |      508
    16 |     10 |      606
    17 |     10 |      651
    18 |     10 |      699
    19 |     10 |      750
    20 |     11 |      858
    21 |     11 |      934
    22 |     11 |     1014
    23 |     12 |     1140
    24 |     12 |     1250
    25 |     12 |     1365
    26 |     12 |     1485
    27 |     12 |     1610
    28 |     13 |     1766
    29 |     13 |     1928

Из полученной выборки остается лишь взять "последнее" (с наибольшим posdsk) значение checksum. В целом, наш итоговый запрос принимает следующий вид:

WITH RECURSIVE map AS (
  SELECT
    sz::integer -- размер сегмента
  , n           -- порядковый номер сегмента
  , CASE
      WHEN n % 2 = 1 THEN n / 2
    END fid     -- ID файла
  FROM
    regexp_split_to_table( -- разбиение в таблицу ...
      '2333133121414131402'
    , ''                   -- ... по отдельным символам
    )
      WITH ORDINALITY T(sz, n)
)
, blk AS (
  SELECT
    array_agg(fid ORDER BY n) blkdsk
  , array_agg(fid ORDER BY n DESC) FILTER(WHERE fid IS NOT NULL) blkfil
  FROM
    map
  , unnest(array_fill(NULL::integer, ARRAY[sz::integer])) -- размножим запись sz раз
)
, r AS (
  SELECT
    1 posdsk -- позиция блока "на диске"
  , 1 posfil -- позиция "перемещаемого" файлового блока
  , 0::bigint checksum
UNION ALL
  SELECT
    posdsk + 1 -- позиция "на диске" увеличивается каждый раз
  , posfil + (blkdsk[posdsk] IS NULL)::integer -- позиция "файла" - только если "дисковый" блок пуст
  , checksum + (posdsk - 1) * coalesce(blkdsk[posdsk], blkfil[posfil])
  FROM
    r
  , blk
  WHERE
    posdsk <= array_length(blkfil, 1) -- вычислять надо до исчерпания всех файловых блоков
)
SELECT
  checksum
FROM
  r
ORDER BY
  posdsk DESC
LIMIT 1;

В принципе, этот запрос решает задачу, но при вводе целевой последовательности (а там 20 тысяч цифр-сегментов) уходит считать долго-долго...

Давайте посмотрим на план "маленького" запроса, чтобы заметить причину:

Оказывается, у нас вообще нет никаких промежуточных CTE map и blk! Чрезмерно "умный" PostgreSQL "заинлайнил" их вычисление, поскольку они используются по ходу запроса лишь однократно. Только вот из-за этого условие выхода из рекурсии (Join Filter в узле Nested Loop (#4)) ему приходится перевычислять на каждом шаге!

А оно ни разу не простое! Приведем его в минимально-читаемый вид:

Join Filter: (
  r_1.posdsk <= array_length(
    (
      array_agg(
        CASE WHEN ((t.n % '2'::bigint) = 1) THEN (t.n / 2) ELSE NULL::bigint END
        ORDER BY t.n DESC
      )
      FILTER (
        WHERE (
          CASE WHEN ((t.n % '2'::bigint) = 1) THEN (t.n / 2) ELSE NULL::bigint END IS NOT NULL
        )
      )
    )
  , 1
  )
)

Чтобы PostgreSQL не слишком умничал, достаточно лишь добавить MATERIALIZED у CTE blk :

WITH RECURSIVE map AS (
  SELECT
    sz::integer -- размер сегмента
  , n           -- порядковый номер сегмента
  , CASE
      WHEN n % 2 = 1 THEN n / 2
    END fid     -- ID файла
  FROM
    regexp_split_to_table( -- разбиение в таблицу ...
      '2333133121414131402'
    , ''                   -- ... по отдельным символам
    )
      WITH ORDINALITY T(sz, n)
)
, blk AS MATERIALIZED (
  SELECT
    array_agg(fid ORDER BY n) blkdsk
  , array_agg(fid ORDER BY n DESC) FILTER(WHERE fid IS NOT NULL) blkfil
  FROM
    map
  , unnest(array_fill(NULL::integer, ARRAY[sz::integer])) -- размножим запись sz раз
)
, r AS (
  SELECT
    1 posdsk -- позиция блока "на диске"
  , 1 posfil -- позиция "перемещаемого" файлового блока
  , 0::bigint checksum
UNION ALL
  SELECT
    posdsk + 1 -- позиция "на диске" увеличивается каждый раз
  , posfil + (blkdsk[posdsk] IS NULL)::integer -- позиция "файла" - только если "дисковый" блок пуст
  , checksum + (posdsk - 1) * coalesce(blkdsk[posdsk], blkfil[posfil])
  FROM
    r
  , blk
  WHERE
    posdsk <= array_length(blkfil, 1) -- вычислять надо до исчерпания всех файловых блоков
)
SELECT
  checksum
FROM
  r
ORDER BY
  posdsk DESC
LIMIT 1;

Тогда план выправляется, и результат вычисляется всего за 8 с небольшим секунд:

А теперь - без рекурсии!

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

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

, blk AS (
  SELECT
    posdsk
  , fid
  , CASE
      WHEN fid IS NULL THEN
        count(*) FILTER(WHERE fid IS NULL) OVER(ORDER BY posdsk)
    END posfiln -- "пронумеруем" свободные блоки в прямом порядке
  , CASE
      WHEN fid IS NOT NULL THEN
        count(*) FILTER(WHERE fid IS NOT NULL) OVER(ORDER BY posdsk DESC)
    END posfilo -- "пронумеруем" занятые блоки в обратном порядке
  FROM
    (
      SELECT
        row_number() OVER() posdsk -- пронумеруем все блоки
      , map.*
      FROM
        map
      , unnest(array_fill(NULL::integer, ARRAY[sz::integer])) -- размножим запись sz раз
    ) T
)

posdsk | fid | posfiln | posfilo
     1 |   0 |         |      28
     2 |   0 |         |      27
     3 |     |       1 |
     4 |     |       2 |
     5 |     |       3 |
     6 |   1 |         |      26
     7 |   1 |         |      25
     8 |   1 |         |      24
     9 |     |       4 |
    10 |     |       5 |
    11 |     |       6 |
    12 |   2 |         |      23
    13 |     |       7 |
    14 |     |       8 |
    15 |     |       9 |
    16 |   3 |         |      22
    17 |   3 |         |      21
    18 |   3 |         |      20
    19 |     |      10 |
    20 |   4 |         |      19
    21 |   4 |         |      18
    22 |     |      11 |
    23 |   5 |         |      17
    24 |   5 |         |      16
    25 |   5 |         |      15
    26 |   5 |         |      14
    27 |     |      12 |
    28 |   6 |         |      13
    29 |   6 |         |      12
    30 |   6 |         |      11
    31 |   6 |         |      10
    32 |     |      13 |
    33 |   7 |         |       9
    34 |   7 |         |       8
    35 |   7 |         |       7
    36 |     |      14 |
    37 |   8 |         |       6
    38 |   8 |         |       5
    39 |   8 |         |       4
    40 |   8 |         |       3
    41 |   9 |         |       2
    42 |   9 |         |       1

Собственно, остается лишь совместить полученную выборку с собой же, стыкуя новую позицию перемещаемого файлового блока к старой через LEFT JOIN , и вычислить чек-сумму. Не забываем ограничить подсчет количеством занятых блоков:

SELECT
  sum((n.posdsk - 1) * coalesce(n.fid, o.fid)) -- не забываем -1!
FROM
  blk n
LEFT JOIN
  blk o
    ON n.posfiln = o.posfilo -- совмещаем новую/старую позицию файлового блока
WHERE
  n.posdsk <= (SELECT sum(sz) FILTER(WHERE fid IS NOT NULL) FROM map); -- ограничиваемся только занятыми блоками

Полностью наш запрос теперь выглядит так:

WITH map AS (
  SELECT
    sz::integer -- размер сегмента
  , n           -- порядковый номер сегмента
  , CASE
      WHEN n % 2 = 1 THEN n / 2
    END fid     -- ID файла
  FROM
    regexp_split_to_table( -- разбиение в таблицу ...
      '2333133121414131402'
    , ''                   -- ... по отдельным символам
    )
      WITH ORDINALITY T(sz, n)
)
, blk AS (
  SELECT
    posdsk
  , fid
  , CASE
      WHEN fid IS NULL THEN
        count(*) FILTER(WHERE fid IS NULL) OVER(ORDER BY posdsk)
    END posfiln -- "пронумеруем" свободные блоки в прямом порядке
  , CASE
      WHEN fid IS NOT NULL THEN
        count(*) FILTER(WHERE fid IS NOT NULL) OVER(ORDER BY posdsk DESC)
    END posfilo -- "пронумеруем" занятые блоки в обратном порядке
  FROM
    (
      SELECT
        row_number() OVER() posdsk -- пронумеруем все блоки
      , map.*
      FROM
        map
      , unnest(array_fill(NULL::integer, ARRAY[sz::integer])) -- размножим запись sz раз
    ) T
)
SELECT
  sum((n.posdsk - 1) * coalesce(n.fid, o.fid)) -- не забываем -1!
FROM
  blk n
LEFT JOIN
  blk o
    ON n.posfiln = o.posfilo -- совмещаем новую/старую позицию файлового блока
WHERE
  n.posdsk <= (SELECT sum(sz) FILTER(WHERE fid IS NOT NULL) FROM map); -- ограничиваемся только занятыми блоками

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

UPD:

С учетом предложенных в комментариях доработок, запрос можно модифицировать до вот такого варианта, что дает ускорение еще в два раза:

WITH map AS (
  SELECT
    row_number() OVER(ORDER BY n) pos
  , CASE
      WHEN n % 2 = 1 THEN n / 2
    END fid
  FROM
    regexp_split_to_table(
      '2333133121414131402'
    , ''
    )
      WITH ORDINALITY T(sz, n)
  , generate_series(1, sz::integer)
)
, remap AS (
  SELECT
    array_agg(fid ORDER BY pos DESC) rpl
  FROM
    map
  WHERE
    fid IS NOT NULL
)
SELECT
  sum((pos - 1) * coalesce(fid, (TABLE remap)[rplpos])) -- именно не JOIN!
FROM
  (
    SELECT
      *
    , count(*) FILTER(WHERE fid IS NULL) OVER(ORDER BY pos) rplpos
    FROM
      (
        TABLE
          map
        LIMIT
          array_length((TABLE remap), 1) -- LIMIT вместо условия на порядковый номер
      ) T
  ) T;

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

• вместо WHERE-условия на порядковый номер записи воспользовались LIMIT и тем фактом, что CTE в PostgreSQL всегда читается в одном порядке

• вместо JOIN с remap, что приводит к избыточному появлению узла Nested Loop в плане, мы обратились к CTE из единственного поля как "к словарю" через TABLE, прочитав ее в InitPlan всего два раза - для определения длины массива и для получения значения

Часть 2

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

Добавим вычисление позиции каждого такого сегмента в самое начало нашего запроса:

WITH map AS (
  SELECT
    sz::integer -- размер сегмента
  , n           -- порядковый номер сегмента
  , CASE
      WHEN n % 2 = 1 THEN n / 2
    END fid     -- ID файла
  , sum(sz::bigint) OVER(ORDER BY n) - sz::bigint pos -- позиция начала сегмента
  FROM
    regexp_split_to_table( -- разбиение в таблицу ...
      '2333133121414131402'
    , ''                   -- ... по отдельным символам
    )
      WITH ORDINALITY T(sz, n)
)

sz |  n | fid | pos
 2 |  1 |   0 |   0
 3 |  2 |     |   2
 3 |  3 |   1 |   5
 3 |  4 |     |   8
 1 |  5 |   2 |  11
 3 |  6 |     |  12
 3 |  7 |   3 |  15
 1 |  8 |     |  18
 2 |  9 |   4 |  19
 1 | 10 |     |  21
 4 | 11 |   5 |  22
 1 | 12 |     |  26
 4 | 13 |   6 |  27
 1 | 14 |     |  31
 3 | 15 |   7 |  32
 1 | 16 |     |  35
 4 | 17 |   8 |  36
 0 | 18 |     |  40
 2 | 19 |   9 |  40

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

, seg AS MATERIALIZED (
  SELECT
    array_agg(ARRAY[pos, pos + sz]::integer[] ORDER BY n DESC)
      FILTER(WHERE fid IS NOT NULL) segfile -- карта файлов
  , array_agg(ARRAY[pos, pos + sz]::integer[] ORDER BY n)
      FILTER(WHERE fid IS NULL) segfree     -- карта свободных сегментов
  FROM
    map
)

segfile : {{40,42},{36,40},{32,35},{27,31},{22,26},{19,21},{15,18},{11,12},{5,8},{0,2}}
segfree : {{2,5},{8,11},{12,15},{18,19},{21,22},{26,27},{31,32},{35,36},{40,40}}

Теперь самое сложное - на каждом шаге рекурсии найти переносимый файл, последовательно "примеряя" его к каждому "свободному" сегменту:

, r AS (
  SELECT
    1 i
  , *
  FROM
    seg
UNION ALL
  SELECT
    i + 1
  , coalesce(T.segfile, r.segfile) -- если нашли возможный перенос для файла - используем его ...
  , coalesce(T.segfree, r.segfree) -- ... если нет - сохраняем прежние состояния
  FROM
    r
  LEFT JOIN
    LATERAL (
      SELECT -- реконструкция массивов-карт с учетом переноса
        segfile[:i - 1]
        || ARRAY[segfree[j][1], segfree[j][1] + segfile[i][2] - segfile[i][1]]
        || segfile[i + 1:] segfile
      , segfree[:j - 1]
        || ARRAY[segfree[j][1] + segfile[i][2] - segfile[i][1], segfree[j][2]]
        || segfree[j + 1:] segfree
      FROM
        generate_subscripts(segfree, 1) j -- перебор свободных сегментов
      WHERE
        segfree[j][1] < segfile[i][1] AND -- проверка возможности переноса
        segfree[j][2] - segfree[j][1] >= segfile[i][2] - segfile[i][1]
      LIMIT 1 -- ищем до первой возможности
    ) T
      ON TRUE
  WHERE
    i <= array_length(r.segfile, 1) -- ограничиваемся количеством файлов
)

 i | segfile/segfree
 1 | {{40,42},{36,40},{32,35},{27,31},{22,26},{19,21},{15,18},{11,12},{5,8},{0,2}}
     {{2,5},{8,11},{12,15},{18,19},{21,22},{26,27},{31,32},{35,36},{40,40}}
 2 | {{2,4},{36,40},{32,35},{27,31},{22,26},{19,21},{15,18},{11,12},{5,8},{0,2}}
     {{4,5},{8,11},{12,15},{18,19},{21,22},{26,27},{31,32},{35,36},{40,40}}
 3 | {{2,4},{36,40},{32,35},{27,31},{22,26},{19,21},{15,18},{11,12},{5,8},{0,2}}
     {{4,5},{8,11},{12,15},{18,19},{21,22},{26,27},{31,32},{35,36},{40,40}}
 4 | {{2,4},{36,40},{8,11},{27,31},{22,26},{19,21},{15,18},{11,12},{5,8},{0,2}}
     {{4,5},{11,11},{12,15},{18,19},{21,22},{26,27},{31,32},{35,36},{40,40}}
 5 | {{2,4},{36,40},{8,11},{27,31},{22,26},{19,21},{15,18},{11,12},{5,8},{0,2}}
     {{4,5},{11,11},{12,15},{18,19},{21,22},{26,27},{31,32},{35,36},{40,40}}
 6 | {{2,4},{36,40},{8,11},{27,31},{22,26},{19,21},{15,18},{11,12},{5,8},{0,2}}
     {{4,5},{11,11},{12,15},{18,19},{21,22},{26,27},{31,32},{35,36},{40,40}}
 7 | {{2,4},{36,40},{8,11},{27,31},{22,26},{12,14},{15,18},{11,12},{5,8},{0,2}}
     {{4,5},{11,11},{14,15},{18,19},{21,22},{26,27},{31,32},{35,36},{40,40}}
 8 | {{2,4},{36,40},{8,11},{27,31},{22,26},{12,14},{15,18},{11,12},{5,8},{0,2}}
     {{4,5},{11,11},{14,15},{18,19},{21,22},{26,27},{31,32},{35,36},{40,40}}
 9 | {{2,4},{36,40},{8,11},{27,31},{22,26},{12,14},{15,18},{4,5},{5,8},{0,2}}
     {{5,5},{11,11},{14,15},{18,19},{21,22},{26,27},{31,32},{35,36},{40,40}}
10 | {{2,4},{36,40},{8,11},{27,31},{22,26},{12,14},{15,18},{4,5},{5,8},{0,2}}
     {{5,5},{11,11},{14,15},{18,19},{21,22},{26,27},{31,32},{35,36},{40,40}}
11 | {{2,4},{36,40},{8,11},{27,31},{22,26},{12,14},{15,18},{4,5},{5,8},{0,2}}
     {{5,5},{11,11},{14,15},{18,19},{21,22},{26,27},{31,32},{35,36},{40,40}}

Собственно, на последнем шаге мы и получаем целевое расположение файлов, которые необходимо пронумеровать в обратном порядке и пронумеровать каждый его сегмент:

SELECT
  sum(fid * i) -- контрольная сумма
FROM
  (
    SELECT
      segfile -- состояние после последнего переноса
    FROM
      r
    ORDER BY
      i DESC
    LIMIT 1
  ) T
, array_length(segfile, 1) files -- общее количество файлов
, generate_series(
    files - 1
  , 0
  , -1
  ) fid -- нумерация файлов в обратном порядке
, generate_series(
    segfile[files - fid][1]
  , segfile[files - fid][2] - 1
  ) i; -- нумерация блоков внутри файла

Итоговый запрос принимает следующий вид:

WITH RECURSIVE map AS (
  SELECT
    sz::integer -- размер сегмента
  , n           -- порядковый номер сегмента
  , CASE
      WHEN n % 2 = 1 THEN n / 2
    END fid     -- ID файла
  , sum(sz::bigint) OVER(ORDER BY n) - sz::bigint pos -- позиция начала сегмента
  FROM
    regexp_split_to_table( -- разбиение в таблицу ...
      '2333133121414131402'
    , ''                   -- ... по отдельным символам
    )
      WITH ORDINALITY T(sz, n)
)
, seg AS MATERIALIZED (
  SELECT
    array_agg(ARRAY[pos, pos + sz]::integer[] ORDER BY n DESC)
      FILTER(WHERE fid IS NOT NULL) segfile -- карта файлов
  , array_agg(ARRAY[pos, pos + sz]::integer[] ORDER BY n)
      FILTER(WHERE fid IS NULL) segfree     -- карта свободных сегментов
  FROM
    map
)
, r AS (
  SELECT
    1 i
  , *
  FROM
    seg
UNION ALL
  SELECT
    i + 1
  , coalesce(T.segfile, r.segfile) -- если нашли возможный перенос для файла - используем его ...
  , coalesce(T.segfree, r.segfree) -- ... если нет - сохраняем прежние состояния
  FROM
    r
  LEFT JOIN
    LATERAL (
      SELECT -- реконструкция массивов-карт с учетом переноса
        segfile[:i - 1]
        || ARRAY[segfree[j][1], segfree[j][1] + segfile[i][2] - segfile[i][1]]
        || segfile[i + 1:] segfile
      , segfree[:j - 1]
        || ARRAY[segfree[j][1] + segfile[i][2] - segfile[i][1], segfree[j][2]]
        || segfree[j + 1:] segfree
      FROM
        generate_subscripts(segfree, 1) j -- перебор свободных сегментов
      WHERE
        segfree[j][1] < segfile[i][1] AND -- проверка возможности переноса
        segfree[j][2] - segfree[j][1] >= segfile[i][2] - segfile[i][1]
      LIMIT 1 -- ищем до первой возможности
    ) T
      ON TRUE
  WHERE
    i <= array_length(r.segfile, 1) -- ограничиваемся количеством файлов
)
SELECT
  sum(fid * i) -- контрольная сумма
FROM
  (
    SELECT
      segfile -- состояние после последнего переноса
    FROM
      r
    ORDER BY
      i DESC
    LIMIT 1
  ) T
, array_length(segfile, 1) files -- общее количество файлов
, generate_series(
    files - 1
  , 0
  , -1
  ) fid -- нумерация файлов в обратном порядке
, generate_series(
    segfile[files - fid][1]
  , segfile[files - fid][2] - 1
  ) i; -- нумерация блоков внутри файла

Логично, что в этот раз вычисления заняли побольше времени - порядка 22.5 секунд, а 90% времени - поиски подходящего для переноса сегмента:

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