В этой челлендж-серии статей попробуем использовать PostgreSQL как среду для решения задач Advent of Code 2024.
Возможно, SQL не самый подходящий для этого язык, зато мы рассмотрим его различные возможности, о которых вы могли и не подозревать.
Рекурсивно вычисляем логические выражения и разбираем устройство двоичного сумматора.
Решение Day 1: Historian Hysteria (регулярные выражения и условная агрегация)
Решение Day 5: Print Queue (поиск в словаре и массивах, сортировка "пузырьком")
Решение Day 6: Guard Gallivant (рекурсивные циклы и их контроль)
Решение Day 8: Resonant Collinearity (генерация и подсчет уникальных комбинаций)
Решение Day 11: Plutonian Pebbles (агрегация внутри рекурсии)
Решение Day 12: Garden Groups (волновой алгоритм и подсчет границ)
Решение Day 14: Restroom Redoubt (находим "елочку" с помощью центра масс)
Решение Day 15: Warehouse Woes (играем в сокобан с помощью json-карты и типа point)
Решение Day 16: Reindeer Maze (укрощаем рекурсию в лабиринте)
Решение Day 17: Chronospatial Computer (подбираем значение ветвлением)
Решение Day 19: Linen Layout (динамическое программирование)
Решение Day 20: Race Condition (кратчайший путь "туда и обратно" и его самосоединение)
Решение Day 21: Keypad Conundrum (моделирование против подсчета)
Оригинальная постановка задачи и ее перевод:
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 | 1inp0 | 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 с небольшим миллисекунд:
