Part One
输入x,y，经过一系列的运算后得出z的值
已知x,y的值，后续会陆续得出更多的已知值，因此需要每一轮迭代的输出要带上所有的已知值。终止条件就是所有的值都已找出，没有后续的未知值了。
with recursive origin AS (
SELECT row_number() over () as rn, line
FROM lance_input
), input AS (
SELECT split_part(line, ': ', 1) as key, split_part(line, ': ', 2) :: INTEGER as value
FROM origin
WHERE rn < (select rn from origin where line is null)
), gate AS (
SELECT split_part(line, ' ', 1) as l,
split_part(line, ' ', 2) as op,
split_part(line, ' ', 3) as r,
split_part(line, ' ', 5) as output
FROM origin
WHERE rn > (select rn from origin where line is null)
), gate_output AS (
SELECT key, value
FROM input
UNION ALL
SELECT key, value
FROM (
WITH inner_gate AS (select * from gate_output),
new_output as (
SELECT key, value from inner_gate
UNION ALL
SELECT output as key,
CASE WHEN op = 'AND' THEN b.value & c.value
WHEN op = 'OR' THEN b.value | c.value
WHEN op = 'XOR' THEN b.value # c.value
END as value
FROM gate a
JOIN inner_gate b
ON a.l = b.key
JOIN inner_gate c
ON a.r = c.key
LEFT JOIN inner_gate d
ON a.output = d.key
WHERE d.value is null
)
SELECT key, value
FROM new_output
WHERE exists (
SELECT 1
FROM gate
LEFT JOIN inner_gate
ON gate.output = inner_gate.key
WHERE inner_gate.value is null
)
) t
)
SELECT sum(value * power(2, substring(key, 2) :: integer))
FROM (
select distinct key, value
from gate_output
where key like 'z%'
) t;
Part Two
这道题的实际目的是为了计算两个二进制数的求和，00,01,02代表着对应bit位的值。最终结果是不正确的，因此有几对运算结果错误，需要调换下，找出这几对的运算结果。
这道题很巧妙，需要理解二进制进行加法运算的规律。
00位加法运算
x00
+ y00
--------------
z00
z00 = x00 XOR y00
z00的值其实就是x00与y00的XOR，题面也是这么设计的
y10 AND x10 -> wrk
x00 XOR y00 -> z00
qfp XOR vhf -> z17
如果x00与y00均为1值，要往前进一位，因此就是x00 AND y00的值
x28 XOR y28 -> scd
y00 AND x00 -> mgk
fgn OR cpm -> qfp
01位加法运算
mgk
x01 x00
+ y01 y00
-----------------
z01 z00
z01 = (x01 XOR y01) XOR mgk
z01的值，其实是x01，y01，mgk三个值的xor
y34 AND x34 -> qmr
x01 XOR y01 -> rkf
djs AND chf -> pwv
cdf OR npv -> jbg
rkf XOR mgk -> z01
y44 XOR x44 -> pvc
现在比较复杂的就是计算出01位是否往前进位，根据加法运算，三个数中至少2个1就可以往前进位。
x01与y01的xor为1，代表0｜1，如果上个bit位的进位值为1，则取AND就是本bit位的进位值
1 1
0 1
+ 1 0
----------------------
0 0
(x01 XOR y01) AND (x00 AND y00)
y34 AND x34 -> qmr
x01 XOR y01 -> rkf
djs AND chf -> pwv
x26 XOR y26 -> pjf
rkf AND mgk -> kmj
pvk XOR kdf -> z10
还有一种情况，x01与y01都为1，那么肯定要往前进位
0 1
1 1
+ 1 1
----------------------
0 1
x01 AND y01
tsw AND mvj -> nwd
x01 AND y01 -> nfw
gkw XOR mhv -> z21
那么两种情况都有可能往前进位，因此求OR即可
y17 AND x17 -> vmq
nfw OR kmj -> rwp
dkm OR hgm -> shr
rwp，即01位运算后往前的进位
最后一位结果
最后一位，无需加法运算，直接就是前一位的进位值即可
qfj AND rcg -> bck
vrk OR nhn -> z45
x28 AND y28 -> bwk
计算每一位的取值及进位
接下来就按照这个规则，递归地求出每一位的取值以及进位，如果在某一位计算中断，则肯定是某一项计算不正确导致。
with recursive origin AS (
SELECT row_number() over () as rn, line
FROM lance_input
), input AS (
SELECT split_part(line, ': ', 1) as key, split_part(line, ': ', 2) :: INTEGER as value
FROM origin
WHERE rn < (select rn from origin where line is null)
), gate AS (
SELECT split_part(line, ' ', 1) as l,
split_part(line, ' ', 2) as op,
split_part(line, ' ', 3) as r,
split_part(line, ' ', 5) as output
FROM origin
WHERE rn > (select rn from origin where line is null)
), bit_calc AS (
SELECT 0 as bit_seq,
max(case when op = 'XOR' then output end) as bit_val,
max(case when op = 'AND' then output end) as bit_carry
FROM gate
WHERE least(l, r) = 'x00' and greatest(l, r) = 'y00'
UNION ALL
SELECT bit_seq, bit_val, bit_carry
FROM (
WITH inner_bit AS (select * From bit_calc)
SELECT a.bit_seq, c.output as bit_val, e.output as bit_carry
FROM (
SELECT b.bit_seq + 1 as bit_seq,
max(case when op = 'XOR' then output end) as bit_xor,
max(case when op = 'AND' then output end) as bit_and
FROM gate a
JOIN inner_bit b
ON least(l, r) = 'x' || lpad((b.bit_seq + 1)::text, 2, '0') and greatest(l, r) = 'y' || lpad((b.bit_seq + 1)::text, 2, '0')
GROUP BY b.bit_seq
) a
JOIN inner_bit b
ON a.bit_seq = b.bit_seq + 1
JOIN gate c
ON ((c.l = a.bit_xor and c.r = b.bit_carry) OR (c.l = b.bit_carry and c.r = a.bit_xor))
AND c.op = 'XOR'
LEFT JOIN gate d
ON ((d.l = a.bit_xor and d.r = b.bit_carry) OR (d.l = b.bit_carry and d.r = a.bit_xor))
AND d.op = 'AND'
LEFT JOIN gate e
ON ((e.l = a.bit_and and e.r = d.output) OR (e.l = d.output and e.r = a.bit_and))
AND e.op = 'OR'
) t
)
select * from bit_calc;
比如，最一开始，计算至z08时，结果中断，则说明mvb的计算不正确，应该与z08调换。
postgres-# select * from bit_calc;
bit_seq | bit_val | bit_carry
---------+---------+-----------
0 | z00 | mgk
1 | z01 | rwp
2 | z02 | fmj
3 | z03 | ncp
4 | z04 | qfj
5 | z05 | hjm
6 | z06 | tnr
7 | z07 | sjd
8 | mvb |
(9 rows)
找出4对不正确之后，则最终可以计算到最后一位
31 | z31 | shr
32 | z32 | mqb
33 | z33 | smq
34 | z34 | prv
35 | z35 | vvt
36 | z36 | jrs
37 | z37 | chf
38 | z38 | wch
39 | z39 | sfr
40 | z40 | rmb
41 | z41 | vcr
42 | z42 | mvj
43 | z43 | sgh
44 | z44 | z45
(45 rows)