SQL HowTo: генерируем строкочисла (Advent of Code 2025, Day 2: Gift Shop)

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

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

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

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

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

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

• Решение Day 4: Printing Department ("запекаем" шаг рекурсии)

• Решение Day 5: Cafeteria (проверяем и объединяем диапазоны)

• Решение Day 6: Trash Compactor (математика вдоль и поперек)

• Решение Day 7: Laboratories (трассировка и подсчет путей)

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

11-22,95-115,998-1012,1188511880-1188511890,222220-222224,
1698522-1698528,446443-446449,38593856-38593862,565653-565659,
824824821-824824827,2121212118-2121212124

Часть 1

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

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

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

• aa = 11 * a

• abab = 101 * ab

• abcabc = 1001 * abc

• ...

Сначала разберем ввод уже знакомой по вчерашней задаче функцией regexp_matches, причем наличие или отсутствие переводов строк нас тут совсем не интересует:

  regexp_matches($$
11-22,95-115,998-1012,1188511880-1188511890,222220-222224,
1698522-1698528,446443-446449,38593856-38593862,565653-565659,
824824821-824824827,2121212118-2121212124
$$, '(\d+)-(\d+)', 'g') ids

Затем определим, сколько нулей может быть в множителе: не менее округленной вверх половины длины первого идентификатора, но не более округленной вниз половины длины второго:

ceil(length(ids[1]) * 0.5) <= zeroes <= floor(length(ids[2]) * 0.5)

Сгенерируем все эти значения множителя функцией generate_series, вычислив сразу и min/max границы диапазона, для которого он подойдет - это все числа соответствующей ему [четной] длины:

10     <= a   * 11   <= 99
1000   <= ab  * 101  <= 9999
100000 <= abc * 1001 <= 999999
...

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

Можно было бы сразу оперировать на уровне чисел со степенями 10, но - зачем?..

Остался последний шаг - непосредственно сгенерировать искомые идентификаторы с шагом множителя в каждом из диапазонов и посчитать их сумму.

Опять же, сумму чисел в интервале, кратных конкретному множителю, можно представить как сумму арифметической прогрессии:

abcabc + abdabd + abeabe + ...= 1001 * (abc + abd + abe + ...) = 1001 * ((abc + 0) + (abc + 1) + (abc + 2) + ...) = 1001 * (abc * N + sum(0, N - 1))

Можно, да, но современных мощностей хватает, чтобы обойтись и без этого.

Проверим себя, сгенерировав все подходящие под условия числа, воспользовавшись возможностью указывать "шаг" для generate_series:

SELECT
  *
--  sum(num)
FROM
  regexp_matches($$
11-22,95-115,998-1012,1188511880-1188511890,222220-222224,
1698522-1698528,446443-446449,38593856-38593862,565653-565659,
824824821-824824827,2121212118-2121212124
$$, '(\d+)-(\d+)', 'g') ids
, LATERAL (
    SELECT
      ('1' || repeat('0', zeroes::integer - 1) || '1')::bigint mul -- множитель
    , ('1' || repeat('0', zeroes::integer * 2 - 1))::bigint min    -- 10..0
    , (repeat('9', zeroes::integer * 2))::bigint max               -- 9..99
    FROM
      generate_series(
        ceil(length(ids[1]) * 0.5)
      , floor(length(ids[2]) * 0.5)
      ) zeroes -- сколько нулей может быть в множителе
  ) T
, generate_series(
    ceil(
      greatest(ids[1]::double precision, min) -- граница интервала справа
    / mul)::bigint * mul                      -- первое кратное на интервале
  , least(ids[2]::bigint, max)                -- граница интервала справа
  , mul                                       -- шаг по множителю
  ) num;

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

 ids                    |  mul   |  min       |  max       |  num
{11,22}                 |     11 |         10 |         99 |         11
{11,22}                 |     11 |         10 |         99 |         22
{95,115}                |     11 |         10 |         99 |         99
{998,1012}              |    101 |       1000 |       9999 |       1010
{1188511880,1188511890} | 100001 | 1000000000 | 9999999999 | 1188511885
{222220,222224}         |   1001 |     100000 |     999999 |     222222
{446443,446449}         |   1001 |     100000 |     999999 |     446446
{38593856,38593862}     |  10001 |   10000000 |   99999999 |   38593859

Для решения задачи остается лишь заменить SELECT * на SELECT sum(num).

Часть 2

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

SELECT
  mul
, ('1' || repeat('0', digits - 1))::bigint min
, (repeat('9', digits))::bigint max
FROM
  generate_series(
    length(ids[1])
  , length(ids[2])
  ) digits -- сколько цифр может быть в идентификаторе
, LATERAL (
    SELECT
      (repeat(repeat('0', len - 1) || '1', digits / len))::bigint mul
    FROM
      generate_series(1, digits - 1) len
    WHERE
      digits % len = 0 -- количество цифр должно делиться нацело на группы по len
  ) T

Тут мы удачно пользуемся тем фактом, что преобразование строки в число само отбрасывает лидирующие нули: '001001'::bigint -> 1001.

Проверим, что там сгенерировалось:

SELECT
  *
--  sum(DISTINCT num)
FROM
  regexp_matches($$
11-22,95-115,998-1012,1188511880-1188511890,222220-222224,
1698522-1698528,446443-446449,38593856-38593862,565653-565659,
824824821-824824827,2121212118-2121212124
$$, '(\d+)-(\d+)', 'g') ids
, LATERAL (
    SELECT
      mul
    , ('1' || repeat('0', digits - 1))::bigint min
    , (repeat('9', digits))::bigint max
    FROM
      generate_series(
        length(ids[1])
      , length(ids[2])
      ) digits
    , LATERAL (
        SELECT
          (repeat(repeat('0', len - 1) || '1', digits / len))::bigint mul
        FROM
          generate_series(1, digits - 1) len
        WHERE
          digits % len = 0
      ) T
  ) T
, generate_series(
    ceil(greatest(ids[1]::double precision, min) / mul)::bigint * mul
  , least(ids[2]::bigint, max)
  , mul
  ) num;

 ids                    |  mul      |  min       |  max       |  num
{11,22}                 |        11 |         10 |         99 |         11
{11,22}                 |        11 |         10 |         99 |         22
{95,115}                |        11 |         10 |         99 |         99
{95,115}                |       111 |        100 |        999 |        111
{998,1012}              |       111 |        100 |        999 |        999
{998,1012}              |       101 |       1000 |       9999 |       1010
{1188511880,1188511890} |    100001 | 1000000000 | 9999999999 | 1188511885
{222220,222224}         |    111111 |     100000 |     999999 |     222222
{222220,222224}         |     10101 |     100000 |     999999 |     222222
{222220,222224}         |      1001 |     100000 |     999999 |     222222
{446443,446449}         |      1001 |     100000 |     999999 |     446446
{38593856,38593862}     |     10001 |   10000000 |   99999999 |   38593859
{565653,565659}         |     10101 |     100000 |     999999 |     565656
{824824821,824824827}   |   1001001 |  100000000 |  999999999 |  824824824
{2121212118,2121212124} | 101010101 | 1000000000 | 9999999999 | 2121212121

Обратите внимание, что число 222222 попало в нашу выборку аж 3 раза - 6 x '2', 3 x '22', 2 x '222'. Поэтому при суммировании надо не забыть исключить дубли с помощью sum(DISTINCT num).

На сегодня - все!