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

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

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

• Решение Day 1: Secret Entrance (немного математики)

• Решение Day 2: Gift Shop (генерируем строкочисла)

• Решение Day 3: Lobby (от частностей к рекурсии)

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

987654321111111
811111111111119
234234234234278
818181911112111

987654321111111
811111111111119
234234234234278
818181911112111

Часть 1

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

• найти максимальную "первую" цифру, исключив последнюю позицию (иначе где же будет "вторая"?)

• найти максимальную "вторую" цифру из расположенных правее "первой"

Сначала преобразуем ввод в массивы значений каждого из аккумуляторов:

SELECT
  regexp_split_to_array(blk[1], '')::integer[] acc
FROM
  regexp_matches($$
987654321111111
811111111111119
234234234234278
818181911112111
  $$, '\d+', 'g') blk

 acc
{9,8,7,6,5,4,3,2,1,1,1,1,1,1,1}
{8,1,1,1,1,1,1,1,1,1,1,1,1,1,9}
{2,3,4,2,3,4,2,3,4,2,3,4,2,7,8}
{8,1,8,1,8,1,9,1,1,1,1,2,1,1,1}

Теперь, пользуясь "разворотом" массива с нумерацией unnest(...) WITH ORDINALITY, последовательно найдем позиции сначала первой, а затем и второй цифр:

, LATERAL (
    SELECT
      p1
    FROM
      unnest(acc)
        WITH ORDINALITY T(digit, p1)
    WHERE
      p1 < array_length(acc, 1) -- "первая" цифра не должна стоять в последней позиции
    ORDER BY
      digit DESC                -- цифра должна быть максимальная из возможных
    LIMIT 1
  ) p1
, LATERAL (
    SELECT
      p2
    FROM
      unnest(acc)
        WITH ORDINALITY T(digit, p2)
    WHERE
      p2 > p1                   -- "вторая" цифра должна стоять правее уже выбранной "первой"
    ORDER BY
      digit DESC                -- и тоже должна быть максимальна
    LIMIT 1
  ) p2

Осталось только превратить позиции цифр в число:

, LATERAL (
    SELECT acc[p1] * 10 + acc[p2] num -- простая математика
  ) num

 acc                            | p1 | p2 | num
{9,8,7,6,5,4,3,2,1,1,1,1,1,1,1} |  1 |  2 | 98
{8,1,1,1,1,1,1,1,1,1,1,1,1,1,9} |  1 | 15 | 89
{2,3,4,2,3,4,2,3,4,2,3,4,2,7,8} | 14 | 15 | 78
{8,1,8,1,8,1,9,1,1,1,1,2,1,1,1} |  7 | 12 | 92

... и просуммировать для получения итогового результата:

SELECT
  sum(num)
FROM
  (
    SELECT
      regexp_split_to_array(blk[1], '')::integer[] acc
    FROM
      regexp_matches($$
987654321111111
811111111111119
234234234234278
818181911112111
      $$, '\d+', 'g') blk
  ) T
, LATERAL (
    SELECT
      p1
    FROM
      unnest(acc)
        WITH ORDINALITY T(digit, p1)
    WHERE
      p1 < array_length(acc, 1)
    ORDER BY
      digit DESC
    LIMIT 1
  ) p1
, LATERAL (
    SELECT
      p2
    FROM
      unnest(acc)
        WITH ORDINALITY T(digit, p2)
    WHERE
      p2 > p1
    ORDER BY
      digit DESC
    LIMIT 1
  ) p2
, LATERAL (
    SELECT acc[p1] * 10 + acc[p2] num
  ) num;

Часть 2

Во второй части задачи вопрос все тот же, только цифр - 12 вместо 2. Конечно, можно было бы скопипастить много-много раз, но мы воспользуемся рекурсией.

Достаточно заметить, что каждая цифра подчиняется двум условиям:

• стоит правее позиции предыдущей цифры

• не может стоять в позиции "правее", чем оставшаяся часть "хвоста" (то есть, например, в предпоследней позиции, если подобрать надо еще 2 цифры)

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

WITH RECURSIVE arr AS (
  SELECT
    id
  , regexp_split_to_array(blk[1], '')::integer[] acc
  FROM
    regexp_matches($$
987654321111111
811111111111119
234234234234278
818181911112111
    $$, '\d+', 'g')
     WITH ORDINALITY T(blk, id)
)

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

, r AS (
  SELECT
    id
  , acc
  , ARRAY[0::bigint] p -- стартовое состояние массива позиций
  FROM
    arr
UNION ALL
  SELECT
    id
  , acc
  , p || pn
  FROM
    r
  , LATERAL(
      SELECT
        pn
      FROM
        unnest(acc)
          WITH ORDINALITY T(digit, pn)
      WHERE
        pn > p[array_length(p, 1)] AND -- правее предыдущей цифры
        pn <= array_length(acc, 1) + array_length(p, 1) - 12 -- есть место для "хвоста"
      ORDER BY
        digit DESC, pn
      LIMIT 1
    ) T
  WHERE
    array_length(p, 1) <= 12 -- пока не набрали нужное количество цифр
)

Если посмотреть для конкретной строки-блока, будет получаться что-то такое:

id |  acc                            |  p
 3 | {2,3,4,2,3,4,2,3,4,2,3,4,2,7,8} | {0}
 3 | {2,3,4,2,3,4,2,3,4,2,3,4,2,7,8} | {0,3}
 3 | {2,3,4,2,3,4,2,3,4,2,3,4,2,7,8} | {0,3,5}
 3 | {2,3,4,2,3,4,2,3,4,2,3,4,2,7,8} | {0,3,5,6}
 3 | {2,3,4,2,3,4,2,3,4,2,3,4,2,7,8} | {0,3,5,6,7}
 3 | {2,3,4,2,3,4,2,3,4,2,3,4,2,7,8} | {0,3,5,6,7,8}
 3 | {2,3,4,2,3,4,2,3,4,2,3,4,2,7,8} | {0,3,5,6,7,8,9}
 3 | {2,3,4,2,3,4,2,3,4,2,3,4,2,7,8} | {0,3,5,6,7,8,9,10}
 3 | {2,3,4,2,3,4,2,3,4,2,3,4,2,7,8} | {0,3,5,6,7,8,9,10,11}
 3 | {2,3,4,2,3,4,2,3,4,2,3,4,2,7,8} | {0,3,5,6,7,8,9,10,11,12}
 3 | {2,3,4,2,3,4,2,3,4,2,3,4,2,7,8} | {0,3,5,6,7,8,9,10,11,12,13}
 3 | {2,3,4,2,3,4,2,3,4,2,3,4,2,7,8} | {0,3,5,6,7,8,9,10,11,12,13,14}
 3 | {2,3,4,2,3,4,2,3,4,2,3,4,2,7,8} | {0,3,5,6,7,8,9,10,11,12,13,14,15}

Оставим для каждого блока только последнее (самое длинное) состояние найденных позиций, используя DISTINCT ON:

, pos AS (
  SELECT DISTINCT ON(id) -- уникализация по id
    *
  FROM
    r
  ORDER BY
    id                      -- ключ уникализации
  , array_length(p, 1) DESC -- выбираем строку с максимальной длиной массива позиций
)

id |  acc                            |  p
 1 | {9,8,7,6,5,4,3,2,1,1,1,1,1,1,1} | {0,1,2,3,4,5,6,7,8,9,10,11,12}
 2 | {8,1,1,1,1,1,1,1,1,1,1,1,1,1,9} | {0,1,2,3,4,5,6,7,8,9,10,11,15}
 3 | {2,3,4,2,3,4,2,3,4,2,3,4,2,7,8} | {0,3,5,6,7,8,9,10,11,12,13,14,15}
 4 | {8,1,8,1,8,1,9,1,1,1,1,2,1,1,1} | {0,1,3,5,7,8,9,10,11,12,13,14,15}

Осталось только "собрать" цифры (кроме первого 0) в строку с помощью string_agg, скастовать в число и просуммировать результат:

SELECT
  sum(num)
FROM
  pos
, LATERAL (
    SELECT
      string_agg(acc[unnest]::text, '')::bigint num -- "клеим" цифры в число
    FROM
      unnest(p[2:]) -- "разворачиваем" массив без стартового 0
  ) T

Собственно, итоговый запрос принимает такой вид:

WITH RECURSIVE arr AS (
  SELECT
    id
  , regexp_split_to_array(blk[1], '')::integer[] acc
  FROM
    regexp_matches($$
987654321111111
811111111111119
234234234234278
818181911112111
    $$, '\d+', 'g')
     WITH ORDINALITY T(blk, id)
)
, r AS (
  SELECT
    id
  , acc
  , ARRAY[0::bigint] p
  FROM
    arr
UNION ALL
  SELECT
    id
  , acc
  , p || pn
  FROM
    r
  , LATERAL(
      SELECT
        pn
      FROM
        unnest(acc)
          WITH ORDINALITY T(digit, pn)
      WHERE
        pn > p[array_length(p, 1)] AND
        pn <= array_length(acc, 1) + array_length(p, 1) - 12
      ORDER BY
        digit DESC, pn
      LIMIT 1
    ) T
  WHERE
    array_length(p, 1) <= 12
)
, pos AS (
  SELECT DISTINCT ON(id)
    *
  FROM
    r
  ORDER BY
    id, array_length(p, 1) DESC
)
SELECT
  sum(num)
FROM
  pos
, LATERAL (
    SELECT
      string_agg(acc[unnest]::text, '')::bigint num
    FROM
      unnest(p[2:])
  ) T;

На реальных данных запрос укладывается в 115мс, при этом больше половины времени тратится на разворот и нумерацию массива внутри рекурсии:

Bonus

Ускорить вычисления более чем вдвое, до 50мс, мы сможем, если заметим, что при каждом развороте массива условие на позицию следующей цифры отбрасывало в среднем по 77 записей, оставляя для выбора максимума только лишь по 23 - то есть 3/4 массива нам в общем-то и не нужны.

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

SELECT
  p[array_length(p, 1)] + i pn
FROM
  unnest(acc[
    p[array_length(p, 1)] + 1 : array_length(acc, 1) + array_length(p, 1) - 12
  ]) -- слайс
    WITH ORDINALITY T(digit, i)
ORDER BY
  digit DESC, i
LIMIT 1