SavePearlHarbor

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

—

от автора

admin

В этой челлендж-серии статей попробуем использовать 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 шагов внутри рекурсии:


ссылка на оригинал статьи https://habr.com/ru/articles/884522/

Комментарии

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *