SQL HowTo: поиск в словаре и массивах, сортировка «пузырьком» (Advent of Code 2024, Day 5: Print Queue)

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

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

47|53 97|13 97|61 97|47 75|29 61|13 75|53 29|13 97|29 53|29 61|53 97|53 61|29 47|13 75|47 97|75 47|61 75|61 47|29 75|13 53|13  75,47,61,53,29 97,61,53,29,13 75,29,13 75,97,47,61,53 61,13,29 97,13,75,29,47

75,47,61,53,29 97,61,53,29,13 75,29,13

Часть 1

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

2. Уже традиционно, с помощью регулярных выражений вычленим правила и сгруппируем их в jsonb-словарь по номерам «последующих» страниц — чтобы заменить медленный JOIN «точечным» обращением по значению ключа.

3. Для каждого обновления проверим, что для каждого элемента (bool_and) в слайсе массива после конкретной позиции (upd[i + 1:]) нет пересечений (оператор &&) с массивом before-номеров, который мы получим из словаря по ключу — значению текущего элемента ((TABLE rul) ->> upd[i]::text).

4. Остается лишь просуммировать «средние» значения.

WITH src AS (   SELECT $$ 47|53 97|13 97|61 97|47 75|29 61|13 75|53 29|13 97|29 53|29 61|53 97|53 61|29 47|13 75|47 97|75 47|61 75|61 47|29 75|13 53|13  75,47,61,53,29 97,61,53,29,13 75,29,13 75,97,47,61,53 61,13,29 97,13,75,29,47 $$ ) , rul AS ( -- правила в виде jsonb-словаря   SELECT     jsonb_object(       array_agg(pagea)       -- ключ словаря - номер after-страницы     , array_agg(pageb::text) -- значение - массив номеров before-страниц     )   FROM     (       SELECT         line[2] pagea            -- номер страницы "после"       , array_agg(line[1]) pageb -- массив номеров, которые должны быть "до"       FROM         regexp_matches(           (TABLE src)         , '(\d+)\|(\d+)'         , 'g'         ) line       GROUP BY         1     ) T ) , upd AS ( -- обновления в виде массива номеров   SELECT     string_to_array(line, ',')::numeric[] upd   FROM     regexp_split_to_table(       (TABLE src)     , '[\r\n]+'     ) line   WHERE     line ~ '^(\d+)(,\d+)*$' ) SELECT   sum(upd[array_length(upd, 1) / 2 + 1]) -- суммируем значения в середине массива FROM   upd , LATERAL (     SELECT       bool_and(         NOT(           upd[i + 1:] && coalesce(             ((TABLE rul) ->> upd[i]::text)::numeric[] -- массив-значение по ключу словаря           , '{}' -- если такого ключа в словаре нет, подставим пустой массив           )         )       ) cond -- условие не нарушается ни для одной позиции     FROM       generate_series(1, array_length(upd, 1) - 1) i -- [1..n-1]   ) T WHERE   cond;

На реальных данных вычисление занимает меньше 50мс:

Часть 2

1. Делаем первичный отбор «неправильных» обновлений ровно как в первой части.

2. Фактически, правила упорядочивания задают отношения «больше/меньше» для каждой конкретной пары номеров. Поэтому, чтобы правильно упорядочить все номера страниц в обновлении, нам необходимо «отсортировать» каждый «неправильный» массив в соответствии с этими правилами.

3. Реализуем примитивный вариант сортировки «пузырьком»: заведем счетчик n от 0 до квадрата длины массива (ln ^ 2). Из него мы можем получить два указателя: «левый» i = (n / ln) + 1 и «правый» j = (n % ln) + 1.

4. Если j <= i, то просто «пропускаем ход», ничего не делая с массивом. В противном случае оператором = ANY(...) проверяем, не содержится ли «правое» значение в массиве before-номеров.

5. Если таки содержится — меняем их местами, «переклеивая» массив: [..i-1, i, i+1..j-1, j, j+1..] -> [..i-1, j, i+1..j-1, i, j+1..].

6. Последний по счетчику шаг рекурсии содержит отсортированное в соответствии с правилами состояние массива — получим его с помощью DISTINCT ON(id) ... ORDER BY id, n DESC.

WITH RECURSIVE src AS (   SELECT $$ 47|53 97|13 97|61 97|47 75|29 61|13 75|53 29|13 97|29 53|29 61|53 97|53 61|29 47|13 75|47 97|75 47|61 75|61 47|29 75|13 53|13  75,47,61,53,29 97,61,53,29,13 75,29,13 75,97,47,61,53 61,13,29 97,13,75,29,47 $$ ) , rul AS ( -- словарь правил   SELECT     jsonb_object(       array_agg(pagea)     , array_agg(pageb::text)     )   FROM     (       SELECT         line[2] pagea       , array_agg(line[1]) pageb       FROM         regexp_matches(           (TABLE src)         , '(\d+)\|(\d+)'         , 'g'         ) line       GROUP BY         1     ) T ) , upd AS ( -- массивы обновлений   SELECT     string_to_array(line, ',')::numeric[] upd   FROM     regexp_split_to_table(       (TABLE src)     , '[\r\n]+'     ) line   WHERE     line ~ '^(\d+)(,\d+)*$' ) , wrong AS ( -- только ошибочные обновления   SELECT     row_number() OVER() id -- пронумеровали   , upd   FROM     upd   , LATERAL (       SELECT         bool_and(NOT(upd[i + 1:] && coalesce(((TABLE rul) ->> upd[i]::text)::numeric[], '{}'))) cond       FROM         generate_series(1, array_length(upd, 1) - 1) i     ) T   WHERE     NOT cond ) , r AS ( -- рекурсивная сортировка "пузырьком"   SELECT     id   , upd   , array_length(upd, 1) ln -- длина конкретного массива-обновления   , 0 n                     -- счетчик шагов в нем   FROM     wrong UNION ALL   SELECT     id   , CASE       WHEN j <= i THEN upd -- пропускаем неподходящие положения указателей       WHEN upd[j] = ANY(coalesce(((TABLE rul) ->> upd[i]::text)::numeric[], '{}'))         THEN upd[:i - 1] || upd[j] || upd[i + 1:j - 1] || upd[i] || upd[j + 1:] -- swap(upd, i, j)       ELSE upd     END   , ln   , n + 1   FROM     r   , LATERAL ( -- преобразуем счетчик в пару "указателей"       SELECT         (n / ln) + 1 i       , (n % ln) + 1 j     ) T   WHERE     n < ln ^ 2 ) SELECT   sum(upd[array_length(upd, 1) / 2 + 1]) FROM   (     SELECT DISTINCT ON(id) -- отбираем по каждому обновлению ...       upd     FROM       r     ORDER BY       id, n DESC           -- ... только последнее по счетчику состояние   ) T;

Очевидно, что перебирать номера «указателей» i и j можно более эффективно, избегая половины «холостых» шагов. Но даже в таком виде решение занимает всего 160мс.