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

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

Рекурсивно вычисляем логические выражения и разбираем устройство двоичного сумматора.

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

Advent of Code 2024, Day 24: Crossed Wires

--- День 24: Перекрещенные провода ---

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

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

AND-вентили выдают 1, если оба входа равны 1; если хотя бы один из входов равен 0, на выходе будет 0.
OR-вентили выдают 1, если один или оба входа равны 1; если оба входа равны 0, эти вентили выводят 0.
XOR-вентили выдают значение 1, если входы различны; если входы одинаковы, эти вентили выдают сигнал 0.

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

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

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 означает, что названный провод x00 начинается со значения 1 (как будто вентиль уже выводит это значение на этот провод).

Во втором разделе перечислены все вентили и провода, подключенные к ним. Например, x00 AND y00 -> z00 описывает экземпляр AND-вентиля, на входы которого подключены провода x00 и y00, и который будет записывать свой выход в провод z00.

В этом примере имитация этих вентилей в конечном итоге приводит 0 к появлению на проводе z00, появлению 0 на проводе z01 и появлению 1 на проводе z02.

В конечном итоге система пытается создать число, объединяя биты на всех проводах, начинающихся на z. z00 - это младший бит, затем z01, затем z02, и так далее.

В этом примере три выходных бита образуют двоичное число 100, равное десятичному числу 4.

Вот более крупный пример:

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

После ожидания значений на всех проводах, начинающихся с z, провода в этой системе имеют следующие значения:

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

Объединение битов со всех проводов, начинающихся с z дает двоичное число 0011111101000. Преобразование этого числа в десятичное дает 2024.

Смоделируйте систему вентилей и проводов. Какое десятичное число она выводит на проводах, начинающихся на z?

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

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

В частности, он обрабатывает биты на проводах, начинающихся на x, как одно двоичное число, биты на проводах, начинающихся на y, как второе двоичное число, а затем пытается сложить эти два числа. Выход этой операции создается как двоичное число на проводах, начинающихся на z. (Во всех трех случаях провод 00 является наименее значимым битом, затем 01, затем 02, и так далее.)

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

Например, если у вас есть система сложения с четырьмя x-проводами, четырьмя y-проводами и пятью z-проводами, вы должны иметь возможность подавать любое четырехбитное число на x-провода, любое четырехбитное число на y-провода и, в конечном итоге, находить сумму этих двух чисел как пятибитное число на z-проводах. Один из многих способов, которыми вы могли бы подавать числа в такую систему, - это передавать 11 по x-проводам (1011 в двоичном виде) и 13 по y-проводам (1101 в двоичном виде):

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

Если система работает правильно, то после того, как все вентили завершат обработку, вы должны обнаружить 24 (11+13) на z-проводах в виде пятибитного двоичного числа 11000:

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

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

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

Например, система ниже должна находить побитовое AND шестибитного числа на x00..x05 и шестибитного числа на y00..y05, а затем записывать результат как шестибитное число в z00..z05:

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 -> z05 и x05 AND y05 -> z00; вторая пара вентилей - это x01 AND y01 -> z02 и x02 AND y02 -> z01. Исправление этих двух замен приводит к тому, что эта система работает так, как и предполагалось, для любого набора начальных значений на проводах, начинающихся на x и y:

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

В этом примере две пары вентилей имеют выходы, которые участвуют в обмене. Отсортировав имена их выходных проводов и объединив их запятыми, получим список проводов, участвующих в обменах z00,z01,z02,z05.

Конечно, ваша реальная система намного сложнее этой, и вентили, выходы которых нужно поменять местами, могут быть где угодно, а не только подключены к проводу, начинающемуся на z. Если бы вы определили, что вам нужно поменять местами выходные провода aaa с eee, ooo с z99, bbb с ccc и aoc с z24, ваш ответ был бы aaa,aoc,bbb,ccc,eee,ooo,z24,z99.

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

Часть 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 с небольшим миллисекунд:

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