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

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

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

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

Advent of Code 2024, Day 25: Code Chronicle

--- День 25: Хроника кода ---

За неимением идей и времени Историки соглашаются, что им следует вернуться и проверить кабинет Главного историка в последний раз, просто на тот случай, если он вернулся туда без вашего ведома.

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

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

Схемы представлены в зашифрованном формате файла, но они содержат информацию о производителе, поэтому вам нужно найти его номер поддержки.

«Наш продукт Virtual Five-Pin Tumbler? Это наша самая дорогая модель! Гораздо надежнее, чем...» Вы объясняете, что вам нужно открыть дверь, а времени мало.

«Ну, вы не можете знать, открывает ли ключ замок, не попробовав вставить ключ в замок (из-за скрытых квантовых переменных), но вы можете исключить некоторые комбинации ключа и замка».

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

Он передает вам несколько примеров схем:

#####
.####
.####
.####
.#.#.
.#...
.....

#####
##.##
.#.##
...##
...#.
...#.
.....

.....
#....
#....
#...#
#.#.#
#.###
#####

.....
.....
#.#..
###..
###.#
###.#
#####

.....
.....
.....
#....
#.#..
#.#.#
#####

«Замки — это схемы, в которых верхняя строка заполнена (#), а нижняя строка пуста (.); у ключей верхняя строка пуста, а нижняя строка заполнена. Если вы посмотрите внимательно, то увидите, что каждая схема на самом деле представляет собой набор столбцов различной высоты, идущих либо сверху вниз (для замков), либо снизу вверх (для ключей)».

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

«Итак, можно сказать, что первый замок имеет высоту штифта 0,5,3,4,3:»

#####
.####
.####
.####
.#.#.
.#...
.....

«Или, что первый ключ имеет высоту 5,0,2,1,3:»

.....
#....
#....
#...#
#.#.#
#.###
#####

«Кажется, они должны подходить друг другу; в первых четырех столбцах штифты и ключ не перекрываются. Однако этот ключ не может быть для этого замка: в самом правом столбце штифт замка перекрывается с ключом, что вы знаете, потому что в этом столбце сумма высоты замка и высоты ключа больше, чем доступное пространство».

«Так или иначе, вы можете сузить круг ключей, которые вам нужно будет попробовать, просто проверив каждый ключ с каждым замком, а это значит, что вам придется проверить... подождите, сколько у вас замков? Но единственная установка такого размера находится на Севере...» Вы отключаете вызов.

В этом примере преобразование обоих замков в высоту штифтов дает:

0,5,3,4,3
1,2,0,5,3

Преобразование всех трех ключей в высоты дает:

5,0,2,1,3
4,3,4,0,2
3,0,2,0,1

Затем вы можете попробовать каждый ключ с каждым замком:

Замок 0,5,3,4,3 и ключ 5,0,2,1,3: перекрываются в последнем столбце.
Замок 0,5,3,4,3 и ключ 4,3,4,0,2: перекрываются во втором столбце.
Замок 0,5,3,4,3 и ключ 3,0,2,0,1: все столбцы подходят!
Замок 1,2,0,5,3 и ключ 5,0,2,1,3: перекрываются в первом столбце.
Замок 1,2,0,5,3 и ключ 4,3,4,0,2: все столбцы подходят!
Замок 1,2,0,5,3 и ключ 3,0,2,0,1: все столбцы подходят!

Таким образом, в этом примере количество уникальных пар замков/ключей, которые подходят друг другу без перекрытия ни в одном столбце, равно 3.

Проанализируйте свои схемы замков и ключей. Сколько уникальных пар замков/ключей подходят друг другу, не перекрываясь ни в одном столбце?

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

Вы и Историки врываетесь в кабинет, напугав Главного Историка! Все Историки по очереди выглядят растерянными, пока один из них не спрашивает, где он был последние несколько месяцев.

«Я был здесь, работал над этим первоочередным поручением от Санты! Кажется, единственный раз, когда я отвлекся, был где-то месяц назад, когда я пошел выпить чашечку кофе...»

Тут Шеф замечает время. «О нет! Я опоздаю! Должно быть, я заснул, пытаясь доделать последние штрихи в этой хронике, которую просил Санта, но теперь у меня нет времени посетить последние 50 мест в моем списке и закончить хронику до того, как Санта уедет! Он сказал, что это ему нужно до сегодняшнего спуска саней на воду».

Один из Историков держит список, который они использовали все это время, чтобы отслеживать, где они искали. Рядом с каждым местом, которое вы все посетили, они отметили это место звездочкой. Другие Историки держат свои собственные заметки, которые они делали во время путешествия; как Историки могли устоять перед желанием записать все, посещая все эти исторически значимые места?

Глаза Шефа округляются. «Со всем этим у нас, возможно, хватит времени закончить хронику! Санта сказал, что хочет, чтобы ее упаковали с бантом, так что я позвоню в отдел упаковки и... эй, можешь отнести ее Санте? Мне нужно будет к тому времени быть на своем месте, чтобы посмотреть, как отпустят сани».

Вы киваете, и Историки быстро собирают свои заметки в финальный набор страниц хроники.

Если хотите, можете доставить хронику снова.

Используя заметки из мест, отмеченных всеми пятьюдесятью звездами, Историки заканчивают хронику, упаковывают ее и передают вам, чтобы вы могли отнести ее Санте перед большим запуском саней.

Санта уже в санях, делает последние приготовления к запуску, когда вы приезжаете. Вы пытаетесь вручить ему хронику, но он не берет ее. «Хо-хо-хо», — смеется он про себя. «Этот подарок не для меня, а для тебя. Эта хроника — запись всех мест, где ты был, и людей, которым ты помог за последнее десятилетие. Спасибо тебе за все». С этими словами Санта уезжает в своих санях, чтобы доставить оставшиеся подарки этого года.

Часть 2

Для начала превратим вход нашей головоломки в нумерованные массивы символов с помощью regexp_matches/regexp_split_to_array и WITH ORDINALITY:

WITH src AS (
  SELECT
    regexp_split_to_array(line[1], '') line
  , n
  FROM
    regexp_matches(
      $$
#####
.####
.####
.####
.#.#.
.#...
.....

#####
##.##
.#.##
...##
...#.
...#.
.....

.....
#....
#....
#...#
#.#.#
#.###
#####

.....
.....
#.#..
###..
###.#
###.#
#####

.....
.....
.....
#....
#.#..
#.#.#
#####
$$
    , '(\S+)'
    , 'g'
    )
      WITH ORDINALITY T(line, n)
)

line        |  n
{#,#,#,#,#} |  1 -- это замок
{.,#,#,#,#} |  2
{.,#,#,#,#} |  3
{.,#,#,#,#} |  4
{.,#,.,#,.} |  5
{.,#,.,.,.} |  6
{.,.,.,.,.} |  7
{#,#,#,#,#} |  8 -- и это замок
{#,#,.,#,#} |  9
{.,#,.,#,#} | 10
{.,.,.,#,#} | 11
{.,.,.,#,.} | 12
{.,.,.,#,.} | 13
{.,.,.,.,.} | 14
{.,.,.,.,.} | 15 -- а это - не замок
{#,.,.,.,.} | 16
{#,.,.,.,.} | 17
{#,.,.,.,#} | 18
{#,.,#,.,#} | 19
{#,.,#,#,#} | 20
{#,#,#,#,#} | 21 -- ... это - ключ!
{.,.,.,.,.} | 22
{.,.,.,.,.} | 23
{#,.,#,.,.} | 24
{#,#,#,.,.} | 25
{#,#,#,.,#} | 26
{#,#,#,.,#} | 27
{#,#,#,#,#} | 28
{.,.,.,.,.} | 29
{.,.,.,.,.} | 30
{.,.,.,.,.} | 31
{#,.,.,.,.} | 32
{#,.,#,.,.} | 33
{#,.,#,.,#} | 34
{#,#,#,#,#} | 35

Заметим, что каждый ключ/замок состоит из 7 идущих подряд строк, причем у замка в первой из них (с номером 7i + 1) весь массив заполнен. Преобразуем все объекты в массивы из 5 "высот" штифтов и выясним, ключ это или замок:

, obj AS (
  SELECT
    ARRAY[ -- подсчитываем "высоту" каждого столбца
      sum((line[1] = '#')::integer) - 1
    , sum((line[2] = '#')::integer) - 1
    , sum((line[3] = '#')::integer) - 1
    , sum((line[4] = '#')::integer) - 1
    , sum((line[5] = '#')::integer) - 1
    ] pins
  , bool_or(n % 7 = 1 AND line = '{#,#,#,#,#}') is_lock
  FROM
    src
  GROUP BY
    (n - 1) / 7 -- группируем по 7 строк
)

pins        | is_lock
{1,2,0,5,3} | t
{3,0,2,0,1} | f
{5,0,2,1,3} | f
{0,5,3,4,3} | t
{4,3,4,0,2} | f

Совместим все возможные пары замок/ключ, подсчитав суммарную "высоту" в каждой позиции:

SELECT
  (
    SELECT
      array_agg(lp + kp) -- массив с суммарной "высотой" в каждом столбце
    FROM
      unnest(l.pins, k.pins) T(lp, kp)
  ) sum
FROM
  obj l
JOIN
  obj k
    ON l.is_lock AND
    NOT k.is_lock

sum
{4,2,2,5,4}
{6,2,2,6,6}
{5,5,4,5,5}
{3,5,5,4,4}
{5,5,5,5,6}
{4,8,7,4,5}

Остается лишь подсчитать количество вариантов, где значение для каждого столбца не превосходит 5. Для этого воспользуемся условным агрегатом count(*) FILTER(WHERE 5 >= ALL(sum)), и полный текст запроса примет следующий вид:

WITH src AS (
  SELECT
    regexp_split_to_array(line[1], '') line
  , n
  FROM
    regexp_matches(
      $$
#####
.####
.####
.####
.#.#.
.#...
.....

#####
##.##
.#.##
...##
...#.
...#.
.....

.....
#....
#....
#...#
#.#.#
#.###
#####

.....
.....
#.#..
###..
###.#
###.#
#####

.....
.....
.....
#....
#.#..
#.#.#
#####
$$
    , '(\S+)'
    , 'g'
    )
      WITH ORDINALITY T(line, n)
)
, obj AS (
  SELECT
    ARRAY[ -- подсчитываем "высоту" каждого столбца
      sum((line[1] = '#')::integer) - 1
    , sum((line[2] = '#')::integer) - 1
    , sum((line[3] = '#')::integer) - 1
    , sum((line[4] = '#')::integer) - 1
    , sum((line[5] = '#')::integer) - 1
    ] pins
  , bool_or(n % 7 = 1 AND line = '{#,#,#,#,#}') is_lock
  FROM
    src
  GROUP BY
    (n - 1) / 7 -- группируем по 7 строк
)
SELECT
  count(*) FILTER(WHERE 5 >= ALL(sum)) -- "высоты" всех столбцов не превосходят 5
FROM
  (
    SELECT
      (
        SELECT
          array_agg(lp + kp) -- массив с суммарной "высотой" в каждом столбце
        FROM
          unnest(l.pins, k.pins) T(lp, kp)
      ) sum
    FROM
      obj l
    JOIN
      obj k
        ON l.is_lock AND
        NOT k.is_lock
  ) T;

Запустив запрос на реальных данных, получим результат всего за 300мс:

На этом все задачи Advent of Code 2024 решены!

А мы научились использовать PostgreSQL для некоторых алгоритмических задач, которые могут вам встретиться и на практике. Часть из использованных нами приемов как раз была «заточена» на «профильную» для SQL простую обработку больших объемов однотипных данных, другие — позволяют не слишком сложно избавить приложение от «перекачивания» трафика с базы на бизнес‑логику.

В общем, учите матчасть!

SQL HowTo: простой финал с агрегатами (Advent of Code 2024, Day 25: Code Chronicle)