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

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

В этой части воспользуемся обширными возможностями поиска в массивах и реализуем рекурсивную сортировку «пузырьком».

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

Advent of Code 2024, Day 5: Print Queue

--- День 5: Очередь печати ---

Удовлетворенные результатами своих поисков на Церере, отряд ученых предлагает затем просканировать стопки канцелярских товаров в подвале 17.

В преддверии Рождества в типографии «Северный полюс» кипит работа, как никогда прежде, и пока историки продолжают исследовать этот исторически значимый объект, эльф, работающий на очень знакомом принтере, подзывает вас.

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

Протоколы безопасности четко указывают, что новые страницы для руководств по безопасности должны печататься в строго определенном порядке. Обозначение X|Yозначает, что если и номер страницы X, и номер страницы Yдолжны быть напечатаны как часть обновления, номер страницы X должен быть напечатан в какой-то момент перед номером страницы Y.

У эльфа есть как правила порядка страниц, так и страницы, которые нужно создать в каждом обновлении (ваши входные данные для головоломки), но он не может понять, в правильном ли порядке расположены страницы в каждом обновлении.

Например:

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

В первом разделе указаны правила упорядочивания страниц, по одному на строку. Первое правило 47|53означает, что если обновление включает как страницу номер 47, так и страницу номер 53, то страница номер 47 должна быть напечатана в какой-то момент перед страницей номер 53. (47 не обязательно должна быть непосредственно перед 53; другие страницы могут быть между ними.)

Во втором разделе указаны номера страниц каждого обновления. Поскольку большинство руководств по безопасности отличаются, страницы, необходимые для обновлений, также отличаются. Первое обновление, 75,47,61,53,29означает, что обновление состоит из страниц с номерами 75, 47, 61, 53 и 29.

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

В приведенном выше примере первое обновление (75,47,61,53,29) выполнено в правильном порядке:

75правильно стоит первым, потому что существуют правила, которые помещают каждую следующую страницу после него: 75|47, 75|61, 75|53, и 75|29.
47правильно стоит на втором месте, потому что 75 должна быть перед ней (75|47), а каждая вторая страница должна быть после нее согласно 47|61, 47|53, и 47|29.
61находится правильно посередине, потому что 75 и 47 находятся перед ним (75|61и 47|61), а 53 и 29 — после него (61|53и 61|29).
53правильно стоит на четвертом месте, поскольку находится перед страницей номер 29 (53|29).
29осталась единственная страница, поэтому она по праву последняя.

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

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

Четвертое обновление, 75,97,47,61,53, выполнено в неправильном порядке: оно выведет 75 перед 97, что нарушает правило 97|75.

Пятое обновление 61,13,29, также не в правильном порядке, поскольку нарушает правило 29|13.

Последнее обновление, 97,13,75,29,47, имеет неправильный порядок из-за нарушения нескольких правил.

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

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

Они имеют средние номера страниц 61, 53, и 29соответственно. Сложение этих номеров страниц вместе дает 143.

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

Определите, какие обновления уже находятся в правильном порядке. Что вы получите, если сложите средний номер страницы из этих правильно упорядоченных обновлений?

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

Пока эльфы печатают обновления в правильном порядке, у вас есть немного времени, чтобы исправить остальные.

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

75,97,47,61,53становится .97,75,47,61,53
61,13,29становится 61,29,13
97,13,75,29,47становится 97,75,47,29,13

После взятия только неправильно упорядоченных обновлений и их правильного упорядочивания их средние номера страниц будут 47, 29, и 47. Сложение этих данных дает 123.

Найдите обновления, которые не в правильном порядке. Что вы получите, если сложите номера средних страниц после правильного упорядочивания только этих обновлений?

Часть 1

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

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

Делаем первичный отбор «неправильных» обновлений ровно как в первой части.
Фактически, правила упорядочивания задают отношения «больше/меньше» для каждой конкретной пары номеров. Поэтому, чтобы правильно упорядочить все номера страниц в обновлении, нам необходимо «отсортировать» каждый «неправильный» массив в соответствии с этими правилами.
Реализуем примитивный вариант сортировки "пузырьком": заведем счетчик n от 0 до квадрата длины массива (ln ^ 2). Из него мы можем получить два указателя: "левый" i = (n / ln) + 1 и "правый" j = (n % ln) + 1.
Если j <= i, то просто «пропускаем ход», ничего не делая с массивом. В противном случае оператором = ANY(...) проверяем, не содержитсяли «правое» значение в массиве before-номеров.
Если таки содержится - меняем их местами, "переклеивая" массив: [..i-1, i, i+1..j-1, j, j+1..] -> [..i-1, j, i+1..j-1, i, j+1..].
Последний по счетчику шаг рекурсии содержит отсортированное в соответствии с правилами состояние массива - получим его с помощью 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мс.

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