SQL HowTo: динамическое программирование (Advent of Code 2024, Day 19: Linen Layout)

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

• Решение Day 9: Disk Fragmenter (оптимизируем рекурсию)

• Решение Day 10: Hoof It (поиск "в ширину" внутри цикла)

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

• Решение Day 12: Garden Groups (волновой алгоритм и подсчет границ)

• Решение Day 13: Claw Contraption (пошагово решаем СЛУ)

• Решение Day 14: Restroom Redoubt (находим "елочку" с помощью центра масс)

• Решение Day 15: Warehouse Woes (играем в сокобан с помощью json-карты и типа point)

• Решение Day 16: Reindeer Maze (укрощаем рекурсию в лабиринте)

• Решение Day 17: Chronospatial Computer (подбираем значение ветвлением)

• Решение Day 18: RAM Run (поиск пути и дихотомия)

• Решение Day 19: Linen Layout (динамическое программирование)

• Решение Day 20: Race Condition (кратчайший путь "туда и обратно" и его самосоединение)

• Решение Day 21: Keypad Conundrum (моделирование против подсчета)

---

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

Advent of Code 2024, Day 19: Linen Layout

--- День 19: Раскладка белья ---

Сегодня Историки отведут вас к горячим источникам на острове Гир! Очень подозрительно, что абсолютно все идет не так, когда они начинают свой тщательный поиск на обширном поле спиралей.

Может быть, это ваш шанс посетить онсэн по соседству? Есть только один способ узнать.

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

Каждое полотенце в этом онсэне отмечено узором из цветных полос. Существует всего несколько узоров, но для любого конкретного узора персонал может предоставить вам столько полотенец с этим узором, сколько вам нужно. Каждая полоса может быть белой (w), синей (u), черной (b), красной (r) или зеленой (g). Таким образом, полотенце с узором ggr будет иметь зеленую полосу, зеленую полосу, а затем красную полосу, именно в таком порядке. (Вы не можете изменить узор, перевернув полотенце вверх дном, так как это приведет к тому, что логотип онсэна будет смотреть в неправильном направлении.)

Официальный эксперт по брендингу Онсэнов составил список дизайнов (каждый представляет собой длинную последовательность цветов полос), которые они хотели бы иметь возможность отображать. Вы можете использовать любые полотенца, но все полосы на полотенцах должны точно соответствовать желаемому дизайну. Таким образом, чтобы отобразить дизайн rgrgr, вы можете использовать два rg полотенца и r полотенце, или rgr полотенце и gr полотенце или даже одно большое rgrgr полотенце (предполагая, что такие узоры для полотенец действительно доступны).

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

r, wr, b, g, bwu, rb, gb, br

brwrr
bggr
gbbr
rrbgbr
ubwu
bwurrg
brgr
bbrgwb

Первая строка указывает доступные образцы полотенец; в этом примере в онсэне есть неограниченное количество полотенец с одной красной полосой (r), неограниченное количество полотенец с белой полосой, а затем с красной полосой (wr) и т. д.

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

Не все дизайны будут возможны с имеющимися полотенцами. В приведенном выше примере дизайны возможны или невозможны следующим образом:

• brwrr можно сделать из br полотенца, затем из wr полотенца, и наконец из r полотенца.

• bggr можно сделать из b полотенца, двух g полотенец и еще одного r полотенца.

• gbbr можно сделать с gb полотенцем, а потом с br полотенцем.

• rrbgbr можно сделать с помощью r, rb, g и br.

• ubwu невозможно.​

• bwurrg можно сделать с помощью bwu, r, r и g.

• brgr можно сделать с помощью br, g и r.

• bbrgwb невозможно.​

В этом примере 6 из восьми дизайнов возможны с имеющимися узорами полотенец.

Чтобы попасть в онсэн как можно скорее, внимательно изучите список образцов полотенец и желаемых дизайнов. Сколько дизайнов возможно?

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

Персоналу не очень нравятся некоторые из предложенных вами вариантов размещения полотенец. Чтобы избежать бесконечного цикла перестановки полотенец, может быть, вам стоит просто предоставить им все возможные варианты.

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

brwrr можно сделать двумя способами: b, r, wr, r или br, wr, r.

bggr можно сделать только с b, g, g, и r.

gbbr можно приготовить 4 разными способами:

• g, b, b, r

• g, b, br

• gb, b, r

• gb, br

rrbgbr можно приготовить 6 различными способами:

• r, r, b, g, b, r

• r, r, b, g, br

• r, r, b, gb, r

• r, rb, g, b, r

• r, rb, g, br

• r, rb, gb, r

bwurrg можно сделать только с bwu, r, r и g.

brgr можно сделать двумя способами: b, r, g, r или br, g, r.

ubwu и bbrgwb по-прежнему невозможны.

Суммируя все способы, которыми полотенца в этом примере можно расположить в желаемых узорах, получаем 16 (2 + 1 + 4 + 6 + 1 + 2).

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

Часть 1

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

WITH src AS (
  SELECT
    string_to_array((array_agg(line[1]) FILTER(WHERE i = 1))[1], ', ') towels
  , array_agg(line[1]) FILTER(WHERE i > 1) designs
  FROM
    regexp_matches($$
r, wr, b, g, bwu, rb, gb, br

brwrr
bggr
gbbr
rrbgbr
ubwu
bwurrg
brgr
bbrgwb
$$
  , '([wubrg ,]+)'
  , 'g')
    WITH ORDINALITY T(line, i)
)

towels                  | designs
{r,wr,b,g,bwu,rb,gb,br} | {brwrr,bggr,gbbr,rrbgbr,ubwu,bwurrg,brgr,bbrgwb}

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

SELECT
  count(*)
FROM
  src
, unnest(designs) design -- получаем список дизайнов
, length(design) ln      -- для каждого кэшируем длину
, LATERAL (
    ... -- тут мы проверяем возможность конкретного дизайна
  ) T;

Осталось лишь решить вопрос самой возможности существования раскладки, дающей каждый конкретный дизайн. Для начала, давайте переведем задачу из плоскости операций со строками в операции над числами.

Каждый вариант полотенца, которое может быть положено в позиции pos, означает возможность перехода из нее в позицию pos + length(towel):

rrbgbr
r
 r
 rb
  b
   g
   gb
    b
    br
     r

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

, matches AS (
  SELECT
    pos                                    -- для каждой позиции
  , array_agg(pos + length(towel)) nextpos -- получаем список следующих доступных
  FROM
    generate_series(1, ln) pos
  , unnest(towels) towel
  WHERE
    substr(design, pos) ^@ towel           -- starts_with
  GROUP BY
    1
)

design | ln | pos | nextpos
brwrr  |  5 |   1 | {2,3}
brwrr  |  5 |   2 | {3}
brwrr  |  5 |   3 | {5}
brwrr  |  5 |   4 | {5}
brwrr  |  5 |   5 | {6}
bggr   |  4 |   1 | {2}
bggr   |  4 |   2 | {3}
bggr   |  4 |   3 | {4}
bggr   |  4 |   4 | {5}
gbbr   |  4 |   1 | {2,3}
gbbr   |  4 |   2 | {3}
gbbr   |  4 |   3 | {4,5}
gbbr   |  4 |   4 | {5}
rrbgbr |  6 |   1 | {2}
rrbgbr |  6 |   2 | {3,4}
rrbgbr |  6 |   3 | {4}
rrbgbr |  6 |   4 | {5,6}
rrbgbr |  6 |   5 | {6,7}
rrbgbr |  6 |   6 | {7}
ubwu   |  4 |   2 | {3,5}
bwurrg |  6 |   1 | {2,4}
bwurrg |  6 |   4 | {5}
bwurrg |  6 |   5 | {6}
bwurrg |  6 |   6 | {7}
brgr   |  4 |   1 | {2,3}
brgr   |  4 |   2 | {3}
brgr   |  4 |   3 | {4}
brgr   |  4 |   4 | {5}
bbrgwb |  6 |   1 | {2}
bbrgwb |  6 |   2 | {3,4}
bbrgwb |  6 |   3 | {4}
bbrgwb |  6 |   4 | {5}
bbrgwb |  6 |   6 | {7}

Соответственно, возможность раскладки конкретного дизайна указанным набором полотенец эквивалентна задаче возможности прохода по графу из вершины 1 в вершину ln + 1, а это мы уже неоднократно делали в предыдущих задачах:

    , r AS (
      SELECT
        0 i
      , ARRAY[1] success              -- набор уже доступных позиций
    UNION ALL
      SELECT
        i + 1
      , nextpos
      FROM
        r
      , LATERAL (
          SELECT
            array_agg(unnest) nextpos -- набор всех достижимых "следующих" позиций
          FROM
            matches
          , unnest(nextpos)
          WHERE
            pos = ANY(success)
        ) T
      WHERE
        (ln + 1) <> ALL(success)      -- продолжаем, пока не достигли конечной позиции
    )
    SELECT
      TRUE
    FROM
      r
    WHERE
      (ln + 1) = ANY(success)         -- находим запись с достигнутой целевой позицией
    LIMIT 1

Соберем все вместе:

WITH src AS (
  SELECT
    string_to_array((array_agg(line[1]) FILTER(WHERE i = 1))[1], ', ') towels
  , array_agg(line[1]) FILTER(WHERE i > 1) designs
  FROM
    regexp_matches($$
r, wr, b, g, bwu, rb, gb, br

brwrr
bggr
gbbr
rrbgbr
ubwu
bwurrg
brgr
bbrgwb
$$
  , '([wubrg ,]+)'
  , 'g')
    WITH ORDINALITY T(line, i)
)
SELECT
  count(*)
FROM
  src
, unnest(designs) design -- получаем список дизайнов
, length(design) ln      -- для каждого кэшируем длину
, LATERAL (
    WITH RECURSIVE matches AS (
      SELECT
        pos                                    -- для каждой позиции
      , array_agg(pos + length(towel)) nextpos -- получаем список следующих доступных
      FROM
        generate_series(1, ln) pos
      , unnest(towels) towel
      WHERE
        substr(design, pos) ^@ towel           -- starts_with
      GROUP BY
        1
    )
    , r AS (
      SELECT
        0 i
      , ARRAY[1] success              -- набор уже доступных позиций
    UNION ALL
      SELECT
        i + 1
      , nextpos
      FROM
        r
      , LATERAL (
          SELECT
            array_agg(unnest) nextpos -- набор всех достижимых "следующих" позиций
          FROM
            matches
          , unnest(nextpos)
          WHERE
            pos = ANY(success)
        ) T
      WHERE
        (ln + 1) <> ALL(success)      -- продолжаем, пока не достигли конечной позиции
    )
    SELECT
      TRUE
    FROM
      r
    WHERE
      (ln + 1) = ANY(success)         -- находим запись с достигнутой целевой позицией
    LIMIT 1
  ) T;

На поиск ответа требуется всего 43 секунды:

Часть 2

Во второй части нас просят узнать количество вариантов, которым можно достичь конечной точки - вот тут и воспользуемся динамическим программированием!

Каждый переход из позиции i в позицию i + length(towel) добавляет к ней столько вариантов, каким можно было дойти до i.

Начнем с первой позиции - очевидно, до нее можно добраться единственным стартовым способом, а до остальных мы пока никак не добрались - будем сохранять эту информацию в массиве (на i-й позиции записываем количество вариантов дойти до нее), который получит вид {1,0,0,...}:

    , r AS (
      SELECT
        1 i
      , ARRAY[1::bigint] || array_fill(0, ARRAY[ln]) paths -- 1,0,0,...
    UNION ALL
      SELECT
        i + 1
      , ARRAY(
          SELECT
            sum(qty)::bigint -- суммируем для каждой позиции
          FROM
            (
              SELECT -- сюда уже дошли
                pos
              , qty
              FROM
                unnest(paths)
                  WITH ORDINALITY T(qty, pos)
            UNION ALL
              SELECT -- сюда можем дойти из позиции i
                npos
              , paths[i] -- количество способов добраться в i
              FROM
                matches
              , unnest(nextpos) npos
              WHERE
                pos = i
            ) T
          GROUP BY
            pos
          ORDER BY
            pos
        ) -- сворачиваем обратно в массив
      FROM
        r
      WHERE
        i <= ln
    )

design | i | paths
brwrr  | 1 | {1,0,0,0,0,0}
brwrr  | 2 | {1,1,1,0,0,0}
brwrr  | 3 | {1,1,2,0,0,0}
brwrr  | 4 | {1,1,2,0,2,0}
brwrr  | 5 | {1,1,2,0,2,0}
brwrr  | 6 | {1,1,2,0,2,2}
bggr   | 1 | {1,0,0,0,0}
bggr   | 2 | {1,1,0,0,0}
bggr   | 3 | {1,1,1,0,0}
bggr   | 4 | {1,1,1,1,0}
bggr   | 5 | {1,1,1,1,1}
gbbr   | 1 | {1,0,0,0,0}
gbbr   | 2 | {1,1,1,0,0}
gbbr   | 3 | {1,1,2,0,0}
gbbr   | 4 | {1,1,2,2,2}
gbbr   | 5 | {1,1,2,2,4}
rrbgbr | 1 | {1,0,0,0,0,0,0}
rrbgbr | 2 | {1,1,0,0,0,0,0}
rrbgbr | 3 | {1,1,1,1,0,0,0}
rrbgbr | 4 | {1,1,1,2,0,0,0}
rrbgbr | 5 | {1,1,1,2,2,2,0}
rrbgbr | 6 | {1,1,1,2,2,4,2}
rrbgbr | 7 | {1,1,1,2,2,4,6}
ubwu   | 1 | {1,0,0,0,0}
ubwu   | 2 | {1,0,0,0,0}
ubwu   | 3 | {1,0,0,0,0}
ubwu   | 4 | {1,0,0,0,0}
ubwu   | 5 | {1,0,0,0,0}
bwurrg | 1 | {1,0,0,0,0,0,0}
bwurrg | 2 | {1,1,0,1,0,0,0}
bwurrg | 3 | {1,1,0,1,0,0,0}
bwurrg | 4 | {1,1,0,1,0,0,0}
bwurrg | 5 | {1,1,0,1,1,0,0}
bwurrg | 6 | {1,1,0,1,1,1,0}
bwurrg | 7 | {1,1,0,1,1,1,1}
brgr   | 1 | {1,0,0,0,0}
brgr   | 2 | {1,1,1,0,0}
brgr   | 3 | {1,1,2,0,0}
brgr   | 4 | {1,1,2,2,0}
brgr   | 5 | {1,1,2,2,2}
bbrgwb | 1 | {1,0,0,0,0,0,0}
bbrgwb | 2 | {1,1,0,0,0,0,0}
bbrgwb | 3 | {1,1,1,1,0,0,0}
bbrgwb | 4 | {1,1,1,2,0,0,0}
bbrgwb | 5 | {1,1,1,2,2,0,0}
bbrgwb | 6 | {1,1,1,2,2,0,0}
bbrgwb | 7 | {1,1,1,2,2,0,0}

Легко заметить, что искомое количество вариантов для каждого дизайна находится в последней (ln + 1) позиции массива на последней итерации.

Осталось все собрать и просуммировать:

WITH src AS (
  SELECT
    string_to_array((array_agg(line[1]) FILTER(WHERE i = 1))[1], ', ') towels
  , array_agg(line[1]) FILTER(WHERE i > 1) designs
  FROM
    regexp_matches($$
r, wr, b, g, bwu, rb, gb, br

brwrr
bggr
gbbr
rrbgbr
ubwu
bwurrg
brgr
bbrgwb
$$
  , '([wubrg ,]+)'
  , 'g')
    WITH ORDINALITY T(line, i)
)
SELECT
  sum(paths)
FROM
  src
, unnest(designs) design -- получаем список дизайнов
, length(design) ln      -- для каждого кэшируем длину
, LATERAL (
    WITH RECURSIVE matches AS (
      SELECT
        pos                                    -- для каждой позиции
      , array_agg(pos + length(towel)) nextpos -- получаем список следующих доступных
      FROM
        generate_series(1, ln) pos
      , unnest(towels) towel
      WHERE
        substr(design, pos) ^@ towel           -- starts_with
      GROUP BY
        1
    )
    , r AS (
      SELECT
        1 i
      , ARRAY[1::bigint] || array_fill(0, ARRAY[ln]) paths -- 1,0,0,...
    UNION ALL
      SELECT
        i + 1
      , ARRAY(
          SELECT
            sum(qty)::bigint -- суммируем для каждой позиции
          FROM
            (
              SELECT -- сюда уже дошли
                pos
              , qty
              FROM
                unnest(paths)
                  WITH ORDINALITY T(qty, pos)
            UNION ALL
              SELECT -- сюда можем дойти из позиции i
                npos
              , paths[i] -- количество способов добраться в i
              FROM
                matches
              , unnest(nextpos) npos
              WHERE
                pos = i
            ) T
          GROUP BY
            pos
          ORDER BY
            pos
        ) -- сворачиваем обратно в массив
      FROM
        r
      WHERE
        i <= ln
    )
    SELECT
      paths[array_length(paths, 1)] -- значение в последней позиции с последней итерации
    FROM
      r
    ORDER BY
      i DESC
    LIMIT 1
  ) T;

Если искомое количество ненулевое, то такая раскладка вообще возможна - так что этот способ является решением и для первой части, причем еще и более быстрым - поиск ответа занимает меньше 7 секунд: