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

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

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

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

Advent of Code 2024, Day 7: Bridge Repair

--- День 7: Ремонт моста ---

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

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

Вы спрашиваете, сколько времени это займет; инженеры говорят вам, что нужны только окончательные калибровки, но несколько молодых слонов играли неподалеку и украли все операторы из их уравнений калибровки! Они могли бы закончить калибровки, если бы только кто-то мог определить, какие тестовые значения могут быть получены путем помещения любой комбинации операторов в их уравнения калибровки (ваши входные данные для головоломки).

Например:

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

Каждая строка представляет собой одно уравнение. Тестовое значение появляется перед двоеточием в каждой строке; ваша задача — определить, можно ли объединить оставшиеся числа с операторами для получения тестового значения.

Операторы всегда оцениваются слева направо, а не в соответствии с правилами приоритета. Более того, числа в уравнениях нельзя переставлять. Заглянув в джунгли, можно увидеть слонов, держащих два разных типа операторов: сложить (+) и умножить (*).

Только три из приведенных выше уравнений можно сделать истинными, вставив операторы:

190: 10 19имеет только одну позицию, которая принимает оператор: между 10и 19. Выбор +даст 29, но выбор *даст тестовое значение ( 10 * 19 = 190).
3267: 81 40 27имеет две позиции для операторов. Из четырех возможных конфигураций операторов, две заставляют правую сторону соответствовать тестовому значению: 81 + 40 * 27и 81 * 40 + 27обе равны 3267(при оценке слева направо)!
292: 11 6 16 20можно решить только одним способом: 11 + 6 * 16 + 20.

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

Определите, какие уравнения могли бы быть верными. Каков их общий результат калибровки?

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

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

Оператор конкатенации (||) объединяет цифры из левого и правого входов в одно число. Например, 12 || 345станет 12345. Все операторы по-прежнему оцениваются слева направо.

Теперь, помимо трех уравнений, которые можно сделать истинными, используя только сложение и умножение, в приведенном выше примере есть еще три уравнения, которые можно сделать истинными, вставив операторы:

156: 15 6можно сделать истинным с помощью одной конкатенации: 15 || 6 = 156.
7290: 6 8 6 15можно сделать истинным, используя 6 * 8 || 6 * 15.
192: 17 8 14можно сделать истинным, используя 17 || 8 + 14.

Суммирование всех шести тестовых значений (трех, которые можно было получить ранее, используя только +, и *новых трех, которые теперь можно получить, также используя ||) дает новый общий результат калибровки 11387.

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

Часть 1

Сначала разобъем входящий текст, уже привычными регулярными выражениями, в список уравнений, автоматически присвоив каждому выражению уникальный номер с помощью WITH ORDINALITY.
Для каждого из них определим количество участвующих чисел - соответственно, позиций операторов будет на 1 меньше.
Сгенерируем набор сразу всех возможных комбинаций расстановки знаков - чисел [0 .. 2^N-1] - тогда значение бита в каждой из позиций каждого из чисел означает установку в соответствующей позиции + (для 0) или * (для 1).
Рекурсивно пошагово вычислим значение выражения в соответствии с комбинацией.
Если нашлась с помощью 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) уже вычисленное левее значение. А это значит, что нам незачем вычислять до конца "вообще все возможные" комбинации - достаточно вычислять лишь до непревышения целевого значения.
Воспользуемся внутри рекурсии возможностью "размножения строк" с помощью комбинации unnest(ARRAY[...]), где в массив поместим варианты применения каждого из трех доступных операторов. Таким образом, количество строк на каждом шаге рекурсии будет "ветвиться", увеличиваясь экспоненциально, - если бы не ограничение из п.1.
Если на последнем шаге рекурсии мы получили целевое значение хоть по какой-то из "веток" - вернем эту запись. А если ни одной такой не нашлось, то 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 секунд:

SQL HowTo: «экспоненциальная» рекурсия (Advent of Code 2024, Day 7: Bridge Repair)