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