В этой челлендж-серии статей попробуем использовать 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 6: Guard Gallivant (рекурсивные циклы и их контроль)

• Решение Day 7: Bridge Repair ("экспоненциальная" рекурсия)

• Решение Day 11: Plutonian Pebbles (агрегация внутри рекурсии)

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

190: 10 19
3267: 81 40 27
83: 17 5
156: 15 6
7290: 6 8 6 15
161011: 16 10 13
192: 17 8 14
21037: 9 7 18 13
292: 11 6 16 20

Часть 1

1. Сначала разобъем входящий текст, уже привычными регулярными выражениями, в список уравнений, автоматически присвоив каждому выражению уникальный номер с помощью WITH ORDINALITY.

2. Для каждого из них определим количество участвующих чисел - соответственно, позиций операторов будет на 1 меньше.

3. Сгенерируем набор сразу всех возможных комбинаций расстановки знаков - чисел [0 .. 2^N-1] - тогда значение бита в каждой из позиций каждого из чисел означает установку в соответствующей позиции + (для 0) или * (для 1).

4. Рекурсивно пошагово вычислим значение выражения в соответствии с комбинацией.

5. Если нашлась с помощью bool_or хотя бы одна комбинация, дающая целевое значение для конкретного выражения (сгруппируем их оконной функцией по DISTINCT ON(id)) - суммируем его в результат.

SELECT
  sum(res) FILTER(WHERE cond) -- суммируем только значения, для которых нашлась комбинация
FROM
  (
    SELECT DISTINCT ON(id) -- "схлапываем" по ID выражения
      res
    , bool_or(v = res) OVER(PARTITION BY id) cond -- получено ли среди всех комбинаций целевое значение
    FROM
      (
        SELECT
          id                                            -- ID уравнения
        , line[1]::numeric res                          -- целевой результат
        , string_to_array(line[2], ' ')::numeric[] expr -- массив значений
        FROM
          regexp_matches($$
190: 10 19
3267: 81 40 27
83: 17 5
156: 15 6
7290: 6 8 6 15
161011: 16 10 13
192: 17 8 14
21037: 9 7 18 13
292: 11 6 16 20
$$
          , '(\d+):\s([^\r\n]*?)[\r\n]+'
          , 'g'
          )
            WITH ORDINALITY T(line, id) -- разбиваем на строки с автонумерацией
      ) src
    , array_length(expr, 1) ln                         -- запомним длину массива
    , generate_series(0, (2 ^ (ln - 1))::bigint - 1) n -- значения [0 .. 2^N-1]
    , LATERAL (
        WITH RECURSIVE r AS (
          SELECT
            0 i
          , expr[1] v
        UNION ALL
          SELECT
            i + 1
          , CASE
              WHEN n & (1 << i) = 0 THEN v + expr[i + 2] -- если бит погашен, складываем
              ELSE v * expr[i + 2]                       -- если установлен - умножаем
            END
          FROM
            r
          WHERE
            i < ln - 1
        )
        SELECT
          v -- результат после последнего шага
        FROM
          r
        ORDER BY
          i DESC
        LIMIT 1
      ) calc
  ) T;

Итого, при 850 выражениях и 292K числах вычисления заняли чуть меньше 13 секунд:

Часть 2

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

1. Заметим, что все три оператора (+, * и ||) заведомо не уменьшают (но могут и не увеличивать в случае * 1) уже вычисленное левее значение. А это значит, что нам незачем вычислять до конца "вообще все возможные" комбинации - достаточно вычислять лишь до непревышения целевого значения.

2. Воспользуемся внутри рекурсии возможностью "размножения строк" с помощью комбинации unnest(ARRAY[...]), где в массив поместим варианты применения каждого из трех доступных операторов. Таким образом, количество строк на каждом шаге рекурсии будет "ветвиться", увеличиваясь экспоненциально, - если бы не ограничение из п.1.

3. Если на последнем шаге рекурсии мы получили целевое значение хоть по какой-то из "веток" - вернем эту запись. А если ни одной такой не нашлось, то INNER JOIN (он же ,) просто уберет нам такое выражение из итоговой выборки.

SELECT
  sum(res)
FROM
  (
    SELECT
      line[1]::numeric res
    , string_to_array(line[2], ' ')::numeric[] expr
    FROM
      regexp_matches($$
190: 10 19
3267: 81 40 27
83: 17 5
156: 15 6
7290: 6 8 6 15
161011: 16 10 13
192: 17 8 14
21037: 9 7 18 13
292: 11 6 16 20
$$
      , '(\d+):\s([^\r\n]*?)[\r\n]+'
      , 'g'
      ) line
  ) src
, array_length(expr, 1) ln
, LATERAL ( -- если внутри не нашлось подходящей записи, то и выражение "пропадет"
    WITH RECURSIVE r AS (
      SELECT
        0 i
      , expr[1] v
    UNION ALL
      SELECT
        i + 1
      , unnest(ARRAY[ -- "размножение" строк в рекурсии
          v + expr[i + 2]
        , v * expr[i + 2]
        , (v::text || expr[i + 2]::text)::numeric
        ])
      FROM
        r
      WHERE
        i < ln - 1 AND
        v <= res -- ограничиваем целевым значением
    )
    SELECT
      *                      -- возвращаем запись ...
    FROM
      r
    WHERE
      (i, v) = (ln - 1, res) -- ... если дошли до последнего шага и получили целевое значение
    LIMIT 1
  ) calc;

Несмотря на существенно возросшее количество вариантов, нам удалось вычислить решение за 47 секунд: