Part One
一堆的key有上下游依赖关系，根据已知的值，求出root对应的值
root: pppw + sjmn
dbpl: 5
cczh: sllz + lgvd
zczc: 2
这个难题就是postgres递归查询的典型应用场景，参见之前的一篇文章。基本思路，就是先定义出每个key的层级，从第一层依次向下，并最终计算出root的值。
层级计算
每个key的上游，可能在不同层级，需要取最大层级
WITH recursive origin AS (
SELECT k,
case when v like '% %' THEN split_part(v, ' ', 1) END as l,
case when v like '% %' THEN split_part(v, ' ', 2) END as op,
case when v like '% %' THEN split_part(v, ' ', 3) END as r,
case when v not like '% %' THEN v :: INTEGER END as v
FROM (
SELECT split_part(line, ': ', 1) as k,
split_part(line, ': ', 2) as v
FROM lance_input
) t
), dep AS (
SELECT k, 1 as level
FROM origin
WHERE v is not null
UNION ALL
SELECT y.k, x.level + 1 as level
FROM dep x
JOIN origin y
ON y.l = x.k OR y.r = x.k
), max_dep AS (
SELECT k, max(level) as level
FROM dep
GROUP BY k
)
结果和猜想的差不多，root处于最后一层，整体有76层
k | level
------+-------
root | 76
pqpw | 75
fhld | 74
rmct | 73
czst | 72
bzrh | 71
mgct | 70
bjpg | 69
qwhh | 68
mvdn | 67
(10 rows)
逐层计算
后续从1层开始，逐层计算即可。
walkthrough AS (
SELECT 1 as current_level, k, l, op, r, v ::BIGINT
FROM origin
UNION ALL
SELECT *
FROM (
WITH walk AS (
SELECT * FROM walkthrough
)
SELECT m.current_level + 1 as current_level, m.k, m.l, m.op, m.r, coalesce(n.v, m.v) as v
FROM walk m
LEFT JOIN (
SELECT x.k, CASE WHEN x.op = '+' then lw.v + rw.v
WHEN x.op = '-' then lw.v - rw.v
WHEN x.op = '*' then lw.v * rw.v
WHEN x.op = '/' then lw.v / rw.v
END :: BIGINT as v
FROM walk x
JOIN max_dep y
ON x.current_level + 1 = y.level
AND x.k = y.k
JOIN walk lw
ON x.l = lw.k
JOIN walk rw
ON x.r = rw.k
) n
ON m.k = n.k
) t
WHERE current_level <= (select max(level) from max_dep)
)
SELECT *
FROM walkthrough
WHERE current_level = (select max(level) from max_dep)
AND k = 'root'
Part Two
需要计算humn的value为多少时，root的两个上游值相同
root: pqpw + vqmv
显示未知值
humn值未知，那么其所有的下游key肯定也是未知，用v来代表未知值，重新走一遍计算
walkthrough AS (
SELECT 1 as current_level, k, l, op, r, case when k = 'humn' then 'v' else v :: VARCHAR end as v
FROM origin
UNION ALL
SELECT *
FROM (
WITH walk AS (
SELECT * FROM walkthrough
)
SELECT m.current_level + 1 as current_level, m.k, m.l, m.op, m.r, coalesce(n.v, m.v) as v
FROM walk m
LEFT JOIN (
SELECT x.k,
CASE WHEN lw.v = 'v' OR rw.v = 'v' THEN 'v'
when x.op = '+' THEN (lw.v :: BIGINT + rw.v :: BIGINT) :: VARCHAR
WHEN x.op = '-' THEN (lw.v :: BIGINT - rw.v :: BIGINT) :: VARCHAR
WHEN x.op = '*' THEN (lw.v :: BIGINT * rw.v :: BIGINT) :: VARCHAR
WHEN x.op = '/' THEN (lw.v :: BIGINT / rw.v :: BIGINT) :: VARCHAR
END as v
FROM walk x
JOIN max_dep y
ON x.current_level + 1 = y.level
AND x.k = y.k
JOIN walk lw
ON x.l = lw.k
JOIN walk rw
ON x.r = rw.k
) n
ON m.k = n.k
) t
WHERE current_level <= (select max(level) from max_dep)
)
SELECT *
FROM walkthrough
WHERE current_level = (select max(level) from max_dep)
AND k IN ('pqpw', 'vqmv');
current_level | k | l | op | r | v
---------------+------+------+----+------+----------------
76 | pqpw | vprc | * | fhld | v
76 | vqmv | qvgq | * | sfqc | 56517685690674
(2 rows)
自底向上
上一步，求出了pqpw的值，现在需要从它开始，依次计算出上游。计算方式，需要根据实际的操作符转换下
know_values AS (
SELECT *
FROM walkthrough
WHERE current_level = (select max(level) from max_dep)
), reverse_walk AS (
SELECT 'pqpw' as k, 56517685690674 as v
UNION ALL
SELECT CASE WHEN lk.v = 'v' THEN lk.k ELSE rk.k END as k,
CASE WHEN b.op = '+' AND lk.v = 'v' THEN a.v :: BIGINT - rk.v :: BIGINT
WHEN b.op = '+' AND rk.v = 'v' THEN a.v :: BIGINT - lk.v :: BIGINT
WHEN b.op = '-' AND lk.v = 'v' THEN a.v :: BIGINT + rk.v :: BIGINT
WHEN b.op = '-' AND rk.v = 'v' THEN lk.v :: BIGINT - a.v :: BIGINT
WHEN b.op = '*' AND lk.v = 'v' THEN a.v :: BIGINT / rk.v :: BIGINT
WHEN b.op = '*' AND rk.v = 'v' THEN a.v :: BIGINT / lk.v :: BIGINT
WHEN b.op = '/' AND lk.v = 'v' THEN a.v :: BIGINT * rk.v :: BIGINT
WHEN b.op = '.' AND rk.v = 'v' THEN lk.v :: BIGINT / a.v :: BIGINT
END as v
FROM reverse_walk a
JOIN know_values b
ON a.k = b.k
JOIN know_values lk
ON b.l = lk.k
JOIN know_values rk
ON b.r = rk.k
)
SELECT *
FROM reverse_walk