Part One
某组数字按照一定的规律进行裂变，求这组数字裂变25次后的结果有多少数字？
按照递归查询的写法，并且裂变后的数字用空格分隔
with recursive stones AS (
SELECT line, 0 as blink
FROM lance_input
UNION ALL
SELECT string_agg(num, ' ') as line, blink + 1
FROM (
SELECT blink,
CASE WHEN num = '0' then '1'
WHEN length(num) % 2 = 0 THEN substr(num, 1, length(num) / 2) :: BIGINT || ' ' ||
substr(num, length(num) / 2 + 1, length(num) / 2) :: BIGINT
ELSE (num :: BIGINT * 2024) :: VARCHAR
END as num
FROM (
SELECT x.pos as num, blink
FROM stones, regexp_split_to_table(line, ' ') with ordinality as x(pos, idx)
) t
) t
WHERE blink < 25
GROUP BY blink
)
SELECT * FROM stones;
Part Two
裂变规则未变，但是需要求出裂变75次后的结果
如果仍然按照第一轮的逻辑去写，75次的运算计算量巨大，基本无法运算出来。
仔细分析下，可以有以下几点推论
- 数字裂变后，会出现重复的数字，如果可以缓存下结果，那么后续就无需计算了。
- 裂变后的数字，顺序不重要，只要求数字的数量。
因此我们需要将某个数字，裂变N轮后数字的数量保存起来，供后续查询。
postgres=# \d cache;
Table "public.cache"
Column | Type | Collation | Nullable | Default
-------------+---------+-----------+----------+---------
cache_num | bigint | | |
cache_blink | integer | | |
cache_stone | bigint | | |
Indexes:
"idx_cache" UNIQUE, btree (cache_num, cache_blink)
再通过一个函数递归，来查询某个数字N轮后的结果
CREATE OR REPLACE FUNCTION count_stones(num bigint, blink_left integer)
RETURNS BIGINT AS $$
DECLARE
query_num BIGINT;
stone_num BIGINT;
BEGIN
IF blink_left = 0 THEN
RETURN 1;
END IF;
query_num := (SELECT cache_stone FROM cache WHERE cache_num = num AND cache_blink = blink_left);
IF query_num IS NOT NULL THEN
return query_num;
END IF;
IF num = 0 THEN
stone_num := count_stones(1, blink_left - 1);
ELSE
IF length(num :: VARCHAR) % 2 = 0 THEN
stone_num := count_stones(substr(num :: VARCHAR, 1, length(num :: VARCHAR) / 2) :: BIGINT, blink_left - 1)
+ count_stones(substr(num :: VARCHAR, length(num :: VARCHAR) / 2 + 1, length(num :: VARCHAR) / 2) :: BIGINT, blink_left - 1);
ELSE
stone_num := count_stones(num * 2024, blink_left - 1);
END IF;
END IF;
query_num := (SELECT cache_stone FROM cache WHERE cache_num = num AND cache_blink = blink_left);
IF query_num IS NULL THEN
INSERT INTO cache values(num, blink_left, stone_num);
RAISE NOTICE 'add map: %', (num || ' ' || blink_left);
END IF;
RETURN stone_num;
END;
$$ LANGUAGE plpgsql;