SQL HowTo: моделирование против подсчета (Advent of Code 2024, Day 21: Keypad Conundrum) / Хабр

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

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

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

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

Advent of Code 2024, Day 21: Keypad Conundrum

--- День 21: Головоломка с клавиатурой ---

Когда вы телепортируетесь на звездолет Санты класса «Олень», Историки начинают паниковать: кто-то из их поисковой группы пропал. Быстрое сканирование жизненных форм корабельным компьютером показывает, что когда пропавший Историк телепортировался, он оказался в другой части корабля.

Дверь в эту зону заперта, но компьютер не может ее открыть; ее можно открыть, только физически введя коды двери (данные головоломки) на цифровой клавиатуре на двери.

Цифровая клавиатура имеет четыре ряда кнопок: 789, 456, 123, и, наконец, пустой пробел, за которым следует 0A. Визуально они расположены следующим образом:

+---+---+---+
| 7 | 8 | 9 |
+---+---+---+
| 4 | 5 | 6 |
+---+---+---+
| 1 | 2 | 3 |
+---+---+---+
    | 0 | A |
    +---+---+

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

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

Направляющая клавиатура имеет два ряда кнопок: пробел / ^ (вверх) / A (активировать) в первом ряду и < (влево) / v (вниз) / > (вправо) во втором ��яду. Визуально они расположены следующим образом:

    +---+---+
    | ^ | A |
+---+---+---+
| < | v | > |
+---+---+---+

Когда робот достигает цифровой клавиатуры, его роботизированная рука указывает на кнопку A в правом нижнем углу. После этого необходимо использовать этот пульт дистанционного управления с направляющей клавиатурой для маневрирования роботизированной рукой: кнопки вверх / вниз / влево / вправо заставляют его перемещать руку на одну кнопку в этом направлении, а кнопка A заставляет робота кратковременно двигаться вперед, нажимая кнопку, на которую нацелена роботизированная рука.

Например, чтобы заставить робота печатать 029A на цифровой клавиатуре, можно использовать следующую последовательность ввода на клавиатуре направлений:

< , чтобы переместить руку из A (исходного положения) в 0.
A , чтобы нажать кнопку 0.
^A, чтобы переместить руку к кнопке 2 и нажать ее.
>^^A, чтобы переместить руку к кнопке 9 и нажать ее.
vvvA переместить руку к кнопке A и нажать ее.

Всего существует три кратчайшие возможные последовательности нажатий кнопок на этой навигационной клавиатуре, которые заставят робота набрать 029A: <A^A>^^AvvvA, <A^A^>^AvvvA, и <A^A^^>AvvvA.

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

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

Существует несколько кратчайших возможных последовательностей нажатий кнопок направленной клавиатуры, которые заставят этого робота сказать первому роботу набрать текст 029A на двери. Одна из таких последовательностей — v<<A>>^A<A>AvA<^AA>A<vAAA>^A.

К сожалению, область, содержащая этот второй пульт дистанционного управления с клавиатурой направления, в настоящее время составляет -40 градусов! Необходимо будет отправить еще одного робота, чтобы он тоже печатал на этой клавиатуре направления.

Существует множество кратчайших возможных последовательностей нажатий кнопок направленной клавиатуры, которые заставят этого робота сказать второму роботу сказать первому роботу в конечном итоге набрать текст 029A на двери. Одна из таких последовательностей — <vA<AA>>^AvAA<^A>A<v<A>>^AvA^A<vA>^A<v<A>^A>AAvA^A<v<A>A>^AAAvA<^A>A.

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

Если бы вы выбрали эту последовательность нажатий кнопок, вот все кнопки, которые будут нажаты на вашей навигационной клавиатуре, навигационных клавиатурах двух роботов и цифровой клавиатуре:

<vA<AA>>^AvAA<^A>A<v<A>>^AvA^A<vA>^A<v<A>^A>AAvA^A<v<A>A>^AAAvA<^A>A
v<<A>>^A<A>AvA<^AA>A<vAAA>^A
<A^A>^^AvvvA
029A

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

Одна из используемых вами навигационных клавиатур.
Две навигационные клавиатуры, которые используют роботы.
Одна цифровая клавиатура (на двери), которую использует робот.

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

Чтобы открыть дверь, нужно будет ввести пять кодов на ее цифровой клавиатуре. Например:

029A
980A
179A
456A
379A

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

029A: <vA<AA>>^AvAA<^A>A<v<A>>^AvA^A<vA>^A<v<A>^A>AAvA^A<v<A>A>^AAAvA<^A>A
980A: <v<A>>^AAAvA^A<vA<AA>>^AvAA<^A>A<v<A>A>^AAAvA<^A>A<vA>^A<A>A
179A: <v<A>>^A<vA<A>>^AAvAA<^A>A<v<A>>^AAvA^A<vA>^AA<A>A<v<A>A>^AAAvA<^A>A
456A: <v<A>>^AA<vA<A>>^AAvAA<^A>A<vA>^A<A>A<vA>^A<A>A<v<A>A>^AAvA<^A>A
379A: <v<A>>^AvA^A<vA<AA>>^AAvA<^A>AAvA^A<vA>^AA<A>A<v<A>A>^AAAvA<^A>A

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

Сложность одного кода (например, 029A) равна результату умножения двух значений:

Длина самой короткой последовательности нажатий кнопок, которую необходимо нажать на навигационной клавиатуре, чтобы ввести код на цифровой клавиатуре; для 029A это будет 68.
Числовая часть кода (без учета начальных нулей); для 029A это будет 29.

В приведенном выше примере сложность пяти кодов можно найти вычислением 68 * 29, 60 * 980, 68 * 179, 64 * 456 и 64 * 379. Их сложение дает 126384.

Найдите наименьшее количество нажатий кнопок, которое вам нужно будет выполнить, чтобы заставить робота перед дверью набрать каждый код. Какова сумма сложностей пяти кодов в вашем списке?

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

Как только пропавший Историк оказывается на свободе, Историки понимают, что второй член их поисковой группы также пропал без вести все это время!

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

На этот раз задействовано гораздо больше роботов. Вкратце, есть следующие клавиатуры:

Одна из используемых вами навигационных клавиатур.
25 навигационных клавиатур, которые используют роботы.
Одна цифровая клавиатура (на двери), которую использует робот.

Клавиатуры образуют цепочку, как и прежде: ваша направляющая клавиатура управляет роботом, который печатает на направляющей клавиатуре, которая управляет роботом, который печатает на направляющей клавиатуре... и так далее, заканчивая роботом, который печатает на цифровой клавиатуре.

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

Часть 1

Сначала, уже привычными регулярными выражениями, разложим список имеющихся кодов в строки:

WITH src AS (
  SELECT
    line[1] code
  FROM
    regexp_matches(
      $$
029A
980A
179A
456A
379A
$$
    , '[^\r\n]+(?=$|[\r\n])'
    , 'g'
    ) line
)

Теперь преобразуем макет цифровой клавиатуры в список кнопок с координатами:

, numpad AS (
  SELECT
    d[1] k
  , x
  , y
  FROM
    regexp_matches(
      $$
789
456
123
 0A
$$
    , '[^\r\n]+(?=$|[\r\n])'
    , 'g'
    )
      WITH ORDINALITY y(line, y)
  , regexp_matches(
      line[1]
    , '.'
    , 'g'
    )
      WITH ORDINALITY x(d, x)
  WHERE
    d[1] <> ' '
)

k | x | y
7 | 1 | 1
8 | 2 | 1
9 | 3 | 1
4 | 1 | 2
5 | 2 | 2
6 | 3 | 2
1 | 1 | 3
2 | 2 | 3
3 | 3 | 3
0 | 2 | 4
A | 3 | 4

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

, numpad_step AS (
  SELECT DISTINCT
    kb1.k || kb2.k pair
  , unnest(ARRAY[
      -- сначала горизонтально, потом вертикально
      repeat(CASE WHEN kb2.x > kb1.x THEN '>' ELSE '<' END, abs(kb2.x - kb1.x)::integer)
   || repeat(CASE WHEN kb2.y > kb1.y THEN 'v' ELSE '^' END, abs(kb2.y - kb1.y)::integer)
      -- или сначала вертикально, потом горизонтально
    , repeat(CASE WHEN kb2.y > kb1.y THEN 'v' ELSE '^' END, abs(kb2.y - kb1.y)::integer)
   || repeat(CASE WHEN kb2.x > kb1.x THEN '>' ELSE '<' END, abs(kb2.x - kb1.x)::integer)
    ]) || 'A' code
  FROM
    numpad kb1
  , numpad kb2
EXCEPT ALL -- исключаем пути через "пустое место"
  VALUES
    ('01', '<^A')
  , ('04', '<^^A')
  , ('07', '<^^^A')
  , ('A1', '<<^A')
  , ('A4', '<<^^A')
  , ('A7', '<<^^^A')
  , ('10', 'v>A')
  , ('40', 'vv>A')
  , ('70', 'vvv>A')
  , ('1A', 'v>>A')
  , ('4A', 'vv>>A')
  , ('7A', 'vvv>>A')
)

pair | code
  00 | A
  01 | ^<A
  02 | ^A
  03 | >^A
  03 | ^>A
  04 | ^^<A
  05 | ^^A
  06 | ^^>A
  06 | >^^A
  07 | ^^^<A
  08 | ^^^A
  09 | >^^^A
  09 | ^^^>A
  0A | >A
...

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

, arrpad AS (
  SELECT
    d[1] k
  , x
  , y
  FROM
    regexp_matches(
      $$
 ^A
<v>
$$
    , '[^\r\n]+(?=$|[\r\n])'
    , 'g'
    )
      WITH ORDINALITY y(line, y)
  , regexp_matches(
      line[1]
    , '.'
    , 'g'
    )
      WITH ORDINALITY x(d, x)
  WHERE
    d[1] <> ' '
)
, arrpad_step AS (
  SELECT DISTINCT
    kb1.k || kb2.k pair
  , unnest(ARRAY[
      repeat(CASE WHEN kb2.x > kb1.x THEN '>' ELSE '<' END, abs(kb2.x - kb1.x)::integer)
  || repeat(CASE WHEN kb2.y > kb1.y THEN 'v' ELSE '^' END, abs(kb2.y - kb1.y)::integer)
    , repeat(CASE WHEN kb2.y > kb1.y THEN 'v' ELSE '^' END, abs(kb2.y - kb1.y)::integer)
  || repeat(CASE WHEN kb2.x > kb1.x THEN '>' ELSE '<' END, abs(kb2.x - kb1.x)::integer)
    ]) || 'A' code
  FROM
    arrpad kb1
  , arrpad kb2
EXCEPT ALL
  VALUES
    ('<^', '^>A')
  , ('<A', '^>>A')
  , ('^<', '<vA')
  , ('A<', '<<vA')
)

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

SELECT
  *
FROM
  src
, LATERAL (
    WITH RECURSIVE step AS ( -- превращаем код в цепочку переходов между парами кнопок
      SELECT
        i
      , substr('A' || code, i, 2) pair
      FROM
        generate_series(1, length(code)) i
    )
    , r AS ( -- рекурсивно пробуем разные варианты подстановок
      SELECT
        1 i
      , '' code0
    UNION ALL
      SELECT
        i + 1
      , code0 || code
      FROM
        r
      JOIN
        step
          USING(i)
      JOIN
        numpad_step -- цифровая клавиатура
          USING(pair)
    )
    TABLE r
    ORDER BY
      i DESC
    FETCH FIRST 1 ROW -- оставляем только строки с последнего шага
    WITH TIES
  ) T0

code | i | code0
029A | 5 | <A^A^^>AvvvA
029A | 5 | <A^A>^^AvvvA
980A | 5 | ^^^A<AvvvA>A
179A | 5 | ^<<A^^A>>AvvvA
456A | 5 | ^^<<A>A>AvvA
379A | 5 | ^A<<^^A>>AvvvA
379A | 5 | ^A^^<<A>>AvvvA

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

code | i | code0        |  i | code1                        |  i | code2
029A | 5 | <A^A^^>AvvvA | 13 | v<<A>>^A<A>A<AAv>A^Av<AAA^>A | 29 | v<A<AA>>^AvAA^<A>Av<<A>>^AvA^Av<<A>>^AAv<A>A^A<A>Av<A<A>>^AAA<Av>A^A
029A | 5 | <A^A^^>AvvvA | 13 | v<<A>>^A<A>A<AAv>A^Av<AAA^>A | 29 | <vA<AA>>^AvAA<^A>Av<<A>>^AvA^Av<<A>>^AA<vA>A^A<A>A<vA<A>>^AAA<A>vA^A
029A | 5 | <A^A^^>AvvvA | 13 | v<<A>>^A<A>A<AAv>A^Av<AAA^>A | 29 | v<A<AA>>^AvAA<^A>Av<<A>>^AvA^Av<<A>>^AA<vA>A^A<A>A<vA<A>>^AAA<A>vA^A
...

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

SELECT
  sum(regexp_replace(code, '\D', '', 'g')::integer * length(code2))
FROM
  (
    SELECT DISTINCT ON(code)
      ...
    ORDER BY
      code, length(code2)
  ) T;

Остается лишь сложить все вместе и получить ответ:

WITH src AS (
  SELECT
    line[1] code
  FROM
    regexp_matches(
      $$
029A
980A
179A
456A
379A
$$
    , '[^\r\n]+(?=$|[\r\n])'
    , 'g'
    ) line
)
, numpad AS (
  SELECT
    d[1] k
  , x
  , y
  FROM
    regexp_matches(
      $$
789
456
123
 0A
$$
    , '[^\r\n]+(?=$|[\r\n])'
    , 'g'
    )
      WITH ORDINALITY y(line, y)
  , regexp_matches(
      line[1]
    , '.'
    , 'g'
    )
      WITH ORDINALITY x(d, x)
  WHERE
    d[1] <> ' '
)
, numpad_step AS (
  SELECT DISTINCT
    kb1.k || kb2.k pair
  , unnest(ARRAY[
      repeat(CASE WHEN kb2.x > kb1.x THEN '>' ELSE '<' END, abs(kb2.x - kb1.x)::integer) || repeat(CASE WHEN kb2.y > kb1.y THEN 'v' ELSE '^' END, abs(kb2.y - kb1.y)::integer)
    , repeat(CASE WHEN kb2.y > kb1.y THEN 'v' ELSE '^' END, abs(kb2.y - kb1.y)::integer) || repeat(CASE WHEN kb2.x > kb1.x THEN '>' ELSE '<' END, abs(kb2.x - kb1.x)::integer)
    ]) || 'A' code
  FROM
    numpad kb1
  , numpad kb2
EXCEPT ALL
  VALUES
    ('01', '<^A')
  , ('04', '<^^A')
  , ('07', '<^^^A')
  , ('A1', '<<^A')
  , ('A4', '<<^^A')
  , ('A7', '<<^^^A')
  , ('10', 'v>A')
  , ('40', 'vv>A')
  , ('70', 'vvv>A')
  , ('1A', 'v>>A')
  , ('4A', 'vv>>A')
  , ('7A', 'vvv>>A')
)
, arrpad AS (
  SELECT
    d[1] k
  , x
  , y
  FROM
    regexp_matches(
      $$
 ^A
<v>
$$
    , '[^\r\n]+(?=$|[\r\n])'
    , 'g'
    )
      WITH ORDINALITY y(line, y)
  , regexp_matches(
      line[1]
    , '.'
    , 'g'
    )
      WITH ORDINALITY x(d, x)
  WHERE
    d[1] <> ' '
)
, arrpad_step AS (
  SELECT DISTINCT
    kb1.k || kb2.k pair
  , unnest(ARRAY[
      repeat(CASE WHEN kb2.x > kb1.x THEN '>' ELSE '<' END, abs(kb2.x - kb1.x)::integer) || repeat(CASE WHEN kb2.y > kb1.y THEN 'v' ELSE '^' END, abs(kb2.y - kb1.y)::integer)
    , repeat(CASE WHEN kb2.y > kb1.y THEN 'v' ELSE '^' END, abs(kb2.y - kb1.y)::integer) || repeat(CASE WHEN kb2.x > kb1.x THEN '>' ELSE '<' END, abs(kb2.x - kb1.x)::integer)
    ]) || 'A' code
  FROM
    arrpad kb1
  , arrpad kb2
EXCEPT ALL
  VALUES
    ('<^', '^>A')
  , ('<A', '^>>A')
  , ('^<', '<vA')
  , ('A<', '<<vA')
)
SELECT
  sum(regexp_replace(code, '\D', '', 'g')::integer * length(code2))
FROM
  (
    SELECT DISTINCT ON(code)
      *
    FROM
      src
    , LATERAL (
        WITH RECURSIVE step AS (
          SELECT
            i
          , substr('A' || code, i, 2) pair
          FROM
            generate_series(1, length(code)) i
        )
        , r AS (
          SELECT
            1 i
          , '' code0
        UNION ALL
          SELECT
            i + 1
          , code0 || code
          FROM
            r
          JOIN
            step
              USING(i)
          JOIN
            numpad_step
              USING(pair)
        )
        TABLE r
        ORDER BY
          i DESC
        FETCH FIRST 1 ROW
        WITH TIES
      ) T0
    , LATERAL (
        WITH RECURSIVE step AS (
          SELECT
            i
          , substr('A' || code0, i, 2) pair
          FROM
            generate_series(1, length(code0)) i
        )
        , r AS (
          SELECT
            1 i
          , '' code1
        UNION ALL
          SELECT
            i + 1
          , code1 || code
          FROM
            r
          JOIN
            step
              USING(i)
          JOIN
            arrpad_step
              USING(pair)
        )
        TABLE r
        ORDER BY
          i DESC
        FETCH FIRST 1 ROW
        WITH TIES
      ) T1
    , LATERAL (
        WITH RECURSIVE step AS (
          SELECT
            i
          , substr('A' || code1, i, 2) pair
          FROM
            generate_series(1, length(code1)) i
        )
        , r AS (
          SELECT
            1 i
          , '' code2
        UNION ALL
          SELECT
            i + 1
          , code2 || code
          FROM
            r
          JOIN
            step
              USING(i)
          JOIN
            arrpad_step
              USING(pair)
        )
        TABLE r
        ORDER BY
          i DESC
        FETCH FIRST 1 ROW
        WITH TIES
      ) T2
    ORDER BY
      code, length(code2)
  ) T;

Ничего хоть сколько-то сложного в нашем запросе нет, поэтому результат мы получим всего за 120мс:

Часть 2

Во второй части нам предлагается сделать все ровно то же самое, только роботов с направляющей клавиатурой будет не 2, а 25. Казалось бы, копипаста рулит!.. Но нет - длина каждой строки растет экспоненциально, и даже для 10 роботов дождаться уже нереально.

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

, arrpad_step AS (
  SELECT DISTINCT
    kb1.k || kb2.k pair
  , unnest(ARRAY[
      repeat(CASE WHEN kb2.x > kb1.x THEN '>' ELSE '<' END, abs(kb2.x - kb1.x)::integer) || repeat(CASE WHEN kb2.y > kb1.y THEN 'v' ELSE '^' END, abs(kb2.y - kb1.y)::integer)
    , repeat(CASE WHEN kb2.y > kb1.y THEN 'v' ELSE '^' END, abs(kb2.y - kb1.y)::integer) || repeat(CASE WHEN kb2.x > kb1.x THEN '>' ELSE '<' END, abs(kb2.x - kb1.x)::integer)
    ]) || 'A' code
  FROM
    arrpad kb1
  , arrpad kb2
EXCEPT ALL
  VALUES
    ('<^', '^>A')
  , ('<A', '^>>A')
  , ('^<', '<vA')
  , ('A<', '<<vA')
  -- неэффективные пути
  , ('>^', '^<A')
  , ('^>', '>vA')
  , ('Av', 'v<A')
  , ('vA', '>^A')
)

Теперь у наше преобразование на каждом из шагов набора на направляющей клавиатуре стало однозначным - 5 кнопок дают 25 возможных переходов между ними:

pair | code
<<   | A
<>   | >>A
<^   | >^A
><   | <<A
>>   | A
>^   | <^A
^<   | v<A
^>   | v>A
^^   | A
<A   | >>^A
>A   | ^A
^A   | >A
A<   | v<<A
A>   | vA
A^   | <A
AA   | A
Av   | <vA
<v   | >A
>v   | <A
^v   | vA
v<   | <A
v>   | >A
v^   | ^A
vA   | ^>A
vv   | A

А теперь давайте обратим внимание, что каждый переход между парой кнопок дает не просто последовательность нажатий, но и набор таких же парных переходов с определенным количеством - соберем их в jsonb:

, map AS (
  SELECT
    s.pair src
  , jsonb_object(
      array_agg(T.t)
    , array_agg(T.q)::text[]
    ) trg
  FROM
    arrpad_step s
  , LATERAL (
      SELECT
        substr('A' || code, i, 2) t
      , count(*) q
      FROM
        generate_series(1, length(code)) i
      GROUP BY
        1
    ) T
  GROUP BY
    1
)

src | trg
<<  | {"AA": "1"}
<>  | {">>": "1", ">A": "1", "A>": "1"}
<^  | {">^": "1", "A>": "1", "^A": "1"}
><  | {"<<": "1", "<A": "1", "A<": "1"}
>>  | {"AA": "1"}
>^  | {"<^": "1", "A<": "1", "^A": "1"}
^<  | {"<A": "1", "Av": "1", "v<": "1"}
^>  | {">A": "1", "Av": "1", "v>": "1"}
^^  | {"AA": "1"}
<A  | {">>": "1", ">^": "1", "A>": "1", "^A": "1"}
>A  | {"A^": "1", "^A": "1"}
^A  | {">A": "1", "A>": "1"}
A<  | {"<<": "1", "<A": "1", "Av": "1", "v<": "1"}
A>  | {"Av": "1", "vA": "1"}
A^  | {"<A": "1", "A<": "1"}
AA  | {"AA": "1"}
Av  | {"<v": "1", "A<": "1", "vA": "1"}
<v  | {">A": "1", "A>": "1"}
>v  | {"<A": "1", "A<": "1"}
^v  | {"Av": "1", "vA": "1"}
v<  | {"<A": "1", "A<": "1"}
v>  | {">A": "1", "A>": "1"}
v^  | {"A^": "1", "^A": "1"}
vA  | {">A": "1", "A^": "1", "^>": "1"}
vv  | {"AA": "1"}

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

Осталось лишь написать рекурсивное "погружение" на нужное количество шагов:

, r AS (
  SELECT
    0 bot
  , code src
  , trg
  FROM
    src
  , LATERAL ( -- преобразуем числовой код в варианты последовательностей стрелок
      WITH RECURSIVE step AS (
        SELECT
          i
        , substr('A' || code, i, 2) pair
        FROM
          generate_series(1, length(code)) i
      )
      , r AS (
        SELECT
          1 i
        , '' code0
      UNION ALL
        SELECT
          i + 1
        , code0 || code
        FROM
          r
        JOIN
          step
            USING(i)
        JOIN
          numpad_step
            USING(pair)
      )
      TABLE r
      ORDER BY
        i DESC
      FETCH FIRST 1 ROW
      WITH TIES
    ) T0
  , LATERAL ( -- последовательность стрелок превращаем в набор парных переходов
      SELECT
        jsonb_object(
          array_agg(T.t)
        , array_agg(T.q)::text[]
        ) trg
      FROM
        (
          SELECT
            substr('A' || code0, i, 2) t
          , count(*) q
          FROM
            generate_series(1, length(code0)) i
          GROUP BY
            1
        ) T
    ) T
UNION ALL
  SELECT
    bot + 1
  , r.src
  , T.*
  FROM
    r
  , LATERAL (
      SELECT
        jsonb_object(
          array_agg(k)
        , array_agg(v)::text[]
        ) trg -- собираем счетчики
      FROM
        (
          SELECT
            k1 k
          , sum(v0::bigint * v1::bigint) v
          FROM
            jsonb_each_text(r.trg) T0(k0, v0) -- разворачиваем ключ-значение текущего шага
          JOIN
            map
              ON map.src = k0 -- находим, во что превратится каждый ключ
          , jsonb_each_text(map.trg) T1(k1, v1) -- разворачиваем ключ-значение следующего шага
          GROUP BY
            1
        ) T
    ) T
  WHERE
    bot < 25
)

bot | src  | trg
  0 | 029A | {"<A": "1", ">^": "1", "A<": "1", "A>": "1", "A^": "1", "Av": "1", "^A": "2", "^^": "1", "vA": "1", "vv": "2"}
  0 | 029A | {"<A": "1", ">A": "1", "A<": "1", "A^": "2", "Av": "1", "^>": "1", "^A": "1", "^^": "1", "vA": "1", "vv": "2"}
  0 | 179A | {"<<": "1", "<A": "1", ">>": "1", ">A": "1", "A>": "1", "A^": "2", "Av": "1", "^<": "1", "^A": "1", "^^": "1", "vA": "1", "vv": "2"}
  0 | 379A | {"<<": "1", "<^": "1", ">>": "1", ">A": "1", "A<": "1", "A>": "1", "A^": "1", "Av": "1", "^A": "2", "^^": "1", "vA": "1", "vv": "2"}
  0 | 379A | {"<<": "1", "<A": "1", ">>": "1", ">A": "1", "A>": "1", "A^": "2", "Av": "1", "^<": "1", "^A": "1", "^^": "1", "vA": "1", "vv": "2"}
  0 | 456A | {"<<": "1", "<A": "1", ">A": "2", "A>": "2", "A^": "1", "Av": "1", "^<": "1", "^^": "1", "vA": "1", "vv": "1"}
  0 | 980A | {"<A": "1", ">A": "1", "A<": "1", "A>": "1", "A^": "1", "Av": "1", "^A": "1", "^^": "2", "vA": "1", "vv": "2"}
  1 | 029A | {"<<": "1", "<A": "3", "<v": "1", ">>": "1", ">A": "3", ">^": "1", "A<": "3", "A>": "2", "AA": "3", "A^": "2", "Av": "2", "^>": "1", "^A": "2", "v<": "1", "v>": "1", "vA": "1"}
  1 | 029A | {"<<": "1", "<A": "2", "<^": "1", "<v": "1", ">>": "1", ">A": "3", ">^": "1", "A<": "3", "A>": "3", "AA": "3", "A^": "1", "Av": "2", "^>": "1", "^A": "2", "v<": "1", "vA": "2"}
...

Каждый парный переход означает наличие +1 символа в целевой последовательности, поэтому для подсчета длины строки нам надо лишь просуммировать все jsonb-значения с последнего шага преобразования по каждому из кодов и взять минимальные:

SELECT
  sum(regexp_replace(src, '\D', '', 'g')::integer * ln)
FROM
  (
    SELECT DISTINCT ON(src)
      src
    , (
        SELECT
          sum(v::bigint) -- суммируем jsonb-значения
        FROM
          jsonb_each_text(trg) T(k, v)
      ) ln
    FROM
      r
    WHERE
      bot = (SELECT max(bot) FROM r) -- значения с последнего шага
    ORDER BY
      1, 2
  ) T;

Собираем все вместе (очевидно, если заменить лимит ботов 25 на 2, то мы получим решение для первой части):

WITH RECURSIVE src AS (
  SELECT
    line[1] code
  FROM
    regexp_matches(
      $$
029A
980A
179A
456A
379A
$$
    , '[^\r\n]+(?=$|[\r\n])'
    , 'g'
    ) line
)
, numpad AS (
  SELECT
    d[1] k
  , x
  , y
  FROM
    regexp_matches(
      $$
789
456
123
 0A
$$
    , '[^\r\n]+(?=$|[\r\n])'
    , 'g'
    )
      WITH ORDINALITY y(line, y)
  , regexp_matches(
      line[1]
    , '.'
    , 'g'
    )
      WITH ORDINALITY x(d, x)
  WHERE
    d[1] <> ' '
)
, numpad_step AS (
  SELECT DISTINCT
    kb1.k || kb2.k pair
  , unnest(ARRAY[
      repeat(CASE WHEN kb2.x > kb1.x THEN '>' ELSE '<' END, abs(kb2.x - kb1.x)::integer) || repeat(CASE WHEN kb2.y > kb1.y THEN 'v' ELSE '^' END, abs(kb2.y - kb1.y)::integer)
    , repeat(CASE WHEN kb2.y > kb1.y THEN 'v' ELSE '^' END, abs(kb2.y - kb1.y)::integer) || repeat(CASE WHEN kb2.x > kb1.x THEN '>' ELSE '<' END, abs(kb2.x - kb1.x)::integer)
    ]) || 'A' code
  FROM
    numpad kb1
  , numpad kb2
EXCEPT ALL
  VALUES
    ('01', '<^A')
  , ('04', '<^^A')
  , ('07', '<^^^A')
  , ('A1', '<<^A')
  , ('A4', '<<^^A')
  , ('A7', '<<^^^A')
  , ('10', 'v>A')
  , ('40', 'vv>A')
  , ('70', 'vvv>A')
  , ('1A', 'v>>A')
  , ('4A', 'vv>>A')
  , ('7A', 'vvv>>A')
)
, arrpad AS (
  SELECT
    d[1] k
  , x
  , y
  FROM
    regexp_matches(
      $$
 ^A
<v>
$$
    , '[^\r\n]+(?=$|[\r\n])'
    , 'g'
    )
      WITH ORDINALITY y(line, y)
  , regexp_matches(
      line[1]
    , '.'
    , 'g'
    )
      WITH ORDINALITY x(d, x)
  WHERE
    d[1] <> ' '
)
, arrpad_step AS (
  SELECT DISTINCT
    kb1.k || kb2.k pair
  , unnest(ARRAY[
      repeat(CASE WHEN kb2.x > kb1.x THEN '>' ELSE '<' END, abs(kb2.x - kb1.x)::integer) || repeat(CASE WHEN kb2.y > kb1.y THEN 'v' ELSE '^' END, abs(kb2.y - kb1.y)::integer)
    , repeat(CASE WHEN kb2.y > kb1.y THEN 'v' ELSE '^' END, abs(kb2.y - kb1.y)::integer) || repeat(CASE WHEN kb2.x > kb1.x THEN '>' ELSE '<' END, abs(kb2.x - kb1.x)::integer)
    ]) || 'A' code
  FROM
    arrpad kb1
  , arrpad kb2
EXCEPT ALL
  VALUES
    ('<^', '^>A')
  , ('<A', '^>>A')
  , ('^<', '<vA')
  , ('A<', '<<vA')
  --
  , ('>^', '^<A')
  , ('^>', '>vA')
  , ('Av', 'v<A')
  , ('vA', '>^A')
)
, map AS (
  SELECT
    s.pair src
  , jsonb_object(
      array_agg(T.t)
    , array_agg(T.q)::text[]
    ) trg
  FROM
    arrpad_step s
  , LATERAL (
      SELECT
        substr('A' || code, i, 2) t
      , count(*) q
      FROM
        generate_series(1, length(code)) i
      GROUP BY
        1
    ) T
  GROUP BY
    1
)
, r AS (
  SELECT
    0 bot
  , code src
  , trg
  FROM
    src
  , LATERAL (
      WITH RECURSIVE step AS (
        SELECT
          i
        , substr('A' || code, i, 2) pair
        FROM
          generate_series(1, length(code)) i
      )
      , r AS (
        SELECT
          1 i
        , '' code0
      UNION ALL
        SELECT
          i + 1
        , code0 || code
        FROM
          r
        JOIN
          step
            USING(i)
        JOIN
          numpad_step
            USING(pair)
      )
      TABLE r
      ORDER BY
        i DESC
      FETCH FIRST 1 ROW
      WITH TIES
    ) T0
  , LATERAL (
      SELECT
        jsonb_object(
          array_agg(T.t)
        , array_agg(T.q)::text[]
        ) trg
      FROM
        (
          SELECT
            substr('A' || code0, i, 2) t
          , count(*) q
          FROM
            generate_series(1, length(code0)) i
          GROUP BY
            1
        ) T
    ) T
UNION ALL
  SELECT
    bot + 1
  , r.src
  , T.*
  FROM
    r
  , LATERAL (
      SELECT
        jsonb_object(
          array_agg(k)
        , array_agg(v)::text[]
        ) trg -- собираем счетчики
      FROM
        (
          SELECT
            k1 k
          , sum(v0::bigint * v1::bigint) v
          FROM
            jsonb_each_text(r.trg) T0(k0, v0) -- разворачиваем ключ-значение текущего шага
          JOIN
            map
              ON map.src = k0 -- находим, во что превратится каждый ключ
          , jsonb_each_text(map.trg) T1(k1, v1) -- разворачиваем ключ-значение следующего шага
          GROUP BY
            1
        ) T
    ) T
  WHERE
    bot < 25
)
SELECT
  sum(regexp_replace(src, '\D', '', 'g')::integer * ln)
FROM
  (
    SELECT DISTINCT ON(src)
      src
    , (
        SELECT
          sum(v::bigint) -- суммируем jsonb-значения
        FROM
          jsonb_each_text(trg) T(k, v)
      ) ln
    FROM
      r
    WHERE
      bot = (SELECT max(bot) FROM r) -- значения с последнего шага
    ORDER BY
      1, 2
  ) T;

Самый интересный эффект заключается в том, что более сложную задачу мы решили в 4 раза эффективнее, чем первую часть!

SQL HowTo: моделирование против подсчета (Advent of Code 2024, Day 21: Keypad Conundrum)

--- День 21: Головоломка с клавиатурой ---

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

Часть 1

Часть 2

Публикации

Информация