Part One
猴子扔东西的游戏，初始值经过一系列运算后，计算出下一个猴子。
Monkey 0:
Starting items: 79, 98
Operation: new = old * 19
Test: divisible by 23
If true: throw to monkey 2
If false: throw to monkey 3
需要在原始查询后，额外增加两个字段来记录当前状态。next_id用来记录当前运算哪只猴子，round用来记录当前是第几轮游戏了。
递归查询的终止条件，就是完全运行了20轮游戏
WHERE round + next_id / (select max(id) from origin) <= 20
next_id等于自己的时候才需要运算，根据是否有余数来判断走true还是false
CASE WHEN t.id = next_id THEN CASE WHEN (t.total / 3) % t.divide :: integer = 0 THEN t.true_id ELSE t.false_id END ELSE t.id END
完整SQL如下
with recursive origin AS (
SELECT *
FROM (values(0, '66, 59, 64, 51', 'old', '*', '3', '2', 1, 4),
(1, '67, 61', 'old', '*', '19', '7', 3, 5),
(2, '86, 93, 80, 70, 71, 81, 56', 'old', '+', '2', '11', 4, 0),
(3, '94', 'old', '*', 'old', '19', 7, 6),
(4, '71, 92, 64', 'old', '+', '8', '3', 5, 1),
(5, '58, 81, 92, 75, 56', 'old', '+', '6', '5', 3, 6),
(6, '82, 98, 77, 94, 86, 81', 'old', '+', '7', '17', 7, 2),
(7, '54, 95, 70, 93, 88, 93, 63, 50', 'old', '+', '4', '13', 2, 0)
) AS t(id, items, l, operator, r, divide, true_id, false_id)
), monkey AS (
SELECT id, regexp_split_to_table(items, ', ') :: integer as item, l, operator, r, divide, true_id, false_id, 0 :: bigint as next_id, 1 :: bigint as round
FROM origin
UNION ALL
SELECT CASE WHEN t.id = next_id THEN CASE WHEN (t.total / 3) % t.divide :: integer = 0 THEN t.true_id ELSE t.false_id END ELSE t.id END as id,
CASE WHEN t.id = next_id THEN total / 3 ELSE item END as item,
o.l, o.operator, o.r, o.divide, o.true_id, o.false_id, (next_id + 1) % (select count(*) from origin) as next_id, round + next_id / (select max(id) from origin) as round
FROM (
SELECT CASE WHEN operator = '*' THEN real_l * real_r WHEN operator = '+' THEN real_l + real_r END as total,
id, item, l, operator, r, divide, true_id, false_id, next_id, round
FROM (
SELECT case when l = 'old' then item :: integer else l :: integer end as real_l,
case when r = 'old' then item :: integer else r :: integer end as real_r,
id, item, l, operator, r, divide, true_id, false_id, next_id, round
FROM monkey
) s
) t
LEFT JOIN origin o
ON CASE WHEN t.id = next_id THEN CASE WHEN (t.total / 3) % t.divide :: integer = 0 THEN t.true_id ELSE t.false_id END ELSE t.id END = o.id
WHERE round + next_id / (select max(id) from origin) <= 20
)
select id, count(*) From monkey where round <= 20 and next_id = id group by id order by 2 desc;
Part Two
首先，结果不需要除3，此外，需要进行10000轮游戏
如果只是简单的将除3的运算去除掉，并不能解决问题，因为经过不停地乘法运算，结果会非常大。而且计算性能也会受到严重影响。
等价换算
仔细观察，判断true还是false，只需要判断取余的结果，并不需要保留完全的结果。因此可以通过一些等价替换，缩小这个计算结果。
以(old * 19) mod 23为例
(old * 19) mod 23
= ((23 * M + N) * 19) mod 23
= (N * 19) mod 23
上述的例子说明，old的运算结果，等价于取余之后的运算结果。同理也可以得出，其他的old * old，old + 7等操作，同样等价于取余之后的结果。
取余结果的合集
但是我们还需要考虑结果向后传递的问题。以两步运算为例，((old * 19) + 17) mod 23为例
((old * 19) + 17) mod 23
= ((old mod 23 * 19) mod 23 + 17) mod 23
从上个例子可以看出，只要每一步运算都保留对23取余的结果，并将这个结果向后传递即可，就可以得到准确的取余结果。
但是我们当前运算的时候，并不知晓下一步需要对哪个数字求余数，那么干脆每一步运算，将所有的余数都计算出来即可。
比如，最一开始初始化的时候，就直接初始为divide:value, divide:value的格式
postgres-# SELECT id, item :: integer, string_agg(s.v || ':' || item, ',') as divide_agg
postgres-# FROM origin,
postgres-# regexp_split_to_table(items, ', ') WITH ORDINALITY as t(item, seq) ,
postgres-# (SELECT distinct divide :: integer as v from origin) s
postgres-# GROUP BY id, item, seq, l, operator, r, divide, true_id, false_id;
id | item | divide_agg
----+------+---------------------------------------------
0 | 51 | 13:51,17:51,19:51,7:51,3:51,5:51,11:51,2:51
0 | 59 | 17:59,19:59,11:59,13:59,3:59,7:59,5:59,2:59
0 | 64 | 3:64,5:64,2:64,11:64,17:64,13:64,19:64,7:64
0 | 66 | 7:66,11:66,13:66,19:66,5:66,2:66,17:66,3:66
1 | 61 | 7:61,3:61,19:61,17:61,13:61,11:61,2:61,5:61
1 | 67 | 19:67,3:67,17:67,11:67,13:67,7:67,5:67,2:67
取余结果合集运算
后续每一次迭代运算的时候，首先将divide_agg的合集，拆分为一条条记录。
SELECT max(id) as id,
max(l) as l,
max(operator) as operator,
max(r) as r,
max(divide) as divide,
max(true_id) as true_id,
max(false_id) as false_id,
max(next_id) as next_id,
max(round) as round,
max(divide_agg) as divide_agg,
max(case when id = next_id and divide = new_divide then reminder end) as reminder,
string_agg(new_divide || ':' || reminder, ',') as new_agg
FROM (
SELECT seq, id, l, operator, r, divide, true_id, false_id, next_id, round, divide_agg, new_divide, new_item,
(CASE WHEN operator = '*' THEN real_l * real_r WHEN operator = '+' THEN real_l + real_r END) % new_divide as reminder
FROM (
SELECT seq,
case when l = 'old' then split_part(divide_item, ':', 2) :: integer else l :: integer end as real_l,
case when r = 'old' then split_part(divide_item, ':', 2) :: integer else r :: integer end as real_r,
id, l, operator, r, divide :: integer as divide, true_id, false_id, next_id, round, divide_agg,
split_part(divide_item, ':', 1) :: integer as new_divide,
split_part(divide_item, ':', 2) :: integer as new_item
FROM (
SELECT row_number() over () as seq, id, l, operator, r, divide, true_id, false_id, next_id, round, divide_agg
FROM monkey
) monkey,
LATERAL regexp_split_to_table(divide_agg, ',') as divide_item
) s
) m
group by seq
在上面的SQL中，做了如下的处理
- seq用来唯一定位一条记录，从而方便后续的聚合
- 针对每一条divide的记录，都会计算对应的total、reminder等信息。
- 将divide -> reminder的新的mapping关系，再次合并为新的divide_agg信息。
最终SQL
with recursive origin AS (
SELECT *
FROM (values(0, '66, 59, 64, 51', 'old', '*', '3', '2', 1, 4),
(1, '67, 61', 'old', '*', '19', '7', 3, 5),
(2, '86, 93, 80, 70, 71, 81, 56', 'old', '+', '2', '11', 4, 0),
(3, '94', 'old', '*', 'old', '19', 7, 6),
(4, '71, 92, 64', 'old', '+', '8', '3', 5, 1),
(5, '58, 81, 92, 75, 56', 'old', '+', '6', '5', 3, 6),
(6, '82, 98, 77, 94, 86, 81', 'old', '+', '7', '17', 7, 2),
(7, '54, 95, 70, 93, 88, 93, 63, 50', 'old', '+', '4', '13', 2, 0)
) AS t(id, items, l, operator, r, divide, true_id, false_id)
), monkey AS (
SELECT id, l, operator, r, divide, true_id, false_id, 0 :: bigint as next_id, 1 :: bigint as round, string_agg(s.v || ':' || item, ',') as divide_agg
FROM origin,
regexp_split_to_table(items, ', ') WITH ORDINALITY as t(item, seq) ,
(SELECT distinct divide :: integer as v from origin) s
GROUP BY id, item, seq, l, operator, r, divide, true_id, false_id
UNION ALL
SELECT CASE WHEN t.id = next_id THEN CASE WHEN reminder = 0 THEN t.true_id ELSE t.false_id END ELSE t.id END as id,
o.l, o.operator, o.r, o.divide, o.true_id, o.false_id, (next_id + 1) % (select count(*) from origin) as next_id, round + next_id / (select max(id) from origin) as round,
CASE WHEN t.id = next_id THEN t.new_agg ELSE t.divide_agg END as divide_agg
FROM (
SELECT max(id) as id,
max(l) as l,
max(operator) as operator,
max(r) as r,
max(divide) as divide,
max(true_id) as true_id,
max(false_id) as false_id,
max(next_id) as next_id,
max(round) as round,
max(divide_agg) as divide_agg,
max(case when id = next_id and divide = new_divide then reminder end) as reminder,
string_agg(new_divide || ':' || reminder, ',') as new_agg
FROM (
SELECT seq, id, l, operator, r, divide, true_id, false_id, next_id, round, divide_agg, new_divide, new_item,
(CASE WHEN operator = '*' THEN real_l * real_r WHEN operator = '+' THEN real_l + real_r END) % new_divide as reminder
FROM (
SELECT seq,
case when l = 'old' then split_part(divide_item, ':', 2) :: integer else l :: integer end as real_l,
case when r = 'old' then split_part(divide_item, ':', 2) :: integer else r :: integer end as real_r,
id, l, operator, r, divide :: integer as divide, true_id, false_id, next_id, round, divide_agg,
split_part(divide_item, ':', 1) :: integer as new_divide,
split_part(divide_item, ':', 2) :: integer as new_item
FROM (
SELECT row_number() over () as seq, id, l, operator, r, divide, true_id, false_id, next_id, round, divide_agg
FROM monkey
) monkey,
LATERAL regexp_split_to_table(divide_agg, ',') as divide_item
) s
) m
group by seq
) t
LEFT JOIN origin o
ON CASE WHEN t.id = next_id THEN CASE WHEN reminder = 0 THEN t.true_id ELSE t.false_id END ELSE t.id END = o.id
WHERE round + next_id / (select max(id) from origin) <= 10000
)
select id, count(*) From monkey where round <= 10000 and next_id = id group by id order by 2 desc;