15.12.2025 06:10
Kilor 0 3200 Источник

Осторожно, спойлеры! Не читайте, пока хотите решить задачу самостоятельно.

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

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

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

Advent of Code 2025, Day 5: Cafeteria

--- День 5: Кафетерий ---

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

Из кухни доносится шум. «Такими темпами у нас совсем не останется времени, чтобы повесить венки в столовой!» Непреклонные в своем стремлении, вы отправляетесь на место происшествия.

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

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

База данных работает с идентификаторами ингредиентов. Она состоит из списка диапазонов идентификаторов свежих ингредиентов, пустой строки и списка доступных идентификаторов ингредиентов. Например:

3-5
10-14
16-20
12-18

1
5
8
11
17
32

Диапазоны идентификаторов свежих ингредиентов являются включающими: диапазон 3-5 означает, что идентификаторы ингредиентов 3, 4, и 5являются свежими. Диапазоны также могут перекрываться; идентификатор ингредиента считается свежим, если он находится в любом из диапазонов.

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

  • Ингредиент с идентификатором 1 испорчен, поскольку не попадает ни в один из диапазонов.

  • Ингредиент с идентификатором 5считается свежим, поскольку он находится в заданном диапазоне 3-5.

  • Ингредиент с идентификатором 8 испорчен.

  • Ингредиент с идентификатором 11считается свежим, поскольку он находится в заданном диапазоне 10-14.

  • Ингредиент с идентификатором 17считается свежим, поскольку он попадает в диапазон значений 16-20, а также в диапазон 12-18.

  • Ингредиент с идентификатором 32 испорчен.

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

Обработайте файл базы данных из новой системы управления запасами. Сколько из имеющихся ингредиентов являются свежими?

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

Эльфы начинают выносить испорченные продукты в мусоропровод в задней части кухни.

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

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

3-5
10-14
16-20
12-18

Идентификаторы ингредиентов в этих диапазонах считаются свежими, это 3, 4, 5, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19и 20. Таким образом, в этом примере диапазоны идентификаторов свежих ингредиентов содержат в общей сложности  14 штук.

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

Часть 1

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

Кроме того, значения идентификаторов хоть и велики, но не слишком, чтобы не уместиться в тип bigint - им и воспользуемся:

  • выделим с помощью regexp_matches все имеющиеся диапазоны и идентификаторы

  • а потом просто подсчитаем количество идентификаторов, для которых есть хотя бы один подходящий диапазон

WITH src AS (
  SELECT $$
3-5
10-14
16-20
12-18

1
5
8
11
17
32
$$
)
, rngs AS (
  SELECT
    ids[1]::bigint src -- определяем диапазоны
  , ids[2]::bigint dst
  FROM
    regexp_matches((TABLE src), '(\d+)-(\d+)', 'g') ids
)
, ids AS (
  SELECT
    id[1]::bigint -- определяем идентификаторы
  FROM
    regexp_matches((TABLE src), '[\r\n](\d+)(?=[\r\n]|$)', 'g') id
)
SELECT
  count(*)
FROM
  ids
WHERE
  EXISTS( -- есть хотя бы один подходящий диапазон
    SELECT
      NULL
    FROM
      rngs
    WHERE
      id BETWEEN src AND dst -- идентификатор в диапазоне
    LIMIT 1
  );

Часть 2

Решение более сложной задачи на определение суммарной длины всех диапазонов с учетом возможных пересечений с использованием возможностей PostgreSQL оказывается даже короче решения первой части:

  • преобразуем все входные диапазоны в тип int8range, включающие свои границы

  • воспользуемся функцией range_agg, чтобы получить мультидиапазон, представляющий объединение диапазонов, входящих в него

  • "разворачиваем" мультидиапазон в "обычные" диапазоны функцией unnest

  • осталось только подсчитать сумму длин (разность значений верхней и нижней границ, upper - lower) каждого диапазона

SELECT
  sum(upper(rng) - lower(rng)) -- сумма длин
FROM
  (
    SELECT
      unnest(range_agg(rng)) rng -- "разворачиваем" мультидиапазон-объединение
    FROM
      (
        SELECT
          int8range(       -- диапазон из bigint-значений
            ids[1]::bigint
          , ids[2]::bigint
          , '[]'           -- включение границ диапазона
          ) rng
        FROM
          regexp_matches($$
3-5
10-14
16-20
12-18
          $$, '(\d+)-(\d+)', 'g') ids
      ) rngs
  ) T;

Если посмотреть на исходном примере, то пошагово это будет выглядеть так:

 rng
int8range
[3,6)     -- диапазон [3,5] в целых числах равен [3,6), без включения правой границы
[10,15)
[16,21)
[12,19)

После "разворачивания" объединенного диапазона получим:

 rng
int8range
[3,6)      -- длина 3
[10,21)    -- длина 11

Комментарии (0)