Как стать автором
Поиск
Написать публикацию
Обновить
75.75
Рейтинг
Тензор
Разработчик системы Saby

SQL HowTo: подбираем значение ветвлением (Advent of Code 2024, Day 17: Chronospatial Computer)

Уровень сложностиПростой
Время на прочтение10 мин
Количество просмотров1.1K
Блог компании ТензорPostgreSQL*SQL*Алгоритмы*Занимательные задачки
Кейс

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

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

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

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

Advent of Code 2024, Day 17: Chronospatial Computer

--- День 17: Хронопространственный компьютер ---

Историки нажимают кнопку на своем странном устройстве, но на этот раз вы все просто чувствуете, что падаете.

«Ситуация критическая», — сообщает устройство знакомым голосом. «Процесс начальной загрузки не удался. Инициализация отладчика...»

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

Похоже, это 3-битный компьютер: его программа представляет собой список 3-битных чисел (от 0 до 7), например 0,1,2,3. Компьютер также имеет три регистра с именами A, B, и C, но эти регистры не ограничены 3 битами и могут содержать любое целое число.

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

Число, называемое указателем инструкции, определяет позицию в программе, с которой будет считан следующий код операции; он начинается с 0, указывая на первое 3-битное число в программе. За исключением инструкций перехода, указатель инструкции увеличивается на 2 после обработки каждой инструкции (чтобы пройти код операции инструкции и ее операнд). Если компьютер пытается прочитать код операции после конца программы, он вместо этого останавливается.

Таким образом, программа 0,1,2,3 выполнит инструкцию с кодом операции 0 и передаст ей операнд 1 затем выполнит инструкцию с кодом операции 2 и передаст ей операнд 3, а затем остановится.

Существует два типа операндов; каждая инструкция сама определяет тип своего операнда. Значением литерального операнда является сам операнд. Например, значением литерального операнда 7 является число 7. Значение комбинированного операнда можно найти следующим образом:

  • Комбинированные операнды от 0 до 3 представляют сами значения от 0 до 3.

  • Комбинированный операнд 4 представляет значение регистра A.

  • Комбинированный операнд 5 представляет значение регистра B.

  • Комбинированный операнд 6 представляет значение регистра C.

  • Комбинированный операнд 7 зарезервирован и не будет отображаться в допустимых программах.

Восемь инструкций таковы:

Инструкция adv (код операции 0) выполняет деление. Числитель - это значение в регистре A. Знаменатель находится путем возведения 2 в степень комбинированного операнда. (Таким образом, операнд 2 будет делить A на 4 (2^2); операнд 5 будет делить A на 2^B.) Результат операции деления усекается до целого числа и затем записывается в регистр A.

Инструкция bxl (код операции 1) вычисляет побитовое исключающее ИЛИ регистра B и литерального операнда инструкции, затем сохраняет результат в регистре B.

Инструкция bst (код операции 2) вычисляет значение своего комбинированного операнда по модулю 8 (тем самым сохраняя только его младшие 3 бита), затем записывает это значение в регистр B.

Инструкция jnz (код операции 3) ничего не делает, если регистр A равен 0. Однако, если регистр A не равен нулю, он осуществляет переход, устанавливая указатель инструкции на значение своего литерального операнда; если переход происходит, указатель инструкции не увеличивается на 2 после этой инструкции.

Инструкция bxc (код операции 4) вычисляет побитовое XOR регистров B и C, затем сохраняет результат в регистре B. (В целях совместимости эта инструкция считывает операнд, но игнорирует его.)

Инструкция out (код операции 5) вычисляет значение своего комбинированного операнда по модулю 8, а затем выводит это значение. (Если программа выводит несколько значений, они разделяются запятыми.)

Инструкция bdv (код операции 6) работает точно так же, как инструкция adv, за исключением того, что результат сохраняется в регистре B. (Числитель по-прежнему считывается из регистра A.)

Инструкция cdv (код операции 7) работает точно так же, как инструкция adv, за исключением того, что результат сохраняется в регистре C. (Числитель по-прежнему считывается из регистра A.)

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

  • Если регистр C содержит 9, программа 2,6 установит регистр B в 1.

  • Если регистр A содержит 10, программа 5,0,5,1,5,4 выведет 0,1,2.

  • Если регистр A содержит 2024, программа 0,1,5,4,3,0 выведет 4,2,5,6,7,7,7,7,3,1,0 и оставит 0 в регистре A.

  • Если регистр B содержит 29, программа 1,7 установит регистр B в 26.

  • Если регистр B содержит 2024 и регистр C содержит 43690, программа 4,0 установит регистр B в 44354.

Странное устройство Историков завершило инициализацию своего отладчика и отображает некоторую информацию о программе, которую оно пытается запустить (ваш ввод головоломки). Например:

Register A: 729
Register B: 0
Register C: 0

Program: 0,1,5,4,3,0

Ваша первая задача — определить, что программа пытается вывести. Для этого инициализируйте регистры заданными значениями, затем запустите заданную программу, собирая весь вывод, производимый инструкциями out. (Всегда соединяйте значения, произведенные инструкциями out, запятыми.) После остановки указанной выше программы ее конечный вывод будет 4,6,3,5,6,3,5,2,1,0.

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

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

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

Например:

Register A: 2024
Register B: 0
Register C: 0

Program: 0,3,5,4,3,0

Эта программа выводит копию самой себя, если регистр A инициализируется значением 117440. (Оригинальное начальное значение регистра A, 2024, игнорируется.)

Каково наименьшее положительное начальное значение регистра A, при котором программа выводит свою копию?

Часть 1

Сначала разберем ввод на значения регистров и непосредственно код "программы":

WITH RECURSIVE src AS (
  SELECT
    array_agg(d[1])
      FILTER(WHERE i <= 3)::integer[] reg -- первые 3 числа - регистры
  , array_agg(d[1])
      FILTER(WHERE i > 3)::integer[] prg  -- остальные - программа
  FROM
    regexp_matches($$
Register A: 729
Register B: 0
Register C: 0

Program: 0,1,5,4,3,0
$$
    , '(\d+)'                 -- находим числа (цепочки цифр)
    , 'g'
    )
      WITH ORDINALITY T(d, i) -- ... и нумеруем их по порядку
)
reg       | prg
{729,0,0} | {0,1,5,4,3,0}

А дальше нам просто надо реализовать с помощью рекурсии пошаговое исполнение кода "программы". Для этого на каждом из шагов (i) потребуется состояние указателя инструкции (p), значения регистров (a, b, c) и накопленный вывод (o).

Самое сложное тут - не ошибиться в реализации вычислений каждой из инструкций. Из всех UNION ALL-блоков на каждом шаге по условию будет выполняться только одна нужная:

, r AS (
  SELECT
    0 i
  , 0 p                  -- указатель инструкции
  , reg[1] a             -- значения регистров
  , reg[2] b
  , reg[3] c
  , ARRAY[]::integer[] o -- накопленный вывод
  FROM
    src
UNION ALL
  SELECT
    i + 1
  , step.*
  FROM
    r
  , src
  , LATERAL ( -- вычисляем код операции и значения для комбинированного и литерального операндов
      SELECT
        prg[p + 1] opi
      , CASE prg[p + 2]
          WHEN 0 THEN 0
          WHEN 1 THEN 1
          WHEN 2 THEN 2
          WHEN 3 THEN 3
          WHEN 4 THEN a
          WHEN 5 THEN b
          WHEN 6 THEN c
          WHEN 7 THEN 7
        END opс
      , prg[p + 2] opl
  ) T
  , LATERAL ( -- реализуем выполнение каждой инструкции
      -- adv
      SELECT
        p + 2 p
      , a >> opс a
      , b
      , c
      , o
      WHERE
        opi = 0
    UNION ALL
      -- bxl
      SELECT
        p + 2 p
      , a
      , b # opl b
      , c
      , o
      WHERE
        opi = 1
    UNION ALL
      -- bst
      SELECT
        p + 2 p
      , a
      , opс & 7 b
      , c
      , o
      WHERE
        opi = 2
    UNION ALL
      -- jnz
      SELECT
        CASE WHEN a = 0 THEN p + 2 ELSE opl END p
      , a
      , b
      , c
      , o
      WHERE
        opi = 3
    UNION ALL
      -- bxc
      SELECT
        p + 2 p
      , a
      , b # c b
      , c
      , o
      WHERE
        opi = 4
    UNION ALL
      -- out
      SELECT
        p + 2 p
      , a
      , b
      , c
      , o || (opс & 7) o
      WHERE
        opi = 5
    UNION ALL
      -- bdv
      SELECT
        p + 2 p
      , a
      , a >> opс b
      , c
      , o
      WHERE
        opi = 6
    UNION ALL
      -- cdv
      SELECT
        p + 2 p
      , a
      , b
      , a >> opс c
      , o
      WHERE
        opi = 7
  ) step
)
 i | p |  a  | b | c | o
 0 | 0 | 729 | 0 | 0 | {}
 1 | 2 | 364 | 0 | 0 | {}
 2 | 4 | 364 | 0 | 0 | {4}
 3 | 0 | 364 | 0 | 0 | {4}
 4 | 2 | 182 | 0 | 0 | {4}
 5 | 4 | 182 | 0 | 0 | {4,6}
 6 | 0 | 182 | 0 | 0 | {4,6}
 7 | 2 |  91 | 0 | 0 | {4,6}
 8 | 4 |  91 | 0 | 0 | {4,6,3}
 9 | 0 |  91 | 0 | 0 | {4,6,3}
10 | 2 |  45 | 0 | 0 | {4,6,3}
11 | 4 |  45 | 0 | 0 | {4,6,3,5}
12 | 0 |  45 | 0 | 0 | {4,6,3,5}
13 | 2 |  22 | 0 | 0 | {4,6,3,5}
14 | 4 |  22 | 0 | 0 | {4,6,3,5,6}
15 | 0 |  22 | 0 | 0 | {4,6,3,5,6}
16 | 2 |  11 | 0 | 0 | {4,6,3,5,6}
17 | 4 |  11 | 0 | 0 | {4,6,3,5,6,3}
18 | 0 |  11 | 0 | 0 | {4,6,3,5,6,3}
19 | 2 |   5 | 0 | 0 | {4,6,3,5,6,3}
20 | 4 |   5 | 0 | 0 | {4,6,3,5,6,3,5}
21 | 0 |   5 | 0 | 0 | {4,6,3,5,6,3,5}
22 | 2 |   2 | 0 | 0 | {4,6,3,5,6,3,5}
23 | 4 |   2 | 0 | 0 | {4,6,3,5,6,3,5,2}
24 | 0 |   2 | 0 | 0 | {4,6,3,5,6,3,5,2}
25 | 2 |   1 | 0 | 0 | {4,6,3,5,6,3,5,2}
26 | 4 |   1 | 0 | 0 | {4,6,3,5,6,3,5,2,1}
27 | 0 |   1 | 0 | 0 | {4,6,3,5,6,3,5,2,1}
28 | 2 |   0 | 0 | 0 | {4,6,3,5,6,3,5,2,1}
29 | 4 |   0 | 0 | 0 | {4,6,3,5,6,3,5,2,1,0}
30 | 6 |   0 | 0 | 0 | {4,6,3,5,6,3,5,2,1,0}

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

WITH RECURSIVE src AS (
  SELECT
    array_agg(d[1])
      FILTER(WHERE i <= 3)::bigint[] reg -- первые 3 числа - регистры
  , array_agg(d[1])
      FILTER(WHERE i > 3)::integer[] prg -- остальные - программа
  FROM
    regexp_matches($$
Register A: 729
Register B: 0
Register C: 0

Program: 0,1,5,4,3,0
$$
    , '(\d+)'                 -- находим числа (цепочки цифр)
    , 'g'
    )
      WITH ORDINALITY T(d, i) -- ... и нумеруем их по порядку
)
, r AS (
  SELECT
    0 i
  , 0 p                  -- указатель инструкции
  , reg[1] a             -- значения регистров
  , reg[2] b
  , reg[3] c
  , ARRAY[]::integer[] o -- накопленный вывод
  FROM
    src
UNION ALL
  SELECT
    i + 1
  , step.*
  FROM
    r
  , src
  , LATERAL ( -- вычисляем код операции и значения для комбинированного и литерального операндов
      SELECT
        prg[p + 1] opi
      , CASE prg[p + 2]
          WHEN 0 THEN 0
          WHEN 1 THEN 1
          WHEN 2 THEN 2
          WHEN 3 THEN 3
          WHEN 4 THEN a
          WHEN 5 THEN b
          WHEN 6 THEN c
          WHEN 7 THEN 7
        END::bigint opс
      , prg[p + 2] opl
  ) T
  , LATERAL ( -- реализуем выполнение каждой инструкции
      -- adv
      SELECT
        p + 2 p
      , a >> opс::integer a
      , b
      , c
      , o
      WHERE
        opi = 0
    UNION ALL
      -- bxl
      SELECT
        p + 2 p
      , a
      , b # opl b
      , c
      , o
      WHERE
        opi = 1
    UNION ALL
      -- bst
      SELECT
        p + 2 p
      , a
      , opс & 7 b
      , c
      , o
      WHERE
        opi = 2
    UNION ALL
      -- jnz
      SELECT
        CASE WHEN a = 0 THEN p + 2 ELSE opl END p
      , a
      , b
      , c
      , o
      WHERE
        opi = 3
    UNION ALL
      -- bxc
      SELECT
        p + 2 p
      , a
      , b # c b
      , c
      , o
      WHERE
        opi = 4
    UNION ALL
      -- out
      SELECT
        p + 2 p
      , a
      , b
      , c
      , o || (opс & 7)::integer o
      WHERE
        opi = 5
    UNION ALL
      -- bdv
      SELECT
        p + 2 p
      , a
      , a >> opс::integer b
      , c
      , o
      WHERE
        opi = 6
    UNION ALL
      -- cdv
      SELECT
        p + 2 p
      , a
      , b
      , a >> opс::integer c
      , o
      WHERE
        opi = 7
  ) step
)
SELECT
  array_to_string(o, ',') -- собираем вывод последнего шага в строку
FROM
  r
ORDER BY
  i DESC
LIMIT 1;

Часть 2

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

Обратим внимание, что за вывод у нас отвечает только лишь инструкция out, которая выводит всегда только последние 3 бита регистра B. Собственно, из какого регистра - неважно, а вот "по 3 бита" - важно.

Значит, мы точно можем определить перебором последних 3 бит (всего 8 вариантов!) возможное состояние регистра A на последнем шаге (при выводе последнего значения). А потом - на предпоследнем для всех вариантов, найденных на последнем...

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

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

, ro AS (
  SELECT
    0 l                  -- длина "хвоста"
  , 0::bigint a          -- подобранный префикс значения A
  , ARRAY[]::integer[] o -- накопленный вывод
UNION ALL
  SELECT
    l + 1
  , (ro.a << 3) + s      -- подошедшее значение
  , T.o
  FROM
    ro
  , generate_series(0, 7) s -- перебираемые последние 3 бита
  , src
  , LATERAL (
      WITH RECURSIVE r AS ( -- та же самая рекурсия с исполнением программы
        SELECT
          0 i
        , 0 p
        , (ro.a << 3) + s a -- инициализация значением из перебора
        , reg[2] b
        , reg[3] c
        , ARRAY[]::integer[] o
        FROM
          src
      UNION ALL
        ...
      )
      SELECT -- результат программы с последнего шага рекурсии
        *
      FROM
        r
      ORDER BY
        i DESC
      LIMIT 1
    ) T
  WHERE
    T.o = prg[array_length(prg, 1) - l:] AND -- оставляем только варианты с совпадающим "хвостом"
    ro.o <> prg                              -- выходим, как только результат совпал
)
SELECT
  a
FROM
  ro
, src
WHERE
  o = prg
LIMIT 1;

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

WITH RECURSIVE src AS (
  SELECT
    array_agg(d[1])
      FILTER(WHERE i <= 3)::bigint[] reg -- первые 3 числа - регистры
  , array_agg(d[1])
      FILTER(WHERE i > 3)::integer[] prg -- остальные - программа
  FROM
    regexp_matches($$
Register A: 2024
Register B: 0
Register C: 0

Program: 0,3,5,4,3,0
$$
    , '(\d+)'
    , 'g'
    )
      WITH ORDINALITY T(d, i)
)
, ro AS (
  SELECT
    0 l                  -- длина "хвоста"
  , 0::bigint a          -- подобранный префикс значения A
  , ARRAY[]::integer[] o -- накопленный вывод
UNION ALL
  SELECT
    l + 1
  , (ro.a << 3) + s      -- подошедшее значение
  , T.o
  FROM
    ro
  , generate_series(0, 7) s -- перебираемые последние 3 бита
  , src
  , LATERAL (
      WITH RECURSIVE r AS ( -- та же самая рекурсия с исполнением программы
        SELECT
          0 i
        , 0 p
        , (ro.a << 3) + s a -- инициализация значением из перебора
        , reg[2] b
        , reg[3] c
        , ARRAY[]::integer[] o
        FROM
          src
      UNION ALL
        SELECT
          i + 1
        , step.*
        FROM
          r
        , src
        , LATERAL ( -- вычисляем код операции и значения для комбинированного и литерального операндов
            SELECT
              prg[p + 1] opi
            , CASE prg[p + 2]
                WHEN 0 THEN 0
                WHEN 1 THEN 1
                WHEN 2 THEN 2
                WHEN 3 THEN 3
                WHEN 4 THEN a
                WHEN 5 THEN b
                WHEN 6 THEN c
                WHEN 7 THEN 7
              END::bigint opс
            , prg[p + 2] opl
        ) T
        , LATERAL ( -- реализуем выполнение каждой инструкции
            -- adv
            SELECT
              p + 2 p
            , a >> opс::integer a
            , b
            , c
            , o
            WHERE
              opi = 0
          UNION ALL
            -- bxl
            SELECT
              p + 2 p
            , a
            , b # opl b
            , c
            , o
            WHERE
              opi = 1
          UNION ALL
            -- bst
            SELECT
              p + 2 p
            , a
            , opс & 7 b
            , c
            , o
            WHERE
              opi = 2
          UNION ALL
            -- jnz
            SELECT
              CASE WHEN a = 0 THEN p + 2 ELSE opl END p
            , a
            , b
            , c
            , o
            WHERE
              opi = 3
          UNION ALL
            -- bxc
            SELECT
              p + 2 p
            , a
            , b # c b
            , c
            , o
            WHERE
              opi = 4
          UNION ALL
            -- out
            SELECT
              p + 2 p
            , a
            , b
            , c
            , o || (opс & 7)::integer o
            WHERE
              opi = 5
          UNION ALL
            -- bdv
            SELECT
              p + 2 p
            , a
            , a >> opс::integer b
            , c
            , o
            WHERE
              opi = 6
          UNION ALL
            -- cdv
            SELECT
              p + 2 p
            , a
            , b
            , a >> opс::integer c
            , o
            WHERE
              opi = 7
        ) step
      )
      SELECT -- результат программы с последнего шага рекурсии
        *
      FROM
        r
      ORDER BY
        i DESC
      LIMIT 1
    ) T
  WHERE
    T.o = prg[array_length(prg, 1) - l:] AND -- оставляем только варианты с совпадающим "хвостом"
    ro.o <> prg                              -- выходим, как только результат совпал
)
SELECT
  a
FROM
  ro
, src
WHERE
  o = prg
LIMIT 1;

Для подбора значения нам понадобилось всего 0.4 секунды и 108 шагов внутри рекурсии:

Теги:
Хабы:
Всего голосов 7: ↑7 и ↓0+9
Комментарии0
Тензор
Разработчик системы Saby
Сайт
206
Карма
3
Рейтинг
Боровиков Кирилл @Kilor

Архитектура ИС: PostgreSQL, Node.js и highload

Отправить сообщение
СайтСайт

Публикации

Информация

Сайт
saby.ru
Дата регистрации
Дата основания
Численность
1 001–5 000 человек
Местоположение
Россия

Ваш аккаунт

Разделы

Информация

Услуги

Техническая поддержка
© 2006–2025, Habr