Part One
通过输入的xmas四个值，一步步最终走到A。每个workflow的规则相当于case when。
px{a<2006:qkq,m>2090:A,rfg}
pv{a>1716:R,A}
lnx{m>1548:A,A}
rfg{s<537:gd,x>2440:R,A}
第一关比较简单，通过递归查询，最终查询到A终止。
WITH RECURSIVE origin AS (
SELECT row_number() over () as _row, line
FROM lance_input
),
input AS (
SELECT _row, matches[1]::bigint as x, matches[2]::bigint as m, matches[3]::bigint as a, matches[4]::bigint as s
FROM (
SELECT _row, regexp_match(line, 'x=(\d+),m=(\d+),a=(\d+),s=(\d+)') as matches
FROM origin
WHERE _row > (SELECT _row FROM origin WHERE line IS NULL)
) a
),
workflow AS (
SELECT name,
row_number() over (partition by _row) as step,
CASE WHEN rule like '%:%' THEN split_part(rule, ':', 1) END as condition,
CASE WHEN rule like '%:%' THEN split_part(rule, ':', 2) ELSE rule END as result
FROM (
SELECT _row, matches[1] as name, unnest(regexp_split_to_array(matches[2], ',')) as rule
FROM (
SELECT _row, regexp_match(line, '(\w+)\{(.*)\}') as matches
FROM origin
WHERE _row < (SELECT _row FROM origin WHERE line IS NULL)
) a
) t
),
go AS (
SELECT _row, x, m, a, s, 'in' as name, 1 as step
FROM input
UNION ALL
SELECT _row, x, m, a, s,
CASE WHEN r THEN result ELSE name END as name,
CASE WHEN r THEN 1 ELSE step + 1 END as step
FROM (
SELECT CASE WHEN condition IS NULL THEN true
WHEN condition like 'x>%' THEN x > substring(condition, 3) :: bigint
WHEN condition like 'x<%' THEN x < substring(condition, 3) :: bigint
WHEN condition like 'm>%' THEN m > substring(condition, 3) :: bigint
WHEN condition like 'm<%' THEN m < substring(condition, 3) :: bigint
WHEN condition like 'a>%' THEN a > substring(condition, 3) :: bigint
WHEN condition like 'a<%' THEN a < substring(condition, 3) :: bigint
WHEN condition like 's>%' THEN s > substring(condition, 3) :: bigint
WHEN condition like 's<%' THEN s < substring(condition, 3) :: bigint
END as r, go.*, workflow.result
FROM go
JOIN workflow
ON go.name = workflow.name
AND go.step = workflow.step
AND go.name NOT in ('A', 'R')
) t
)
SELECT sum(x+m+a+s) FROM go where name = 'A';
Part Two
需要计算出所有能够达到A的xmas的组合数，每个数范围是[1-4000]。
Each of the four ratings (x, m, a, s) can have an integer value ranging from a minimum of 1 to a maximum of 4000
反向查询
第一关是xmas -> A的查询，但是这里要的是A -> xmas的查询，而且查询的结果应该不是具体的四个值，而是每个字母的取值范围。最终四个取值范围相乘就是最终的组合数，因此需要求出每个A对应的取值范围。具体的步骤如下：
- 举例来说，
rfg{s<537:gd,x>2440:R,A}这个规则中，需要需要走到A，则代表前两个条件都未满足，则求出对应的取值范围是s ∈ [1-536] && x ∈ [2441-4000]。 - 接着再找到rfg对应的上一个规则， px{a<2006:qkq,m>2090:A,rfg}，则这里的取值范围合并前一个取值范围，最终变成了s ∈ [1-536] && x ∈ [2441-4000] && a ∈ [1-2005] && m ∈ [2091-4000]。
- 继续向前查找，直到找到in入口为止。
具体的计算方式，就集中在下面的查询中
xmas_range AS (
SELECT name, step,
max(min_x) as min_x, min(max_x) as max_x,
max(min_m) as min_m, min(max_m) as max_m,
max(min_a) as min_a, min(max_a) as max_a,
max(min_s) as min_s, min(max_s) as max_s
FROM (
SELECT name, step,
CASE WHEN condition like 'x>=%' THEN substring(condition, 4) :: bigint
WHEN condition like 'x>%' THEN substring(condition, 3) :: bigint + 1
ELSE 1
END as min_x,
CASE WHEN condition like 'x<=%' THEN substring(condition, 4) :: bigint
WHEN condition like 'x<%' THEN substring(condition, 3) :: bigint - 1
ELSE 4000
END as max_x,
CASE WHEN condition like 'm>=%' THEN substring(condition, 4) :: bigint
WHEN condition like 'm>%' THEN substring(condition, 3) :: bigint + 1
ELSE 1
END as min_m,
CASE WHEN condition like 'm<=%' THEN substring(condition, 4) :: bigint
WHEN condition like 'm<%' THEN substring(condition, 3) :: bigint - 1
ELSE 4000
END as max_m,
CASE WHEN condition like 'a>=%' THEN substring(condition, 4) :: bigint
WHEN condition like 'a>%' THEN substring(condition, 3) :: bigint + 1
ELSE 1
END as min_a,
CASE WHEN condition like 'a<=%' THEN substring(condition, 4) :: bigint
WHEN condition like 'a<%' THEN substring(condition, 3) :: bigint - 1
ELSE 4000
END as max_a,
CASE WHEN condition like 's>=%' THEN substring(condition, 4) :: bigint
WHEN condition like 's>%' THEN substring(condition, 3) :: bigint + 1
ELSE 1
END as min_s,
CASE WHEN condition like 's<=%' THEN substring(condition, 4) :: bigint
WHEN condition like 's<%' THEN substring(condition, 3) :: bigint - 1
ELSE 4000
END as max_s
FROM (
SELECT a.name, a.step,
CASE WHEN a.step = b.step THEN b.condition
ELSE
CASE WHEN b.condition like '%>%' then replace(b.condition, '>', '<=')
WHEN b.condition like '%<%' then replace(b.condition, '<', '>=')
END
END as condition
FROM workflow a
JOIN workflow b
ON a.name = b.name
AND b.step <= a.step
) t
) t
GROUP BY name, step
)
递归查询
从A触发，通过递归查询，直到找到in入口。中途不停更新四个取值范围。
r_range AS (
SELECT a.name, a.step, a.name as next_name,
min_x, max_x, min_m, max_m, min_a, max_a, min_s, max_s
FROM workflow a, xmas_range b
WHERE a.name = b.name
AND a.step = b.step
AND a.result = 'A'
UNION ALL
SELECT a.name, a.step, c.name as next_name,
greatest(a.min_x, b.min_x) as min_x,
least(a.max_x, b.max_x) as max_x,
greatest(a.min_m, b.min_m) as min_m,
least(a.max_m, b.max_m) as max_m,
greatest(a.min_a, b.min_a) as min_a,
least(a.max_a, b.max_a) as max_a,
greatest(a.min_s, b.min_s) as min_s,
least(a.max_s, b.max_s) as max_s
FROM r_range a, xmas_range b, workflow c
WHERE b.name = c.name
AND b.step = c.step
AND c.result = a.next_name
)
SELECT sum((max_x-min_x+1) * (max_m-min_m+1) * (max_a-min_a+1) * (max_s-min_s+1))
FROM r_range
WHERE next_name = 'in';
从A出发，和从R出发的结果数相加，应该正好是全部组合数，4000的四次方
postgres=# select 132668443537397 + 123331556462603;
?column?
-----------------
256000000000000
(1 row)