SQL HowTo: немного двоичной логики (Advent of Code 2024, Day 24: Crossed Wires)

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

• Решение Day 22: Monkey Market (оконные функции)

• Решение Day 23: LAN Party (работаем с массивами)

• Решение Day 24: Crossed Wires (немного двоичной логики)

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

x00: 1 x01: 1 x02: 1 y00: 0 y01: 1 y02: 0  x00 AND y00 -> z00 x01 XOR y01 -> z01 x02 OR y02 -> z02

x00: 1 x01: 0 x02: 1 x03: 1 x04: 0 y00: 1 y01: 1 y02: 1 y03: 1 y04: 1  ntg XOR fgs -> mjb y02 OR x01 -> tnw kwq OR kpj -> z05 x00 OR x03 -> fst tgd XOR rvg -> z01 vdt OR tnw -> bfw bfw AND frj -> z10 ffh OR nrd -> bqk y00 AND y03 -> djm y03 OR y00 -> psh bqk OR frj -> z08 tnw OR fst -> frj gnj AND tgd -> z11 bfw XOR mjb -> z00 x03 OR x00 -> vdt gnj AND wpb -> z02 x04 AND y00 -> kjc djm OR pbm -> qhw nrd AND vdt -> hwm kjc AND fst -> rvg y04 OR y02 -> fgs y01 AND x02 -> pbm ntg OR kjc -> kwq psh XOR fgs -> tgd qhw XOR tgd -> z09 pbm OR djm -> kpj x03 XOR y03 -> ffh x00 XOR y04 -> ntg bfw OR bqk -> z06 nrd XOR fgs -> wpb frj XOR qhw -> z04 bqk OR frj -> z07 y03 OR x01 -> nrd hwm AND bqk -> z03 tgd XOR rvg -> z12 tnw OR pbm -> gnj

bfw: 1 bqk: 1 djm: 1 ffh: 0 fgs: 1 frj: 1 fst: 1 gnj: 1 hwm: 1 kjc: 0 kpj: 1 kwq: 0 mjb: 1 nrd: 1 ntg: 0 pbm: 1 psh: 1 qhw: 1 rvg: 0 tgd: 0 tnw: 1 vdt: 1 wpb: 0 z00: 0 z01: 0 z02: 0 z03: 1 z04: 0 z05: 1 z06: 1 z07: 1 z08: 1 z09: 1 z10: 1 z11: 0 z12: 0

x00: 1 x01: 1 x02: 0 x03: 1 y00: 1 y01: 0 y02: 1 y03: 1

z00: 0 z01: 0 z02: 0 z03: 1 z04: 1

x00: 0 x01: 1 x02: 0 x03: 1 x04: 0 x05: 1 y00: 0 y01: 0 y02: 1 y03: 1 y04: 0 y05: 1  x00 AND y00 -> z05 x01 AND y01 -> z02 x02 AND y02 -> z01 x03 AND y03 -> z03 x04 AND y04 -> z04 x05 AND y05 -> z00

x00 AND y00 -> z00 x01 AND y01 -> z01 x02 AND y02 -> z02 x03 AND y03 -> z03 x04 AND y04 -> z04 x05 AND y05 -> z05

Часть 1

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

Сначала, традиционно, разберем входные данные регулярными выражениями на входные значения и операции над ними:

WITH RECURSIVE src AS (   SELECT     $$ x00: 1 x01: 0 x02: 1 x03: 1 x04: 0 y00: 1 y01: 1 y02: 1 y03: 1 y04: 1  ntg XOR fgs -> mjb y02 OR x01 -> tnw kwq OR kpj -> z05 x00 OR x03 -> fst tgd XOR rvg -> z01 vdt OR tnw -> bfw bfw AND frj -> z10 ffh OR nrd -> bqk y00 AND y03 -> djm y03 OR y00 -> psh bqk OR frj -> z08 tnw OR fst -> frj gnj AND tgd -> z11 bfw XOR mjb -> z00 x03 OR x00 -> vdt gnj AND wpb -> z02 x04 AND y00 -> kjc djm OR pbm -> qhw nrd AND vdt -> hwm kjc AND fst -> rvg y04 OR y02 -> fgs y01 AND x02 -> pbm ntg OR kjc -> kwq psh XOR fgs -> tgd qhw XOR tgd -> z09 pbm OR djm -> kpj x03 XOR y03 -> ffh x00 XOR y04 -> ntg bfw OR bqk -> z06 nrd XOR fgs -> wpb frj XOR qhw -> z04 bqk OR frj -> z07 y03 OR x01 -> nrd hwm AND bqk -> z03 tgd XOR rvg -> z12 tnw OR pbm -> gnj $$ ) -- входные значения , wire AS (   SELECT     line[1] inp   , line[2]::integer val   FROM     regexp_matches(       (TABLE src)     , '([a-z0-9]+): (0|1)'     , 'g'     ) line ) -- операции , gate AS (   SELECT     line[1] inp0   , line[3] inp1   , line[2] op   , line[4] out   FROM     regexp_matches(       (TABLE src)     , '([a-z0-9]+) (AND|OR|XOR) ([a-z0-9]+) -> ([a-z0-9]+)'     , 'g'     ) line )

inp | val x00 |  1 x01 |  0 x02 |  1 x03 |  1 x04 |  0 y00 |  1 y01 |  1 y02 |  1 y03 |  1 y04 |  1

inp0 | inp1 | op  | out ntg  | fgs  | XOR | mjb y02  | x01  | OR  | tnw kwq  | kpj  | OR  | z05 x00  | x03  | OR  | fst tgd  | rvg  | XOR | z01 vdt  | tnw  | OR  | bfw bfw  | frj  | AND | z10 ffh  | nrd  | OR  | bqk y00  | y03  | AND | djm y03  | y00  | OR  | psh bqk  | frj  | OR  | z08 tnw  | fst  | OR  | frj gnj  | tgd  | AND | z11 bfw  | mjb  | XOR | z00 x03  | x00  | OR  | vdt gnj  | wpb  | AND | z02 x04  | y00  | AND | kjc djm  | pbm  | OR  | qhw nrd  | vdt  | AND | hwm kjc  | fst  | AND | rvg y04  | y02  | OR  | fgs y01  | x02  | AND | pbm ntg  | kjc  | OR  | kwq psh  | fgs  | XOR | tgd qhw  | tgd  | XOR | z09 pbm  | djm  | OR  | kpj x03  | y03  | XOR | ffh x00  | y04  | XOR | ntg bfw  | bqk  | OR  | z06 nrd  | fgs  | XOR | wpb frj  | qhw  | XOR | z04 bqk  | frj  | OR  | z07 y03  | x01  | OR  | nrd hwm  | bqk  | AND | z03 tgd  | rvg  | XOR | z12 tnw  | pbm  | OR  | gnj

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

Будем хранить состояние уже вычисленных проводов в виде jsonb-объекта.

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

, r AS (   SELECT     0 i   , jsonb_object( -- исходное состояние известных входов       array_agg(inp)     , array_agg(val)::text[]     ) state   FROM     wire UNION ALL   SELECT     i + 1   , state || diff -- "складываем" jsonb   FROM     r   , LATERAL (       SELECT         jsonb_object(           array_agg(out)         , array_agg(             CASE op               WHEN 'OR'  THEN val0 | val1               WHEN 'AND' THEN val0 & val1               WHEN 'XOR' THEN val0 # val1             END           )::text[]         ) diff       FROM         gate       , LATERAL ( -- определяем значения входов вентиля           SELECT             (state ->> inp0)::integer val0           , (state ->> inp1)::integer val1         ) T       WHERE         (val0, val1) IS NOT NULL AND -- оба входа вычислены, ...         NOT state ? out              -- ... а выход - еще нет     ) T   WHERE     diff::text <> '{}' -- вычисляем, пока есть что )

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

i | state 0 | {"x00": "1", "x01": "0", "x02": "1", "x03": "1", "x04": "0", "y00": "1", "y01": "1",      "y02": "1", "y03": "1", "y04": "1"}" 1 | {"djm": "1", "ffh": "0", "fgs": "1", "fst": "1", "kjc": "0", "nrd": "1", "ntg": "0",      "pbm": "1", "psh": "1", "tnw": "1", "vdt": "1", "x00": "1", "x01": "0", "x02": "1",      "x03": "1", "x04": "0", "y00": "1", "y01": "1", "y02": "1", "y03": "1", "y04": "1"}" 2 | {"bfw": "1", "bqk": "1", "djm": "1", "ffh": "0", "fgs": "1", "frj": "1", "fst": "1",      "gnj": "1", "hwm": "1", "kjc": "0", "kpj": "1", "kwq": "0", "mjb": "1", "nrd": "1",      "ntg": "0", "pbm": "1", "psh": "1", "qhw": "1", "rvg": "0", "tgd": "0", "tnw": "1",      "vdt": "1", "wpb": "0", "x00": "1", "x01": "0", "x02": "1", "x03": "1", "x04": "0",      "y00": "1", "y01": "1", "y02": "1", "y03": "1", "y04": "1"}" 3 | {"bfw": "1", "bqk": "1", "djm": "1", "ffh": "0", "fgs": "1", "frj": "1", "fst": "1",      "gnj": "1", "hwm": "1", "kjc": "0", "kpj": "1", "kwq": "0", "mjb": "1", "nrd": "1",      "ntg": "0", "pbm": "1", "psh": "1", "qhw": "1", "rvg": "0", "tgd": "0", "tnw": "1",      "vdt": "1", "wpb": "0", "x00": "1", "x01": "0", "x02": "1", "x03": "1", "x04": "0",      "y00": "1", "y01": "1", "y02": "1", "y03": "1", "y04": "1", "z00": "0", "z01": "0",      "z02": "0", "z03": "1", "z04": "0", "z05": "1", "z06": "1", "z07": "1", "z08": "1",      "z09": "1", "z10": "1", "z11": "0", "z12": "0"}"

Осталось лишь получить итоговое значение из финального состояния всех z-проводов. Для этого просуммируем значения с соответствующим битовым сдвигом — то есть получим (z00 << 0) | (z01 << 1) | (z02 << 2) | ...:

SELECT   sum(val::bigint << replace(inp, 'z', '')::integer) -- бит-значение с соответствующим сдвигом     FILTER(WHERE inp ^@ 'z')                         -- суммируем только для z-проводов FROM   (     SELECT       state     FROM       r     ORDER BY -- берем последнее вычисленное состояние       i DESC     LIMIT 1   ) T , jsonb_each_text(state) kv(inp, val); -- разворачиваем в пары ключ-значение

Соберем итоговый запрос целиком:

WITH RECURSIVE src AS (   SELECT     $$ x00: 1 x01: 0 x02: 1 x03: 1 x04: 0 y00: 1 y01: 1 y02: 1 y03: 1 y04: 1  ntg XOR fgs -> mjb y02 OR x01 -> tnw kwq OR kpj -> z05 x00 OR x03 -> fst tgd XOR rvg -> z01 vdt OR tnw -> bfw bfw AND frj -> z10 ffh OR nrd -> bqk y00 AND y03 -> djm y03 OR y00 -> psh bqk OR frj -> z08 tnw OR fst -> frj gnj AND tgd -> z11 bfw XOR mjb -> z00 x03 OR x00 -> vdt gnj AND wpb -> z02 x04 AND y00 -> kjc djm OR pbm -> qhw nrd AND vdt -> hwm kjc AND fst -> rvg y04 OR y02 -> fgs y01 AND x02 -> pbm ntg OR kjc -> kwq psh XOR fgs -> tgd qhw XOR tgd -> z09 pbm OR djm -> kpj x03 XOR y03 -> ffh x00 XOR y04 -> ntg bfw OR bqk -> z06 nrd XOR fgs -> wpb frj XOR qhw -> z04 bqk OR frj -> z07 y03 OR x01 -> nrd hwm AND bqk -> z03 tgd XOR rvg -> z12 tnw OR pbm -> gnj $$ ) -- входные значения , wire AS (   SELECT     line[1] inp   , line[2]::integer val   FROM     regexp_matches(       (TABLE src)     , '([a-z0-9]+): (0|1)'     , 'g'     ) line ) -- операции , gate AS (   SELECT     line[1] inp0   , line[3] inp1   , line[2] op   , line[4] out   FROM     regexp_matches(       (TABLE src)     , '([a-z0-9]+) (AND|OR|XOR) ([a-z0-9]+) -> ([a-z0-9]+)'     , 'g'     ) line ) , r AS (   SELECT     0 i   , jsonb_object( -- исходное состояние известных входов       array_agg(inp)     , array_agg(val)::text[]     ) state   FROM     wire UNION ALL   SELECT     i + 1   , state || diff -- "складываем" jsonb   FROM     r   , LATERAL (       SELECT         jsonb_object(           array_agg(out)         , array_agg(             CASE op               WHEN 'OR'  THEN val0 | val1               WHEN 'AND' THEN val0 & val1               WHEN 'XOR' THEN val0 # val1             END           )::text[]         ) diff       FROM         gate       , LATERAL ( -- определяем значения входов вентиля           SELECT             (state ->> inp0)::integer val0           , (state ->> inp1)::integer val1         ) T       WHERE         (val0, val1) IS NOT NULL AND -- оба входа вычислены, ...         NOT state ? out              -- ... а выход - еще нет     ) T   WHERE     diff::text <> '{}' -- вычисляем, пока есть что ) SELECT   sum(val::bigint << replace(inp, 'z', '')::integer) -- бит-значение с соответствующим сдвигом     FILTER(WHERE inp ^@ 'z')                         -- суммируем только для z-проводов FROM   (     SELECT       state     FROM       r     ORDER BY -- берем последнее вычисленное состояние       i DESC     LIMIT 1   ) T , jsonb_each_text(state) kv(inp, val); -- разворачиваем в пары ключ-значение

Для решения полной версии головоломки нам потребовалось 89 шагов и 20мс:

Часть 2

Во второй части нас просят исправить схему, поменяв местами 4 пары выходов, так, чтобы схема в целом работала как двоичный сумматор.

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

x00 XOR y00 -> z00 ---- y00 AND x00 -> ksw x01 XOR y01 -> kgn            kgn XOR ksw -> z01 ---- ksw AND kgn -> kmk x01 AND y01 -> hkv            hkv OR  kmk -> gcm            x02 XOR y02 -> pfd                       pfd XOR gcm -> z02 ---- gcm AND pfd -> rgn y02 AND x02 -> jmb            rgn OR  jmb -> tmr            y03 XOR x03 -> kpp                       tmr XOR kpp -> z03 ---- ... ---- hdt AND wcc -> qbr y43 AND x43 -> gmm            gmm OR  qbr -> ptm            y44 XOR x44 -> smj                       ptm XOR smj -> z44 ---- gmm OR qbr -> ptm y44 XOR x44 -> smj            smj AND ptm -> swb            y44 AND x44 -> wcr                       wcr OR  swb -> z45

Сформулируем некоторые очевидные правила, которых будет достаточно для решения задачи:

• z-значение всегда получается в результате операции XOR (за исключением старшего бита)

• результат каждой операции xNN AND yNN (за исключением первой x00 AND y00) должен попасть на вход какой-то OR-операции

• результат каждой операции xNN XOR yNN (за исключением первой x00 XOR y00) должен попасть на вход какой-то XOR-операции, где выходом является z-бит

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

-- упорядоченные пары входов , iop AS (   SELECT     least(line[1], line[3]) inp0    -- min   , greatest(line[1], line[3]) inp1 -- max   , line[2] op   , line[4] out   FROM     regexp_matches(       (TABLE src)     , '([a-z0-9]+) (AND|OR|XOR) ([a-z0-9]+) -> ([a-z0-9]+)'     , 'g'     ) line )

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

-- ??? XOR ??? -> z?? , bug_xorz AS (   SELECT     out bug   FROM     iop   WHERE     out ^@ 'z' AND     op <> 'XOR' AND     out <> ( -- except z45       SELECT         max(out)       FROM         iop       WHERE         out ^@ 'z'   ) ) -- xNN AND yNN -> res | res OR ??? -> ??? , bug_or AS (   SELECT     out bug   FROM     iop   WHERE     inp0 ^@ 'x' AND     inp1 ^@ 'y' AND     (inp0, inp1) <> ('x00', 'y00') AND     op = 'AND' AND     out NOT IN (       SELECT         unnest(ARRAY[inp0, inp1])       FROM         iop       WHERE         op = 'OR'     ) ) -- xNN XOR yNN -> res | res XOR ??? -> z?? , bug_xor AS (   SELECT     coalesce(Y.out, X.out) bug   FROM     (       SELECT         *       FROM         iop       WHERE         inp0 ^@ 'x' AND         inp1 ^@ 'y' AND         (inp0, inp1) <> ('x00', 'y00') AND         op = 'XOR'     ) X   LEFT JOIN     iop Y       ON X.out IN (Y.inp0, Y.inp1) AND       Y.op = 'XOR'   WHERE     NOT Y.out ^@ 'z' OR     Y.out IS NULL )

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

SELECT   string_agg(DISTINCT bug, ',' ORDER BY bug) FROM   (     TABLE bug_xorz   UNION ALL     TABLE bug_or   UNION ALL     TABLE bug_xor   ) T;

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

WITH src AS (   SELECT     $$ ... $$ ) -- упорядоченные пары входов , iop AS (   SELECT     least(line[1], line[3]) inp0    -- min   , greatest(line[1], line[3]) inp1 -- max   , line[2] op   , line[4] out   FROM     regexp_matches(       (TABLE src)     , '([a-z0-9]+) (AND|OR|XOR) ([a-z0-9]+) -> ([a-z0-9]+)'     , 'g'     ) line ) -- ??? XOR ??? -> z?? , bug_xorz AS (   SELECT     out bug   FROM     iop   WHERE     out ^@ 'z' AND     op <> 'XOR' AND     out <> ( -- except z45       SELECT         max(out)       FROM         iop       WHERE         out ^@ 'z'   ) ) -- xNN AND yNN -> res | res OR ??? -> ??? , bug_or AS (   SELECT     out bug   FROM     iop   WHERE     inp0 ^@ 'x' AND     inp1 ^@ 'y' AND     (inp0, inp1) <> ('x00', 'y00') AND     op = 'AND' AND     out NOT IN (       SELECT         unnest(ARRAY[inp0, inp1])       FROM         iop       WHERE         op = 'OR'     ) ) -- xNN XOR yNN -> res | res XOR ??? -> z?? , bug_xor AS (   SELECT     coalesce(Y.out, X.out) bug   FROM     (       SELECT         *       FROM         iop       WHERE         inp0 ^@ 'x' AND         inp1 ^@ 'y' AND         (inp0, inp1) <> ('x00', 'y00') AND         op = 'XOR'     ) X   LEFT JOIN     iop Y       ON X.out IN (Y.inp0, Y.inp1) AND       Y.op = 'XOR'   WHERE     NOT Y.out ^@ 'z' OR     Y.out IS NULL ) SELECT   string_agg(DISTINCT bug, ',' ORDER BY bug) FROM   (     TABLE bug_xorz   UNION ALL     TABLE bug_or   UNION ALL     TABLE bug_xor   ) T;

Поскольку никаких сложных алгоритмов, кроме пары JOIN мы в запросе не использовали, то решение занимает всего лишь 5 с небольшим миллисекунд: